## 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