Криптографическая полилинейная карта - Википедия - Cryptographic multilinear map

А криптографический ${ displaystyle n}$-многолинейная карта это своего рода многолинейная карта, то есть функция ${ displaystyle e: G_ {1} times cdots times G_ {n} rightarrow G_ {T}}$ такой, что для любых целых чисел ${ displaystyle a_ {1}, ldots, a_ {n}}$ и элементы ${ displaystyle g_ {i} in 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}}}$, который, кроме того, эффективно вычислим и удовлетворяет некоторым свойствам безопасности. У него есть несколько приложений в криптографии, например обмен ключами протоколы, шифрование на основе личности, и широковещательное шифрование. Существуют конструкции криптографических 2-полилинейных отображений, известных как билинейные отображения,^[1] однако проблема построения таких полилинейных^[1] карты для ${ displaystyle n> 2}$ кажется намного сложнее^[2] и безопасность предложенных кандидатов все еще не ясна.^[3]

Определение

За п = 2

В этом случае полилинейные карты в основном известны как билинейные карты или сопряжения, и они обычно определяются следующим образом:^[4] Позволять ${ displaystyle G_ {1}, G_ {2}}$ - две аддитивные циклические группы простого порядка ${ displaystyle q}$, и ${ displaystyle G_ {T}}$ другая циклическая группа порядка ${ displaystyle q}$ написано мультипликативно. Спаривание - это карта: ${ displaystyle e: G_ {1} times G_ {2} rightarrow G_ {T}}$, который удовлетворяет следующим свойствам:

Билинейность

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

Невырожденность

Если ${ displaystyle g_ {1}}$ и ${ displaystyle g_ {2}}$ являются генераторами ${ displaystyle G_ {1}}$ и ${ displaystyle G_ {2}}$соответственно, то ${ displaystyle e (g_ {1}, g_ {2})}$ является генератором ${ displaystyle G_ {T}}$.

Вычислимость

Существует эффективный алгоритм вычисления ${ displaystyle e}$.

Кроме того, в целях безопасности задача дискретного логарифмирования требуется быть трудным в обоих ${ displaystyle G_ {1}}$ и ${ displaystyle G_ {2}}$.

Общий случай (для любого п)

Мы говорим, что карта ${ displaystyle e: G_ {1} times cdots times G_ {n} rightarrow G_ {T}}$ это ${ displaystyle n}$-моллинейная карта, если она удовлетворяет следующим свойствам:

1. Все ${ displaystyle G_ {i}}$ (за ${ Displaystyle 1 Leq я Leq п}$) и ${ displaystyle G_ {T}}$ группы одного порядка;
2. если ${ displaystyle a_ {1}, ldots, a_ {n} in mathbb {Z}}$ и ${ displaystyle (g_ {1}, ldots, g_ {n}) in G_ {1} times cdots times G_ {n}}$, тогда ${ displaystyle e (g_ {1} ^ {a_ {1}}, ldots, g_ {n} ^ {a_ {n}}) = e (g_ {1}, ldots, g_ {n}) ^ { prod _ {i = 1} ^ {n} a_ {i}}}$;
3. отображение невырождено в том смысле, что если ${ displaystyle g_ {1}, ldots, g_ {n}}$ являются генераторами ${ Displaystyle G_ {1}, ldots, G_ {n}}$соответственно, то ${ displaystyle e (g_ {1}, ldots, g_ {n})}$ является генератором ${ displaystyle G_ {T}}$
4. Существует эффективный алгоритм вычисления ${ displaystyle e}$.

Кроме того, в целях безопасности задача дискретного логарифмирования требуется быть трудным в ${ Displaystyle G_ {1}, ldots, G_ {n}}$.

Кандидаты

Все полилинейные карты-кандидаты на самом деле являются немного обобщениями полилинейных карт, известных как системы градуированного кодирования, поскольку они позволяют отображать ${ displaystyle e}$ применяется частично: вместо того, чтобы применяться во всех ${ displaystyle n}$ значения сразу, что даст значение в целевом наборе ${ displaystyle G_ {T}}$, можно применить ${ displaystyle e}$ к некоторым значениям, который генерирует значения в промежуточных целевых наборах. Например, для ${ displaystyle n = 3}$, можно сделать ${ displaystyle y = e (g_ {2}, g_ {3}) in G_ {T_ {2}}}$ тогда ${ displaystyle e (g_ {1}, y) in G_ {T}}$.

Три основных кандидата - GGH13,^[5] который основан на идеалы колец многочленов; CLT13,^[6] который основан на приближенной задаче GCD и работает с целыми числами, следовательно, его проще понять, чем полилинейную карту GGH13; и GGH15,^[7] который основан на графиках.

Рекомендации