The 2013 Godel Prize winners have just been announced as being Antoine Joux, Dan Boneh and Matt Franklin; for their work in pairing based cryptography. The press release can be found here.
In the early 2000's the world of cryptography was revolutionized by two papers by these authors. A bit of background is probably needed to understand the revolution. In 1985 Victor Miller and Neal Koblitz introduced the idea of using elliptic curves as a means of building cryptographic systems; and since then elliptic curves have become deployed in a number of application domains such as on the web, in your mobile phone, or in your games console.
However, quite early on it was realised that some elliptic curves are weaker than others; in particular those for which there exists an efficiently computable bilinear pairing (sometimes called a bilinear map). In its basic form this is a map from two groups G1 and G2 into a new group GT which is linear in the first two coordinates. In practice one instantiates
these with G1 and G2 being subgroups of an elliptic curve and GT being a subgroup of a finite field. Only a small subset of elliptic curves have an efficiently computable pairing, and since the early 1990's these had been avoided in normal applications of elliptic curves in cryptography.
However, in a paper in the ANTS conference in 2000 Antoine Joux showed how if we carefully chose the parameters of elliptic curves with a pairing then we could achieve a cryptographic functionality which we could not achieve with other techniques. This first application was to allowing three parties to agree a secret key using only one round of interaction; so called Tripartite Diffie-Hellman.
Then in 2001 at the CRYPTO conference Boneh and Franklin showed how the same technique could be used to create an identity based encryption scheme. This is an encryption scheme in which the receivers key is simply their name. Again this is something which had not be possible before.
Over the first decade of this century the number of papers on so-called Pairing Based Cryptography exploded. For example, according to Google Scholar, Joux's paper has been cited 886 times and the Boneh/Franklin paper has been cited 4527 times. The following work has ranged from algorithms to efficiently compute the various pairings needed (including the work in Bristol on the Ate-pairing algorithm) through to work on using pairings in advanced protocols such as group signatures, credentials, functional and attribute based encryption and our own work recent work on DAA protocols.
We have all just returned from Eurocrypt where the best paper award was given to some new ground breaking work which showed how one can construct pairings between more than two objects efficiently; so called multi-linear maps. We have discussed new work a lot in this blog in recent months; so I refer the reader to the previous posts on this topic. It can be expected that the development of multi-linear maps is going to have the same profound effect that the development of bilinear pairings had in the last decade.
However, in a paper in the ANTS conference in 2000 Antoine Joux showed how if we carefully chose the parameters of elliptic curves with a pairing then we could achieve a cryptographic functionality which we could not achieve with other techniques. This first application was to allowing three parties to agree a secret key using only one round of interaction; so called Tripartite Diffie-Hellman.
Then in 2001 at the CRYPTO conference Boneh and Franklin showed how the same technique could be used to create an identity based encryption scheme. This is an encryption scheme in which the receivers key is simply their name. Again this is something which had not be possible before.
Over the first decade of this century the number of papers on so-called Pairing Based Cryptography exploded. For example, according to Google Scholar, Joux's paper has been cited 886 times and the Boneh/Franklin paper has been cited 4527 times. The following work has ranged from algorithms to efficiently compute the various pairings needed (including the work in Bristol on the Ate-pairing algorithm) through to work on using pairings in advanced protocols such as group signatures, credentials, functional and attribute based encryption and our own work recent work on DAA protocols.
We have all just returned from Eurocrypt where the best paper award was given to some new ground breaking work which showed how one can construct pairings between more than two objects efficiently; so called multi-linear maps. We have discussed new work a lot in this blog in recent months; so I refer the reader to the previous posts on this topic. It can be expected that the development of multi-linear maps is going to have the same profound effect that the development of bilinear pairings had in the last decade.
No comments:
Post a Comment