Cryptographic multilinear map
A cryptographic [math]\displaystyle{ n }[/math]-multilinear map is a kind of multilinear map, that is, a function [math]\displaystyle{ e:G_1\times \cdots \times G_n \rightarrow G_T }[/math] such that for any integers [math]\displaystyle{ a_1, \ldots, a_n }[/math] and elements [math]\displaystyle{ g_i \in G_i }[/math], [math]\displaystyle{ 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,[1] however, the problem of constructing such multilinear[1] maps for [math]\displaystyle{ n \gt 2 }[/math] seems much more difficult[2] and the security of the proposed candidates is still unclear.[3]
Definition
For n = 2
In this case, multilinear maps are mostly known as bilinear maps or pairings, and they are usually defined as follows:[4] Let [math]\displaystyle{ G_1, G_2 }[/math] be two additive cyclic groups of prime order [math]\displaystyle{ q }[/math], and [math]\displaystyle{ G_T }[/math] another cyclic group of order [math]\displaystyle{ q }[/math] written multiplicatively. A pairing is a map: [math]\displaystyle{ e: G_1 \times G_2 \rightarrow G_T }[/math], which satisfies the following properties:
- Bilinearity
- [math]\displaystyle{ \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]\displaystyle{ g_1 }[/math] and [math]\displaystyle{ g_2 }[/math] are generators of [math]\displaystyle{ G_1 }[/math] and [math]\displaystyle{ G_2 }[/math], respectively, then [math]\displaystyle{ e(g_1, g_2) }[/math] is a generator of [math]\displaystyle{ G_T }[/math].
- Computability
- There exists an efficient algorithm to compute [math]\displaystyle{ e }[/math].
In addition, for security purposes, the discrete logarithm problem is required to be hard in both [math]\displaystyle{ G_1 }[/math] and [math]\displaystyle{ G_2 }[/math].
General case (for any n)
We say that a map [math]\displaystyle{ e:G_1\times \cdots \times G_n \rightarrow G_T }[/math] is a [math]\displaystyle{ n }[/math]-multilinear map if it satisfies the following properties:
- All [math]\displaystyle{ G_i }[/math] (for [math]\displaystyle{ 1 \le i \le n }[/math]) and [math]\displaystyle{ G_T }[/math] are groups of same order;
- if [math]\displaystyle{ a_1, \ldots, a_n \in \mathbb{Z} }[/math] and [math]\displaystyle{ (g_1, \ldots, g_n) \in G_1 \times \cdots \times G_n }[/math], then [math]\displaystyle{ e(g_1^{a_1},\ldots,g_n^{a_n})=e(g_1,\ldots,g_n)^{\prod_{i=1}^n a_i} }[/math];
- the map is non-degenerate in the sense that if [math]\displaystyle{ g_1, \ldots, g_n }[/math] are generators of [math]\displaystyle{ G_1, \ldots, G_n }[/math], respectively, then [math]\displaystyle{ e(g_1, \ldots, g_n) }[/math] is a generator of [math]\displaystyle{ G_T }[/math]
- There exists an efficient algorithm to compute [math]\displaystyle{ e }[/math].
In addition, for security purposes, the discrete logarithm problem is required to be hard in [math]\displaystyle{ 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]\displaystyle{ e }[/math] to be applied partially: instead of being applied in all the [math]\displaystyle{ n }[/math] values at once, which would produce a value in the target set [math]\displaystyle{ G_T }[/math], it is possible to apply [math]\displaystyle{ e }[/math] to some values, which generates values in intermediate target sets. For example, for [math]\displaystyle{ n = 3 }[/math], it is possible to do [math]\displaystyle{ y = e(g_2, g_3) \in G_{T_2} }[/math] then [math]\displaystyle{ e(g_1, y) \in G_T }[/math].
The three main candidates are GGH13,[5] which is based on ideals of polynomial rings; CLT13,[6] 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,[7] which is based on graphs.
References
- ↑ 1.0 1.1 Dutta, Ratna; Barua, Rana; Sarkar, Palash (2004). "Pairing-Based Cryptographic Protocols : A Survey". e-Print IACR. https://eprint.iacr.org/2004/064.
- ↑ Boneh, Dan; Silverberg, Alice (2003). "Applications of multilinear forms to cryptography". Topics in Algebraic and Noncommutative Geometry. Contemporary Mathematics. 324. pp. 71–90. doi:10.1090/conm/324/05731. ISBN 9780821832097. http://crypto.stanford.edu/~dabo/abstracts/mlinear.html. Retrieved 14 March 2018.
- ↑ Albrecht, Martin R.. "Are Graded Encoding Scheme broken yet?". http://malb.io/are-graded-encoding-schemes-broken-yet.html. Retrieved 14 March 2018.
- ↑ Koblitz, Neal; Menezes, Alfred (2005). "Pairing-Based cryptography at high security levels". Cryptography and Coding. Lecture Notes in Computer Science. 3796. pp. 13–36. doi:10.1007/11586821_2. ISBN 978-3-540-30276-6.
- ↑ Garg, Sanjam; Gentry, Craig; Halevi, Shai (2013). "Candidate Multilinear Maps from Ideal Lattices". Advances in Cryptology – EUROCRYPT 2013. Lecture Notes in Computer Science. 7881. pp. 1–17. doi:10.1007/978-3-642-38348-9_1. ISBN 978-3-642-38347-2.
- ↑ Coron, Jean-Sébastien; Lepoint, Tancrède; Tibouchi, Mehdi (2013). "Practical Multilinear Maps over the Integers". Advances in Cryptology – CRYPTO 2013. Lecture Notes in Computer Science. 8042. pp. 476–493. doi:10.1007/978-3-642-40041-4_26. ISBN 978-3-642-40040-7.
- ↑ Gentry, Craig; Gorbunov, Sergey; Halevi, Shai (2015). "Graph-Induced Multilinear Maps from Lattices". Theory of Cryptography. Lecture Notes in Computer Science. 9015. pp. 498–527. doi:10.1007/978-3-662-46497-7_20. ISBN 978-3-662-46496-0.
 |  |
