Криптография на основе пар

Криптография на основе спаривания — это использование спаривания элементов двух криптографических групп с третьей группой с отображением $e:G_{1}\times G_{2}\to G_{T}$ для создания или анализа криптографических систем.

Определение

Следующее определение обычно используется в большинстве научных работ. ^[1]

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

Билинейность: $\forall a,b\in \mathbb {F} _{q}^{*},P\in G_{1},Q\in G_{2}:\ e\left(aP,bQ\right)=e\left(P,Q\right)^{ab}$
Невырожденность: $e\neq 1$
Вычислимость: Существует эффективный алгоритм вычисления $e$ .

Классификация

Если одна и та же группа используется для первых двух групп (т.е. $G_{1}=G_{2}$ ), спаривание называется симметричным и представляет собой отображение двух элементов одной группы на элемент второй группы.

Некоторые исследователи классифицируют парные экземпляры на три (или более) основных типа:

$G_{1}=G_{2}$ ;
$G_{1}\neq G_{2}$ но существует эффективно вычислимый гомоморфизм $\phi :G_{2}\to G_{1}$ ;
$G_{1}\neq G_{2}$ и не существует эффективно вычислимых гомоморфизмов между $G_{1}$ и $G_{2}$ . ^[2]

Использование в криптографии

Если они симметричны, пары можно использовать для сведения сложной проблемы в одной группе к другой, обычно более простой задаче в другой группе.

Например, в группах, оснащенных билинейным отображением , таким как спаривание Вейля или спаривание Тейта обобщения вычислительной проблемы Диффи-Хеллмана , считается, что невозможны, в то время как более простая проблема Диффи-Хеллмана с принятием решения может быть легко решена с использованием функции спаривания. Первую группу иногда называют « группой пробелов» из-за предполагаемой разницы в сложности между этими двумя задачами в группе. ^[3]

Позволять $e$ быть невырожденным, эффективно вычислимым, билинейным спариванием. Позволять $g$ быть генератором $G$ . Рассмотрим пример проблемы CDH : $g$ , $g^{x}$ , $g^{y}$ . Интуитивно, функция спаривания $e$ не поможет нам вычислить $g^{xy}$ , решение проблемы CDH. Предполагается, что этот случай проблемы CDH неразрешим. Данный $g^{z}$ , мы можем проверить, $g^{z}=g^{xy}$ без знания $x$ , $y$ , и $z$ , проверяя, является ли $e(g^{x},g^{y})=e(g,g^{z})$ держит.

Используя свойство билинейности $x+y+z$ раз, мы видим, что если $e(g^{x},g^{y})=e(g,g)^{xy}=e(g,g)^{z}=e(g,g^{z})$ , тогда, поскольку $G_{T}$ является группой простого порядка, $xy=z$ .

Впервые использованный для криптоанализа , ^[4] пары также использовались для создания многих криптографических систем, для которых не известна другая эффективная реализация, таких как схемы шифрования на основе идентификаторов или схемы шифрования на основе атрибутов . Таким образом, уровень безопасности некоторых дружественных к спариванию эллиптических кривых позже был снижен.

используется криптография на основе пар В схеме криптографического обязательства KZG .

Современный пример использования билинейных пар — схема цифровой подписи BLS . ^[3]

Криптография, основанная на спаривании, опирается на предположения о стойкости, отличные от, например, криптографии с эллиптическими кривыми , которая более старая и изучается в течение длительного времени.

Криптоанализ

В июне 2012 года Национальный институт информационных и коммуникационных технологий (NICT), Университет Кюсю и Fujitsu Laboratories Limited улучшили предыдущую границу для успешного вычисления дискретного логарифма на суперсингулярной эллиптической кривой с 676 бит до 923 бит. ^[5]

В 2016 году алгоритм сита с расширенным номером башни ^[6] позволило снизить трудоемкость нахождения дискретного логарифма в некоторых результирующих группах пар. Существует несколько вариантов решетчатого алгоритма множественного и расширенного поля номера башни, расширяющие применимость и повышающие сложность алгоритма. Единое описание всех подобных алгоритмов с дальнейшими улучшениями было опубликовано в 2019 году. ^[7] Учитывая эти достижения, несколько работ ^[8]^[9] представила пересмотренные конкретные оценки размеров ключей криптосистем на основе безопасных пар.

Ссылки

^ Коблиц, Нил; Менезес, Альфред (2005). «Криптография на основе спаривания на высоком уровне безопасности». Криптография и кодирование . Конспекты лекций по информатике. Том. 3796. стр. 13–36. дои : 10.1007/11586821_2 . ISBN 978-3-540-30276-6 .
^ Гэлбрейт, Стивен; Патерсон, Кеннет; Смарт, Найджел (2008). «Пары для криптографов» . Дискретная прикладная математика . 156 (16): 3113–3121. дои : 10.1016/j.dam.2007.12.010 .
^ Jump up to: Перейти обратно: ^а ^б Боне, Дэн; Линн, Бен; Шахам, Ховав (2001). Бойд, Колин (ред.). «Короткие подписи от пары Вейля» . Достижения в криптологии — ASIACRYPT 2001 . Берлин, Гейдельберг: Springer: 514–532. дои : 10.1007/3-540-45682-1_30 . ISBN 978-3-540-45682-7 .
^ Менезес, Альфред Дж. Менезес; Окамато, Тацуаки; Ванстон, Скотт А. (1993). «Приведение логарифмов эллиптической кривой к логарифмам в конечном поле». Транзакции IEEE по теории информации . 39 (5): 1639–1646. дои : 10.1109/18.259647 .
^ «NICT, Университет Кюсю и лаборатории Fujitsu достигли мирового рекорда в криптоанализе криптографии следующего поколения» . Пресс-релиз НИКТ . 18 июня 2012 г.
^ Ким, Тэчан; Барбулеску, Разван (2015). «Сито с расширенным числом башен: новая сложность для случая среднего простого числа» . Архив электронной печати по криптологии .
^ Саркар, Палаш; Сингх, Шашанк (2019). «Единый полиномиальный метод выбора для алгоритма сита (башенного) числового поля» . Достижения в математике связи . дои : 10.3934/amc.2019028 .
^ Менезес, Альфред; Саркар, Палаш; Сингх, Шашанк (2016), Проблемы с оценкой влияния достижений NFS на безопасность парной криптографии , Конспекты лекций по информатике, том. 10311, Springer-Verlag, стр. 83–108, ISBN. 978-3-319-61272-0
^ Барбулеску, Разван; Дюкен, Сильвен (01 октября 2019 г.). «Обновление оценок размера ключей для пар» . Журнал криптологии . 32 (4): 1298–1336. дои : 10.1007/s00145-018-9280-5 . ISSN 1432-1378 . S2CID 253635514 .

Внешние ссылки

[1] Коблиц, Нил; Менезес, Альфред (2005). «Криптография на основе спаривания на высоком уровне безопасности». Криптография и кодирование . Конспекты лекций по информатике. Том. 3796. стр. 13–36. дои : 10.1007/11586821_2 . ISBN 978-3-540-30276-6 .

[pfc-2] Гэлбрейт, Стивен; Патерсон, Кеннет; Смарт, Найджел (2008). «Пары для криптографов» . Дискретная прикладная математика . 156 (16): 3113–3121. дои : 10.1016/j.dam.2007.12.010 .

[:0-3] Jump up to: Перейти обратно: ^а ^б Боне, Дэн; Линн, Бен; Шахам, Ховав (2001). Бойд, Колин (ред.). «Короткие подписи от пары Вейля» . Достижения в криптологии — ASIACRYPT 2001 . Берлин, Гейдельберг: Springer: 514–532. дои : 10.1007/3-540-45682-1_30 . ISBN 978-3-540-45682-7 .

[4] Менезес, Альфред Дж. Менезес; Окамато, Тацуаки; Ванстон, Скотт А. (1993). «Приведение логарифмов эллиптической кривой к логарифмам в конечном поле». Транзакции IEEE по теории информации . 39 (5): 1639–1646. дои : 10.1109/18.259647 .

[5] «NICT, Университет Кюсю и лаборатории Fujitsu достигли мирового рекорда в криптоанализе криптографии следующего поколения» . Пресс-релиз НИКТ . 18 июня 2012 г.

[6] Ким, Тэчан; Барбулеску, Разван (2015). «Сито с расширенным числом башен: новая сложность для случая среднего простого числа» . Архив электронной печати по криптологии .

[7] Саркар, Палаш; Сингх, Шашанк (2019). «Единый полиномиальный метод выбора для алгоритма сита (башенного) числового поля» . Достижения в математике связи . дои : 10.3934/amc.2019028 .

[8] Менезес, Альфред; Саркар, Палаш; Сингх, Шашанк (2016), Проблемы с оценкой влияния достижений NFS на безопасность парной криптографии , Конспекты лекций по информатике, том. 10311, Springer-Verlag, стр. 83–108, ISBN. 978-3-319-61272-0

[9] Барбулеску, Разван; Дюкен, Сильвен (01 октября 2019 г.). «Обновление оценок размера ключей для пар» . Журнал криптологии . 32 (4): 1298–1336. дои : 10.1007/s00145-018-9280-5 . ISSN 1432-1378 . S2CID 253635514 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]