20.09.2023 15:53
ENCRY 8 804 Источник

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

Введение

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

Разъяснения относительно исчезающе малой вероятности (сокращённо и.м.в.), булевской переменной \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-полной задаче \textit{Subset Product} [GJ'79] (SP14, c. 224) или, по-другому,  \textit{Произведение Размеров} [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.

Комментарии (8)


  1. MAXH0
    20.09.2023 16:29
    #25983654

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

    Как я понимаю это скорее не подпись для Кабинета Министров, а для ячейки Ананимусов. Когда важно показать групповую принадлежность не показывая конкретный источник.


  1. AndrChm
    20.09.2023 16:29
    #25983688

    Когда важно показать групповую принадлежность не показывая конкретный источник.

    По сути так и есть. Но при этом решается заявленная во Введении задача. Только иным, до селе неизвестным, способом. Чтобы что-то понять надо не бояться задавать вопросы. Но в начале лучше подумать. С такими результатами надо разбираться. Здесь такие тексты обычно не публикуют, так как они требуют подготовки иного уровня.


    1. MAXH0
      20.09.2023 16:29
      #25983914

      Как я понял Вы ответили мне, только в общую ветку. Тогда я Вам отвечу...
      Я, конечно, ничего не понял. Но мне, реально, и не надо. Приведено доказательство. Если его подтвердят, то можно уже будет писать код на C, а затем на Python и вот уже на готовых библиотеках будут писаться программы. Но только когда до пользователя дойдет экосистема - это начнет работать.

      А теперь позвольте небольшой не оффтоп, а вбоквел, вызванный статьёй...
      Когда-то давно, я прочитал в КомпьюТерре спецвыпуск о PGP и тема меня заинтересовала. Потом мне попалась книга про Веб-Мани (помните такие фантики?) и я осознал, что в принципе это реализация тех подписей, что описаны в КомпьюТерре, но уже отдельной экосистемой.
      Когда я услышал про биткоин я ожидал разворачивания подобной Веб-Мани экосистемы, но все ушло несколько в другую сторону.

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

      Я оставил этот вбоквел чисто для тех, кто придет сюда, привлеченный статьёй. Как затравку на будущее. Может кто сделает, а я буду пользоваться... Или скорее уже не я.


      1. AndrChm
        20.09.2023 16:29
        #25983934

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


        1. MAXH0
          20.09.2023 16:29
          #25984058

          Холократия - это метод управления основанный на самоорганизующихся командах. Уникальная команда - холон. Мне этот метод понравился тем, что в идеале он максимально не авторитарный. А анархизм он не против любой власти. Он против авторитарной власти. В холократии (в идеале) власть идет вместе с принятием роли и получением ответственности за дело. В реале там есть проблемы с появлением ненужной иерархии и многие другие.

          Холократия прошла пик популярности. Но я почерпнул много полезных идей изучая её.


          1. AndrChm
            20.09.2023 16:29
            #25984074

            Ок. Я как-то не очень увлекаюсь всеми этими штуками. Не вижу повода и темы для обсуждения. Мне бы чего-нибудь по-конкретнее.


            1. MAXH0
              20.09.2023 16:29
              #25984852

              Хорошо. НО у меня появился еще один вопрос, если можно.
              Где узнать все не тривиальные методы, которыми владеет современная криптография по типу такого, как описано в статье. Без математики, а просто - можно

              А то, те кто увлекаются криптографией не увлекаются менеджментом, а менеджеры не увлекаются криптографией. В итоге не происходит переопыления идеями.


              1. AndrChm
                20.09.2023 16:29
                #25985470

                Где узнать все не тривиальные методы, которыми владеет современная криптография по типу такого, как описано в статье. Без математики,…

                Боюсь, что это невозможно. Особенно, если речь идёт о не тривиальных методах. Криптография, как и криптоанализ, — сугубо математические дисциплины. За исключением PKI, может быть. Последнее имеет отношении к организации инфраструктуры, управлению и пр. Хотя и здесь существуют решения на основе математических методов. Так что просто так не прорваться. Самый простое описание Pairings for beginners by Craig Costello. Только «простота» эта весьма относительна.

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

                Если занимаешься криптографией/криптоанализом лет так сорок, то это уже не увлечение, а профессионализм.