Geometric cryptography is an area of
cryptology
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...
where
message
A message is a discrete unit of communication intended by the source for consumption by some recipient or group of recipients. A message may be delivered by various means, including courier, telegraphy, carrier pigeon and electronic bus.
A ...
s and
ciphertext
In cryptography, ciphertext or cyphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext ...
s are represented by geometric quantities such as
angle
In Euclidean geometry, an angle is the figure formed by two Ray (geometry), rays, called the ''Side (plane geometry), sides'' of the angle, sharing a common endpoint, called the ''vertex (geometry), vertex'' of the angle.
Angles formed by two ...
s or intervals and where
computation
Computation is any type of arithmetic or non-arithmetic calculation that follows a well-defined model (e.g., an algorithm).
Mechanical or electronic devices (or, historically, people) that perform computations are known as ''computers''. An es ...
s 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
Ronald Linn Rivest (; born May 6, 1947) is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial Inte ...
and
Adi Shamir
Adi Shamir ( he, עדי שמיר; born July 6, 1952) is an Israeli cryptographer. He is a co-inventor of the Rivest–Shamir–Adleman (RSA) algorithm (along with Ron Rivest and Len Adleman), a co-inventor of the Feige–Fiat–Shamir identificat ...
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 an arbitrary angle. Hence the function which assigns the triple of an angle to a given angle can be thought of as a one-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, spe ...
, 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 YA which is constructed by Alice as the triple of an angle XA she has constructed at random. Because trisecting an angle is impossible Alice is confident that she is the only one who knows XA.
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 + XA and Bob checks that 3*L = R + YA.
The four 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 XA (the identity of Alice) with
error 2−''t''. The protocol is also zero-knowledge.
References
{{reflist
Cryptographic algorithms