Геометрическая криптография

Геометрическая криптография — теоретические криптографические методы, в которых сообщения и шифротексты представлены в виде геометрических величин: углов, отрезков, а вычисления проводятся с помощью циркуля и линейки. Основана на сложности решения определенного класса геометрических задач, например, трисекции угла. Геометрическая криптография не имеет практического применения, но её предлагается использовать в педагогических целях, чтобы наглядно продемонстрировать принципы криптографии такие, как протокол с нулевым разглашением информации. Идея геометрической криптографии, а именно: идентификации с помощью трисекции угла, была предложена в неопубликованной работе^[1] в 1997 году. Является примером криптографии в нестандартной модели вычислений^[2][3].

Аксиоматика

Современная теория вычислений построена на применении логических операций к последовательности бит. Невозможность решения проблемы трисекции угла может быть использована в качестве аналога проблемы остановки. В результате чего, можно построить теорию вычислений, основанную на других канонических понятиях^[1].

Простейшие операции, осуществимые с помощью циркуля и линейки на плоскости:^[4]

• Через две данные точки ${\displaystyle A}$ и ${\displaystyle B}$ можно провести прямую ${\displaystyle AB}$, притом единственную.
• Две различные перескающиеся прямые имеют точку пересечения, притом единственную.
• Пусть ${\displaystyle A}$ и ${\displaystyle B}$ различные точки, то всегда существуют различные точки ${\displaystyle C_{1},C_{2},C_{3}}$, несовпадающие с точками ${\displaystyle A}$ и ${\displaystyle B}$, удовлетворящие следующим условиям:

1. ${\displaystyle C_{1}\in AB}$
2. ${\displaystyle C_{2}\in }$ прямой ${\displaystyle AB,}$ ${\displaystyle B\in AC_{2}}$
3. ${\displaystyle C_{3}\not \in AB}$

• Пусть ${\displaystyle AB}$ — отрезок, ${\displaystyle CD}$ — луч. Тогда существует точка ${\displaystyle E\in CD}$, такая что ${\displaystyle AB}$ и ${\displaystyle CE}$ конгруэнтны.
• Имея окружность и пересекающую её прямую, можно получить точки их пересечения.

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

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

• Возможно выбрать точку принадлежащую единичному кругу.

Трисекция угла

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

Протокол идентификации

Алиса (доказывающая сторона) должна подтвердить свою личность Бобу (проверяющей стороне)^[1].

Инициализация: Алиса случайным образом генерирует угол ${\displaystyle \angle X_{A}}$, публикует угол в три раза больший ${\displaystyle \angle Y_{A}=3\angle X_{A}}$. При этом Алиса может быть уверена, что угол ${\displaystyle \angle X_{A}}$ известен только ей.

Протокол:

1. Алиса передает Бобу угол ${\displaystyle \angle R=3\angle K}$, где угол ${\displaystyle \angle K}$ выбран случайно.
2. Боб бросает монетку и сообщает Алисе результат.
3. Если выпадает "орел", Алиса передает Бобу угол ${\displaystyle \angle K}$, и Боб проверяет, что ${\displaystyle \angle R=3\angle K}$. В противном случае, Алиса передает Бобу угол${\displaystyle \angle L=\angle K+\angle X_{A}}$, Боб проверяет, что ${\displaystyle 3\angle L=\angle R+\angle Y_{A}}$.

Описанная выше последовательность шагов повторяется ${\displaystyle t}$ раз независимо. Боб подтверждает личность Алисы тогда и только тогда, когда все ${\displaystyle t}$ итераций протокола завершились корректно. Постороннее лицо, не знающее ключ ${\displaystyle \angle X_{A}}$, не может построить оба угла ${\displaystyle \angle L,\angle K}$, иначе это значило бы, что возможно построить угол ${\displaystyle \angle X_{A}=\angle L-\angle K}$.

После успешного выполнения операций можно утверждать с вероятностью ${\displaystyle P(t)=1-2^{-t}}$, что доказывающая сторона знает ключ ${\displaystyle \angle X_{A}}$.

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

Доказательство:

Пространство событий с точки зрения Боба состоит из исходов двух типов: ${\displaystyle (\angle R,0,\angle K),}$ ${\displaystyle (\angle R,1,\angle L)}$.

Для имитации первого случая Бобу достаточно взять случайный угол ${\displaystyle \angle K}$ и угол ${\displaystyle \angle R=3\angle K}$. Случайно выбирая угол ${\displaystyle \angle L}$ и выражая ${\displaystyle \angle R}$ из соотношения ${\displaystyle 3\angle L=\angle R+\angle Y_{A}}$, Боб может имитировать второй случай.

Таким образом Боб может полностью имитировать свое взаимодействие с Алисой, а значит не получает никакой информации о ключе ${\displaystyle \angle X_{A}}$.

Протокол аутентификации

Протокол идентификации может быть преобразован в протокол аутентификации^[1]. Пусть ${\displaystyle m}$ - сообщение, которое Алиса хочет аутентифицировать:

Инициализация: Для данного протокола Алисе необходимы два ключа ${\displaystyle \angle X_{A1},\angle X_{A2}}$. Публикуются углы ${\displaystyle \angle Y_{A1}=3\angle X_{A1},}$${\displaystyle \angle Y_{A2}=3\angle X_{A2}}$. Для аутентификации сообщения ${\displaystyle m}$ Алиса доказывает Бобу, что ей известен угол ${\displaystyle \angle Z=m\angle X_{A1}+\angle X_{A2}}$ , используя описанный ранее протокол идентификации.

Протокол:

1. Алиса передает Бобу угол ${\displaystyle \angle R=3\angle K}$, где угол ${\displaystyle \angle K}$ выбирается случайно.
2. Боб кидает монетку и сообщает Алисе о результате в виде ${\displaystyle b\in \{0,1\}}$.
3. Алиса отправляет Бобу угол ${\displaystyle \angle L=\angle K+b(m\angle X_{A1}+\angle X_{A2})}$. Боб проверяет, что ${\displaystyle 3\angle L=\angle R+b(m\angle Y_{A1}+\angle Y_{A2})}$.

Примечания

Литература

• Mike Burmester, Ronald L Rivest and Adi Shamir. Geometric Cryptography: Identification by Angle Trisection. — 1997.
• The New Encyclopdia Brittanica, Volume 19, Geometry. — Encyclopædia Britannica, Inc., 2008. — С. 887-936.
• John Rompel. One-way functions are necessary and sufficient for secure signatures. — In Proc. 22nd ACM Symp. on Theory of Computing, ACM, Baltimore, Maryland. — 1990. — P. 387—394.
• U. Feige, A. Fiat and A. Shamir. Zero Knowledge Proofs of Identity // Vol 1. — Journal of Cryptology, 1988. — P. 77-94.
• David P. Woodruff, Marten van Dijk. Cryptography in an Unbounded Computational Model. — Advances in Cryptology — EUROCRYPT, 2002. — P. 149-164.
• Edward Ruggeri. Cryptography in an unconventional model. — University of Chicago VIGRE REU, 2007.

Эта страница в последний раз была отредактирована 12 ноября 2023 в 23:08.