Криптографическая многолинейная карта

Криптографический ​ $n$-мультилинейная карта — это разновидность полилинейной карты , то есть функция $e:G_{1}\times \cdots \times G_{n}\rightarrow G_{T}$ такая, что для любых целых чисел $a_{1},\ldots ,a_{n}$ и элементы $g_{i}\in G_{i}$, $e(g_{1}^{a_{1}},\ldots ,g_{n}^{a_{n}})=e(g_{1},\ldots ,g_{n})^{\prod _{i=1}^{n}a_{i}}$, который, кроме того, эффективно вычислим и удовлетворяет некоторым свойствам безопасности. Он имеет несколько приложений в криптографии, таких как обмена ключами протоколы , шифрование на основе идентификации и широковещательное шифрование . Существуют конструкции криптографических 2-полилинейных отображений, известные как билинейные отображения. однако проблема построения таких полилинейных карты для $n>2$ кажется гораздо сложнее и безопасность предложенных кандидатов все еще неясна.

Определение

Для n = 2

В этом случае полилинейные карты в основном известны как билинейные карты или пары и обычно определяются следующим образом: Позволять $G_{1},G_{2}$ — две аддитивные циклические группы простого порядка $q$, и $G_{T}$ еще одна циклическая группа порядка $q$ написано мультипликативно. Пейринг – это карта: $e:G_{1}\times G_{2}\rightarrow G_{T}$, который удовлетворяет следующим свойствам:

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

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

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

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

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

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

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

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

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

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

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

Кандидаты

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

Три основных кандидата — GGH13, основанный на идеалах колец полиномов ; CLT13, который основан на приближенной задаче НОД и работает с целыми числами, следовательно, его легче понять, чем многолинейную карту GGH13; и GGH15, который основан на графиках.