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

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

Аксиоматика

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

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

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

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

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

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

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

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

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

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

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

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

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

Протокол:

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

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

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

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

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

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

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

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

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

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

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

Протокол:

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