Как стать автором
Обновить

Анонимная идентификация для групп

Время на прочтение13 мин
Количество просмотров1.2K

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

Введение

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

Разъяснения относительно исчезающе малой вероятности (сокращённо и.м.в.), булевской переменной \mathfrak{B}и устройстве сертификатов общедоступных ключей, приводятся в опубликованной ранее статье.

В фундаментальной работе [RST'01] рассматривается следующая практическая задача. Некоторая сторона \texttt{A}, например, член кабинета министров (КМ), намеревается опубликовать компрометирующую информацию о действиях премьер-министра. С этой целью \texttt{A} обращается к \texttt{B} — журналисту независимого издания, например. При этом необходимо, с одной стороны, гарантировать анонимность источника, но убедиться в достоверности информации, — с другой. С точки зрения \texttt{B} достоверной считается та информация, которую предоставил член КМ.

Разберём возможные варианты.

  1. \texttt{A} не может передать \texttt{B} сообщение, заверенное электронной цифровой подписью (ЭЦП), так как проверка подписи приведёт к деанонимизации, поскольку персональные данные \texttt{A} будут указаны в сертификате общедоступного ключа,  при помощи которого осуществляется проверка. Хотя такой способ безусловно убедит \texttt{B} в том, что информация исходит от члена КМ.

  2. Если \texttt{A} воспользуется услугами анонимайзера, то из переданного сообщения будут удалены все идентификаторы, так или иначе указывающие на конкретного отправителя. Следовательно, \texttt{B} не сможет убедиться в том, что информация исходит от члена КМ.

В [RST'01] предложено решение, в котором каждый член КМ способен сформировать ЭЦП при помощи своего персонального секретного ключа, но проверить эту ЭЦП возможно только при помощи персональных общедоступных ключей всех членов КМ, включая самого заверителя. В результате \texttt{B} убеждается сам и может убедить третью сторону, что информация исходит от КМ, но при этом \texttt{A} остаётся неизвестным.

Мы предлагаем решение сформулированной выше задачи посредством протокола анонимной идентификации для групп. Преимущество решения в том, что помимо анонимной идентификации, \texttt{A} может передать информацию конфиденциально, воспользовавшись защищённым туннелем передачи данных. Туннель (виртуальный) доступен по построению, поскольку \texttt{A} и  \texttt{B} способны независимо сформировать общий сессионный секретный ключ по факту успешной идентификации. Конфиденциальность гарантируется применением симметричной криптографической схемы.

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

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

Протоколы анонимной идентификации для групп

Смысловое содержание используемых ниже параметров, таких как p, m, \mathbb{G}_1, \mathbb{G}_3, \mathbb{F}_m, e_m(\cdot, \cdot), объясняется в Приложение A.

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

Для 2\leqslant n<mучастников, представленных множеством нумераторов \mathcal{I}=\{1,\ldots,n,n+1,\ldots,2n\}, доверенная сторона Tформирует набор долговременных общедоступных ключей \mathcal{P}, набор персональных секретных ключей участников \mathcal{K}, а также групповой общедоступный ключ \mathsf{Q}.

  1. \widetilde{\mathcal{I}}=\mathcal{I}\setminus \{n+1\}=\{1, \ldots, n, n+2, \ldots, 2n\}, |\widetilde{\mathcal{I}}|=2n-1.

  2. \alpha\in_R\!(0,m-1].

  3. \omega\in_R\!(0,m-1], если \omega=\alpha, то выбирает другое \omega.

  4. \mathsf{P}_i=[\alpha^i\omega\pmod m]\mathsf{G}_1, \forall i\in\widetilde{\mathcal{I}} если 	\exists!_{i\in\widetilde{\mathcal{I}}}(\mathsf{P}_i=\infty), то переходит к 3.

  5. \gamma\in_R\!(0,m-1], если (\gamma=\omega)\lor(\gamma=\alpha), то выбирает другое \gamma.

  6. \mathsf{Q}=[\gamma\omega\alpha^{n+1}\pmod m]\mathsf{G}_1, если \mathsf{Q}=\infty, то переходит к 5.

  7. s_{i}=\alpha^i\gamma\pmod m, i=\overline{1,n}, если \exists!_{i\in[1,n]}(s_{i}=0), то переходит к 5.

  8. \mathcal{P}=\{\mathsf{P}_1,\ldots,\mathsf{P}_n,\mathsf{P}_{n+2},\ldots,\mathsf{P}_{2n}\}, |\mathcal{P}|=2n-1, \mathcal{K}=\{s_1,\ldots, s_n\}, |\mathcal{K}|=n.

Секретный ключ s_i\in\mathcal{K} доставляется i-му участнику способом, исключающим утечку, например, при помощи \textit{Протокола 3} из этой публикации. Для каждого общедоступного ключа из \{\mathsf{P}_1, \ldots, \mathsf{P}_n\} выпускается отдельный сертификат с указанием персональных данных владельца. Кроме этого, выпускается единый сертификат для \{\mathsf{P}_{n+2}, \ldots, \mathsf{P}_{2n}, \mathsf{Q}, n\}, который устанавливает связь компонентов этого набора с ключами из \{\mathsf{P}_1, \ldots, \mathsf{P}_n\}.

Подготовка \underline{выполняется однократно} завершается удалением \alpha, \gamma, \omega, s_i из локальной долговременной секретной памяти стороны T. В совокупности выпускается и обслуживается n+1 сертификат.

Протокол 1

Рассмотрим протокол анонимной идентификации для случая, когда V не принадлежит к группе зарегистрированных участников и \mathsf{P}_V отличен от общедоступных ключей из \mathcal{P}. Предположим, что V владеет парой ключей \{\mathbf{y},\mathsf{P}_V=[\mathbf{y}]\mathsf{G}_1\}, где {\mathbf{y}\in_R\!(0,m-1]}. Для \mathsf{P}_V выпущен сертификат \{D_V,\mathsf{P}_V, {\Im}_{\rm{T}}\}. V имеет доступ к \mathcal{S} и знает n.

Пусть в роли P выступает \ell-й участник, \ell\in\mathcal{S}, \mathcal{S}\subseteq\{1,\ldots,n\}.

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

  1. P \longrightarrow V : \mathsf{S}=[\upsilon s_\ell \pmod m]\mathsf{P}_V= [\upsilon s_\ell \mathbf{y} \pmod m]\mathsf{G}_1

  2. P \longleftarrow V :  \mathsf{T}=[\mathbf{y}^\phi\pmod m]\mathsf{P}_V=[\mathbf{y}^{\phi+1}\pmod m]\mathsf{G}_1

  3. P \longrightarrow  V  : g_a, \mathsf{R}=[s_\ell^{-1}]\mathsf{Q}=[\omega\alpha^{n+1-\ell}\pmod m]\mathsf{G}_1

Действия сторон.

P доказывает V, что знает секретный ключ s_\ell, такой, что \ell\in\mathcal{S} и \mathsf{P}_\ell\in\{\mathsf{P}_1,\ldots,\mathsf{P}_n\}. В ходе доказательства \ell, s_\ell и \mathsf{P}_\ell не раскрываются. Для этого выполняются следующие действия:

  1. P считывает актуальный сертификат \{D_V,\mathsf{P}_V, {\Im}_{\rm{T}}\} и проверяет ЭЦП доверенной стороны \rm{T}. Если \mathfrak{B}=False, то сессия завершается. Если \mathfrak{B}=True, то выбирает {\upsilon\in_R\!(0,m-1]} (\textit{commitment}), вычисляет \mathsf{S} (\textit{witness}), проверяет условие {\mathsf{S}\stackrel{?}\neq\infty}. Если \mathsf{S}=\infty, то выбирает новое \upsilon и заново выполняет необходимые вычисления и проверки.

  1. V считывает актуальный сертификат \{D_V,\mathsf{P}_V, {\Im}_{\rm{T}}\} и проверяет ЭЦП доверенной стороны \rm{T}. Если \mathfrak{B}=False, то сессия завершается. Если \mathfrak{B}=True, то выбирает {\phi\in_R\!(0, m-1]}  и вычисляет \mathsf{T} (\textit{challenge}). Если \mathsf{T}=\infty, то выбирает новое \phi и заново выполняет необходимые вычисления и проверки.

  1. P проверяет целостность, подлинность и актуальность общедоступных ключей \mathsf{P}_{n+1-j}, j\in\widetilde{\mathcal{S}}, \widetilde{\mathcal{S}}=\{\mathcal{S}\}\setminus\{\ell\}, при помощи соответствующих сертификатов, если  актуальность не подтверждена или \mathfrak{B}=False, то текущая сессия завершается. Проверяет условие \mathsf{T}\stackrel{?}\neq\infty, если выполняется, то для  \widetilde{\mathcal{S}} вычисляет \textit{response} как \{g_a=g_\ell^{-1}, \mathsf{R}\}, где

g_\ell =e_m([\upsilon s_\ell\pmod m]\mathsf{T}, \mathsf{G}_1+\sum_{j\in\widetilde{\mathcal{S}}}\mathsf{P}_{n+1-j})= g^{\upsilon\mathbf{y}^{\phi+1}\gamma(\alpha^\ell+\omega\sum_{j\in\widetilde{\mathcal{S}}}\alpha^{n+1-j+\ell})\pmod m}\text{,}

в противном случае сессия завершается;

  1. V проверяет целостность, подлинность и актуальность общедоступных ключей \mathsf{P}_{n+1-j}, j\in\mathcal{S}, при помощи соответствующих сертификатов, если  актуальность не подтверждена или \mathfrak{B}=False, то текущая сессия завершается. Проверяет условие (\mathsf{S}\neq\infty)\land((g_a\neq 1)\lor(g_a\neq g)), если не выполняется, то сессия завершается. Если выполняется, то вычисляет

g_b=e_m([\mathbf{y}^\phi\pmod m]\mathsf{S}, \mathsf{G}_1+\sum_{j\in \mathcal{S}}\mathsf{P}	_{n+1-j})=g^{\upsilon\mathbf{y}^{\phi+1}\gamma(\alpha^\ell+\omega\sum_{j\in\mathcal{S}}\alpha^{n+1-j+\ell})\pmod m}\text{,}\\g_c=g_bg_a=g^{\upsilon\mathbf{y}^{\phi+1}\gamma\omega(\sum_{j\in\mathcal{S}}\alpha^{n+1-j+\ell}-\sum_{j\in\widetilde{\mathcal{S}}}\alpha^{n+1-j+\ell})\pmod m}=g^{\upsilon\mathbf{y}^{\phi+1}\gamma\omega\alpha^{n+1}\pmod m}\text{.}

Затем проверяет g_c\stackrel{?}{=}e_m([\mathbf{y}^\phi\pmod m]\mathsf{S}, \mathsf{R}). Если равно, то доказательство принимается, и отвергается в противном случае.

В случае успешного завершения этапа идентификации стороны независимо формируют общий сессионный секретный ключ в соответствии со следующими правилами:

  1. P вычисляет \mathsf{A}=[\upsilon s_\ell\pmod m]\mathsf{T}=[\upsilon s_\ell\mathbf{y}^{\phi+1}\pmod m]\mathsf{G}_1.

  2. V вычисляет \mathsf{B}=[\mathbf{y}^\phi\pmod m]\mathsf{S}=[\mathbf{y}^{\phi+1}\upsilon s_\ell\pmod m]\mathsf{G}_1.

Протокол 2

Теперь рассмотрим вариант протокола, когда V принадлежит группе зарегистрированных участников. Тогда V владеет парой ключей \{s_c,\mathsf{P}_c\}, где c\in \widetilde{\mathcal{S}} и {s_c=\gamma\alpha^c\pmod m}, \mathsf{P}_c=[\omega\alpha^c\pmod m]\mathsf{G}_1. Для \mathsf{P}_c выпущен сертификат \{D_c,\mathsf{P}_c, \widehat{\Im}_{\rm{T}}\}.

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

  1. P \longrightarrow V : \widehat{\mathsf{S}}=[\upsilon s_\ell \pmod m]\mathsf{P}_c= [\upsilon \gamma\omega\alpha^{c+\ell}\pmod m]\mathsf{G}_1

  2. P \longleftarrow V :  \widehat{\mathsf{T}}=[\phi]\widehat{\mathsf{P}}_c=[\phi\gamma^{-1}\omega\pmod m]\mathsf{G}_1

  3. P \longrightarrow  V : \hat{g}_a, \mathsf{R}=[s_\ell^{-1}]\mathsf{Q}=[\omega\alpha^{n+1-\ell}\pmod m]\mathsf{G}_1

Действия сторон.

P доказывает V, что знает секретный ключ s_\ell, такой, что \ell\in\mathcal{S} и \mathsf{P}_\ell\in\{\mathsf{P}_1,\ldots,\mathsf{P}_n\}. В ходе доказательства \ell, s_\ell и \mathsf{P}_\ell не раскрываются. Для этого выполняются следующие действия:

  1. P считывает актуальный сертификат \{D_c,\mathsf{P}_c, \widehat{\Im}_{\rm{T}}\} и проверяет ЭЦП доверенной стороны \rm{T}. Если \mathfrak{B}=False, то сессия завершается. Если \mathfrak{B}=True, то выбирает {\upsilon\in_R\!(0,m-1]} (\textit{commitment}), вычисляет \widehat{\mathsf{S}} (\textit{witness}), проверяет условие {\widehat{\mathsf{S}}\stackrel{?}\neq\infty}. Если \widehat{\mathsf{S}}=\infty, то выбирает новое \upsilon и заново выполняет необходимые вычисления и проверки.

  2. V считывает актуальный сертификат \{D_c,\mathsf{P}_c, \widehat{\Im}_{\rm{T}}\} и проверяет ЭЦП доверенной стороны \rm{T}. Если \mathfrak{B}=False, то сессия завершается. Если \mathfrak{B}=True, то вычисляет {\widehat{\mathsf{P}}_c=[s_c^{-1}]\mathsf{P}_c=[\gamma^{-1}\omega\pmod m]\mathsf{G}_1}, выбирает {\phi\in_R\!(0, m-1]} и затем вычисляет \widehat{\mathsf{T}} (\textit{challenge}).  Если \widehat{\mathsf{T}}=\infty, то выбирает новое \phi и заново выполняет необходимые вычисления и проверки.

  3. P проверяет целостность, подлинность и актуальность общедоступных ключей \mathsf{P}_{n+1-j}, j\in\widetilde{\mathcal{S}}, \widetilde{\mathcal{S}}=\{\mathcal{S}\}\setminus\{\ell\}, при помощи соответствующих сертификатов, если  актуальность не подтверждена или \mathfrak{B}=False, то текущая сессия завершается. Проверяет условие \widehat{\mathsf{T}}\stackrel{?}\neq\infty, если выполняется, то для  \widetilde{\mathcal{S}} вычисляет \textit{response} как \{\hat{g}_a=\hat{g}_\ell^{-1}, \mathsf{R}\}, где

\hat{g}_\ell=e_m([\upsilon s_\ell\pmod m]\widehat{\mathsf{T}}, \mathsf{G}_1+	\sum_{j\in\widetilde{\mathcal{S}}}\mathsf{P}_{n+1-j})=  g^{\phi\upsilon\omega(\alpha^\ell+\omega\sum_{j\in\widetilde{\mathcal{S}}}\alpha^{n+1-j+\ell})\pmod m}	\text{,}

в противном случае сессия завершается;

  1. V проверяет целостность, подлинность и актуальность общедоступных ключей \mathsf{P}_{n+1-j}, j\in\mathcal{S}, при помощи соответствующих сертификатов, если  актуальность не подтверждена или \mathfrak{B}=False, то текущая сессия завершается. Проверяет условие (\widehat{\mathsf{S}}\neq\infty)\land((\hat{g}_a\neq 1)\lor(\hat{g}_a\neq g)), если не выполняется, то сессия завершается. Если выполняется, то вычисляет

\hat{g}_b=e_m([\phi s_c^{-1}\pmod m]\widehat{\mathsf{S}}, \mathsf{G}_1+\sum_{j\in \mathcal{S}}	\mathsf{P}_{n+1-j})=g^{\phi\upsilon\omega(\alpha^\ell+\omega\sum_{j\in\mathcal{S}}\alpha^{n+1-j+\ell})\pmod m}\text{,}\\\hat{g}_c=\hat{g}_b\hat{g}_a=g^{\phi\upsilon\omega^2(\sum_{j\in\mathcal{S}}\alpha^{n+1-j+\ell}-	\sum_{j\in\widetilde{\mathcal{S}}}\alpha^{n+1-j+\ell})\pmod m}=g^{\phi\upsilon\omega^2\alpha^{n+1}\pmod m}\text{.}

Затем проверяет \hat{g}_c\stackrel{?}{=}e_m([\phi s_c^{-1}\pmod m]\widehat{\mathsf{S}}, \mathsf{R}). Если равно, то доказательство принимается, и отвергается в противном случае.

В случае успешного завершения этапа идентификации стороны независимо формируют общий сессионный секретный ключ в соответствии со следующими правилами:

  1. P вычисляет \mathsf{A}=[\upsilon s_\ell\pmod m]\widehat{\mathsf{T}}=[\phi\upsilon\alpha^\ell\omega\pmod m]\mathsf{G}_1.

  2. V вычисляет \mathsf{B}=[\phi s_c^{-1}\pmod m]\widehat{\mathsf{S}}=[\phi\upsilon\alpha^\ell\omega\pmod m]\mathsf{G}_1.

Криптостойкость ключей

Идея в том, что для общедоступного ключа \mathsf{P}_i выполняется маскировка при помощи \omega, тогда как  в случае секретного ключа s_i такая маскировка выполняется при помощи \gamma, где {\gamma, \omega\in_R\!(0,m-1]} и \gamma\neq\omega\neq\alpha по построению. Это означает, что трудоёмкость раскрытия всех s_i при известном решении ECDLP/DLP для общедоступного ключа из \mathcal{P}, а также известном секретном ключе из \mathcal{K}, не ниже трудоёмкости отыскания решения ECDLP/DLP.

Рассмотрим частный случай. Предположим, что известны s_1=\gamma\alpha\pmod m и \varphi_1=\alpha\omega\pmod m — решение ECDLP/DLP при условии \mathsf{P}_1 или e_m(\mathsf{P}_1, \mathsf{G}_1). Тогда \alpha={\varphi_1\omega^{-1}\pmod m}=s_1\gamma^{-1}\pmod m, \omega={\varphi_1\alpha^{-1}\pmod m}, \gamma=s_1\alpha^{-1}\pmod m и \psi={s_1\varphi_1^{-1}\pmod m}=\gamma\omega^{-1}\pmod m, \psi'=s_1^{-1}\varphi_1\pmod m=\gamma^{-1}\omega\pmod m. Следовательно, если известны \varphi_1 и s_1, то для раскрытия всех s_i, 2\leqslant i\leqslant n, достаточно найти \alpha\lor\gamma\lor\omega.

Атакующий располагает дополнительными возможностями. Пусть известны s_u и \varphi_u, такие, что u=2^{2^w}, u\in[2,n], 0\leqslant w\leqslant\lfloor\log_2{\log_2{n}}\rfloor. Мотивация атакующего заключается в том, что при известном \varphi_u и u>2 (при u=2 квадратный корень вычисляется однократно) можно раскрыть \alpha при помощи итеративного метода извлечения квадратного корня по алгоритму Tonelli-Shanks асимптотической трудоёмкости O((\log_{2}{m})^2)  [C'06] (раздел 11.1.5). Например, при известном \omega, \alpha=\sqrt{\cdots\sqrt{\varphi_u\omega^{-1}\pmod m}} и \gamma={s_u\varphi_u^{-1}\omega\pmod m}. В общем случае неизвестно, как вычислить корень произвольной степени в \mathbb{F}_m^*.

Алгоритмы силовой атаки для некоторых \varphi_u, s_u представлены в Приложении C. Лобовая атака (Алгоритм 1) не оптимальна, так как в среднем потребуется выполнить M/2 опробований, где M=m-1.

Предположим, что задано число \mathsf{a}, такое, что \mathsf{a}\equiv\varphi_u\pmod m, и известно каноническое разложение \mathsf{a}=\prod_{j=1}^t\mathsf{p}_j^{r_j}, \mathsf{p}_j — различные простые, {r_j,t\in\mathbb{N}}, которое можно получить при помощи факторизации \mathsf{a}, например, методом  \textit{решета числового поля} или иным известным методом [I'11]. Пусть задано множество \mathcal{D}=\{\mathsf{p}_1^{r_1}, \ldots, \mathsf{p}_t^{r_t}\}. Если все r_j известны, то справедливо представление:

\widehat{\mathcal{D}}=\{\underbrace{\mathsf{p}^{\mathstrut}_1,\ldots,\mathsf{p}^{\mathstrut}_1}_{r_1}, \ldots, \underbrace{\mathsf{p}^{\mathstrut}_t, \ldots, \mathsf{p}^{\mathstrut}_t}_{r_t}\}, |\widehat{\mathcal{D}}|=\sum_{j=1}^t r_j=d.

Пронумеруем простые числа из \widehat{\mathcal{D}} натуральными числами от 1 до d и перейдём к множеству \widetilde{\mathcal{D}}=\{\tilde{\mathsf{p}}^{\mathstrut}_1, \ldots, \tilde{\mathsf{p}}^{\mathstrut}_d\}.

Оценим трудоёмкость оптимизированной силовой атаки (Алгоритм 2). В атаке задействована вспомогательная последовательность \mathbf{b}=(b_1, \ldots, b_d),  b_j\in\{0,1\}. Вес Хэмминга \mathbf{b} изменяется в диапазоне от 1 до \lceil d/2 \rceil и количество опробований ограничено сверху величиной

A=\sum_{j=1}^{\lceil d/2 \rceil}C_d^j.  \hspace{3.5cm}\text{(1)}                

В среднем для отыскания \alpha, \omega, \gamma потребуется выполнить A/2 опробований.

Предположим, что \alpha=\tilde{\mathsf{p}}_{1}^{\mathsf{x}}\pmod m и \omega=\tilde{\mathsf{p}}_{2}^{\mathsf{y}}\pmod m, \mathsf{x}, \mathsf{y}\in\mathbb{N}. Напомним, что по построению \alpha\neq\omega и тогда возможны следующие варианты:

  1. \tilde{\mathsf{p}}_{1}=\tilde{\mathsf{p}}_{2} \Rightarrow ((\mathsf{x}\geqslant 1)\land(\mathsf{y}\geqslant \mathsf{x}+1))\lor((\mathsf{y}\geqslant 1)\land(\mathsf{x}\geqslant \mathsf{y}+1))

  2. \tilde{\mathsf{p}}_{1}\neq\tilde{\mathsf{p}}_{2} \Rightarrow (\mathsf{x}\geqslant 1)\land(\mathsf{y}\geqslant 1).

Обозначим через \pi(M) количество простых чисел в диапазоне [1, M]. Согласно оценке Чебышева:

{0,92\times\frac{M}{\ln M}<\pi(M)<1,06\times\frac{M}{\ln M}}.

Следовательно, 2<d\leqslant\pi(M). Общеизвестно, что \sum_{j=0}^d C_d^j=2^d,

но в (1) суммируется около половины всех возможных биномиальных коэффициентов и поэтому A<2^d. Следовательно, \forall_{d\leqslant\lceil \log_2{M}\rceil}A<M.

При \alpha, \omega\in_R\!(0,m-1] мощность множества \widetilde{\mathcal{D}} не поддаётся регулированию. В результате d может быть невелико и трудоёмкость силовой атаки, а именно количество опробований A, не обеспечит необходимого уровня криптостойкости.

Для исправления положения поступим следующим образом. Пусть на этапе подготовки доверенная сторона T случайно выбирает d\leqslant \pi(M) различных простых чисел из диапазона [1, M] и формирует множество \widetilde{\mathcal{D}}. Проверка на простоту выполняется при помощи теста из [AKS'04]. Например, если m\sim 2^{160}, то 1,2\times10^{46} < \pi(M) < 1,4\times10^{46}. Затем T формирует случайную двоичную последовательность \mathbf{b} веса Хэмминга \lceil d/2 \rceil, где b_j\in_R\!\{0, 1\}, и для заданного \widetilde{\mathcal{D}} вычисляет:

\alpha=\prod_{j=1}^d\tilde{\mathsf{p}}_j^{b_j}\pmod m  \text{ и }   \omega=\prod_{j=1}^d\tilde{\mathsf{p}}_j^{\bar{b}_j}\pmod m, \forall_{j\in[1,d]}\bar{b}_j=b_j\oplus 1.

Теперь трудоёмкость рассмотренной выше силовой атаки ограничена сверху гарантированной величиной B=C_d^{\lceil d/2 \rceil} и 2^d>A>B\geqslant\frac{2^d}{d+1}.

В общем виде C_d^{[ad]}=\left(\frac{1}{a^a(1-a)^{1-a}}+o(1)\right)^d,

где a\in(0,1), o(1) — некоторая функция, которая по модулю стремится к нулю, но при этом может принимать как отрицательные, так и положительные значения. При a=1/2 получаем B=(2+o(1))^d. Например, для обеспечения 80-битного уровня криптостойкости и выше следует выбрать d\geqslant84.

Отыскание \alpha\lor\omega\lor\gamma при условии \widetilde{\mathcal{D}} по трудоёмкости эквивалентно известной NP-полной задаче Subset Product [GJ'79] (SP14, c. 224) или, по-другому, Произведение Размеров [GJ'82] (МР 14, с. 283). NP-полнота доказана сведением к этой задаче другой NP-полной задачи, известной как Точное Покрытие 3-Множествами [GJ'82] (ТП-3, с. 73). Заметим, что MP 14 — задача с числовыми параметрами и NP-полнота не исключает решения этой задачи при помощи алгоритма псевдополиномиальной временной трудоёмкости при условии P\neq NP [GJ'82] (раздел 4.2 на с. 117, комментарий к MP 14 на с. 283), которая зависит от d и \max(\tilde{\mathsf{p}}_1, \ldots, \tilde{\mathsf{p}}_d). Очевидно, что существование алгоритма такой трудоёмкости предоставляет атакующему дополнительные возможности. Однако, этот недостаток устраняется, если T выбирает d простых чисел из диапазона [\lceil\sqrt{\mathstrut{m}}\rceil, M], а величина d такова, что позволяет компенсировать снижение криптостойкости по причине существования  алгоритма псевдополиномиальной трудоёмкости. Величина d ограничена снизу уровнем криптостойкости. Тогда сторона T может выбрать сколь угодно большое d при соблюдении заданного уровня криптостойкости как необходимого условия. Множество \widetilde{\mathcal{D}} формируется однократно на этапе подготовки и его мощность, а также разрядность простых чисел в него входящих, не влияет на рабочие характеристики протокола идентификации. Количество простых в упомянутом диапазоне по порядку величины не отличается от \pi(M). При 80-битной криптостойкости разрядность простых чисел будет варьироваться от 80 до 160 бит.

Алгоритм Гровера [G'96] позволяет отыскать \alpha\lor\omega\lor\gamma при условии \widetilde{\mathcal{D}} за O(\sqrt{B}) опробований на квантовом компьютере с O(d) кубитами. Если силовая атака на квантовом компьютере представляется реалистичной, то следует выбирать величину d так, чтобы компенсировать снижение криптостойкости в результате применения алгоритма Гровера. Например, уровень криптостойкости от 80 бит включительно и выше обеспечивается при d\geqslant 164.

В [S'97] показано, что на квантовом компьютере трудоёмкость таких трудноразрешимых задач как факторизация, DLP, а также ECDLP по причине существования билинейного отображения e_m:\mathbb{G}_1\times \mathbb{G}_1\mapsto \mathbb{G}_3, ограничена некоторым полиномом от размера входа. 

Отметим, что множество \widetilde{\mathcal{D}} предназначено исключительно для получения \alpha, \omega, на основании которых затем вычисляются  \mathsf{P}_i, s_i. По завершении всех необходимых вычислений сторона T удаляет \widetilde{\mathcal{D}} из локальной долговременной памяти.

Почему это работает

Отметим, что в основу протокола анонимной групповой идентификации легли идеи работы [BGW'05]. 

Разъясним содержательную часть. Обратим внимание на поведение функции {\eta=n+1-j+\ell}, которая присутствует в показателе степени \alpha при вычислении g_\ell и g_b, а также \hat{g}_\ell и \hat{g}_b.

Функция \eta непрерывна и для анализа достаточно предъявить Таблицу 1 значений для некоторых нумераторов из целочисленного интервала  [1, n].

Пусть \mathcal{S}=\{1,\ldots,n\}, \ell\in \mathcal{S} и \widetilde{\mathcal{S}}=\{\mathcal{S}\}\setminus\{\ell\}. Из Таблицы 1 следует, что \eta=n+1 располагается на главной диагонали и удовлетворяет условию j=\ell. По построению \ell\neq 0 и поэтому \eta\in[2,2n]. Поскольку в \widetilde{\mathcal{S}} отсутствует \ell-й нумератор, но с другой стороны, в \mathcal{S} присутствует нумератор j=\ell, то:

\sum_{j\in \mathcal{S}}\alpha^{n+1-j+\ell}-\sum_{j\in\widetilde{\mathcal{S}}}\alpha^{n+1-j+\ell}=\alpha^{n+1}.

В \mathcal{S} неубывающий порядок нумераторов выбран в целях упрощения объяснений. Отметим, что протокол инвариантен относительно такого порядка. Кроме этого, протокол корректно работает с подмножеством \mathcal{S}_\wp\subset\mathcal{S}. Асимптотическая оценка количества таких подмножеств —  O(2^n). Причём наборы нумераторов в этих подмножествах могут как пересекаться, так и нет.

Пример

Предположим \mathcal{S}=\{1,2,3,\ldots,8,9,10\} и (n+1)=11. Имеется некоторое подмножество {\mathcal{S}_\wp\subset\mathcal{S}}, такое, что \mathcal{S}_\wp=\{3,7,5,8,4,2\}. Пусть \ell=7, тогда \widetilde{\mathcal{S}}_\wp=\{3,5,8,4,2\}. Следовательно,


\sum_{j\in\mathcal{S}_\wp}\alpha^{n+1-j+\ell}-\sum_{j\in\widetilde{\mathcal{S}_\wp}}\alpha^{n+1-j+\ell}=

\alpha^{11-3+7}+

\alpha^{11-7+7}+

\alpha^{11-5+7}+

\alpha^{11-8+7}+

\alpha^{11-4+7}+

\alpha^{11-2+7}-

\alpha^{11-3+7}-

\alpha^{11-5+7}-

\alpha^{11-8+7}-

\alpha^{11-4+7}-

\alpha^{11-2+7}=\alpha^{11}.

Предварительный анализ

Предположим, что атакующему известно \ell и \varphi_\ell — решение ECDLP/DLP при условии \mathsf{P}_\ell или e_m(\mathsf{P}_\ell, \mathsf{G}_1). Тогда в \textbf{Протоколе 1} атакующий от лица P вычисляет \textit{witness} как \mathsf{S}'={[\upsilon \varphi_\ell \pmod m]\mathsf{P}_V}= [\upsilon\alpha^\ell\omega \mathbf{y}\pmod m] \mathsf{G}_1. Кроме этого, P вычисляет \textit{response} как

\{\acute{g}_a=\acute{g}_\ell^{-1}, \mathsf{R}'=[\varphi_\ell^{-1}]\mathsf{Q}=[\gamma\alpha^{n+1-\ell}\pmod m]\mathsf{G}_1\}, где

\acute{g}_\ell=e_m([\upsilon \varphi_\ell\pmod m] \mathsf{T},  \mathsf{G}_1+\sum_{j\in\widetilde{ \mathcal{S}}} \mathsf{P}_{n+1-j})=  g^{\upsilon\mathbf{y}^{\phi+1}\omega(\alpha^\ell+\omega\sum_{j\in\widetilde{ \mathcal{S}}}\alpha^{n+1-j+\ell})\pmod m}\text{.}

В свою очередь V вычисляет

\acute{g}_b=e_m([\mathbf{y}^\phi\pmod m] \mathsf{S}',  \mathsf{G}_1+\sum_{j\in \mathcal{S}} \mathsf{P}_{n+1-j})=g^{\upsilon\mathbf{y}^{\phi+1}\omega(\alpha^\ell+\omega\sum_{j\in \mathcal{S}}\alpha^{n+1-j+\ell})\pmod m}\text{,}\\\acute{g}_c=\acute{g}_b\acute{g}_a=g^{\upsilon\mathbf{y}^{\phi+1}\omega^2(\sum_{j\in \mathcal{S}}\alpha^{n+1-j+\ell}-\sum_{j\in\widetilde{ \mathcal{S}}}	\alpha^{n+1-j+\ell})\pmod m}=g^{\upsilon\mathbf{y}^{\phi+1}\omega^2\alpha^{n+1}\pmod m}\text{.}

Следовательно, \grave{g}=e_m([\mathbf{y}^\phi\pmod m] \mathsf{S}',  \mathsf{R}')=g^{\upsilon\mathbf{y}^{\phi+1}\omega\gamma\alpha^{n+1}\pmod m} и \acute{g}_c=\grave{g} с и.м.в.

Для того, чтобы обмануть проверяющего, атакующий должен раскрыть \gamma и \omega, тогда

\mathsf{R}'={[\gamma^{-1}\omega\varphi_\ell^{-1}\pmod m]\mathsf{Q}}=[\omega\alpha^{n+1-\ell}\pmod m]\mathsf{G}_1и \acute{g}_c=\grave{g}.

Для \textbf{Протокола 2} \textit{witness} и \textit{response} вычисляются как \widehat{\mathsf{S}}'=[\upsilon\varphi_\ell \pmod m]\mathsf{P}_c= {[\upsilon\omega^2\alpha^{c+\ell}\pmod m] \mathsf{G}_1} и \{\check{g}_a=\check{g}_\ell^{-1}, \mathsf{R}'=[\varphi_\ell^{-1}]\mathsf{Q}=[\gamma\alpha^{n+1-\ell}\pmod m]\mathsf{G}_1\} соответственно, где

\check{g}\ell=e_m([\upsilon \varphi\ell\pmod m]\widehat{ \mathsf{T}},  \mathsf{G}1+\sum{j\in\widetilde{ \mathcal{S}}} \mathsf{P}_{n+1-j})=  g^{\phi\upsilon\gamma^{-1}\omega^2(\alpha^\ell+\omega\sum_{j\in\widetilde{ \mathcal{S}}}\alpha^{n+1-j+\ell})\pmod m}\text{.}

V вычисляет

\check{g}_b=e_m([\phi s_c^{-1}\pmod m]\widehat{ \mathsf{S}}',  \mathsf{G}_1+\sum_{j\in \mathcal{S}} \mathsf{P}_{n+1-j})=g^{\phi\upsilon\gamma^{-1}\omega^2(\alpha^\ell+\omega\sum_{j\in \mathcal{S}}\alpha^{n+1-j+	\ell})\pmod m}\text{,}\\\check{g}_c=\check{g}_b\check{g}_a=g^{\phi\upsilon\gamma^{-1}\omega^3(\sum_{j\in \mathcal{S}}\alpha^{n+1-j+\ell}-\sum_{j\in\widetilde{ \mathcal{S}}}	\alpha^{n+1-j+\ell})\pmod m}=g^{\phi\upsilon\gamma^{-1}\omega^3\alpha^{n+1}\pmod m}\text{.}

Следовательно, \bar{g}=e_m([\phi s_c^{-1}\pmod m]\widehat{ \mathsf{S}}',  \mathsf{R}')=g^{\phi\upsilon\omega^2\alpha^{n+1}\pmod m} и \check{g}_c=\bar{g} с и.м.в.

Для того, чтобы обмануть проверяющего, атакующий должен раскрыть \gamma и \omega, тогда

\mathsf{R}'={[\gamma^{-1}\omega\varphi_\ell^{-1}\pmod m]\mathsf{Q}}=[\omega\alpha^{n+1-\ell}\pmod m]\mathsf{G}_1 и \check{g}_c=\bar{g}.

Напомним, что для раскрытия \gamma и \omega необходимо отыскать решение конкретной NP-полной задачи при условии известных \varphi_u и s_u.

Пусть фиктивный проверяющий V' владеет парой ключей \{\mathbf{\acute{y}},\mathsf{P}_{V'}=[\mathbf{\acute{y}}]\mathsf{G}_1\}. Рассмотрим потенциальные риски, связанные с имперсонификацией проверяющего, а именно замены V на V'.

Протокол 1

Для имперсонификации проверяющего необходимо отыскать решение ECDLP/DLP при условии \mathsf{P}_V или e_m(\mathsf{P}_V, \mathsf{G}_1). Тогда  \mathsf{S}'=[\mathbf{y}^{-1}\mathbf{\acute{y}}\pmod m]\mathsf{S}={[\upsilon s_\ell\pmod m]\mathsf{P}_{V'}}. Связь между ECDLP и DLP объясняется в Приложении A.

Предположим, что упомянутое выше решение ECDLP/DLP не известно. Однако, атакующий имеет доступ к \mathsf{P}_{V'} и способен вместо \mathsf{T} навязать \mathsf{T}'=[\phi']\mathsf{P}_{V'}, а также вместо  \mathsf{S} навязать некоторое \mathsf{S}'=[\upsilon']\mathsf{P}_{V'}, при этом \phi'=\mathbf{y}^\phi\pmod m и \upsilon'=\upsilon s_\ell\pmod m c и.м.в. Тогда P вычисляет \textit{response} как \acute{g}_a=\acute{g}_\ell^{-1}, \mathsf{R}, где

\acute{g}_\ell=e_m([\upsilon s_\ell\pmod m] \mathsf{T}',  \mathsf{G}_1+\sum_{j\in\widetilde{ \mathcal{S}}} \mathsf{P}_{n+1-j})=  g^{\phi'\upsilon\gamma\acute{\mathbf{y}}(\alpha^\ell+\omega\sum_{j\in\widetilde{ \mathcal{S}}}\alpha^{n+1-j+\ell})\pmod m}\text{.}

V' вычисляет 

\acute{g}_b=e_m([\phi'\pmod m] \mathsf{S}',  \mathsf{G}_1+\sum_{j\in \mathcal{S}} \mathsf{P}_{n+1-j})=g^{\phi'\upsilon'\acute{\mathbf{y}}(1+\omega\sum_{j\in \mathcal{S}}\alpha^{n+1-j})\pmod m}

и \acute{g}_c=\acute{g}_a\acute{g}_b. Очевидно, что \acute{g}_c=g_c и \acute{g}_c=e_m([\phi'] \mathsf{S}',  \mathsf{R}) с и.м.в.

Допустим, что атакующий навязывает \widetilde{\mathsf{T}} = [\phi']\mathsf{P}_V, но при этом отсутствует подмена \mathsf{S}, тогда  

	\acute{g}_b=e_m([\phi'\pmod m] \mathsf{S},  \mathsf{G}_1+\sum_{j\in \mathcal{S}} \mathsf{P}	_{n+1-j})=g^{\phi'\upsilon\gamma\mathbf{y}(\alpha^\ell+\omega\sum_{j\in \mathcal{S}}\alpha^{n+1-j+\ell})\pmod m}\text{,}\\

\acute{g}_c=\acute{g}_b\acute{g}_a=g^{\phi'\upsilon\mathbf{y}\gamma\omega(\sum_{j\in \mathcal{S}}	\alpha^{n+1-j+\ell}-\sum_{j\in\widetilde{ \mathcal{S}}}	\alpha^{n+1-j+\ell})\pmod m}=g^{\phi'\upsilon\gamma\mathbf{y}\omega\alpha^{n+1}\pmod m}.

Если финальную проверку выполняет V, то \acute{g}_c=e_m([\mathbf{y}^{\phi}\pmod m] \mathsf{S},  \mathsf{R}) с и.м.в. Если такую проверку выполняет тот, кто знает \phi', например V', то \acute{g}_c=e_m([\phi'] \mathsf{S},  \mathsf{R}). Однако, несмотря на то, что доказательство принимается V', имперсонификации не происходит, так как отсутствует подмена V.

Далее P вычисляет \mathsf{A}'=[\upsilon s_\ell\pmod m]\mathsf{T}'=[\upsilon s_\ell\mathbf{y}\phi'\pmod m]\mathsf{G}_1 и V вычисляет \mathsf{B}=[\mathbf{y}^{\phi}\pmod m]\mathsf{S}=[\mathbf{y}^{\phi+1}\upsilon s_\ell\pmod m]\mathsf{G}_1.

Следовательно, \mathsf{A}=\mathsf{B}' с и.м.в.

V' не сможет раскрыть сессионный секретный ключ, так как для этого надо знать \mathbf{y}. Однако, V' знает \acute{\mathbf{y}} и может вычислить \mathsf{B}'=[\acute{\mathbf{y}}\phi'\pmod m]\mathsf{S}=[\acute{\mathbf{y}}\phi'\upsilon s_\ell\pmod m]\mathsf{G}_1, но поскольку \acute{\mathbf{y}}=\mathbf{y} с и.м.в., то \mathsf{A}'=\mathsf{B}' с и.м.в.

Протокол 2

Предположим {\varphi_c=\omega\alpha^c\pmod m} — решение ECDLP/DLP при условии \mathsf{P}_c или e_m(\mathsf{P}_c, \mathsf{G}_1). Тогда \widehat{\mathsf{S}}'=[\varphi_c^{-1}\acute{\mathbf{y}}\pmod m]\widehat{\mathsf{S}}=[\upsilon s_\ell\pmod m]\mathsf{P}_{V'}, но для вычисления \widehat{\mathsf{T}}'=[\phi'\gamma\omega^{-1} \acute{\mathbf{y}}\pmod m]\widehat{\mathsf{P}}_c=[\phi']\mathsf{P}_{V'}, где \phi'=\phi с и.м.в., необходимо знать \gamma и \omega, однако, как показано выше, для их раскрытия необходимо решить конкретную NP-полную задачу при условии известных \varphi_u и s_u.

В свете представленного разъяснения дальнейшие рассуждения относительно имперсонификации не имеют смысла.

Количество передаваемой информации

Если применяется компактное представление, то  для доставки \mathsf{S}, \mathsf{T}, \mathsf{R}, g_a в \textbf{Протоколе 1}, а также \widehat{\mathsf{S}}, \widehat{\mathsf{T}}, \mathsf{R}, \hat{g}_a в \textbf{Протоколе 2}, потребуется передать 3(\lceil\log_{2}{p}\rceil+1)+ k\lceil\log_{2}{p}\rceil+\lambda бит, где \lambda — разрядность двоичного представления серийных номеров сертификатов \{D_V,\mathsf{P}_V, \Im_{\rm{T}}\} и \{D_c,\mathsf{P}_c, \widehat{\Im}_{\rm{T}}\}, а k — степень вложения (g_a, \hat{g}_a\in\mathbb{G}_3). Объяснения относительно степени вложения представлены в Приложении A.

Если задействовано некоторое случайное подмножество \mathcal{S}_\wp\subseteq\mathcal{S}, то необходимо уведомить V о нумераторах, входящих в это подмножество. Для этого P должен дополнительно передать R(n) бит информации, где

Когда передаётся n бит, то нумераторы из \mathcal{S}_\wp соответствуют позициям, на которых расположены единицы.

С другой стороны, разумно оценивать количество информации, необходимое для передачи только сообщений протокола, поскольку для большинства практических приложений, несмотря на то, что V должен знать, какие нумераторы входят в \mathcal{S}_\wp\subseteq\mathcal{S}, и, следовательно, каким-то образом получить соответствующую информацию, это подмножество либо зафиксировано, либо медленно изменяется с течением времени. Следовательно, информацию о нумераторах достаточно передать однократно. При оценке можно пренебречь количеством информации, которое нужно передать для модификации такого медленно меняющегося подмножества.

Вычислительная оптимизация

В ряде практических приложений  \mathcal{S} фиксируется. Например, когда некоторые наборы общедоступных ключей, при помощи которых осуществляется проверка, закрепляются за отдельными структурными подразделениями корпорации или госучреждения. В этом случае не нужно каждый раз сообщать нумераторы из  \mathcal{S}, так как набор необходимых общедоступных ключей определён заранее.

Если зафиксировать \mathcal{S}, то можно заблаговременно подтвердить подлинность, целостность и актуальность общедоступных ключей  \mathsf{P}_{n+1-j}, j\in\mathcal{S} при помощи соответствующих сертификатов, а затем вычислить и опубликовать точку:

 \mathsf{M}=\sum_{j\in \mathcal{S}} \mathsf{P}_{n+1-j}

Тогда \ell-й доказывающий заранее вычисляет точку:

\mathsf{K}_\ell=\sum_{j\in\widetilde{ \mathcal{S}}} \mathsf{P}_{n+1-j}

и сохраняет в локальной долговременной секретной памяти.

Если предположить, что инициируется \textbf{Протокол 1}, то в случае \ell-го доказывающего P вычисляет g_\ell={e_m([\upsilon s_\ell\pmod m] \mathsf{T}, \mathsf{G}_1+ \mathsf{K}_\ell)} и V вычисляет g_b={e_m([\mathbf{y}^\phi\pmod m]\mathsf{S}, \mathsf{G}_1+\mathsf{M})}.

Оптимизация актуальна как для \textbf{Протокола 1}, так и \textbf{Протокола 2}.

Если V всегда принадлежит группе зарегистрированных участников и инициируется \textbf{Протокол 2}, то возможна оптимизация, которая опирается на следующее обоснование.

Степень вложения k, а также характеристика поля p, определяют трудоёмкость DLP в \mathbb{G}_3. При фиксированном p, чем больше k, тем выше трудоёмкость отдельного спаривания, а также различных арифметических операций в \mathbb{G}_3, включая дискретное экспоненциирование и мультипликативное обращение. Поскольку для \textbf{Протокола 2} субэкспоненциальная трудоёмкость отыскания решения DLP не является критической, то разумно снизить трудоёмкость арифметических операций, а также сократить ресурс памяти за счёт использования малых значений k.

Выводы

В отношении криптостойкости ключей, \textbf{Протокол 1} и \textbf{Протокол 2} предположительно согласуются с основным императивом \textit{постквантовой криптографии}, где обоснование криптостойкости заключается в доказательстве того, что атака на криптосистему состоит в отыскании решения некоторой задачи гипотетически трудноразрешимой на квантовом компьютере. NP-полные задачи при условии P\neq NP в полной мере отвечают этому положению.

Поскольку решение ECDLP/DLP для произвольного общедоступного ключа из \mathcal{P} не позволяет раскрыть соответствующий секретный ключ по причине специальных приёмов маскировки, мы предположили, что кроме решения \varphi_u, также известен секретный ключ s_u. Показано, что даже при таких допущениях для раскрытия всех остальных секретных ключей необходимо отыскать решение конкретной NP-полной задачи.

Подчеркнем, что выбор чисел u=2^{2^w}, u\in[2,n], ограничен. Таких чисел мало, например, если положить n=2^{16}, то доступны числа из набора \{2, 2^2, 2^4, 2^8, 2^{16}\}. Расширение этого набора маловероятно, так как группы с числом участников n=2^{32} и более редко встречаются на практике. Следовательно, возможности атакующего также ограничены.

Следует отметить, что \textbf{Протокол 1} допускает имперсонификацию при известном решении ECDLP/DLP. Это объясняется тем, что ключи проверяющего, секретный и общедоступный, не имеют дополнительной маскировки, в отличие от ключей, которые задействованы в  \textbf{Протоколе 2}.

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

Заключение

Сконструированы и исследованы МЭЦП-совместимые протоколы анонимной идентификации для групп. Показано, что криптостойкость ключей определяется трудоёмкостью отыскания решения конкретной NP-полной задачи.

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

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

[RST'01] Rivest, Ronald L., Shamir, A., Tauman, Y. "How to leak a secret: Theory and applications of ring signatures." In \textit{Advances in Cryptology — ASIACRYPT'01}, LNCS 3895, (2001) 164-186.

[C'06] Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., Vercauteren, F. \textit{Handbook of Elliptic and Hyperelliptic Curve Cryptography}, Chapman and Hall/CRC, 2006.

[AKS'04] Agrawal, M., Kayal, N., Saxena, N. "PRIMES is in P." \textit{Annals of Mathematics}, v.160, (2004) 781-793.

[I'11] Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие. — Казань: Казан. ун-т, 2011. 200 с.

[GJ'79] Garey, M. R.  and  Johnson, D. S. A Guide to the Theory of NP-Completeness. W. H. Freeman&Co., New York, NY, 1979.

[GJ'82] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

[G'96] Grover, L. "A fast quantum mechanical algorithm for database search." Proceedings of  \textit{28th Annual ACM Symposium on the Theory of Computing (STOC)}, (1996) 212-219. https://arxiv.org/abs/quant-ph/9605043.

[S'97] Shor, Peter W. "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer." \textit{SIAM Journal on Computing}, v.26, 5, (1997) 1484-1509.

[BGW'05] Boneh, D., Gentry, C. and Waters, B.  "Collusion Resistant Broadcast Encryption With Short Ciphertexts and Private Keys." In \textit{Proceedings of Crypto 2005}, LNCS 3621, (2005) 258-275.

Теги:
Хабы:
+2
Комментарии8

Публикации

Истории

Работа

Ближайшие события