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

Криптографической -multilinear карта${\ displaystyle n}$ является своим родом полилинейной карты , то есть функция таким , что для любых целых чисел и элементов , и которые, кроме того, эффективно вычислимая и удовлетворить некоторые свойства безопасности. Он имеет несколько приложений для криптографии, таких как протоколы обмена ключами, шифрование на основе идентификации и шифрование широковещательной передачи . Существуют конструкции криптографических 2-полилинейных отображений, известные как билинейные отображения ^[1], однако проблема построения таких полилинейных ^[1] отображений для кажется намного более сложной ^[2]${\ 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}}}$${\ displaystyle n> 2}$ и безопасность предложенных кандидатов все еще не ясна. ^[3]

Определение [ править ]

Для n = 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}}$

Общий случай (для любого n ) [ править ]

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

1. Все (для ) и являются группами одного порядка;${\displaystyle G_{i}}$${\displaystyle 1\leq i\leq n}$${\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], который основан на графиках.

Ссылки [ править ]