Kryptografická multilineární mapa - Cryptographic multilinear map - Wikipedia

A kryptografické ${ displaystyle n}$-multilineární mapa je druh multilineární mapa, tj. funkce ${ displaystyle e: G_ {1} times cdots times G_ {n} rightarrow G_ {T}}$ taková, že pro všechna celá čísla ${ displaystyle a_ {1}, ldots, a_ {n}}$ a prvky ${ displaystyle g_ {i} v G_ {i}}$, ${ displaystyle e (g_ {1} ^ {a_ {1}}, ldots, g_ {n} ^ {a_ {n}}) = e (g_ {1}, ldots, g_ {n}) ^ { prod _ {i = 1} ^ {n} a_ {i}}}$, a který je navíc efektivně vypočítatelný a splňuje některé vlastnosti zabezpečení. Má několik aplikací na kryptografii, as výměna klíčů protokoly, šifrování založené na identitě, a šifrování vysílání. Existují konstrukce kryptografických 2-vícerozměrných map, známých jako bilineární mapy,^[1] problém konstrukce takové multilineární^[1] mapy pro ${ displaystyle n> 2}$ vypadá mnohem obtížněji^[2] a bezpečnost navrhovaných kandidátů je stále nejasná.^[3]

Definice

Pro n = 2

V tomto případě jsou multilineární mapy většinou známé jako bilineární mapy nebo párování a jsou obvykle definovány takto:^[4] Nechat ${ displaystyle G_ {1}, G_ {2}}$ být dvě aditivní cyklické skupiny hlavního řádu ${ displaystyle q}$, a ${ displaystyle G_ {T}}$ další cyklická skupina řádu ${ displaystyle q}$ psáno multiplikativně. Párování je mapa: ${ displaystyle e: G_ {1} krát G_ {2} rightarrow G_ {T}}$, který splňuje následující vlastnosti:

Bilinearita

${ displaystyle forall a, b in F_ {q} ^ {*}, forall P in G_ {1}, Q v G_ {2}: e (aP, bQ) = e (P, Q) ^ {ab}}$

Nedegenerace

Li ${ displaystyle g_ {1}}$ a ${ displaystyle g_ {2}}$ jsou generátory ${ displaystyle G_ {1}}$ a ${ displaystyle G_ {2}}$pak ${ displaystyle e (g_ {1}, g_ {2})}$ je generátor ${ displaystyle G_ {T}}$.

Vyčíslitelnost

Existuje efektivní algoritmus pro výpočet ${ displaystyle e}$.

Z bezpečnostních důvodů navíc problém diskrétního logaritmu musí být tvrdý v obou ${ displaystyle G_ {1}}$ a ${ displaystyle G_ {2}}$.

Obecný případ (pro všechny n)

Říkáme, že mapa ${ displaystyle e: G_ {1} times cdots times G_ {n} rightarrow G_ {T}}$ je ${ displaystyle n}$-multilineární mapa, pokud splňuje následující vlastnosti:

1. Všechno ${ displaystyle G_ {i}}$ (pro ${ Displaystyle 1 leq i leq n}$) a ${ displaystyle G_ {T}}$ jsou skupiny stejného řádu;
2. -li ${ displaystyle a_ {1}, ldots, a_ {n} in mathbb {Z}}$ a ${ displaystyle (g_ {1}, ldots, g_ {n}) v G_ {1} krát cdots krát G_ {n}}$, pak ${ displaystyle e (g_ {1} ^ {a_ {1}}, ldots, g_ {n} ^ {a_ {n}}) = e (g_ {1}, ldots, g_ {n}) ^ { prod _ {i = 1} ^ {n} a_ {i}}}$;
3. mapa je nedegenerovaná v tom smyslu, že pokud ${ displaystyle g_ {1}, ldots, g_ {n}}$ jsou generátory ${ displaystyle G_ {1}, ldots, G_ {n}}$pak ${ displaystyle e (g_ {1}, ldots, g_ {n})}$ je generátor ${ displaystyle G_ {T}}$
4. Existuje efektivní algoritmus pro výpočet ${ displaystyle e}$.

Z bezpečnostních důvodů navíc problém diskrétního logaritmu musí být tvrdý ${ displaystyle G_ {1}, ldots, G_ {n}}$.

Kandidáti

Všechny kandidátské multilineární mapy jsou vlastně mírně zevšeobecněním multilineárních map známých jako systémy s odstupňovaným kódováním, protože umožňují mapu ${ displaystyle e}$ použít částečně: místo použití ve všech ${ displaystyle n}$ hodnoty najednou, což by vytvořilo hodnotu v cílové sadě ${ displaystyle G_ {T}}$, je možné použít ${ displaystyle e}$ na některé hodnoty, které generují hodnoty v mezilehlých cílových sadách. Například pro ${ displaystyle n = 3}$, je možné to udělat ${ displaystyle y = e (g_ {2}, g_ {3}) v G_ {T_ {2}}}$ pak ${ displaystyle e (g_ {1}, y) v G_ {T}}$.

Tři hlavní kandidáti jsou GGH13,^[5] který je založen na ideály polynomiálních kruhů; CLT13,^[6] který je založen na přibližném problému GCD a funguje na celých číslech, proto by měl být srozumitelnější než multilineární mapa GGH13; a GGH15,^[7] který je založen na grafech.

Reference