Xavier Boyen (Voltage Inc.)
"Modern Identity-Based Encryption and Applications"

Since the advent of the celebrated Boneh-Franklin algorithm, research  on identity-based encryption, and indeed, pairing-based cryptography, has gained an enormous momentum.  From new curve and pairing constructions to innovative protocols and applications, the field has seen many recent and exciting developments.

In this talk, I will give an overview of the state of the art in identity-based encryption proper.  I will review the Boneh-Boyen algorithm, and detail the reasons why, when implemented on modern asymmetric pairings, it offers the best in terms of security, efficiency, and simplicity.  I will then present a few recent extensions to the system, such as hierarchical IBE with minimal overhead, and a very cute way of achieving (threshold) chosen ciphertext security without MACs or signatures.

Slides

back to timetable

Fabien Laguillaumie (University of Caen, France)
"Pairing-based Undeniable Signatures and Variants"

Undeniable signatures were introduced in 1989 by Chaum and van Antwerpen to limit the self-authenticating property of digital signatures. Many variants of these signatures have also been proposed to achieve specific properties desired in real-world applications of cryptography.

In this talk, we will first focus on the so-called "xyz-trick", which is related to a bilinear variant of the Diffie-Hellman problem. In consists of simple
observations about pairings, which permit to achieve trade-offs between authenticity and anonymity in cryptosystems.

In a second part, we will show how to use the "xyz-trick" to construct an efficient pairing-based undeniable signature scheme and also some other variants. In particular, we will define a new requirement for undeniable signatures, namely the time-selective conversion, which is a refinement of the
universal conversion, and we will show how to obtain such a property in our new undeniable signature scheme.

back to timetable

Jun Furakawa (NEC Japan)
"New Group signature scheme"

We propose a new group signature scheme which is secure if we assume the Decision Diffie-Hellman assumption, the q-Strong Diffie-Hellman assumption, and the existence of random oracles. The proposed scheme is the most efficient among the all previous group signature schemes in signature length and in computational complexity. (To appear at ACISP 2005)

back to timetable

Breno de Medeiros (Florida State University)
"Application of DDH-hard Pairing Groups to Cryptography"

The possibility of DDH-hard pairing groups was raised by Verheul and further studied by Galbraith and Rotger. These authors have shown that (only) the subgroups corresponding to the eigenspaces of the Frobenius map in MNT curves do not admit distortion maps. In principle, this would seem to counter-indicate such groups for practical applications, since the existence of distortion maps can be exploited to achieve computational savings. However, Barreto, Lynn, and Scott have shown that working within these groups may lead to very efficient implementations, if one takes into account that they likely provide similar security at smaller key lengths when compared to subgroups of supersingular curves.

More interestingly, it has recently become apparent that the combination of pairings and DDH-hardness in the same groups can lead to novel cryptographic constructions. These new constructions have properties which seem difficult, if not impossible, to achieve in DDH-easy groups. Other constructions which are possible in the DDH-easy setting can also be made simpler and more efficient, or made to rely on more natural assumptions, if one instantiates them in a DDH-hard setting.

We propose, in this talk, to discuss ongoing research on cryptographic applications of DDH-hard pairing groups to cryptography. We hope the discussion will motivate further investigation of these groups, hopefully leading to higher confidence in their suitability (or non-suitability) to such cryptographical purposes.

Note: This talk refers to ongoing collaborative works w/ Jan Camenisch, Giuseppe Ateniese, Fabian Monrose, Matthew Green and Lucas Ballard.

back to timetable

Tanja Lange (Technical University of Denmark)
"Pairings on ordinary hyperelliptic curves"

Curve based cryptography found some extra applications in protocols using pairings. Even though they are usually stated as using bilinear maps from G_1 \times G_1 the protocols can also be applied for two different input groups. Here one can make use of the definition of the Tate-Lichtenbaum pairing and make a clever choice of the residue classes involved in the second argument. This leads to a speed-up of the pairing computation. Basically one uses divisors with only one point in the support. Such a choice was already proposed by Duursma and Lee, however they use it in the first argument and in conjunction with distortion maps. We give arguments that these choices are actually sound and show how this can be applied on non-supersingular curves where one does not have distortion maps.

back to timetable

Robert Ronan (University College Cork)
"A Hardware Accelerator for the eta pairing"

Many cryptographic schemes are based upon the mathematical operation of bilinear pairings of algebraic curve points. These pairings are essentially point transformations. The most popular such pairing  has traditionally been the Duursma-Lee method for computing the Tate pairing on supersingular elliptic curves.
Recently, a bilinear pairing known as the "eta" pairing has been defined. This pairing is a generalisation of the Duursma-Lee method and can be performed on both elliptic and hyperelliptic curves. It has been shown to operate faster in software than the Tate pairing in certain cases.
The authors have designed a hardware accelerator that performs the eta pairing on hyperelliptic curves in characteristic 2. This accelerator targets a Field Programmable Gate Array (FPGA) implementation.
In this talk, the architecture at the foundation of this core is detailed and discussed. Timing and area results for the accelerator are also presented and evaluated.

back to timetable

Tim Kerins (University College Cork)
"Hardware aspects of Tate Pairing Calculation in characteristic three"

In this talk the advantages of dedicated hardware implementation for the Tate Pairing in characteristic three are discussed. The primary observation is that the number of clock cyles for arithemtic in tower fields can be greatly decreased on dedicated hardware as a number of arithemtic cores can be implemented in parallel. Two protptype hardware architectures are described based on the BKLS and DL algorithms.

Slides

back to timetable

Colm O'hEigeartaigh (Dublin City University)
"Implementation of the etaT pairing"

In a recent paper* we established criteria under which pairings on supersingular hyperelliptic curves are efficiently computable by introducing the eta pairing. The eta pairing allows for a halving of the loop compared to the generalised Duursma-Lee approach, at the expense of a more complicated final exponentiation.

In this talk we describe various techniques that lead to an extremely efficient implementation of the tate pairing on supersingular genus 2 curves, which include using degenerate divisors and a fast octupling operation, amongst others. We also provide evidence that performing the extra exponentiationss needed to calculate the tate pairing is trivial.

* http://eprint.iacr.org/2004/375

Slides

back to timetable

Paulo Barreto (University of Sao Paulo)
"Pairing-Friendly Curves of Prime and Near-Prime Order"

Previously known techniques to construct pairing-friendly curves of prime or near-prime order are restricted to embedding degree $k \leqslant 6$. More general methods produce curves over $\F_p$ where $p$ is often twice as large as the order $r$ of the subgroup with embedding degree $k$; the best published results achieve $\log(p)/\log(r) \sim 5/4$. In this talk we will briefly review those methods, discuss some venues of improving them, and describe a method to construct elliptic curves of prime order and embedding degree $k = 12$ as a first step towards surpassing their limitations.

Slides

back to timetable

Jordi Pujols (University/Polytech of Catalonia)
"Distortion maps in genus two"

Distortion Maps are a useful tool in Cryptography. I will present some examples for genus two curves.

back to timetable

Steven Galbraith (Royal Holloway)
"Eta: In Theory"

I will give a crash course in the theory of the eta pairing for supersingular curves over finite fields. In particular I will explain how the eta pairing approach allows shorter loops for computing pairings.

Slides

back to timetable

Bagga Walid (Institut Eurecom, France)
"Policy-Based Cryptography and Applications"

This talk presents the concept of policy-based cryptography (PBC) which has been formulated in [BMF05]. PBC makes it possible to perform policy enforcement in large-scale open environments like the Internet, while respecting the data minimization principle according to which only strictly necessary information should be collected for a given purpose. Two policy-based cryptographic primatives are formally defined: policy based encryption and policy based signature. Intuitively, policy-based encryption allows to encrypt data according to a policy so that only entities fulfilling the policy are able to successfully perform the decryption and retrieve the plaintext data, whereas policy-based signature allows to generate a digital signature on data with respect to a policy so that only entities satisfying the policy are able to generate a valid signature. Two concrete policy-based encryption and signature schemes from bilinear pairings over elliptic curves are described. The proposed schemes allow performing relatively efficient encryption and signature operations with respect to credential-based policies formalized as boolean expressions written in generic conjunctive-disjunctive normal form. The privacy properties of the policy-based cryptographic schemes will be illustrated through the desciption of three application scenarios. Finally, current and future work will be discussed.

[BMF05] W. Bagga and R. Molva. Policy-Based Cryptography and Applications. To appear in Financial Cryptography and Data Security (FC'05)

back to timetable

Yevgeniy Dodis (NYU) 
"Pairing-Based Verifiable Random Functions"

Slides

back to timetable

David Galindo (Radboud University Nijmegen)
"Practice-oriented provable security: the case of pairing based cryptographic schemes"

The idea of practice oriented provable security is to explicitly capture the quantitative aspects of security, by means of an exact treatment of the security reductions. We look at the security reductions of some known constructions, both in the random oracle and standard models. For any pair ``scheme/security reduction", we deduce key sizes to securely implement the schemes. It turns out that some important protocols in the literature appear to be not as efficient as one would wish, due to the lack of tightness of their security reductions.
Our second aim is then to improve the concrete security of these schemes, probably using stronger but reasonable assumptions. Finally, we suggest some open problems.

Slides

back to timetable

Caroline Kudla (Royal Holloway)
"Pairings and Gap Groups"

Pairings are well-known for their applications in identity-based cryptography. However they also have more obscure uses in cryptography. In this talk we discuss the use of Gap problems in provable security and the design of cryptographic primitives and examine the role that pairings play in this context.

Slides

back to timetable

Mike Scott (Dublin City University)
"Faster pairings using an elliptic curve with an efficient endomorphism"

Gallant, Lambert and Vanstone in 2001 demonstrated a fast method for point multiplication on an elliptic curve which supports a fast endomorphism. We demonstrate that on such a curve it is also possible to calculate pairings more efficiently. Our new method either requires half of the storage (if precomputation is possible), or is about 30% faster, than the standard method.

Slides

back to timetable

Florian Hess (TU Berlin)
"Aspects of pairings of general curves"

Slides

back to timetable

Kenny Paterson (Royal Holloway)
"Identity-based cryptography for GRID security"

We investigate the use of identity based cryptography to provide an alternative security architecture for GRID computing. We show how single sign-on and delegation services can be very naturally supported in GRID environments using identity based techniques.

Slides

back to timetable

Hovav Shacham (Stanford)
Talk title TBC

back to timetable

Paula Valenca (Royal Holloway)
"Ordinary abelian varieties having small embedding degree"

Miyaji, Nakabayashi and Takano (MNT) gave families of group orders of ordinary elliptic curves with embedding degree suitable for pairing applications. In this presentation we generalise their results by giving families corresponding to non-prime group orders. We also consider the case of ordinary abelian varieties of dimension 2. We give families of group orders with embedding degrees 5, 10 and 12.

Slides

back to timetable

Cryptographer's Panel
"The future of Pairing-based Crypto"

Informal discussion on future directions for research that will be fuelled by questions from the floor. We are very lucky with the amount of pairing experts that will be in attendance, so make good use of the opportunity to ask questions. Get thinking about questions now, don't leave it up to the day. Your participation will determine the success of this event.

back to timetable

Content © 2005 Workshop on Pairings in Cryptography