Проблема Диффи – Хеллмана - Diffie–Hellman problem

В Проблема Диффи – Хеллмана (DHP) математическая проблема, впервые предложенная Уитфилд Диффи и Мартин Хеллман в контексте криптография. Мотивация этой проблемы заключается в том, что многие системы безопасности используют односторонние функции: математические операции, которые быстро вычисляются, но трудно отменить. Например, они позволяют шифрование сообщения, но отменить шифрование сложно. Если бы решение DHP было легким, эти системы легко сломались бы.

Описание проблемы

Неофициально проблема Диффи – Хеллмана формулируется следующим образом:

Учитывая элемент грамм и значения граммИкс и граммy, какова ценность граммху?

Формально, грамм это генератор некоторых группа (обычно мультипликативная группа из конечное поле или эллиптическая кривая группа) и Икс и y случайно выбранные целые числа.

Например, в Обмен ключами Диффи-Хеллмана, подслушивающий граммИкс и граммy обмениваются как часть протокола, и обе стороны вычисляют общий ключ граммху. Быстрое решение DHP позволит перехватчику нарушить конфиденциальность обмена ключами Диффи-Хеллмана и многих его вариантов, включая Шифрование Эль-Гамаля.

Вычислительная сложность

В криптография, для определенных групп это предполагается что DHP сложен, и это часто называют Предположение Диффи – Хеллмана. Проблема выдерживала тщательное изучение в течение нескольких десятилетий, и ни одно "легкое" решение еще не было опубликовано.

По состоянию на 2006 г. наиболее эффективным средством решения DHP является решение задача дискретного логарифмирования (DLP), который должен найти Икс данный грамм и граммИкс. Фактически, значительный прогресс (по ден Буре, Маурер, Волк, Boneh и Lipton ) был сделан, чтобы показать, что во многих группах DHP почти так же сложен, как DLP. На сегодняшний день нет никаких доказательств того, что DHP или DLP являются сложной проблемой, за исключением общих групп (по Нечаеву и Шоупу).

Другие варианты

Было рассмотрено множество вариантов проблемы Диффи – Хеллмана. Наиболее значимый вариант - это решающая проблема Диффи – Хеллмана (DDHP), который должен различать граммху из случайного элемента группы, учитывая грамм, граммИкс, и граммy. Иногда DHP называют вычислительная проблема Диффи – Хеллмана (CDHP), чтобы более четко отличить его от DDHP. Недавно группы с пары стали популярными, и в этих группах DDHP прост, но все же DHP все еще считается сложным. Для менее значимых вариантов DHP см. Ссылки.

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

  • Б. ден Бур, Диффи – Хеллмана так же силен, как дискретный журнал для некоторых простых чисел в достижениях в криптологии - КРИПТО 88, Конспект лекций по информатике 403, Springer, стр. 530, 1988.
  • У. М. Маурер и С. Вольф, Оракул Диффи – Хеллмана in Advances in Cryptology - CRYPTO 96, (N. Koblitz, ed.), Lecture Notes in Computer Science 1070, Springer, pp. 268–282, 1996.
  • Maurer, Ueli M .; Вольф, Стефан (2000). «Протокол Диффи – Хеллмана». Конструкции, коды и криптография. 19 (2/3): 147–171. Дои:10.1023 / А: 1008302122286.
  • Д. Бонех и Р. Дж. Липтон, Алгоритмы для полей черного ящика и их применение в криптографии in Advances in Cryptology - CRYPTO 96, (N. Koblitz, ed.), Lecture Notes in Computer Science 1070, Springer, pp. 283–297, 1996.
  • А. Музеро, Н. П. Смарт и Ф. Веркаутеран, Эквивалентность DHP и DLP для эллиптических кривых, используемых в практических приложениях, LMS J. Comput. Математика, 7, pp. 50–72, 2004. См. [www.lms.ac.uk].
  • Д. Р. Л. Браун и Р. П. Галлант, Статическая проблема Диффи – Хеллмана, IACR ePrint 2004/306.
  • В. И. Нечаев, Сложность детерминированного алгоритма дискретного логарифма, Математические заметки, 55 (2), с. 165–172, 1994.
  • В. Шоуп, Нижние оценки дискретных логарифмов и смежных задач в достижениях в криптологии - ЕВРОКРИПТ 97, (W. Fumy, ed.), Lecture Notes in Computer Science 1233, Springer, pp. 256–266, 1997.
  • Бао, Фэн; Дэн, Роберт Х .; Чжу, Хуафей (2003). "Вариации проблемы Диффи-Хеллмана". ICICS 2003: Информационная и коммуникационная безопасность. Конспект лекций по информатике. 2836. Springer. С. 301–312. CiteSeerX  10.1.1.104.3007. Дои:10.1007/978-3-540-39927-8_28. ISBN  978-3-540-20150-2.
  • Бонех, Дэн (1998). «Решение проблемы Диффи-Хеллмана». ANTS 1998: алгоритмическая теория чисел. Конспект лекций по информатике. 1423. Springer. С. 48–63. CiteSeerX  10.1.1.461.9971. Дои:10.1007 / bfb0054851. ISBN  978-3-540-64657-0.
  • Брессон, Эммануэль; Чевассут, Оливье; Pointcheval, Дэвид (2003). "Групповые проблемы Диффи-Хеллмана" (PDF). SAC 2002: Избранные области криптографии. Конспект лекций по информатике. 2595. Springer. С. 325–338. Дои:10.1007/3-540-36492-7_21. ISBN  978-3-540-00622-0.
  • Бихам, Эли; Бонех, Дэн; Рейнгольд, Омер (1999). «Нарушение обобщенного Диффи – Хеллмана по модулю композиции не проще, чем факторизация». Письма об обработке информации. 70 (2): 83–87. CiteSeerX  10.1.1.39.110. Дои:10.1016 / S0020-0190 (99) 00047-2.
  • Штайнер, Майкл; Цудик, Гена; Вайднер, Майкл (1996). «Распространение ключей Диффи-Хеллмана на групповое общение». Материалы 3-й конференции ACM по компьютерной и коммуникационной безопасности - CCS '96. ACM. стр.31–37. CiteSeerX  10.1.1.35.9717. Дои:10.1145/238168.238182. ISBN  978-0897918299.
  • Диффи, В .; Хеллман, М. (1976). «Новые направления в криптографии». IEEE Transactions по теории информации. 22 (6): 644–654. CiteSeerX  10.1.1.37.9720. Дои:10.1109 / tit.1976.1055638.