I spent the last week in beautiful Banff at the BIRS workshop on An Algebraic Approach to Multilinear Maps for Cryptography. The workshop participant photo is notable, as the age gap between the oldest and youngest person in the photo is more than 100 years. Three of the talks can be viewed online. I spent most of the time working with Ming-Deh Huang and others on the ideas in his preprint Trilinear maps for cryptography. This preprint sketches some ideas that might lead to a tri-linear map. (In the photo: Huang is in the front row, wearing sunglasses and standing beside Hendrik Lenstra; I’m at the back, hiding behind Boneh and Sahai.)
I am going to describe a simple (but insecure) example that will allow to communicate the main ideas of the proposal.
Let be an ordinary pairing-friendly elliptic curve over and let . Let be the Weil pairing on , meaning that for some integer (the “embedding degree”), where is the cyclic multiplicative group of order .
Write for the -power Frobenius map on . Note that .
The construction is to choose a random and random integers Huang defines to be an endomorphism on , and sets . With high probability (if not then repeat the construction for another point ).
The key idea is that one can now “encode” three integers as follows. Encode as the group element , encode as the group element , encode as the endomorphism where is chosen uniformly at random in . More precisely, is represented as where and One can compute efficiently as . Since the Weil pairing is alternating we have .
In other words, we have a tri-linear map where the three sets are “encodings” of . Note that the integers and are “hidden” due to the hardness of the discrete log problem, and are groups. While the integer is hidden by the “random blinding” by a random multiple of .
The bad news about this particular example is that it is not secure. Since is public, an attacker who sees the encoding in can easily solve for and . In other words the “discrete log problem” in is easy to solve.
We now briefly mention why this tri-linear map concept avoids the negative results by Boneh and Silverberg in their paper Applications of Multilinear Forms to Cryptography. In short, the set is “weight zero” in the motivic language of Section 7.4 of Boneh-Silverberg. One topic of discussion at the BIRS meeting last week was whether or not weight zero objects always have weak discrete logarithms. As far as I can tell the outcome was inconclusive.
Huang’s actual proposal is to work on a 2-dimensional Abelian variety that is pairing friendly and has a non-commutative endomorphism ring. The idea is to publish a set of endomorphisms (extending the single endomorphism in the above example) that can be used to “hide” an integer when encoding it in . Instead of representing these endomorphisms with respect to some -module basis (such as ), which would be insecure, the suggestion is to represent endomorphisms using low degree rational functions on the Abelian surface. This is a very interesting idea, but more work is needed to determine if such an system is secure and efficiently computable.
— Steven Galbraith