24.06.2021 21:41
ENCRY 31 3100 Источник


ENCRY рассказывает о новом интерактивном протоколе идентификации, который позволяет контролировать доступ избранных пользователей к различным ресурсам.

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

Попасть на такую вечеринку — удел избранных. Приглашения рассылаются заблаговременно, и гости не знают, кто был приглашён кроме них. Владелец поместья, таинственный Джей Гэтсби, любитель роскоши, настолько ценит приватность, что не готов доверить список приглашённых никому, даже мажордому. Более того, хозяин поместья хотел бы, чтобы гости могли не разглашать своё имя при въезде на территорию. Право же, ведь среди них может быть и мэр города, и главный прокурор, а они хотели бы сохранить свой визит в тайне. К сожалению, сам владелец поместья настолько занят, что не в силах самостоятельно проверять каждого гостя на входе, тем более что к его дому предусмотрено несколько подъездных дорог. Как же быть?

К счастью для Гэтсби, его друг Альберт, математик по образованию и криптограф по призванию, посоветовал ему хитроумный способ. Он придумал как с помощью специального протокола принимать решение по принципу «свой/чужой» на основе группового общедоступного ключа и персональных секретных ключей для каждого приглашённого. Гэтсби, как устроитель, вправе менять список приглашённых и, соответственно, групповой общедоступный ключ. Кроме этого, Альберт разработал мобильное приложение с настройкой ролевой функциональности. Условно такие настройки можно обозначить как режимы работы «Привратник», «Гость» и «Устроитель». Например, приложение с настройкой «Привратник» передаётся привратникам, а также всем остальным, кто отвечает за проверку гостей. Понятно, что такая настройка позволяет отличить приглашённого от постороннего. Соответственно настройка «Гость» позволяет доказать, что ты приглашён. Решение о той или иной персональной настройке принимает сам Гэтсби.

Как любитель оригинальных затей, Гэтсби согласился испытать новую технологию на ближайшей вечеринке. Он перевёл мобильное приложение в режим «Устроитель» и ввёл список приглашённых. В результате приложение автоматически сформировало групповой общедоступный ключ, а затем при помощи секретного чата мессенджера Telegram адресовало копию с настройкой «Гость» вместе с персональным секретным ключом каждому из приглашённых.

Настал заветный пятничный вечер. К поместью потянулись очереди из Lamborghini, Bentley и Bugatti. Подъезжая к воротам, открывающим подъезд к поместью, гости с помощью мобильного приложения, в котором хранится секретный ключ, доказывают тот факт, что они приглашены. Если протокол, на основе которого работает мобильное приложение, разрешает доступ, то ворота открываются и автомобиль с гостями въезжает на территорию поместья. Так гости Гэтсби попадают на вечеринку, не раскрывая свою личность даже привратникам.

XXI век — эпоха моментальных сообщений и быстрого взаимодействия. Огромный мир сжался до размера компьютера или смартфона. Мы гораздо быстрее и проще контактируем с людьми, живущими на других континентах, можем увидеться с ними в одном виртуальном пространстве. Но появились и новые вызовы, связанные с технологиями. Один из них — необходимость найти новые способы определять «своего» или «чужого» в условиях, когда общение ведётся в онлайне. Именно такую задачу и решило мобильное приложение, созданное другом-математиком в нашей вымышленной истории про Гэтсби.

Вы, наверное, уже догадались — речь пойдёт о протоколе идентификации на основе методов асимметричной криптографии. Рассказывать о том, что такое секретный и общедоступный ключи и как они создаются, мы не будем. Эту информацию можно легко найти в любом учебнике по основам криптографии. И если вы читаете этот текст, то, скорее всего, обладаете базовыми знаниями в области криптографии хотя бы на уровне общих понятий. Проверить свои знания можно с помощью нашего теста в Telegram (@QuizBot quiz:VBwaO0d9). Обратим внимание на то, что в нашем протоколе идентификации идёт речь об одном групповом общедоступном ключе и некотором количестве секретных ключей, а не о парных ключах, когда каждому уникальному секретному ключу соответствует свой общедоступный. Если вам нужно вспомнить методы асимметричной криптографии, то советуем прочитать предыдущий текст в нашем блоге.

Мы расскажем о своей разработке — интерактивном протоколе идентификации. Протокол создан на основе известного криптографического примитива — спаривания точек эллиптической кривой. Он применяется во многих приложениях для шифрования и создания электронных цифровых подписей.

Осторожно, эллиптические кривые!
Криптосистемы на эллиптических кривых применяются в широко распространённых технологиях, таких как TLS, PGP и SSH, и в недавно возникших децентрализованных системах, таких как криптовалюты. Ключевыми в контексте криптосистем являются проблема дискретного логарифма (Discrete Logarithm Problem, DLP), а также смежная труднорешаемая задача, известная как проблема дискретного логарифма на эллиптических кривых (Elliptic Curve Discrete Logarithm Problem, ECDLP).

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

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

Вернемся к DLP. Пусть задано простое конечное поле и некоторый элемент этого поля $z$. Кроме этого известен образующий элемент $x$. По построению $z=x^y$. Задача DLP заключается в нахождении $y$ при заданных $z$ и $x$.

Когда мы говорим «силовая атака», то имеем в виду вычисление $z’=x^i$ для разных $i$ и сравнение результата с $z$. Таким образом, если $z=z’$, то $i=y$.

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

Тут надо сделать шаг в сторону и отметить, что поскольку порядок группы — составное число, то известен эффективный метод решения DLP по принципу «разделяй и властвуй». Внутри группы может существовать подгруппа — аналогичная структура, но меньшей мощности. Согласно теории групп, порядок подгруппы является делителем порядка группы. Иными словами, если порядок группы составное число, то подгруппа простого порядка всегда существует. Но когда порядок группы — простое число, то решение на основе упомянутого принципа не работает. Значит, для сохранения экспоненциальной трудоёмкости решения DLP в случае силовой атаки порядок должен быть простым числом и группа должна содержать подгруппу большого простого порядка. Насколько большого — это уже зависит от требований криптостойкости. Однако, как мы упомянули выше, возможна атака субэкспоненциальной трудоёмкости. Тогда очевидно, что такой порядок должен нивелировать выигрыш от применения субэкспоненциальных методов решения DLP. Таким образом, задача заключается в выборе такой группы, которая содержит подгруппу большого (зависит от требований криптостойкости) простого порядка.

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

Обозначим конечное поле простой характеристики $p>3$ через $\mathbb{F}_p$. Уравнение эллиптической кривой над $\mathbb{F}_p$ имеет вид $y^2=x^3+ax+b$. Здесь $a, b, x$ и $y$ принадлежат $\mathbb{F}_p$. Каждая точка кривой задаётся парой координат $x$ и $y$, удовлетворяющих приведённому выше уравнению. Точки эллиптической кривой над $\mathbb{F}_p$ образуют аддитивную группу, конечнопорождённость которой доказана в теореме Морделла-Вейля. Выберем $a$ и $b$ так, чтобы получить подгруппу некоторого простого порядка группы точек эллиптической кривой. Групповая операция предполагает наличие специальной точки, так называемой точки на бесконечности $\infty$, такой, что для произвольной точки $\mathsf{Q}$ справедливо $\mathsf{Q}+\infty=\infty+\mathsf{Q}=\mathsf{Q}$. Известны различные эффективные способы сложения и удвоения точек.

Пусть задана эллиптическая кривая над $\mathbb{F}_p$. Через $\mathbb{G}_1$ обозначим подгруппу простого порядка $m$ группы точек эллиптической кривой с образующим элементом $\mathsf{G}_1$. Существуют простые поля вида $\mathbb{F}_{p^k}$, где $k>1$ — натуральное число. Пусть $\mathbb{G}_3$ — подгруппа простого порядка $m$ мультипликативной группы $\mathbb{F}^*_{p^k}$ с образующим элементом $g$ для некоторого $k$. Назовём симметричным спариванием отображение вида $e_m:\mathbb{G}_1\times\mathbb{G}_1\mapsto \mathbb{G}_3$. Существует также асимметричное спаривание $\hat{e}_m:\mathbb{G}_1\times \mathbb{G}_2\mapsto \mathbb{G}_3$, где $\mathbb{G}_1=\langle\mathsf{G}_1\rangle$, $\mathbb{G}_2=\langle\mathsf{G}_2\rangle$ — различные подгруппы простого порядка $m$.

Введём скалярное произведение для точек из $\mathbb{G}_1$. Это операция вида $\mathsf{Q}=[\ell]\mathsf{G}_1$, такая, что $\mathsf{Q}=\underbrace{\mathsf{G}_1+\mathsf{G}_1+\ldots+\mathsf{G}_1}_{\ell}$ и $[-\ell]\mathsf{G}_1=[\ell](-\mathsf{G}_1), [0]\mathsf{G}_1=\infty$, где $0\leqslant|\ell|\leqslant m-1$.

Пусть $\ell=a+b$. $\mathsf{Q}=[a]\mathsf{G}_1+[b]\mathsf{G}_1=[\ell]\mathsf{G}_1$. $[c] \mathsf{Q}=[c\ell]\mathsf{G}_1=[ca+cb]\mathsf{G}_1$.

Пример. Предположим $\ell=151_{10}=10010111_2$. Тогда $\mathsf{Q}=[151]\mathsf{G}_1=[2^7]\mathsf{G}_1+[2^4]\mathsf{G}_1+[2^2]\mathsf{G}_1+[2^1]\mathsf{G}_1+[2^0]\mathsf{G}_1$.

  1. Возьмём точку $\mathsf{G}_1$ ($1001011{\color{red}{1}}_2$).
  2. Удвоим $\mathsf{G}_1$ и получим $[2]\mathsf{G}_1$ ($100101{\color{red}{1}}1_2$), $\Sigma_1=[2]\mathsf{G}_1+\mathsf{G}_1$.
  3. Удвоим $[2]\mathsf{G}_1$ и получим $[2^2]\mathsf{G}_1$ ($10010{\color{red}{1}}11_2$), $\Sigma_2=[2^2]\mathsf{G}_1+\Sigma_1$.
  4. Удвоим $[2^2]\mathsf{G}_1$ и получим $[2^3]\mathsf{G}_1$ ($1001{\color{red}{0}}111_2$).
  5. Удвоим $[2^3]\mathsf{G}_1$ и получим $[2^4]\mathsf{G}_1$ ($100{\color{red}{1}}0111_2$), $\Sigma_3=[2^4]\mathsf{G}_1+\Sigma_2$.
  6. Удвоим $[2^4]\mathsf{G}_1$ и получим $[2^5]\mathsf{G}_1$ ($10{\color{red}{0}}10111_2$).
  7. Удвоим $[2^5]\mathsf{G}_1$ и получим $[2^6]\mathsf{G}_1$ ($1{\color{red}{0}}010111_2$).
  8. Удвоим $[2^6]\mathsf{G}_1$ и получим $[2^7]\mathsf{G}_1$ (${\color{red}{1}}0010111_2$), $\Sigma_4=[2^7]\mathsf{G}_1+\Sigma_3$.


Спаривание точек $\mathsf{S}$ и $\mathsf{Q}$ можно представить как $e_m(\mathsf{S},\mathsf{Q})=g^{cd \pmod m}$, где $\mathsf{S}=[c \pmod m]\mathsf{G}_1$ и $\mathsf{Q}=[d \pmod m]\mathsf{G}_1$ и $g^{cd \pmod m}$ — некоторый элемент $\mathbb{G}_3$. Здесь $\mathsf{G}_1$ и $g$ — образующие элементы в $\mathbb{G}_1$ и $\mathbb{G}_3$ соответственно, а $c$ и $d$ принадлежат $\mathbb{F}^*_m$.

Существуют и несимметричные билинейные отображения вида $e_m:\mathbb{G}_1\times \mathbb{G}_2\mapsto \mathbb{G}_3$, где $\mathbb{G}_2$ — подгруппа простого порядка $m$, отличная от $\mathbb{G}_1$.

Известно несколько разновидностей спаривания, например, спаривание по Вейлю, а также спаривание по Тейту-Лихтенбауму. На практике чаще применяется второй вариант. Симметричное спаривание имеет следующие свойства:

• Билинейность.
• Невырожденность.
• Вычислимость.

Тут возникает вопрос: а зачем тогда использовать криптосистемы на эллиптических кривых, если решение ECDLP можно свести к решению DLP? Ведь этот путь могут выбрать не в конструктивных целях, а, например, для выполнения атаки. Со временем выяснилось, что такое сведение справедливо не для всех кривых. Например, суперсингулярные кривые и кривые с единичным следом отличаются низкой криптостойкостью, так как метод сведения позволяет решать DLP за субэкспоненциальное или даже линейное время. Поэтому эти кривые были отвергнуты в качестве основы для построения криптосистем. Известны эллиптические кривые со специальными свойствами, применение которых не приводит к снижению криптостойкости по причине существования билинейного отображения.

В конструктивном плане функция $e_m(\cdot,\cdot)$, в виде которой можно представить спаривание, работает как односторонняя: её легко вычислить, но для обращения, а именно восстановления исходной пары точек из $\mathbb{G}_1$ по имеющемуся элементу из $\mathbb{G}_3$, понадобится решить задачу с экспоненциальным объёмом перебора.

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


Проведя аналогию с вечеринкой у Гэтсби, мы назовём привратника проверяющим (актор $\texttt{V}$), а гостя — доказывающим (актор $\texttt{P}$). $\texttt{P}$ пытается убедить $\texttt{V}$, что является приглашённым гостем. С этой целью он предоставляет $\texttt{V}$ некоторое доказательство. Знание секрета означает принадлежность локальному сообществу зарегистрированных участников. $\texttt{V}$ использует групповой общедоступный ключ для проверки доказательства, после чего-либо принимает, либо отвергает предоставленное доказательство. Возвращаясь к нашему примеру с вечеринкой у Гэтсби, привратник ($\texttt{V}$) либо видит на экране смартфона надпись «пропустить», если доказательство принято, либо «отказать» — в противоположном случае.

Если $\texttt{P}$ действительно располагает секретом, который был учтён при вычислении группового ключа, т.е. он включён в список приглашённых, то с преобладающей вероятностью он сможет убедить $\texttt{V}$, что приглашён и тот откроет ворота. Если $\texttt{P}$ не располагает секретным ключом или располагает, но был исключён из списка приглашённых, то $\texttt{V}$ с преобладающей вероятностью ворота не откроет (откроет с пренебрежимо малой вероятностью).

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

Заглянем внутрь протокола и посмотрим, как он работает. Протокол идентификации состоит из полутора раундов. Раундами называются сеансы обмена сообщениями, в котором каждая из сторон передаёт ровно по одному сообщению. Это напоминает обмен ударами в боксе.

?$\texttt{P} \longrightarrow \texttt{V} : свидетельство (witness)$
?$\texttt{P} \longleftarrow \texttt{V} : вызов (challenge)$
?$\texttt{P} \longrightarrow \texttt{V} : ответ (response)$

В ходе одномоментной реализации нашего протокола (сессии) $\texttt{P}$ передаёт два сообщения, а $\texttt{V}$ — только одно. Каждая отдельная сессия состоит из трёх циклов активности $\texttt{P}\stackrel{1}{\rightarrow}\texttt{V}\stackrel{2}{\rightarrow}\texttt{P}\stackrel{3}{\rightarrow}\texttt{V}$.

Пусть $\Omega^*$ — множество всех последовательностей букв произвольной длины в конечном алфавите $\Omega$ (множество букв). Заданы
$\hslash^i(x)=\overbrace{\hslash(\hslash( \ldots \hslash(\hslash(x)) \ldots )}^{i\hbox{ раз}})$ и $\hslash^i(x)=\hslash(\hslash^{i-1}(x))$, $i\geqslant 1$, $\hslash^0(x)=x$,
где $\hslash(\cdot)$ — стандартная криптографическая хеш-функция из FIPS PUB 180-4, и секретное $\beta\in_R\!(0,m-1]$. Имеется $1\leqslant n < m $ участников. Каждому участнику однозначно соответствует идентификатор $\mathbf{a}_i\in\Omega^*$. Представим идентификаторы в виде множества $\mathbf{X}=\{\mathbf{x}_1,\ldots, \mathbf{x}_n\}$, такого, что $\mathbf{x}_i=\hslash(\mathbf{a}_i\|\hslash^i(\beta))$, где $\mathbf{a}_i\in\Omega^*, \mathbf{x}_i\in \{0,1\}^{\lceil\lg{m}\rceil}, i=\overline{1,n}$. Описанный способ формирования $\mathbf{X}$ гарантирует, что все $\mathbf{x}_i$ различны и даже если $\mathbf{a}_i=\mathbf{a}_j$, то $\mathbf{x}_i\neq\mathbf{x}_j$ при $i\neq j, 1 \leqslant i,j \leqslant n$.

Будем исходить из предположения, что имеется доверенная сторона $T$ (в нашей вымышленной истории с вечеринкой — это хозяин поместья, сам Гэтсби), которая отвечает за выбор параметров, предварительные вычисления и распределение данных.

Заданы $\beta, n, p, m, \mathbb{G}_1, \mathbb{G}_3, e_m(\cdot, \cdot)$. Тогда на подготовительном этапе $T$ выполняет следующие действия:

  1. На основании $\mathbf{a}_i, \beta$ и при помощи $h^{i}(\cdot)$ формирует множество $\mathbf{X}=\{\mathbf{x}_1,\ldots, \mathbf{x}_n\}, i=\overline{1,n}$.
  2. Вычисляет $\Gamma=\prod_{i=1}^n\mathbf{x}_i\pmod m$.
  3. Секретно передаёт $i$-му участнику $\{\mathbf{x}_i, \mathsf{P}_i=[\beta\widehat\Gamma_i\pmod m]\mathsf{G}_1\}$, где $\widehat\Gamma_i=\mathbf{x}_i^{-1}\Gamma\pmod m$, $i=\overline{1,n}$.
  4. Секретно вычисляет и затем публикует общедоступный групповой ключ $\tilde{g}=e_m([\beta\Gamma\pmod m]\mathsf{G}_1, \mathsf{G}_1)=g^{\beta\Gamma\pmod m}$. Предполагается, что подлинность и целостность $\tilde{g}$ гарантируется при помощи ЭЦП. Если ${\rm{Sign}}(\cdot,\cdot)$ и ${\rm{Verify}}(\cdot,\cdot,\cdot)$ — функции формирования и проверки ЭЦП, то выпускается сертификат $\{D_T,\tilde{g}, \Im_{\tilde{g}}\}$, где $\Im_{\tilde{g}}\Leftarrow{\rm{Sign}}(\mathscr{H}(\tilde{g}\|D_T), S)$, $\mathscr{H}(\cdot)$ — криптографическая хеш-функция, $S$ — секретный ключ доверенной стороны $T, D_T$ — информация о $T$. Перед использованием $\tilde{g}$ необходимо проверить валидность $\Im_{\tilde{g}}$ при помощи $\mathfrak{B}\Leftarrow{\rm{Verify}}(\mathscr{H}(\tilde{g}\|D_T),\Im_{\tilde{g}},P)$, где $P$ — парный общедоступный ключ доверенной стороны $T$. Переменная $\mathfrak{B}$ принимает значение $True$, если $\Im_{\tilde{g}}$ валидна, и $False$ — в противном случае. Если $T$ не является удостоверяющим центром в рамках действующей инфраструктуры общедоступных ключей, то для $P$ выпускается соответствующий сертификат.
  5. Сохраняет в секрете $\beta$.

Сообщения. Подтверждение/опровержение факта владения (знания) $\mathbf{x}_i{\in}\mathbf{X}$.

?$\texttt{P} \longrightarrow \texttt{V} : \mathsf{P}_w=[\upsilon]\mathsf{P}_i=[\upsilon\beta\widehat{\Gamma}_i\pmod m]\mathsf{G}_1$
?$\texttt{P} \longleftarrow \texttt{V} : \mathsf{P}_c=[\phi]\mathsf{G}_1$
?$\texttt{P} \longrightarrow \texttt{V} : g_1=e_m([\upsilon+\mathbf{x}_i\pmod m]\mathsf{P}_i,\mathsf{P}_c)=g^{\phi\beta(\upsilon\widehat{\Gamma}_i+\Gamma)\pmod m}$

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

  1. Доказывающий выбирает ${\upsilon\in_R\!(0,m-1]}$ (commitment) и проверяет выполнение условия ${([\upsilon]\mathsf{P}_i\neq\infty)\land([\upsilon+\mathbf{x}_i\pmod m]\mathsf{P}\neq\infty)}$. Если условие выполняется, то вычисляет точку $\mathsf{P}_w$ (witness), в противном случае выбирает новое $\upsilon$.
  2. Проверяющий выбирает $\phi\in_R\!(0, m-1]$ и вычисляет точку $\mathsf{P}_c$ (challenge).
  3. Доказывающий проверяет, что $\mathsf{P}_c\neq\infty$ и затем вычисляет $g_1$ (response).
  4. Проверяющий считывает из общедоступной памяти действующий сертификат $\{D_T, \tilde{g}, \Im_{\tilde{g}}\}$ и проверяет подпись $\Im_{\tilde{g}}$ при помощи $\mathfrak{B}\Leftarrow{\rm{Verify}}(\mathscr{H}(\tilde{g}\|D_T),\Im_{\tilde{g}},P)$, где $P$ — общедоступный ключ $T$. Если $(\mathfrak{B}=True)\land (\mathsf{P}_w\neq\infty)$, то проверяет $\tilde{g}^\phi g_2\stackrel{?}{=} g_1$, где $g_2=e_m(\mathsf{P}_w, \mathsf{P}_c)$. Равенство подтверждает факт владения (знания) $\mathbf{x}_i\in\mathbf{X}$, в противном случае доказательство отвергается.

С точки зрения целевого назначения разработанный протокол похож на протоколы идентификации с нулевым разглашением (Zero-knowledge Proof, ZKP). Они тоже призваны решать схожую задачу: при помощи интерактивного взаимодействия $\texttt{P}$ пытается убедить $\texttt{V}$, что знает некоторый секрет, который не раскрывается в ходе протокола. Как и все другие протоколы идентификации, ZKP-протоколы состоят из полутора раундов (полтора раунда = сессия). В случае ZKP-протоколов отдельная сессия повторяется многократно. Чем больше повторений, тем меньше вероятность обмана. Но это же является минусом с практической точки зрения: многократное повторение сессий приводит к вычислительным затратам, расходу памяти и загрузке каналов связи.

Один из наиболее известных ZKP-протоколов — протокол Фейга-Фиата-Шамира. Разработан в 1986 году Уриэлем Фейгом, Амосом Фиатом и Ади Шамиром. В ходе протокола $\texttt{P}$ доказывает $\texttt{V}$, что обладает секретной информацией, не раскрывая этой информации. Основан на сложности извлечения квадратного корня по составному модулю, включающему не менее двух больших простых множителей, при условии, что разложение неизвестно. Протокол Гиллу-Кискатра — еще один ZKP-протокол. Является вариацией более раннего протокола Фиата-Шамира. Разработан в 1988 году Луи Гиллу и Жаном-Жаком Кискатром. Как и протокол Фиата-Шамира, основан на сложности извлечения квадратного корня по модулю составного числа. Главные отличия:

• не требуется повторения сессии;
• не большой объём памяти для хранения секретов пользователей.

Известными протоколами идентификации также являются протокол аутентификации Шнорра, протоколы Брикелла-МакКерли и Окамото.

Зачем же создавать ещё протокол, если задача решается уже существующими протоколами идентификации? Все дело в том, что наш протокол решает задачу, отличную от той, которую решают известные протоколы идентификации, а именно позволяет принимать решение по принципу «свой/чужой» для локального сообщества зарегистрированных участников с гарантией их анонимности. Кроме этого, отличается относительно невысокой вычислительной трудоёмкостью. Корректно сравнение с протоколом Л.Нгуена (Nguyen, L. “Accumulators from Bilinear Pairings and Applications.” In Topics in Cryptology — CT-RSA’05, LNCS 3376, (2005) 275–292.), так как этот протокол использует схожий математический аппарат. Если сравнивать по числу задействованных операций спаривания и скалярного произведения, то вычислительная трудоёмкость нашего протокола на порядок ниже, чем в протоколе Л.Нгуена.

Доказанные свойства нашего протокола:

• Witness Indistinguishable (WI, «неразличимость свидетельств»). Свойство WI означает, что злоумышленник не может определить, какому секрету соответствует текущее свидетельство (witness), даже если он знает все эти секреты. Если каждому секрету соответствует своё множество свидетельств, то WI-свойство гарантирует статистическую/полиномиальную неразличимость этих множеств. В данном контексте полиномиальная неразличимость означает, что несмотря на расхождение статистических характеристик, эти различия не могут быть выявлены при помощи алгоритма полиномиальной трудоёмкости. Внимательный читатель тут, наверное, воскликнет: «различия можно выявить при помощи алгоритма сверхполиномиальной трудоёмкости!». На это отвечаем: безусловно, только злоумышленник не располагает ресурсами, необходимыми для выполнения такой трудоёмкой вычислительной работы.

• Witness Hiding (WH, «сокрытие свидетельств»). Злоумышленник не может самостоятельно вычислить новое свидетельство, релевантное в контексте исполняемого протокола. Вероятность, с которой злоумышленник может получить такое свидетельство, не выше вероятности угадывания секрета. Злоумышленник вынужден либо угадать свидетельство, либо выполнить некоторую вычислительную работу, трудоёмкость которой не ниже трудоёмкости раскрытия секрета.

В фундаментальных исследованиях (Feige, U. and Shamir, A. “Witness Indistinguishable and Witness Hiding Protocols.” In Proceedings of 22nd STOC, ACM Press, (1990) 416–426.) WH-свойство рассматривается как альтернатива ZKP-свойству. Если злоумышленник получает доступ к транскрипциям различных сессий одного и того же ZKP-протокола, которые осуществлялись одномоментно, то он получает возможность вмешиваться и влиять на ход их исполнения. WH-свойство, в отличие от ZKP, гарантирует, что злоумышленник не извлекает никакой содержательной информации из транскрипций сессий протокола и значит не сможет в дальнейшем выдать себя за доказывающего (в нашем примере — за приглашённого гостя).

Итого, интерактивный протокол идентификации на основе спаривания и скалярных произведений с доказанными свойствами WI и WH — это новое решение, позволяющее сократить вычислительную трудоёмкость и объём памяти для хранения ключей (напомним, что участникам не нужны сертификаты персональных общедоступных ключей). Наш протокол, в отличие от ZKP, не требует многократного повторения сессий для минимизации вероятности обмана. Добиться этого удалось благодаря доказанным свойствам WI и WH. Преимущество нового протокола ещё и в том, что объем памяти для хранения общедоступного группового ключа, а также число сообщений и количество передаваемой информации не зависят от мощности локального сообщества.

Разработанный нами протокол может быть использован даже на смартфонах, а это открывает путь к созданию новых мобильных приложений с адекватным уровнем криптостойкости.

Подписывайтесь на наш Хабраблог, мы планируем и дальше активно освещать наши исследования и разработки, и следите за твиттером, если не хотите пропустить другие новости о проектах ENCRY.