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

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

Аксиоматика

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

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

• Через две данные точки [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math] можно провести прямую [math]\displaystyle{ AB }[/math], притом единственную.
• Две различные перескающиеся прямые имеют точку пересечения, притом единственную.
• Пусть [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math] различные точки, то всегда существуют различные точки [math]\displaystyle{ C_1, C_2, C_3 }[/math], несовпадающие с точками [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math], удовлетворящие следующим условиям:

1. [math]\displaystyle{ C_1 \in AB }[/math]
2. [math]\displaystyle{ C_2 \in }[/math] прямой [math]\displaystyle{ AB, }[/math] [math]\displaystyle{ B \in AC_2 }[/math]
3. [math]\displaystyle{ C_3 \not\in AB }[/math]

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

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

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

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

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

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

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

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

Инициализация: Алиса случайным образом генерирует угол [math]\displaystyle{ \angle X_A }[/math], публикует угол в три раза больший [math]\displaystyle{ \angle Y_A = 3\angle X_A }[/math]. При этом Алиса может быть уверена, что угол [math]\displaystyle{ \angle X_A }[/math] известен только ей.

Протокол:

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

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

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

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

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

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

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

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

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

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

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

Протокол:

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

Литература

• 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.