Geometric cryptography
Geometric cryptography is an area of where and are represented by geometric quantities such as or intervals and where are performed by . 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, and in 1996.<ref name=Shamir/> 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.<ref name=Shamir/>
Contents
A geometric one-way function
Some of the geometric cryptographic methods are based on the 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 , 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<sub>A</sub> which is constructed by Alice as the triple of an angle X<sub>A</sub> she has constructed at random. Because trisecting an angle is impossible Alice is confident that she is the only one who knows X<sub>A</sub>.
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.
- Bob flips a coin and tells Alice the result.
- If Bob says “heads” Alice gives Bob a copy of the angle K and Bob checks that 3*K = R.
- If Bob says “tails” Alice gives Bob a copy of the angle L = K + X<sub>A</sub> and Bob checks that 3*L = R + Y<sub>A</sub>.
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<sub>A</sub> (the identity of Alice) with error 2<sup>−t</sup>. The protocol is also .