О спариваниях Вейля

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

Ответ. Редакция благодарна автору за такой вопрос. Он соответствует тематике сайта, четко сформулирован и, главное, интересен с научной точки зрения. Но ответить на этот вопрос оказалось весьма непросто.

Начнем с задачи Диффи–Хеллмана. Вычислительный вариант этой задачи состоит в вычислении значения $g^{ab}$ по заданным $g^a$ и $g^b$. Здесь и далее предполагается, что вся необходимая информация о группе, в частности порождающий $g$, известна и не указывается во входных данных. Распознавательный вариант задачи Диффи–Хеллмана (DDH) формулируется так. Пусть значения $a$, $b$ и $r$ случайны. Требуется отличить распределения вероятностей $\{ (g^a, g^b, g^{ab})\}$ и $\{ (g^a, g^b, g^r)\}$. Предположение о вычислительной трудности этой задачи является на данный момент основным криптографическим предположением. На его основе доказано множество результатов о стойкости. Математически строгая формулировка этого предположения говорит о семействе групп с некоторыми свойствами эффективности, а основное требование формулируется на основе вычислительной неотличимости семейств распределений. Мы такое определение не приводим, его можно найти в справочнике.

К сожалению, в данной области наблюдается путаница с терминологией. Иногда распознавательной задачей Диффи–Хеллмана называют задачу распознавания языка $L_{DH}=\{ (g^a,g^b,g^{ab})\}$. Здесь предполагается, что входами могут быть произвольные тройки $(g^a,g^b,g^r)$. Заметим, что в этих двух вариантах требования различны: алгоритм, распознающий язык $L_{DH}$, доставит решение задачи DDH. Обратное представляется сомнительным. Вопрос о связи двух указанных вариантов определения задачи DDH рассматривается в обзоре Боне.

Можно было бы сказать, что задача распознавания языка $L_{DH}$ не представляет никакого интереса для криптографии, если бы не одна особенность вычислительной задачи Диффи–Хеллмана. Предположим, что мы решаем эту задачу методом угадывания. Как, зная $g^a$ и $g^b$, проверить, что выбранный нами элемент группы равен $g^{ab}$? Никакие эффективные методы не известны. Задача распознавания языка $L_{DH}$ — это в точности проверка правильности решения задачи Диффи–Хеллмана.

Коллизии терминов — не новость для науки и, в частности, для математики. Но в нашем случае дела совсем плохи. На вопрос, какой из двух указанных вариантов будет правильно, с методической точки зрения, называть распознавательной задачей Диффи–Хеллмана, ответ простой: никакой.

Сам термин «распознавательная задача» заимствован из теории сложности вычислений. Там рассматриваются два типа вычислительных задач: задачи поиска (search) и задачи распознавания (decision). Согласно этой терминологии вычислительный вариант задачи Диффи–Хеллмана есть задача поиска. Ей соответствует множество распознавательных вариантов, например задача распознавания языка $\{ (g^a,g^b,c): g^{ab}>c\}$. Здесь $c$ — произвольный элемент группы. Смысл в том, что вычислительный вариант задачи должен эффективно сводиться к соответствующей распознавательной задаче (так называемая самосводимость).

Теперь о перспективах применения спариваний Вейля к задачам Диффи–Хеллмана.

Есть такая далеко не новая и почти очевидная идея. Предположим, что нам нужно решать задачу дискретного логарифмирования или вычислительный вариант задачи Диффи–Хеллмана в группе $G_1$, где всё сложно. Предположим также, что нам удалось найти группу $G_2$, в которой та же задача решается более эффективно. Можно попытаться найти хорошее отображение $F$ из $G_1$ в $G_2$, позволяющее построить сводимость исходной задачи к аналогичной, но уже в группе $G_2$.

Здесь возникает новая проблема: решение, найденное в группе $G_2$, необходимо «вернуть» в группу $G_1$. Отображение $F$ должно быть обратимым, а следовательно, слишком уж хорошим. Кроме того, при наличии такого $F$ неясно, что препятствует переводу эффективных алгоритмов из $G_2$ в $G_1$.

Но в случае распознавательных вариантов задачи Диффи–Хеллмана обсуждаемый подход выглядит более перспективным, поскольку от отображения $F$ не требуется обратимости.

Исследования, посвященные применимости спариваний Вейля к задачам Диффи–Хеллмана, в целом можно считать развитием данной идеи.

Попытку ответить на заданный вопрос предпринял М. И. Анохин. После некоторых размышлений и сомнений редакция сочла целесообразным поместить этот текст в раздел Лекторий. Можно сказать, что в этом материале излагается подход к проблеме с позиции алгебраиста.

Редакция также обратилась за помощью к Михаилу Алексеевичу Черепневу, одному из ведущих специалистов именно в данной области. Подготовленный им материал о спариваниях Вейля можно найти здесь. Кроме того, Михаил Алексеевич разрешил выложить на сайте адрес своей электронной почты [показать адрес]. Посетители сайта могут задавать ему вопросы по данной тематике.

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна