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

В внешнее предположение Диффи – Хеллмана (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 e(\cdot ,\cdot ):{\mathbb {G} }_{1}\times {\mathbb {G} }_{2}\rightarrow {\mathbb {G} }_{T}}$.
3. В решающая проблема Диффи – Хеллмана (DDH) трудноразрешим в ${\displaystyle {\mathbb {G} }_{1}}$.

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

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

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

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

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