Криптография на основе пар - это использование пары между элементами двух криптографических групп в третью группу с сопоставлениемдля построения или анализа криптографических систем.
Определение
Следующее определение обычно используется в большинстве научных статей. [1]
Позволять - две аддитивные циклические группы простого порядка, а также другая циклическая группа порядка написано мультипликативно. Спаривание - это карта:, который удовлетворяет следующим свойствам:
- Билинейность
- Невырожденность
- Вычислимость
- Существует эффективный алгоритм вычисления .
Классификация
Если одна и та же группа используется для первых двух групп (т. Е. ), спаривание называется симметричным и представляет собой отображение двух элементов одной группы на элемент из второй группы.
Некоторые исследователи классифицируют парные экземпляры на три (или более) основных типа:
- ;
- но существует эффективно вычислимый гомоморфизм ;
- и нет эффективно вычислимых гомоморфизмов между а также . [2]
Использование в криптографии
Если они симметричны, то пары можно использовать, чтобы свести сложную проблему в одной группе к другой, обычно более легкой задаче в другой группе.
Например, в группах, оснащенных билинейным отображением, таким как спаривание Вейля или спаривание Тейта , обобщения вычислительной проблемы Диффи-Хеллмана считаются недопустимыми, в то время как более простая проблема Диффи-Хеллмана, требующая принятия решений, может быть легко решена с помощью функции спаривания. Первую группу иногда называют группой пробелов из-за предполагаемой разницы в сложности между этими двумя проблемами в группе.
В то время как первый используются для криптоанализа , [3] спаривания также были использованы для построения многих криптографических систем , для которых не известна никакой другой эффективной реализации, таких как шифрование на основе идентичности или шифрование атрибутов на основе схемы.
Современный пример использования билинейных пар проиллюстрирован схемой подписи Боне-Линн-Шахам .
Криптография на основе пар основывается на допущениях о твердости отдельно от, например, проблемы дискретного логарифма эллиптической кривой , которая старше и изучается в течение более длительного времени.
Криптоанализ
В июне 2012 года Национальный институт информационных и коммуникационных технологий (NICT), Университет Кюсю и Fujitsu Laboratories Limited улучшили предыдущую оценку для успешного вычисления дискретного логарифма суперсингулярной эллиптической кривой с 676 бит до 923 бит. [4]
Рекомендации
- ^ Коблиц, Нил; Менезеш, Альфред (2005). «Криптография на основе пар с высоким уровнем безопасности». LNCS . 3796 .
- ^ Гэлбрейт, Стивен; Патерсон, Кеннет; Умный, Найджел (2008). «Спаривания для криптографов». Дискретная прикладная математика . 156 (16): 3113–3121. DOI : 10.1016 / j.dam.2007.12.010 .
- ^ Менезес, Альфред Дж. Менезес; Окамато, Тацуаки; Ванстон, Скотт А. (1993). «Приведение логарифмов эллиптических кривых к логарифмам в конечном поле». IEEE Transactions по теории информации . 39 (5).
- ^ «NICT, Университет Кюсю и лаборатории Fujitsu достигли мирового рекорда криптоанализа криптографии следующего поколения» . Пресс-релиз NICT . 18 июня 2012 г.