Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I've encountered this term many times in the fields of Fully-Homomorphic Encryption and Obfuscation.
I want to learn those subjects and Cryptographic Linear Maps seems to be an obstacle in the way.
Can you help me with that and explain it in simple words (as much as you can)?
Ok, I will start with a cryptographic bilinear map.
Cryptographic Bilinear Map
A cryptographic bilinear map $e: G_1\times G_2 \rightarrow G_T$ as the name says is a map that is linear in both components, i.e., it holds that for all $g\in G_1$ and $h\in G_2$ and all $a,b\in Z_p$ (where $p$ is the order of all groups) we have that $e(g^a,h^b)=e(g,h)^{ab}$.
For cryptographic use we want a setting where the discrete logarithm problem is hard in $G_1,G_2$ and $G_T$ (typically one requires also that variants of the computational Diffie Hellman problem are hard and the decisional Diffie Hellman problem may be easy in $G_1$ - that depends on the type of pairng, e.g., symmetric or asymmetric and w/o efficient computable isomorphisms from $G_2$ to $G_1$). Furthermore, we want $e$ to be efficiently computable and non-degenerate, i.e., if $g$ and $h$ generate $G_1$ and $G_2$ respectively, then $e(g,h)$ generates $G_T$ ($e$ which maps to $1$ in $G_T$ is useless).
For pairings there are various Diffie-Hellman like assumptions (bilinear Diffie Hellman assumptions), e.g., in the setting of $G_1=G_2$ and $g=h$ the bilinear CDHP states that it should be hard to compute $e(g,g)^{abc}$ given $g^a$, $g^b$ and $g^c$.
Groups $G_1$ and $G_2$ that we know today where we find such a pairing $e$ are (subgroups of) rational points on elliptic curves (or abelian varieties) over finite fields and the group $G_T$ is a subgroup of a multiplicative group of a finite field. The map $e$ thereby is a variant of the Weil or Tate pairing.
Cryptographic Multilinear Map
Now, a cryptographic multilinear map for $n>2$ is a $n$-linear map $e:G_1\times \ldots \times G_n \rightarrow G_T$, i.e., a map that is linear in all $n$ components. Essentially one requires the same as above but you want to have that it be $n$-linear, which basically means that $e(g_1^{a_1},\ldots,g_n^{a_n})=e(g_1,\ldots,g_n)^{\prod_{i=1}^n a_i}$ and that it is non-degenerate. As in the bilinear case we can also define multilinear CDHP etc (see for instance here).
Such cryptographic multilinear maps would be a very nice tool if they would work as in the pairing setting (as envisioned in the paper linked above). However, the recent constructions for cryptographic multilinear maps are based on tools from constructions of fully homomorphic encryption schemes (AFAIK there is a construction using ideal lattices and one over the integers) and there the encodings of the elements are noisy and thus are approximations of the ideal case and not that nice as within the pairing setting working with cyclic groups. Note that some papers simply assume the existence of a multilinear map that behaves like an extension from the known bilinear map setting with the associated Diffie Hellman assumptions (although it is not yet known if such multilinear maps exist). Worth mentioning is the first candidate construction for indistinguishabiliy obfuscation that relies on a concept related to multilinear maps (which also yields functional encryption for circuits).
I'll add something to the previous answer. The first way to construct multilinear maps is pretty recent and was introduced by Sanjam Garg, Craig Gentry and Shai Halevi. What we want is given groups $G_1,\ldots,G_n$ and $G_T$ a map:
$$e:G_1\times\cdots\times G_n\to G_T$$
that satisfies the linearity property in DrLecter's answer. It's worth nothing here, that $G_1,\ldots,G_n$ do not necessarily have to be distinct groups. Often, they would be the same group and we would call this a symmetric $n$-linear map.
Current constructions are typically called leveled multilinear maps. In the symmetric case this can be described as follows. Assume that you have groups $G_1,\ldots,G_n$ and bilinear maps $e_{i,j}:G_i\times G_j\to G_{i+j}$ for all $i,j > 0$ that satisfy $i+j\leq k$. We can construct a symmetric $n$-linear map $e:G_1\times\cdots\times G_1\to G_n$ from this by recursively defining:
$$e_2 = e_{1,1},\;\; e_n(g_1,\ldots,g_n) = e_{1,k-1}(g_1,e_{n-1}(g_2,\ldots,g_n))$$
For example if $n=3$, then we would compute:
$$e_3(g_1^{a_1},g_2^{a_2},g_3^{a_3}) = e_{1,2}(g_1^{a_1},e_{1,1}(g_2^{a_2},g_3^{a_3}))=e_{1,2}(g_1,e_{1,1}(g_2,g_3)^{a_2a_3})^{a_1}=e_{1,2}(g_1,e_{1,1}(g_2,g_3))^{a_1a_2a_3},$$
which shows that $e_3$ is $3$-linear. The asymmetric case is slightly more complicated (it's a bit heavy notation wise and the subscripts become sets instead of integers). Thus, current constructions have a bit more structure than a pure $n$-linear group. This is both good and bad in that more versatile structures can allow for more elaborate constructions, but on the other hand, if we only need $n$-linearity, then the extra structure might lead to possible attacks. However, in a generic group setting the leveled $n$-linear and $n$-linear settings are essentially equivalent, so there might not be that much danger.
