Tri-linear maps from elliptic curves and abelian surfaces

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 E be an ordinary pairing-friendly elliptic curve over \mathbb{F}_p and let \ell \mid \#E( \mathbb{F}_p ). Let e_\ell be the Weil pairing on E[\ell], meaning that e_\ell : E[ \ell ] \times E[ \ell ] \to \mu_\ell \subseteq \mathbb{F}_{p^k}^* for some integer k (the “embedding degree”), where \mu_\ell is the cyclic multiplicative group of order \ell.

Write \pi for the p-power Frobenius map \pi(x,y) = (x^p, y^p) on E. Note that \mathbb{Z}[\pi] \subseteq End(E).

The construction is to choose a random Q \in E[\ell] and random integers A, B \in \{ 0,1,\dots, \ell-1\}. Huang defines \lambda = A + B \pi to be an endomorphism on E, and sets P = \lambda(Q) = [A]Q + [B]\pi(Q). With high probability e_\ell( P, Q ) \ne 1 (if not then repeat the construction for another point P).

The key idea is that one can now “encode” three integers a, b, c \in \{ 0,1,\dots, \ell-1\} as follows. Encode a as the group element [a]P \in E[ \ell ], encode b as the group element [b]Q, encode c as the endomorphism \phi_c = c  + u \lambda where u is chosen uniformly at random in \{ 0,1,\dots, \ell-1\}. More precisely, \phi_c is represented as x + y \pi where x = c + Au \pmod{\ell} and y = Bu \pmod{\ell}. One can compute \lambda(Q) efficiently as [x]Q + [y] \pi(Q). Since the Weil pairing is alternating we have e_\ell( P , \lambda( Q )) = e_\ell( P, P ) = 1.

So e_{\ell}( [a]P, \phi_c( [b]Q )) = e_{\ell}( [a]P, (c + u \lambda)( [b]Q )) = e_\ell( [a]P , [cb]Q + [cbu] \lambda(Q)) = e_\ell( P, Q)^{abc}.

In other words, we have a tri-linear map e : G_1 \times G_2 \times G_3 \to \mu_\ell where the three sets G_i are “encodings” of \mathbb{Z} / \ell \mathbb{Z}. Note that the integers a and b are “hidden” due to the hardness of the discrete log problem, and G_1, G_2 are groups. While the integer c is hidden by the “random blinding” by a random multiple of \lambda.

The bad news about this particular example is that it is not secure. Since \lambda = A + B \pi is public, an attacker who sees the encoding x + y \pi in G_3 can easily solve for c and u. In other words the “discrete log problem” in G_3 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 G_3 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 \lambda in the above example) that can be used to “hide” an integer c when encoding it in G_3. Instead of representing these endomorphisms with respect to some \mathbb{Z}-module basis (such as x_0 + x_1 \pi + x_2 \pi^2 + x_3 \pi^3), 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

This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to Tri-linear maps from elliptic curves and abelian surfaces

  1. I’m confused. The a and b in λ = a + bπ and in e(P,Q)^abc are not the same a and b, right?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s