XDH предположение

Внешний Диффи-Хеллмана (XDH) предположение является вычислительная предположение твердости используется в эллиптической кривой криптографии . Предположение XDH состоит в том, что существуют определенные подгруппы эллиптических кривых, которые обладают полезными свойствами для криптографии. В частности, XDH подразумевает существование двух различных групп со следующими свойствами:${\ Displaystyle \ langle {\ mathbb {G}} _ {1}, {\ mathbb {G}} _ {2} \ rangle}$

1. Проблема дискретного логарифмирования (DLP), вычислительная проблема Диффи – Хеллмана (CDH) и вычислительная проблема ко-Диффи – Хеллмана неразрешимы в и .${\ Displaystyle {\ mathbb {G}} _ {1}}$${\ displaystyle {\ mathbb {G}} _ {2}}$
2. Существует эффективно вычислимое билинейное отображение (спаривание) .${\ Displaystyle е (\ cdot, \ cdot): {\ mathbb {G}} _ {1} \ times {\ mathbb {G}} _ {2} \ rightarrow {\ mathbb {G}} _ {T}}$
3. Принятия решения проблем Диффи-Хеллмана (ДДГ) является неразрешимой в .${\ Displaystyle {\ mathbb {G}} _ {1}}$

Вышеупомянутый состав называется асимметричным XDH . Более сильный вариант предположения ( симметричное XDH или SXDH ) имеет место , если ДДГ является также неразрешимыми в .${\ displaystyle {\ mathbb {G}} _ {2}}$

Предположение XDH используется в некоторых криптографических протоколах на основе пар . В некоторых подгруппах эллиптических кривых наличие эффективно вычислимого билинейного отображения (спаривания) может позволить найти практические решения проблемы DDH . Эти группы, называемые группами Диффи-Хеллмана (GDH), поддерживают множество новых криптографических протоколов, включая трехчастный обмен ключами , шифрование на основе идентичности и секретное рукопожатие (и это лишь некоторые из них). Однако простота вычисления DDH в группе GDH также может быть препятствием при построении криптосистем; например, невозможно использовать криптосистемы на основе DDH, такие как ElGamalвнутри группы GDH. Поскольку предположение DDH выполняется по крайней мере в одной из пары групп XDH, эти группы могут использоваться для построения протоколов на основе пар, которые допускают шифрование в стиле Эль-Гамаля и другие новые криптографические методы.

На практике считается, что предположение XDH может выполняться в некоторых подгруппах эллиптических кривых MNT . Это понятие было впервые предложено Скоттом (2002), а затем Боне , Бойеном и Шахамом (2002) как средство повышения эффективности схемы подписи. Предположение было формально определено Ballard, Green, de Medeiros и Monrose (2005), и в этой работе были представлены полные детали предлагаемой реализации. Доказательством справедливости этого предположения является доказательство Verheul (2001) и Galbraith and Rotger (2004) отсутствия карт искажения.в двух конкретных подгруппах эллиптических кривых, которые обладают эффективно вычислимым спариванием. Поскольку спаривания и карты искажения в настоящее время являются единственными известными средствами для решения проблемы DDH в группах эллиптических кривых, считается, что предположение DDH, следовательно, выполняется в этих подгруппах, в то время как спаривания по-прежнему возможны между элементами в различных группах.

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

1. Майк Скотт. Обмен на основе аутентифицированного идентификатора и удаленный вход с помощью простого токена и PIN-кода . Архив электронной печати (2002/164), 2002 г. ( файл в формате pdf )
2. Дэн Боне , Ксавьер Бойен, Ховав Шахам. Короткие групповые подписи. CRYPTO 2004. ( файл в формате pdf )
3. Лукас Баллард, Мэтью Грин, Брено де Медейрос, Фабиан Монроуз. Корреляционно-устойчивое хранилище через шифрование с возможностью поиска по ключевым словам. Архив электронной печати (2005/417), 2005 г. ( файл в формате pdf )
4. Стивен Д. Гэлбрейт, Виктор Ротгер. Группы Диффи – Хеллмана с простым решением. LMS Journal of Computing and Mathematics, август 2004 г. ( [1] )
5. ER Verheul, Доказательства того, что XTR более безопасен, чем криптосистемы с суперсингулярными эллиптическими кривыми, в B. Pfitzmann (ed.) EUROCRYPT 2001, Springer LNCS 2045 (2001) 195–210. [2]