Geometric cryptography

Geometric cryptography is an area of cryptology where messages and ciphertexts are represented by geometric quantities such as angles or intervals and where computations are performed by ruler and compass constructions. The difficulty or impossibility of solving certain geometric problems like trisection of an angle using ruler and compass only is the basis for the various protocols in geometric cryptography. This field of study was suggested by Mike Burmester, Ronald L. Rivest and Adi Shamir in 1996. Though the cryptographic methods based on geometry have practically no real life applications, they are of use as pedagogic tools for the elucidation of other more complex cryptographic protocols.

A geometric one-way function

Some of the geometric cryptographic methods are based on the impossibility of trisecting an angle using ruler and compass. Given an arbitrary angle, there is a straightforward ruler and compass construction for finding the triple of the given angle. But there is no ruler and compass construction for finding the angle which is exact one-third of a given angle. Hence the function which assigns the triple of an angle to a given angle can be thought of as a one-way function, the only constructions allowed being ruler and compass constructions.

A geometric identification protocol

A geometric identification protocol has been suggested based on the one-way function indicated above.

Assume that Alice wishes to establish a means of proving her identity later to Bob.

Initialization: Alice publishes a copy of an angle Y_A which is constructed by Alice as the triple of an angle X_A she has constructed at random. Because trisecting an angle is impossible Alice is confident that she is the only one who knows X_A.

Identification Protocol: Alice gives Bob a copy of an angle R which she has constructed as the triple of an angle K that she has selected at random.

1. Bob flips a coin and tells Alice the result.
2. If Bob says "heads" Alice gives Bob a copy of the angle K and Bob checks that 3*K = R.
3. If Bob says "tails" Alice gives Bob a copy of the angle L = K + X_A and Bob checks that 3*L = R + Y_A.

The three steps are repeated t times independently. Bob accepts Alice's proof of identity only if all t checks are successful.

This protocol is an interactive proof of knowledge of the angle X_A (the identity of Alice) with error 2^−t. The protocol is also zero-knowledge.