ENCRY Apr 17 2023 at 17:59

Режим моментальной цифровой подписи

Hard

13 min

1.8K

Analytics

Мы не отступаем от сложившейся традиции и продолжаем знакомить с полученными результатами. В настоящей заметке речь пойдёт об объявленном ранее режиме моментальной электронной цифровой подписи (МЭЦП). Хотя основное смысловое содержание режима МЭЦП раскрыто в предыдущей публикации, мы полагаем, что необходимая конкретизация будет способствовать дополнительному пониманию.

Следует подчеркнуть, что МЭЦП — это не отдельный вид подписи, а специальный режим, в котором может применяться любая известная схема ЭЦП. Иными словами, мы никоим образом не берём на себя ответственность в связи с разработкой новой схемы, но предлагаем резонный способ применения уже существующих схем.

Если отталкиваться от названия, то становится понятно, что режим МЭЦП действует в моменте, то есть в данный конкретный момент времени, сейчас. Это означает, что режим применяется для заверения тех данных, которые неразрывно связаны с некоторой идентифицирующей сущностью, и эта связь непосредственно следует из предъявленного ранее доказательства. Получить такое доказательство можно в результате выполнения интерактивного протокола идентификации. Следовательно, режим МЭЦП оправдан только в сочетании с таким протоколом. Рассуждая о подобном сочетании в первую очередь будем полагать, что в процессе формирования подписи задействованы некоторые уникальные переменные текущей сессии протокола идентификации. Важно понимать, что по построению эти переменные эфемерны и их действие ограничено конкретной сессией.

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

Мы покажем, что режим МЭЦП возможен для любой известной схемы ЭЦП. Однако остаётся открытым вопрос о том, может ли такой режим применяться в сочетании с произвольным протоколом идентификации, например, с любым из известных. С другой стороны, режим МЭЦП без проблем сочетается с интерактивным протоколом идентификации с возможностью формирования общего секретного сессионного ключа, разработанного нами в развитие протокола, представленного в этой заметке.

В настоящем тексте мы не предлагаем формальных доказательств, но придерживаемся такой манеры изложения, которая позволяет раскрыть суть через рассмотрение ряда содержательных примеров. К сожалению, не удалось избежать формальных обозначений. Надеемся, что это не вызовет затруднений, так как все необходимые обозначения были введены нами ранее. К тому же мы используем стандартную математическую нотацию, принятую в специальной литературе. Для примера следует обратиться к [Cohen_etc._2006].

Интерактивный протокол идентификации

Прежде всего напомним, что такое интерактивный протокол идентификации. По сути, это игра двух участников, каждый из которых наделен собственной ролью. Чтобы избежать излишних усложнений умышленно ограничим число субъектов взаимодействия.

Различают Доказывающего (Prover, ) и Проверяющего (Verifier, ). предоставляет доказательство, например, знания секрета, а проверяет это доказательство и выносит вердикт при помощи решающего правила. Вердикт может быть положительным (доказательство принято), отрицательным (доказательство отвергнуто) или даже неопределённым. Как правило, по факту принятого или отвергнутого доказательства инициируется определенное действие. Например, распространен сценарий, когда запрашивает доступ к некоторому ресурсу и такой доступ предоставляется, если принимает доказательство. Возможно и иное применение.

Протоколы идентификации относятся к более общему классу $\Sigma\mbox{-протоколов}$ , которые впервые были введены в работе [Cramer_1996]. и моделируются при помощи вероятностной интерактивной машины Тьюринга, а сам $\Sigma\mbox{-протокол}$ есть суть интерактивная схема доказательства в стиле игры Артура-Мерлина [Babai_Moran_1988], в которой всегда выбирает некоторую случайную величину с дискретным равномерным распределением.

Сосредоточимся на таких протоколах идентификации, которые опираются на методы асимметричной криптографии.

Интерактивный протокол идентификации можно представить в виде следующей диаграммы:
$P \stackrel{\mbox{witness}}{\longrightarrow} V \stackrel{\mbox{challenge}}{\longrightarrow} P \stackrel{\mbox{response}}{\longrightarrow} V.$

Из диаграммы ясно, что в ходе протокола передается три сообщения: witness, challenge и response. При этом передает два сообщения: witness и response, а — только одно: challenge. Назначение сообщений следует из их названия. На наш взгляд перевод упомянутых сообщений с английского языка на русский нецелесообразен, так как возможные неточности перевода способны исказить смысл и привести к непониманию.

Назовём эфемеридами случайные независимые переменные с равномерным распределением, которые меняются от одной сессии протокола к другой. По своему криптографическому назначению эфемериды равнозначны секретным ключам. Для раскрытия неизвестной эфемериды необходимо найти решение некоторой вычислительно-сложностной проблемы или предпринять силовую атаку.

Предполагается, что каждый участник имеет в своём распоряжении пару уникальных ключей: секретный и общедоступный. Кроме этого, для общедоступных ключей выпущены надлежащие сертификаты.

Стороны выполняют следующие действия:

формирует witness на основании общедоступного ключа , а также не менее одной известной только ему эфемериды.
формирует challenge при помощи не менее одной известной только ему эфемериды.
формирует response на основании собственных секретного и общедоступного ключей и challenge.
выносит вердикт на основании witness, response, задействованной в challenge эфемериды и общедоступного ключа .

Любой протокол идентификации включает три сообщения, которые благодаря эфемеридам распределены независимо и равномерно. Доказано, что меньшего количества сообщений быть не может (может быть больше). Все перечисленные сообщения имеют одинаковую смысловую нагрузку в различных протоколах идентификации, но способы их формирования могут существенно различаться и зависеть от основных положений вычислительно-сложностной проблематики, а также выбранного математического аппарата.

После некоторого размышления мы решили оставить те обозначения, которые используются в разработанном нами интерактивном протоколе идентификации с возможностью формирования общего секретного сессионного ключа, который пока не обнародован. Так в качестве response передается $c=\hslash(g_1)$ , где $\hslash(\cdot)$ — некоторая известная обеим сторонам криптографическая хеш-функция. Для проверки доказательства вычисляет При этом используется простое решающее правило вида $\hslash(g_1)\stackrel{?}{=}\hslash(g_3)$ . Здесь $g_1, g_3\in\mathbb{G}_3.$ Заметим, что способ вычисления и в данном контексте несущественен.

Поскольку большинство публикуемых нами текстов взаимосвязаны, то надеемся, что такой подход в дальнейшем упростит «перебрасывание мостика» между различными заметками.

Совместимость с произвольной схемой ЭЦП

Пусть имеется пара ключей $\{\mathbf{z}, \mathsf{P}=[\mathbf{z}]\mathsf{G}_1\}$ и сертификат $\{D_{\mathsf{P}}, \mathsf{P}, \Im_{\mathsf{P}}\}$ . Покажем как это работает на примере известной схемы ЭЦП Шнорра [Schnorr_1990].

выступает в роли заверителя. Для заданных сообщения , секретного ключа $\mathbf{z}$ и заверитель выполняет следующие вычисления:

$\mathsf{Q}=[\varepsilon]\mathsf{G}_1$ , где $\varepsilon\in_R\!(0,m-1]$ ;
$\gamma=\hslash(g_1\|M\|x_{\mathsf{Q}})$ ;
$\delta=\varepsilon-\gamma\mathbf{z}\pmod m$ ;
$\Im=\{\gamma, \delta\}$ .

Пусть имеются подпись $\Im'=\{\gamma', \delta'\}$ и сообщение , такие, что $(\delta'\neq\delta)\land(\gamma'\neq\gamma)\land(M'\neq M)$ . Предположим, что подлинность и целостность ключа $\mathsf{P}$ подтверждены в результате проверки действующего сертификата $\{D_{\mathsf{P}}, \mathsf{P}, \Im_{\mathsf{P}}\}$ . выполняет следующие вычисления:

$\mathsf{S}=[\delta']\mathsf{G}_1+[\gamma']\mathsf{P}=[\delta'+\gamma'\mathbf{z}\pmod m]\mathsf{G}_1$ ;
$\hslash(g_3\|M'\|x_\mathsf{S})\stackrel{?}{=}\gamma'$ .

Если $\hslash(g_3\|M'\|x_\mathsf{S})=\gamma$ , то $\mathfrak{B}=True$ , где $\mathfrak{B}\Leftarrow{\rm{Verify}}(\hslash(g_3\|M'\|x_{\mathsf{S}})),\Im',\mathsf{P})$ . Предположим, что $\delta'=\varepsilon-\gamma\mathbf{z}\pmod m$ . Следовательно, $\mathsf{S}=[\varepsilon-\gamma\mathbf{z}+\gamma'\mathbf{z}\pmod m]\mathsf{G}_1=[\varepsilon]\mathsf{G}_1=\mathsf{Q}$ , если $\gamma'=\gamma=\hslash(g_3\|M'\|x_\mathsf{S})\Rightarrow (M'=M)\land(x_\mathsf{S}=x_\mathsf{Q})\land(g_3=g_1)$ . При $((\delta'\neq\delta)\land(\gamma'=\gamma))\lor((\delta'=\delta)\land(\gamma'\neq\gamma))\lor((\delta'\neq\delta)\land(\gamma'\neq\gamma))$ с преобладающей вероятностью $\mathfrak{B}=False$ и с пренебрежимо малой $\mathfrak{B}=True$ . Однако, если $(\delta'=\delta)\land(\gamma'=\gamma)$ , то с преобладающей вероятностью $\mathfrak{B}=True$ и с пренебрежимо малой $\mathfrak{B}=False$ .

Проверка ЭЦП и верификация взаимосвязаны. Пусть — некоторые персональные данные и $\Im\Leftarrow{\rm{Sign}}(\hslash(D), \mathbf{z})$ . Для проверки предъявлены , $\Im'$ и действующий сертификат $\{D_{\mathsf{P}}, \mathsf{P}, \Im_{\mathsf{P}}\}$ . Если ЭЦП валидна, иначе говоря $\hslash(g_3\|D'\|x_\mathsf{S})=\gamma$ , то . По факту валидности выполняется верификация $D'\stackrel{?}{=}D_{\mathsf{P}}$ . Подлинность персональных данных следует из $D'=D_{\mathsf{P}}$ .

Режим МЭЦП можно реализовать с привлечением произвольной конвенциональной схемы на основе арифметики точек эллиптической кривой. Такой подход присущ подавляющему большинству современных схем ЭЦП [Schnorr_1990, Paterson_2002, Hess_2003, Boneh_Shacham_Lynn_2004, Zhang_Safavi-Naini_Susilo_2004, Boneh_Boyen_2004]. Однако это условие не является необходимым. Например, можно без потери общности заменить подгруппу группы точек эллиптической кривой на подгруппу простого порядка группы $\mathbb{F}^*_p$ . Заметим, что режим также совместим со схемами ЭЦП, которые разработаны с учетом положений постквантовой криптографии.

Такая совместимость имеет простое объяснение. Поскольку в произвольной конвенциональной схеме ЭЦП вычисление $\hslash(M)$ носит нормативный характер, — присутствует всегда в любой схеме ЭЦП, то замена $\hslash(M)$ на $\hslash(\ldots\|M\|\ldots)$ не приводит к негативным последствиям для криптостойкости этой схемы, так как в общем случае неизвестна зависимость вероятности коллизии от аргумента криптографической хеш-функции $\hslash(\cdot)$ . Здесь под коллизией мы понимаем $\hslash(\mathsf{x})=\hslash(\mathsf{y})$ при $\mathsf{x}\neq\mathsf{y}$ и $\mathsf{x},\mathsf{y}\in\{0,1\}^*$ .

Например, если для этой цели воспользоваться схемой ЭЦП [Zhang Safavi-Naini_Susilo_2004], то для заданных сообщения и секретного ключа $\mathbf{z}$ заверитель сначала вычисляет $\phi=\hslash(g_1\|M)$ , а затем формирует подпись $\mathsf{Q}=[\frac{1}{\phi+\mathbf{z}\pmod m}]\mathsf{G}_1=[\psi]\mathsf{G}_1$ .

Пусть имеются подпись $\mathsf{Q}'=[\psi']\mathsf{G}_1$ и сообщение , такие, что $(\mathsf{Q'}\neq\mathsf{Q})\land(M'\neq M)$ . сначала вычисляет $\phi'=\hslash(g_3\|M')$ и затем $g'=e_m([\phi']\mathsf{G}_1+ \mathsf{P}, \mathsf{Q}')=e_m([\phi'+\mathbf{z}\pmod m]\mathsf{G}_1, [\psi']\mathsf{G}_1)=g^{\psi'(\phi'+\mathbf{z})\pmod m}$ . Проверяет $g'\stackrel{?}{=}e_m(\mathsf{G}_1, \mathsf{G}_1)$ и , если $(\psi'=\psi)\land(\phi'=\phi)\Rightarrow (M'=M)\land(g_3=g_1).$

Заметим, что на этапе идентификации по незащищенному каналу связи передаётся $c=\hslash(g_1)$ и для раскрытия при неизвестном секретном ключе необходимо либо вычислить $g_1=\hslash^{-1}(c)$ , либо отыскать решение некоторой вычислительно-сложностной проблемы.

Подведем итог.

не способен выполнить подлог/фальсификацию ЭЦП при известном , так как не знает $\mathbf{z}$ . Он может воспользоваться парой ключей $\{\mathbf{z}', \mathsf{P}'\}$ , где $\mathbf{z}'\neq\mathbf{z}$ , и для $\mathsf{P}'$ выпущен сертификат $\{D_{\mathsf{P}'}, \mathsf{P}', \Im_{\mathsf{P}'}\}$ , но последующая верификация покажет, что $D_{\mathsf{P}'}\neq D_{\mathsf{P}}$ .
(он же заверитель) может сформировать $\Im=\{\gamma, \delta\}$ только, если знает секрет $\mathbf{z}$ .
Проверка ЭЦП возможна только при условии положительного решения относительно response $c=\hslash(g_1)$ .

Перечислим отличительные особенности режима МЭЦП.

Режим действует в рамках текущей сессии и актуален только для .
не может убедить третью сторону в подлинности и целостности данных, полученных в ходе конкретной сессии.
МЭЦП может сформировать тот, кто знает секретный ключ $\mathbf{z}$ и способен вычислить .
Проверить МЭЦП может тот, кому известны $\mathsf{P}$ и .
Корректность МЭЦП гарантирована при условии принятого доказательства.

Режим МЭЦП идеологически близок работе [Dwork_Naor_Sahai_1998], в которой впервые была сформулирована проблема оспоримой подлинности (deniable authentication) и предложено конкретное решение.

Предположим, что удостоверился в подлинности персональных данных заверителя при помощи МЭЦП с последующей верификацией. Теперь заверитель может воспользоваться секретным ключом $\mathbf{z}$ для формирования подписи посредством произвольной конвенциональной схемы ЭЦП на основе арифметики точек эллиптической кривой или любой другой. Отметим, что эта схема может отличаться от той, которая применялась для проверки персональных данных. Такую ЭЦП имеет смысл сохранять в долговременной памяти, а для её проверки необходим действующий сертификат $\{D_{\mathsf{P}}, \mathsf{P}, \Im_{\mathsf{P}}\}$ . Это означает, что после подтверждения подлинности в режиме МЭЦП, для всех остальных данных, заверение которых осуществляется в рамках конвенциональной схемы ЭЦП, гарантируется неоспоримая подлинность (undeniable authentication). Причём без вспомогательных вычислений и дополнительных организационных издержек.

В общем случае злоумышленник не имеет доступа к персональным данным, так как они передаются и хранятся в зашифрованном виде, но может определить серийные номера сертификатов общедоступных ключей заверителей, отслеживая запросы проверяющих, например по правилам протокола OCSP (Online Certificate Status Protocol). Такой мониторинг следует расценивать как угрозу, ведь сертификаты содержат информацию, которая позволяет деанонимизировать участника. Потенциальные риски компенсируются передачей сертификатов посредством защищенного туннеля. Кроме этого, считывание сертификатов может осуществляться методом безопасного извлечения информации (Private Information Retrieval, PIR) [Chor_Goldreich_Kushilevitz_Sudan_1995, Kushilevitz_Ostrovsky_1997].

Несовместимость с произвольным протоколом

Как было показано, в режиме МЭЦП можно применить любую известную схему ЭЦП на основе арифметики точек эллиптической кривой и не только. Все протоколы идентификации состоят из полутора раундов и предусматривают передачу сообщений witness, challenge и response. Следует ответить на следующий принципиальный вопрос: режим МЭЦП возможен только для конкретного протокола идентификации или же совместим с произвольным протоколом?

Рассмотрим конкретный пример. Для этого при описании протокола идентификации Шнорра [Schnorr_1990] перейдём от подгруппы простого порядка группы $\mathbb{F}^*_p$ к подгруппе порядка группы точек эллиптической кривой.

Предварительно выбирает $\mathbf{x}\in_R\!(0, m-1]$ и формирует пару ключей $\{\mathbf{x},\mathsf{R}=[-\mathbf{x}]\mathsf{G}_1\}$ . Затем обращается к доверенной стороне за выпуском сертификата $\{D_{\mathsf{R}},\mathsf{R}, \Im_{\mathsf{R}}\}$ , где $\Im_{\mathsf{R}}\Leftarrow{\rm{Sign}}(\hslash(\mathsf{R}||D_{\mathsf{R}}), \rm{S}_T)$ и $D_{\mathsf{R}}$ — персональные данные .

Для упрощения опустим информацию о месторасположении сертификата, а также его актуализацию путем сверки со списком отозванных сертификатов.

Эллиптический протокол идентификации Шнорра

Сообщения протокола.

$P \longrightarrow V : \mathsf{S}=[\upsilon]\mathsf{G}_1$
$P \longleftarrow V : \phi$
$P \longrightarrow V : \psi=\mathbf{x}\phi+\upsilon\pmod m$

Действия сторон. доказывает , что владеет (знает) $\mathbf{x}$ . Для этого выполняются следующие действия:

выбирает ${\upsilon\in_R\!(0,m-1]}$ (commitment), вычисляет $\mathsf{S}=[\upsilon]\mathsf{G}_1$ (witness), проверяет условие $\mathsf{S}\stackrel{?}\neq\infty$ . Если $\mathsf{S}=\infty$ , то выбирает новое $\upsilon$ и заново выполняет необходимые вычисления и проверки.
считывает действующий сертификат $\{D_{\mathsf{R}},\mathsf{R}, \Im_{\mathsf{R}}\}$ и проверяет ЭЦП $\mathfrak{B}\Leftarrow{\rm{Verify}}(\hslash(\mathsf{R}||D_{\mathsf{R}}),\Im_{\mathsf{R}}, \rm{P}_T)$ . Если $\mathfrak{B}=True$ , то выбирает $\phi\in_R\!(0, m-1]$ (challenge), в противном случае сессия завершается.
проверяет условие $\phi\stackrel{?}\neq 0$ , если выполняется, то вычисляет $\psi=\mathbf{x}\phi+\upsilon\pmod m$ (response), в противном случае сессия завершается.
вычисляет $\mathsf{Q}=[\psi]\mathsf{G}_1+[\phi]\mathsf{R}=[\psi-\phi\mathbf{x}\pmod m]\mathsf{G}_1$ . Затем проверяет $x_{\mathsf{Q}}\stackrel{?}{=}x_{\mathsf{S}}$ . Если равно, то доказательство принимается, и отвергается в противном случае.

В общем случае пара ключей $\{\mathbf{z}, \mathsf{P}=[\mathbf{z}]\mathsf{G}_1]\}$ , при помощи которых формируется/проверяется ЭЦП, отличается от $\{\mathbf{x}, \mathsf{R}\}$ . Для $\mathsf{P}$ доверенная сторона также выпускает сертификат $\{D_{\mathsf{P}},\mathsf{P}, \Im_{\mathsf{P}}\}$ . Для простоты положим $D_{\mathsf{P}}=D_{\mathsf{R}}$ .

Предположим, что передаёт некоторые данные, заверенные ЭЦП. Причём ЭЦП сформирована при помощи секретного ключа $\mathbf{z}$ , а для проверки необходимо применить общедоступный ключ $\mathsf{P}$ из сертификата $\{D_{\mathsf{P}},\mathsf{P}, \Im_{\mathsf{P}}\}$ . При этом отсутствует гарантия того, что данные заверил именно , а не злоумышленник, который обманным путем вынудил сформировать ЭЦП для этих данных или получил их из открытых источников. При этом $D_{\mathsf{P}}=D_{\mathsf{R}}$ также не означает, что данные были заверены тем, кто предоставил доказательство в настоящий момент времени. Так, например, злоумышленник может навязать данные, заверенные ЭЦП, но при этом утратившие актуальность. Выше показано, что режим МЭЦП позволяет решить эту задачу. Следовательно, необходимо продемонстрировать работоспособность режима МЭЦП в протоколе идентификации Шнорра.

Заметим, что ЭЦП в этом протоколе, как впрочем и любое иное действие, «оторвана» от результатов идентификации. Действительно, если принял доказательство от , a затем заверил ЭЦП некоторые данные и отправил , то невозможно гарантировать, что в промежуток времени между фактом принятия доказательства и моментом формирования ЭЦП идентичность не претерпела принципиальных изменений в результате значимых событий. К таким событиям относится, например, отзыв сертификата $\{D_{\mathsf{R}},\mathsf{R}, \Im_{\mathsf{R}}\}$ по причине компрометации секретного ключа $\mathbf{x}$ , истечения сроков его действия и другие. В результате не сможет предоставить доказательство, а предоставленное ранее утрачивает легитимность. Промежуток времени, в течение которого происходит значимое событие, может быть сколь угодно мал, но он отличен от нуля, и поэтому проблема относится к разряду фундаментальных. Таким образом, рассуждая о режиме МЭЦП в протоколе идентификации Шнорра, необходимо следовать необоснованному предположению о пренебрежимо малой вероятности значимого события.

Отметим, что в разработанном нами протоколе идентификации значимые события также возможны, однако защищенный туннель передачи данных, который формируется только по факту доказательства, предоставляет дополнительные гарантии. Иными словами, идентификация легитимна в пределах отдельной сессии, которая завершается в результате деактуализации сессионного ключа по истечении предустановленного интервала времени, который в свою очередь регулируется положениями действующей политики безопасности.

Необходимое условие заключается в том, что response не может передаваться по незащищенному каналу связи без предварительного преобразования посредством односторонней функции. Поясним, почему это так.

Если в качестве response передавать вместо $c=\hslash(g_1)$ , то ЭЦП сможет сформировать не только , а любой, кто получил доступ к . Очевидно, что применение односторонней псевдослучайной функции в предположении модели случайного оракула (random oracle model), например, такой как $\hslash(\cdot)$ , нарушает алгебраическую структуру response в виде . Последнее означает, что проверка доказательства должна опираться на иной способ, отличный от алгебраического. Так в нашем протоколе выполняется проверка $\hslash(g_1)\stackrel{?}{=}\hslash(g_3)$ . Вычислить может только , так как знает секрет, а — только , поскольку знает challenge. Злоумышленник наблюдает и для раскрытия ему необходимо решить вычислительно-сложностную проблему или вычислить $g_1=\hslash^{-1}(c)$ .

В протоколе идентификации Шнорра response задаётся как $\psi=\mathbf{x}\phi+\upsilon\pmod m$ , а для проверки необходимо сначала вычислить точку $\mathsf{Q}=[\psi]\mathsf{G}_1+[\phi]\mathsf{R}=[\psi-\phi\mathbf{x}\pmod m]\mathsf{G}_1$ и затем проверить $x_{\mathsf{Q}}\stackrel{?}{=}x_{\mathsf{S}}$ . Понятно, что если передать $\hslash(\psi)$ вместо $\psi$ и вычислить $\mathsf{Q}'=[\hslash(\psi)]\mathsf{G}_1+[\phi]\mathsf{R}$ , то с преобладающей вероятностью $x_{\mathsf{Q}'}\neq x_{\mathsf{S}}$ . Следовательно, проверка возможна для $\psi$ , но невозможна для $\hslash(\psi)$ . Это означает, что в этом протоколе response может передаваться только в открытом виде, но тогда необходимое условие режима МЭЦП не выполняется.

Просматриваются следующие два направления будущих исследований:

Поиск/разработка протоколов идентификации, для которых необходимое условие выполняется.
Формальное доказательство того факта, что необходимое условие не выполняется для любого протокола идентификации с использованием алгебраического способа проверки доказательства.

Мы также не исключаем, что сомнению может быть подвергнуто выведенное нами доказательство свойств witness indistinguishable и whiness hiding [Feige_Shamir_1990], однако только экспертное сообщество способно подтвердить/опровергнуть это доказательство после публикации разработанного нами протокола идентификации в рецензируемом периодическом издании.

Заключение

По сравнению с конвенциональной схемой, режим МЭЦП имеет некоторые ограничения. Однако, как следует из объяснений, сами по себе конвенциональные схемы ЭЦП бесполезны с точки зрения решения поставленной задачи, так как не гарантируют, что подпись была сформирована именно тем, кто предоставил заверенные данные в настоящий момент времени.

Предположительно режим МЭЦП работоспособен только в нашем протоколе, поскольку алгебраическое уравнение используется для проверки доказательства во всех известных протоколах идентификации [Fiat_Shamir_1987, Feige_Fiat_Shamir_1988, Guillou_Quisquater_1988, Schnorr_1990, Brickell_Mccurley_1992, Okamoto_1993, Nguyen_2005]. Для всех этих протоколов необходимое условие не выполняется.

В настоящей заметке опущено доказательство криптостойкости режима МЭЦП. Это осознанный шаг, цель которого — сокращение текста одновременно с разумным его упрощением. Кроме этого, для таких рассуждений необходимо располагать детальным описанием протокола идентификации. Мы оставляем за собой право вернуться к этой теме после соответствующей публикации.

Скачать статью в pdf-формате

Список литературы

[Cohen_etc._2006] Cohen, H., Frey, G., Roberto Avanzi, R., Doche C., Lange, T., Nguyen, K. and Vercauteren, F. Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman and Hall/CRC, 2006.

[Cramer_1996] Cramer, R. “Modular Design of Secure, yet Practical Cryptographic Protocols.” PhD Thesis, University of Amsterdam, 1996.

[Babai_Moran_1988] Babai, L. and Moran, S. “Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes.” Journal of Computer and System Sciences, Volume 36, Issue 2, April (1988) 254–276.

[Schnorr_1990] Schnorr, C. P. “Efficient identification and signatures for smart cards.” Advances in Cryptology — CRYPTO’89 LNCS 435, (1990) 239–252.

[Paterson_2002] Paterson, K. G. “ID-based signatures from pairings on elliptic curves.” IEEE Electronic Letters, 38(18), (2002) 1025–1026.

[Hess_2003] Hess, F. “Efficient Identity Based Signature Schemes Based on Pairings.” Revised Papers from the 9th Annual International Workshop on Selected Areas in Cryptography — SAC’02, (2003) 310–324.

[Boneh_Shacham_Lynn_2004] Boneh, D., Shacham, H. and Lynn B. “Short Signatures from the Weil Pairing.” J. Cryptol., Vol. 17, No. 4, (2004) 297–319.

[Zhang_Safavi-Naini_Susilo_2004] Zhang, F., Safavi-Naini, R. and Susilo, W. “An efficient signature scheme from bilinear pairing and its applications.” Public Key Cryptography, LNCS 2947, (2004) 277–290.

[Boneh_Boyen_2004] Boneh, D. and Boyen, X. “Short Signatures Without Random Oracles.” EUROCRYPT 2004, LNCS 3027, (2004) 56–73.

[Chor_Goldreich_Kushilevitz_Sudan_1995] Chor, B., Goldreich, O., Kushilevitz, E. and Sudan M. “Private information retrieval.” In Proc. of the 36th IEEE Symp. on Foundations of Computer Science, (1995) 41–51.

[Kushilevitz_Ostrovsky_1997] Kushilevitz, E. and Ostrovsky, R. “Replication is not needed: Single database, computationally-private information retrieval.” In Proc. of the 38th IEEE Symp. on Foundations of Computer Science, (1997) 36–373.

[Fiat_Shamir_1987] Fiat, A. and Shamir, A. “How to prove yourself: Practical solutions to identification and signature problems.” Advances in Cryptology[ — CRYPTO’86 LNCS 263, (1987) 186–194.

[Feige_Fiat_Shamir_1988] Feige, U., Fiat, A. and Shamir, A. “Zero-knowledge Proofs of Identity.” Journal of Cryptology, 1 (1988) 77–94.

[Guillou_Quisquater_1988] Guillou, L. C. and Quisquater, J. -J. “A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory.” Advances in Cryptology — EUROCRYPT’88 LNCS 330, (1988) 123–128.

[Brickell_Mccurley_1992] Brickell, E. F. and Mccurley, K. S. “An interactive identification scheme based on discrete logarithms and factoring.” Journal of Cryptology, 5 (1992) 29–39.

[Okamoto_1993] Okamoto, T. “Provably secure and practical identification schemes and corresponding signature schemes.” Advances in Cryptology — CRYPTO’92 LNCS 740, (1993) 31–53.

[Nguyen_2005] Nguyen, L. “Accumulators from Bilinear Pairings and Applications.” In Topics in Cryptology — CT-RSA’05, LNCS 3376, (2005) 275–292.

[Dwork_Naor_Sahai_1998] Dwork, C., Naor, M. and Sahai, A. “Concurrent Zero-Knowledge.” Proc. 30th ACM Symposium on the Theory of Computing, (1998), 409–418.

[Feige_Shamir_1990] Feige, U. and Shamir, A. “Witness Indistinguishable and Witness Hiding Protocols.” In Proceedings of 22nd STOC, ACM Press, (1990) 416–426.

Tags:

Hubs:

Information Security