Geometric cryptography

From BitcoinWiki
This is the approved revision of this page, as well as being the most recent.
Jump to: navigation, search

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

A geometric one-way function[edit]

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[edit]

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.

  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<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 zero-knowledge.


See Also on BitcoinWiki[edit]