## Multi-linear maps

Recently the paper Candidate Multilinear Maps from Ideal Lattices and Applications, by Sanjam Garg, Craig Gentry and Shai Halevi, has been posted on eprint. The paper gives a construction of multi-linear maps, and gives some applications.

Let’s first recall the background. Bi-linear pairings have been extremely useful for constructing cryptosystems, and it has been a natural question for a long time to consider multi-linear maps. An n-multi-linear map on a group G is a function e : G^n –> G_T such that e( [a1]P, [a2]P, . . ., [an]P ) = e( P, P, . . ., P )^{a1 * a2 * . . . * an}. Such a map would have interesting cryptographic applications. But previously no such map (secure for crypto) was known. Boneh and Silverberg, in the paper Applications of Multilinear Forms to Cryptography, discussed why it seems to be hard to find such maps from algebraic geometry.

The new paper uses lattices and homomorphic encryption to construct an n-multi-linear map for any n.

Their scheme and description use a quite different formulation from the elliptic curve case.  So it is first easier to translate elliptic curve pairings into this different language.  The discrete logarithm problem allows us to “encode” an integer a as the point [a]P.  This is *not* encryption, but a “one-way” encoding. By this we mean it is hard to decode, but easy to determine whether or not a given encoding corresponds to a given integer a.  The bilinear pairing is a function that takes two encodings [a1]P and [a2]P and outputs a binary string.  We think of this as “extracting” some information about the product a1*a2 of the integers corresponding to the two encodings.   The requirement of the extraction function is that it gives the same value even when given different encodings of the same value — this is the essential requirement of pairings that e( [a1]P, [a2]P ) = e( [a1*a2]P, P ).

The new scheme can be expressed, at a high level, in the above way.  There is an “encoding” process, that enables one to generate an encoding of a random element.  We stress again that this is not encryption, in exactly the same way that computing [a]P on an elliptic curve is not encryption of the integer a.  Actually, the analogy with discrete logs already breaks down here: the encoding of a ring element is just multiplication by a fixed public element, so the “discrete log problem” is easily solved by division in the ring.  This weakness is fixed by adding some random “encodings of zero” to hide the ring element. For the n-multi-linear map, one then uses a homomorphic property of multiplication of encodings to compute an encoding of the product.  This is very similar in flavour to recent homomorphic encryption schemes. The crucial new idea is that the public key contains a special element called p_{zt}. This element enables anyone to compute some function of the product from its encoding (in other words, it is a bit like a proxy decryption key).  This process is called “extraction”.  Furthermore, this gadget only works to a certain depth (number of multiplications) and can’t be used to extract information from a product of more than n terms. It is important to understand that extraction is not the reverse operation of decoding — information is lost by the extraction process.

One can use this multi-linear map to achieve a one-round n-party (unauthenticated) Diffie-Hellman key exchange.  One first sets up an (n-1)-multi-linear public key.  The n users then choose random elements ai and publish encodings of them.  A user who receives all the other player’s encodings can multiply one of them by their own element, and then compute the product of them all, and then apply the extraction function to get a session key.  All players will compute the same session key using their inputs.  An eavesdropper needs to compute the n-multi-linear map from all the n encodings. The eavesdropper can indeed compute an encoding of the product of all n values, but the special element p_{zt} only extracts correct information for products of (n-1) encodings. Hence the eavesdropper has no information.

I won’t try to give a description of the scheme.  It suffices to say that it is based on the ring Z_q[x]/(x^{2^n} + 1), as used in NTRU and Ring-LWE. The scheme is somehow motivated by standard techniques in homomorphic encryption using lattices, but it is not identical to any existing scheme. The paper is reasonably clear, especially if one jumps directly to section 4 and ignores the general definition of “graded encodings” in section 2.2.  The scheme relies on a new computational assumption, and the paper contains a great deal of discussion of it.

The paper does not state any explicit parameters, but it seems that the scheme will be quite practical.  Certainly it should be much more practical for small n than general homomorphic encryption, since it only requires computing a product of n terms.  (In other words, there is no bootstrapping required.)

The paper also gives an asymmetric case, which is analogous to pairings on G1 x G2 x . . . x Gn. The SXDH problem makes sense and seems to be hard in this setting. Of course, more research will be needed to evaluate these assumptions.

I now mention some crucial differences between this new proposal and the pairings case:

1. The scheme does not perform any role like “transforming the DLP from one group to another”.  This is because the extraction function does not seem to have any algebraic properties. The point is that the “pairing computation” is replaced by two components. The first component is multiplication in a homomorphic encryption scheme, and so is a map with algebraic properties. The second component is applying an extractor to some high order bits of some ring elements, and is not an algebraic map.

2. The scheme requires a trusted generator to compute the public values. This entity knows a master secret that allows them to decode all ciphertexts/encodings. Interestingly, this means the scheme is somewhat like a “trapdoor discrete logarithm” system with a pairing.  It is possible that this extra functionality will have some new applications, but it could also be a serious problem for some other applications.

3. There is a small chance that extraction does not behave correctly (due to the small additive errors in the encoding).  However, the paper claims that this can be made negligible.

— Steven Galbraith