The conference will feature 4 invited talks and a hot topics session with invited presentations.
Invited speakers are Jean-Luc Beuchat, Jung-Hee Cheon, Dennis Hofheinz, and Hovav Shacham.
Title: Hardware Architectures for the Cryptographic Tate Pairing
In the mid-nineties of the last century, Menezes, Okamoto & Vanstone and Frey & Rück introduced the Weil and Tate pairings in cryptography as a tool to attack the discrete logarithm problem on some classes of elliptic curves defined over finite fields. The discovery of constructive properties by Joux, Mitsunari, Sakai & Kasahara, and Sakai, Oghishi & Kasahara initiated the proposal of an ever-increasing number of protocols based on bilinear pairings: identity-based encryption, short signature, and efficient broadcast encryption, to mention but a few. However, such protocols rely critically on efficient implementations of pairing primitives at high security levels on a wide range of targets.
Miller described the first iterative algorithm to compute the Weil and Tate pairings back in 1986. The Tate pairing seems to be more suited to efficient implementations, and has therefore attracted a lot of interest from the research community. A large number of articles, culminating in the ηT pairing algorithm, focused on shortening the loop of Miller's algorithm in the case of supersingular abelian varieties. The Ate pairing, introduced by Hess et al. for elliptic curves and by Granger et al. in the hyperelliptic case, generalizes the ηT approach to ordinary curves. Eventually, several variants of the Ate pairing aiming at optimally reducing the loop length of Miller's algorithm have been proposed in 2008.
We sketch here several hardware architectures for the Tate pairing on supersingular and ordinary curves. First, we emphasize on reducing the silicon footprint of the circuit to ensure scalability, while trying to minimize the impact on the overall performances. Then, we focus on the other end of the hardware design spectrum and explain how to achieve much lower computation times, at the expense of extra hardware resources. The main lesson learned from this study is that an appropriate mix of theoretical foundations and practical considerations is essential to design cryptographic hardware: fine-tuning of the algorithms, arithmetic operand encoding, scheduling, etc.
Title: Discrete Logarithm in Pairing Groups
In recent years, bilinear pairings have found various applications in cryptography to construct new cryptographic primitives. Pairing-based cryptography raises lots of new computational problems, but they have not been studied very well in the literature. In this talk, we survey recent progress in this field and then would like to address some open questions on the discrete logarithms in pairing groups. For this purpose, this talk is roughly comprised of three parts. The first part mainly focuses on the discrete logarithms on pairing groups. It includes the pairing inversion problem. We also investigate how to apply "Tag Tracing" technique to elliptic curves with bilinear maps. The second topic is related to the strong DH assumption, which is widely used and one of the most popular cryptographic assumptions in the field of pairing-based cryptography. We take a look around the security of the strong DH assumption and its following variants with auxiliary inputs. It was proved that they indeed have less security than the square-root of p when p-1 or p+1 has an appropriate divisor for the base group of order p. We introduce an attempt to generalize this attack using an embedding to an extension field or elliptic curves, and exploit a sparse polynomial with small image size. Finally, we introduce bilinear product groups, which are recently received widespread attention as a new framework in pairing-based cryptography, and show how to extend cryptographic assumptions in pairing groups into bilinear product groups.
Title: Structure-preserving cryptography
A cryptographic scheme is called structure-preserving, if the performed operations are solely abstract group operations. (In particular, this disallows the explicit use of, say, the bit representation of group elements.)
Structure-preserving schemes are interesting because they are compatible with non-interactive proof systems for equations over groups. For instance, efficient Groth-Sahai proofs can be used to prove knowledge of a signature (of a structure-preserving signature scheme). This allows to transport generic paradigms (such as the Naor-Yung paradigm to achieve chosen-ciphertext encryption security) to an efficient group-based setting.
This talk first gives an overview over structure-preserving schemes, and then presents a new result that uses a structure-preserving signature scheme as an essential building block. Concretely, we show how to construct a chosen-ciphertext secure public-key encryption scheme with a tight security reduction in the multi-user, multi-challenge setting.
Title: Alternative Structure for Bilinear Groups (Joint work with Sarah Meiklejohn, UC San Diego) Pairing-based cryptography is a striking illustration of the value of algebraic structure for constructing crypto schemes: A richer structure allows for a wider variety of crypto schemes. It is perhaps surprising, then, that the way in which pairings are used have become quite standard. Most often, we imagine a bilinear group G to be a cyclic group of prime order that induces a map e: G× G → GT (where GT is treated in a similarly abstract manner). In this talk, I survey two lines of work that seek to generalize this understanding of pairings. One line considers bilinear groups G of composite order; the other line reconsiders the mathematical structure of the group G, for example to support asymmetric pairings e: G1 × G2 → GT. Both these lines of work have been exploited to construct new cryptographic schemes. In addition, I consider one of the instantiations of pairing-friendly elliptic curves proposed in a recent paper of Boneh, Rubin, and Silverberg. I show that this instantiation exhibits surprising and unprecedented new structure: projecting a point from the group G onto a subgroup G1 or G2 requires knowledge of a trapdoor. I propose new hardness assumptions for this setting and protocols that rely on them.
The hot topics session will feature talks by Benoit Libert and Katsuyuki Takashima.
Title: Revocable group signatures from the NNL subset cover framework Group signatures are a central cryptographic primitive where users can anonymously sign messages in the name of a group they belong to. Despite years of research, membership revocation remains a non-trivial problem. Existing solutions either suffer from important overheads or require unrevoked users to update their keys after each revocation. We describe a new scalable revocation method, based on the Naor-Naor-Lotspiech (NNL) broadcast encryption framework, that interacts nicely with techniques for building group signatures in the standard model. We eventually obtain a scheme which is truly competitive with group signatures without revocation. Moreover, unrevoked members do not need to update their keys at each revocation.
Title: Adaptively Attribute-Hiding (Hierarchical) Inner Product
(Joint work with Tatsuaki Okamoto, NTT) We propose the first inner product encryption (IPE) scheme that is adaptively secure and fully attribute-hiding (attribute-hiding in the sense of the definition by Katz, Sahai and Waters), while the existing IPE schemes are either fully attribute-hiding but selectively secure or adaptively secure but weakly attribute-hiding. The proposed IPE scheme is proven to be adaptively secure and fully attribute-hiding under the decisional linear assumption in the standard model. The IPE scheme is comparably as efficient as the existing attribute-hiding IPE schemes. We also present a variant of the proposed IPE scheme with the same security that achieves shorter public and secret keys. A hierarchical IPE scheme can be constructed that is also adaptively secure and fully attribute-hiding under the same assumption. In this work, we extend the dual system encryption technique by Waters into a more general manner, in which new forms of ciphertext and secret keys are employed and new types of information theoretical tricks are introduced along with several forms of computational reduction.