Английская Википедия: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,[1] however, the problem of constructing such multilinear[1] maps for <math>n > 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>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:
- All <math>G_i</math> (for <math>1 \le i \le n</math>) and <math>G_T</math> are groups of same order;
- 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>;
- 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>
- 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,[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 Ошибка цитирования Неверный тег
<ref>
; для сносокpairingSurvey
не указан текст - ↑ Ошибка цитирования Неверный тег
<ref>
; для сносокbonehMultilinear
не указан текст - ↑ Ошибка цитирования Неверный тег
<ref>
; для сносокAlbrechtSite
не указан текст - ↑ Ошибка цитирования Неверный тег
<ref>
; для сносокKoblitzMenezes2005
не указан текст - ↑ Ошибка цитирования Неверный тег
<ref>
; для сносокggh13
не указан текст - ↑ Ошибка цитирования Неверный тег
<ref>
; для сносокclt13
не указан текст - ↑ Ошибка цитирования Неверный тег
<ref>
; для сносокggh15
не указан текст