Английская Википедия:Cryptographic multilinear map

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

A cryptographic <math>n</math>-multilinear map is a kind of multilinear map, that is, a function <math>e:G_1\times \cdots \times G_n \rightarrow G_T</math> such that for any integers <math> a_1, \ldots, a_n </math> and elements <math> g_i \in G_i </math>, <math>e(g_1^{a_1},\ldots,g_n^{a_n})=e(g_1,\ldots,g_n)^{\prod_{i=1}^n a_i}</math>, and which in addition is efficiently computable and satisfies some security properties. It has several applications on cryptography, as key exchange protocols, identity-based encryption, and broadcast encryption. There exist constructions of cryptographic 2-multilinear maps, known as bilinear maps, however, the problem of constructing such multilinear maps for <math>n > 2</math> seems much more difficult and the security of the proposed candidates is still unclear.

Definition

For n = 2

In this case, multilinear maps are mostly known as bilinear maps or pairings, and they are usually defined as follows: Let <math>G_1, G_2</math> be two additive cyclic groups of prime order <math>q</math>, and <math>G_T</math> another cyclic group of order <math>q</math> written multiplicatively. A pairing is a map: <math> e: G_1 \times G_2 \rightarrow G_T </math>, which satisfies the following properties:

Bilinearity

<math> \forall a,b \in F_q^*,\ \forall P\in G_1, Q\in G_2:\ e(a P, b Q) = e(P,Q)^{ab}</math>

Non-degeneracy

If <math>g_1</math> and <math>g_2</math> are generators of <math>G_1</math> and <math>G_2</math>, respectively, then <math>e(g_1, g_2)</math> is a generator of <math>G_T</math>.

Computability

There exists an efficient algorithm to compute <math>e</math>.

In addition, for security purposes, the discrete logarithm problem is required to be hard in both <math>G_1</math> and <math>G_2</math>.

General case (for any n)

We say that a map <math>e:G_1\times \cdots \times G_n \rightarrow G_T</math> is a <math>n</math>-multilinear map if it satisfies the following properties:

1. All <math>G_i</math> (for <math>1 \le i \le n</math>) and <math>G_T</math> are groups of same order;
2. if <math>a_1, \ldots, a_n \in \mathbb{Z}</math> and <math>(g_1, \ldots, g_n) \in G_1 \times \cdots \times G_n</math>, then <math>e(g_1^{a_1},\ldots,g_n^{a_n})=e(g_1,\ldots,g_n)^{\prod_{i=1}^n a_i}</math>;
3. the map is non-degenerate in the sense that if <math>g_1, \ldots, g_n</math> are generators of <math>G_1, \ldots, G_n</math>, respectively, then <math>e(g_1, \ldots, g_n)</math> is a generator of <math>G_T</math>
4. There exists an efficient algorithm to compute <math>e</math>.

In addition, for security purposes, the discrete logarithm problem is required to be hard in <math>G_1, \ldots, G_n</math>.

Candidates

All the candidates multilinear maps are actually slightly generalizations of multilinear maps known as graded-encoding systems, since they allow the map <math>e</math> to be applied partially: instead of being applied in all the <math>n</math> values at once, which would produce a value in the target set <math>G_T</math>, it is possible to apply <math>e</math> to some values, which generates values in intermediate target sets. For example, for <math>n = 3</math>, it is possible to do <math>y = e(g_2, g_3) \in G_{T_2}</math> then <math>e(g_1, y) \in G_T</math>.

The three main candidates are GGH13, which is based on ideals of polynomial rings; CLT13, which is based approximate GCD problem and works over integers, hence, it is supposed to be easier to understand than GGH13 multilinear map; and GGH15, which is based on graphs.