%
%% Default Latex template for a paper
%% Ronald L. Rivest
\documentstyle[11pt]{article} %,psfig]{article}
% \input{/a/rivest/papers/math}
% \input{/a/rivest/papers/theorems}
%% Page size
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{9.0in}
\setlength{\oddsidemargin}{0.in}
\setlength{\evensidemargin}{0.in}
\setlength{\textwidth}{6.5in}
\setlength{\parskip}{2pt}

\begin{document}
\bibliographystyle{plain}
\title{Geometric Cryptography: Identification by Angle Trisection\\
       {\small (Draft 2)}}

\author{%
Mike Burmester\thanks{%
email address: {\tt m.burmester@rhbnc.ac.uk}}\\
Information Security Group \\%, Department of Mathematics\\
Royal Holloway--University of London\\ 
Egham, Surrey TW20 OEX, U.K.
\and
Ronald L. Rivest\thanks{%
email address: {\tt rivest@theory.lcs.mit.edu}}\\
Laboratory for Computer Science\\
Massachusetts Institute of Technology\\
Cambridge, MA 02139, U.S.A.
\and
Adi Shamir\thanks{%
email address: {\tt shamir@wisdom.weizmann.ac.il}}\\
Department of Computer Science\\
The Weizmann Institute of Sciences\\
Rehovot 76100, Israel}

\date{\today}

\maketitle
\thispagestyle{empty}
\begin{abstract}
We propose the field of ``geometric cryptography,'' where messages
and ciphertexts may be represented by geometric quantities such as
angles or intervals, and where computation is performed by ruler
and compass constructions.

We describe a elegant little zero-knowledge identification scheme,
based on the impossibility of trisecting an angle using ruler and
compass operations.

While geometric cryptography may have little practical application, it
may facilitate the construction of pedagogic examples making
cryptographic principles accessible to a wider audience, and may also
by contrast illuminate those cryptographic principles.
\end{abstract}

\section{Geometric Cryptography}

The modern theory of computation, following Turing, is based on
representing data as sequences of symbols (typically bits), and
performing operations from a small set of primitive operations (such
as ANDs and ORs).  But the notion of computation is compatible with
other data representations.  For example, the classic geometric notion
of constructability with ruler and compass operations yields a rich
theory analogous in many ways to the modern theory of computation.
The impossibility of trisecting an angle can be viewed as analogous to
the impossibility of solving the halting problem.  The difficulty, or
impossibility, of solving geometric problems %such as angle trisection
can be used as a
foundation for ``geometric cryptography''--a field which we propose
for further study.  By way of getting this field of study off the
ground, we propose here a simple zero-knowledge identification
protocol, based on the impossibility of trisecting an angle by ruler
and compass. 

We begin by reviewing the standard operations allowed in ruler and compass
constructions:
\begin{enumerate}
\item Given two distinct points, one can construct the unique 
      line on which both lie.
\item Given two distinct lines that meet, one can construct their point of 
      intersection.
\item If $A$ and $B$ are distinct points, then one can construct three
      points $C_1$, $C_2$, and $C_3$, distinct from $A$ and $B$, such that:
	\begin{enumerate}
	\item $C_1$ is on the line determined by $A$ and $B$, and between 
              $A$ and $B$.
        \item $C_2$ is on the line determined by $A$ and $B$, and $B$ is
              between $A$ and $C_2$.
        \item $C_3$ is not on the line determined by $A$ and $B$.
	\end{enumerate}
\item If $AB$ is any interval and $CD$ is any ray, then one can construct
      a point $E$ on $CD$ such that $AB$ and $CE$ are congruent. 
\item Given any circle and a line that meets it, 
      one can construct the point(s) of intersection.
\end{enumerate}
These axioms are paraphrased from the excellent survey of geometry
\cite{Brittanica89}.  The undefined terms (such as ``points,'' ``interval,''
``between,'' ``congruent,'' and so on) are used in other axioms (not
given here) that delimit their meaning.  Given the above primitives, one
can show that it is possible to perform other constructions, such as
bisecting an interval or an angle, constructing a perpendicular to
a line through a point on that line, or determining the point(s) of 
intersection of two circles.  The theory of geometric constructability
is a rich one.  We do not elaborate this theory here, since
we will be using only the simplest techniques.
%
In ``geometric cryptography,'' messages and ciphertexts are
represented by geometric objects such as intervals or angles.  More
complicated representations could of course be used.

For cryptographic purposes, one needs to be able to generate and keep
random ``secrets'' that are unpredictable to the adversary.  
These should not be constructable by ruler and compass from previously 
constructed objects, otherwise the adversary  can find them.
To model this within geometric cryptography, we require an additional axiom for
the selection of random points.
%
\begin{enumerate}
\addtocounter{enumi}{5}
\item      
One can select uniformly distributed random points in the unit circle.
\end{enumerate}
%
%
%augment principle 3(c) of constructability to also say that {\em $C_3$ is 
%``random'' point}. 
%
Selecting such points amounts to generating secrets that are 
unknowable to an adversary. 
%
%
%(More precisely, such a point $C_3$ can not be constructed 
%using a deterministic version of principle 3, such as one in which
%any point $C_1$ constructed via principle 3(a)
%is the midpoint of the interval $AB$, any point $C_2$ constructed 
%via principle 3(b) is
%such that $B$ is the midpoint of $AC_2$, and any other point $C_3$
%constructed via principle 3(c)
%is a vertex of an equilateral triangle with other vertices $A$ and $B$.)
%Constructing such a point $C_3$ 
%is generating a secret that is unknowable to an adversary.
%
We also assume that parties can flip coins.

It is well known that trisecting an arbitrary angle is impossible with 
a ruler and (an unmarked) compass.  However, tripling an angle is easy.  
Thus, the operation of
tripling an angle is a ``one-way function'' for geometric cryptography.

We assume that an adversary can do unbounded computation (in the classical
sense), but is limited to performing ruler and compass constructions in
terms of manipulating geometric information, and to selecting random
points in the plane.

\section{An Identification Protocol}\label{protocol}

Alice (the Prover) wishes to establish a means of proving her identity
later to Bob (the Verifier).  

\medskip
\noindent{\bf 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$.

\bigskip
\noindent{\bf Identification Protocol}
\medskip

\noindent
This has the standard form of an iterated ``atomic'' three-round protocol:
%
\begin{enumerate}
\item 
Alice gives Bob a copy of an angle $R$, which she has constructed
as the triple of an angle $K$ that she has selected %constructed 
at random.
\item
Bob flips a coin, and tells Alice the result.
\item
If Bob says ``heads,'' Alice gives Bob a copy of the angle $K$
and Bob checks %verifies 
that $3*K=R$.
If Bob says ``tails,'' Alice gives Bob a copy of the angle $L=K+X_A$,
and Bob checks %verifies 
that $3*L=R+Y_A$.
\end{enumerate}

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

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.
Below we sketch a simplified proof for this (a formal proof can easily be 
obtained by using the approach in~\cite{FeigeFiatShamir88}).

If Alice and Bob  follow the protocol then clearly Bob will always accept Alice's
proof of identity. However %On the other hand, 
an imposter, who does not know the secret angle $X_A$, cannot construct 
both the angles $K$ and $L$ in step 3
(otherwise he could construct $L-K= X_A$). %So in each iteration
Thus Bob will accept with probability no better than $1/2$
for each iteration, and no better than $2^{-t}$ for the $t$ 
iterations.\footnote{Formally, 
the knowledge of the prover is checked by an ``extractor'' $M$. 
If a prover succeeds in convincing the verifier with probability greater 
than the error $2^{-t}$, then $M$ can  extract %the secret angle 
$X_A$ (or an equivalent geometric object)
by ``probing and resetting'' the prover~\cite{FeigeFiatShamir88}. 
With geometric cryptography there are no complexity bounds on $M$.} 
%
%
It follows that the protocol is proof of knowledge of $X_A$~\cite{GoldwasserMicaliRackoff89}.

Next we show that the protocol is zero-knowledge. That is, it is possible 
to simulate Bob's ``view'' during the execution  of the protocol. Now Bob ``sees'' 
the messages of Alice and his own coin flips. The transcripts of these are 
of type $(R,\mbox{``heads''},K)$ or $(R,\mbox{``tails''},L)$. 
To simulate the former, select the angle $K$ at random and take $R=3*K$; for the latter,
select the angle $L$ at random and solve $3*L=R+Y_A$ 
for $R$.\footnote{Bob may use a non-uniform distribution. The following proceedure is
used to simulate Bob's view~\cite{GoldwasserMicaliRackoff89}.  
Suppose that the transcripts of $r<t$ rounds have been simulated. Flip a fair coin
and construct the corresponding transcript. Give this to Bob and get  
his coin flip. If this is the same, append the transcript to the list 
and proceed to the next  round. Otherwise ``reset'' Bob to ``his state
at the beginning of the $r$-th round''
and repeat the trial. Halt when all rounds are simulated. 
The expected number of trials for this simulation $2t$.
If the protocol is executed  in parallel (as in Section~\ref{applications}),
then the expected number of trials is $2^t$.}
So Bob can simulate his interaction with Alice,
and therefore gains zero knowledge about $X_A$.
%
%The proof that this is a secure zero-knowledge identification protocol
%follows the standard pattern.  (Alice can clearly always convince Bob
%of her identity if she follows the protocol, and Bob can compute
%transcripts of the protocol on his own with the same probability
%distribution as that generated by his interaction with Alice, so he
%gains zero knowledge about $X_A$. Details omitted in this version.)

We feel that this protocol is simple and clear enough that it forms an
excellent pedagogical example of a zero-knowledge identification protocol, 
such as may be used for high-school students. For a general discussion on 
interactive proofs, zero-knowledge and identification schemes the reader is 
referred to~\cite{QuisquaterGuillouCrypto89,FeigeFiatShamir88,GoldwasserMicaliRackoff89}.


\section{Security -- the model and background}


The goal with the classical constructions is to find a theoretical solution to
geometrical problems by using a  ruler and a compass, assuming that these have 
perfect precision. 
%It is not to draw figures to a high degree of accuracy.
The difficulty of finding solutions is not an issue: if a problem cannot 
be solved by ruler and compass then this is because there is no solution 
with these tools (and not because it is hard to find one).
We stress that with geometrical constructions the ruler should
be a simple straight-edge, and cannot be used for marking distances. 
%\footnote{A general angle can be trisected with a  compass and a ruler which can be 
%marked~\cite[Archimedes' construction]{Heath21}.} 
%

\subsection{Galois extension fields and impossibility proofs} 

Analytic geometry provides us with the means to associate the quantitative aspects
of geometrical objects (line segments, angles, etc) with real numbers (Desargues). 
We choose a coordinate system, and the points are represented by pairs $(x,y)$ of reals. 
In particular, ruler and compass operations will generate points 
whose coordinates are in number fields $Q'= Q(a_1,a_2,\ldots ,a_n)$, where $a_1,a_2,\ldots ,a_n$ 
are roots of quadratic extensions of the rationals $Q$ (Galois). We
call the roots, {\it radicals\/}. 
For example ~$3\sqrt{5}+2\sqrt{{6}-\sqrt{7}} \ $ is an element of $Q'$
with radicals $\sqrt{5}$, $\sqrt{7}$, $\sqrt{6-\sqrt{7}}$.

Let $Y$ be an angle to be trisected and $Q(\cos Y)$ the field
of all rational functions of $\cos Y$ over $Q$ (that is, numbers
of type $f(\cos Y)/g(\cos Y)$, where $f,g$ are rational polynomials).
>From trigonometry, $\cos Y = 4 \cos ^3 \frac{Y}{3}  - 3 \cos \frac{Y}{3} \, .$
Then the angle $Y$ can be trisected by ruler and compass only if,
%
%
\begin{equation}\label{eqn} 
\cos Y \ = \ 4 x^3  - 3 x ~\hspace{4 cm}
\end{equation}
%
%
has a solution $x$ in some extension field of $Q(\cos Y)$ with radicals
$a_1,\ldots ,a_n$.
It follows that  $\cos Y$ must satisfy an algebraic equation over 
$Q(a_1,\ldots ,a_n)$  which is not trivial.\footnote{For ruler and compass 
constructions such as angle bisections, this equation is trivial: 
only radicals are involved, and these cancel out.}
Therefore  $\cos Y$ is an algebraic number, and  the
set of angles which can be trisected is a subset of the reals which
has measure zero. Hence almost all angles $Y$ cannot be trisected.

A similar argument applies for the non constructibility of $\sqrt[3]{2}$
(doubling the cube), and more generally the non constructibility $\sqrt[3]{x}$, 
where $x$ is the length of randomly selected line segment. It follows that 
the operation of taking cubic powers of the lengths is also a one-way function.


\subsection{Random geometrical objects}\label{randomness}


Geometric constructions often involve selections of arbitrary geometrical objects
(for example when constructing the midpoint of a line segment one uses
an arbitrary circumference). 
In such cases it is normally understood that the corresponding numbers are in 
extensions of the rationals $Q$ with radicals. %quadratic roots. 
If an angle $X$ is chosen this way, then 
the angle $Y=3*X$ can be  trisected by ruler and compass 
(in this case equation (\ref{eqn}) has the solution $x=\cos X$, with
$\cos X$ a rational expression with radicals).

The angle $K$ (and $X_A$) used in the identification protocol is not
constructable by ruler and compass because it was chosen at random in the unit
circle of the real plane. Consequently,
$\cos K$ does not belong to any extension field of $Q$ with radicals, and the angle
$3*K$ cannot be trisected by ruler and compass given all previous constructions 
except $K$, as pointed out in the previous section. 

 
\subsection{\bf Historical background}


According to the Pythagorean doctrine, the {\it number\/} (that is, the rational number)
was the essence of all things. Mathematics,
philosophy and physics, were all based on numbers.
Pythagoras himself may not have been aware of the irrationality
of $\sqrt{2}$, but his followers did discover it.
%
This must have caused them considerable consternation,
and was kept secret for some time (irrational = $\alpha \! \lambda o
\gamma o \varsigma $, which, according to some scholars means, {\it  unutterable\/}). 
It was said that Hippasus, the first Pythagorean to divulge the unutterable,
was thrown off a ship and so perished~\cite{Heath21}.
%\footnote{There seems to have been a pledge of secrecy binding the school.}
The school however overcame this setback and later, according to Euclid,
was the first school to develop a general theory of irrationality~\cite{Heath21}. 

In the 5th and 4th centuries BC there was a proliferation of geometrical
constructions and theorems, many of which overlapped or were flawed. 
It became necessary to organize these results in some way.
% , because of the central role that mathematics played  in philosophy.
Tradition has it that Plato insisted that this task be based on
ruler and compass constructions. This approach was adopted by 
Euclid in his treatise on the {\it Elements\/} of geometry.

One of the most famous classical problems is ``squaring the circle''. 
Other such problems are ``doubling the cube''  and trisecting a general angle. 
More than a century ago it was shown that these problems cannot be solved by
ruler and compass (alone).
%
Recently Peter Neumann proved that Ptolemy's spherical mirror
problem (finding the point on a sperical mirror where a ray is reflected
from a source to an observer) cannot be solved 
by ruler and compass~\cite{Telegraph}.

For a general discussion on this topic the reader is referred 
to~\cite{QuisquaterGuillouCrypto89,CourantRobbins,Brittanica89}.



\section{Extensions of the identification protocol and other applications}\label{applications}


Many conventional cryptographic constructions can be replicated in
geometrical cryptography. Here we consider some of these, starting with two
extensions of the identification protocol in Section~\ref{protocol}.
The first extension is a parallel execution. The second, a ``multiple-secret'' version.

For the parallel execution, the $t$ iterations of the protocol 
are performed at the same time: Alice gives Bob $t$ copies of the
angles $R_i$ (step 1), Bob flips $t$ coins (step 2), 
and finally Alice gives Bob $t$ copies of appropriate angles (step 3).
%
The expected number of trials to simulate this execution
is $2^t$ (see Footnote~2). Since there are no complexity bounds
with  ruler and compass constructions, the protocol can be simulated.
Therefore the parallel execution 
of the identification protocol is also zero-knowledge. 
This is in contrast with conventional cryptography, for which it is not known 
if parallel executions of zero-knowledge protocols are zero-knowledge.


Next we consider a multiple-secret identification 
protocol. For this, Alice selects $k$ random angles 
$X_{A,1},X_{A,2}, \ldots ,X_{A,k}$, and
publishes their triples ~$Y_{A,1},Y_{A,2}, \ldots ,Y_{A,k}$. 
Then Alice proves to Bob that she knows {\it all\/} $k$ angles 
$X_{A,1},X_{A,2}, \ldots ,X_{A,k}$, by using the following
three-round protocol, which is repeated $t$ times independently.
\begin{enumerate}
\item 
Alice gives Bob a copy of an angle $R$, constructed as the triple of a 
random angle $K$.
\item
Bob gives  Alice the bit string $b_1,b_2, \ldots , b_k$ which is determined by 
$k$ coin flips (0 is ``heads'', 1 is ``tails'').
\item
Alice gives Bob a copy of the angle $L= K + \sum _{i=1}^{i=k} b_i X_{A,i}\, $,
and Bob checks  that $3*L=R+  \sum _{i=1}^{i=k} b_i Y_{A,i}\, $.
\end{enumerate}
%
Bob accepts only if the checks are valid for all $t$ iterations. 
For this protocol the error is $2^{-kt}$.

\subsection{An authentication protocol}

The identification protocol in Section~\ref{protocol} can easily be modified to get an 
authentication protocol. Let $m$ be the message which Alice wants to
authenticate. We require that the message be an integer. 
This constraint is not very restrictive and, essentially,  confines  
the messages that Alice can authenticate 
to constructable geometrical objects, since these objects are enumerable.


For the authentication  protocol Alice needs two secret angles $X_{A,1}, X_{A,2}$.
Alice publishes their triples $Y_{A,1},Y_{A,2}$. 
To authenticate $m$ to Bob, Alice proves to Bob that she knows the angle 
$Z = m*X_{A,1} + X_{A,2} \,$, by using the identification protocol
in Section~\ref{protocol} as follows. 

In step~1, Alice gives Bob a copy of the angle $R$, constructed as the triple of
a random angle $K$. In step~2, Bob flips a coin and tells Alice 
the outcome as a bit $b$. Finally in step~3,
Alice gives Bob the angle  $L= K + b\, (m * X_{A,1} + X_{A,2})$,
and Bob checks  that $3*L=R+ b\, (m * Y_{A,1} + Y_{A,2})$.


\subsection{Adding usable structure to geometric constructions}


Let $N$ be an additional angle. We can use $N$ as a modulus when adding or 
subtracting angles with ruler and compass constructions.
Suppose that $Y$ is an angle which is to be trisected \mbox{modulo $N$.} There
are three solutions to the equation ~$Y = 3*X \bmod N$ ~in $X$, which 
differ by multiples of $N/3$.
Anyone who knows two different solutions $X_1, X_2$ %of this equation
can therefore trisect the modulus $N$.
This property %approach 
makes it possible to replicate many of the cryptographic constructions
we use in number theory, where knowledge of two different square roots of
a  number $y$ modulo a number $n$ can lead to the factorization of $n$.
Here is one such %possible 
application. 

Suppose that the distribution of the random points in Axiom 5 is not uniform. 
Then the identification protocol in  Section~\ref{protocol} may fail to be
zero-knowledge, because it may not be possible to simulate the transcripts 
$(R,\mbox{``tails''},L)$ by selecting $L$ at random  
and solving $3*L=R+Y_A$ for $R$ ($R$ may not have the proper distribution).
This means that the protocol may ``leak'' some knowledge to Bob and make it
possible for Bob to construct the secret angle $X_A$ of Alice.
%Consequently the protocol may be insecure.
We shall show have our earlier observation may be used to strengthen 
the security of the identification protocol
when the distribution of the random angles is not uniform. 

First we observe that the distribution of the random angles should
%not be too restrictive.
be continuous.
In particular, the probability that any  specific angle $K$ is selected
should be zero. Otherwise Bob will get both the angles $K$ and
$L=K+X_A$, from which he can construct Alice's secret angle $X_A$.
Now suppose that $N$ is an angle that cannot be trisected by either Alice or Bob
({\it e.g.}, $N$ is selected randomly by a Trusted Center). 
To protect her secret angle  $X_A$,  Alice  will give Bob in the identification
protocol, {\it not\/} absolute angles but angles modulo $N$.
That is, she gives Bob the angle $R\, {\bmod N}$ in step 1,
and either $K {\bmod N}$ or $L\, {\bmod N} $ in step 3.
This will not turn the distribution of the angles to uniform, 
but it will destroy any possible discovery by Bob
about which of the three trisections of $Y_A$: $X_A$, $X_A +N/3$, $X_A +2N/3$, 
Alice used in $L$.
Even if Bob were given one of these, he would not know 
with probability better than $1/3$ whether this was Alice's.
%
%

If we assume that this scheme is breakable and that Bob can construct a trisection 
of $Y_A$ by analyzing the communication, 
then with probability $2/3$ this trisection will not be the one actually 
used by Alice.
Therefore it will lead with reasonable probability to an impossible trisection of the
angle $N$. 

A similar technique was used % proof was used 
to prove the security of parallel execution of the Fiat-Shamir 
identification protocol~\cite{FeigeFiatShamir88},
which is not known to be zero knowledge.

\section{Discussion and Conclusions}

We suggest that the field of geometric cryptography may be a fruitful one
for further study, as it may yield both illuminating examples and insight
into cryptographic fundamentals.

We leave as interesting open problems the development of other
primitives of geometric cryptography, such as secure encryption
techniques or secure signature schemes.  (We note that Rompel's proof
\cite{Rompel90} that ``one-way functions are necessary and sufficient
for secure signatures'' may not apply here, since his proof depends upon
the binary representation of messages and ciphertexts.)

\subsubsection*{Acknowledgments}

We dedicate this paper to Jose Pastor, who organized a marvelous gala
dinner at Eurocrypt '96, at which dinner this research began.


\bibliography{/a/rivest/papers/crypto%%%,other bibliographies
}

\begin{thebibliography}{1}


\bibitem{CourantRobbins}
R. Courant and H. Robbins.
What is Mathematics? An elementary approach to ideas and methods,
Oxford University Press, 1943.

\bibitem{Heath21}
T. Heath. 
\newblock A History of Greek Mathematics, Vol 1, Oxford University Press, 1921.

\bibitem{Brittanica89}
%Brittanica. \newblock Geometry. \newblock In 
\newblock 
{\em The New Encyclop{\ae}dia Brittanica}, Volume 19, Geometry, 
%pages 927--1000, 1989.
pages 887--936, 1995.
%
%Encyclop{\ae}dia Brittanica, 1989.
%\newblock (Volume 19).

\bibitem{Rompel90}
John Rompel.
\newblock One-way functions are necessary and sufficient for secure signatures.
\newblock In {\em Proc.\ $22$nd ACM Symp.\ on Theory of Computing},  ACM,
Baltimore, Maryland, 1990, pages {387--394}.

\bibitem{FeigeFiatShamir88}
U. Feige, A. Fiat and A. Shamir.
Zero Knowledge Proofs of Identity,
{\em Journal of Cryptology}, Vol~1, pages {77--94}, 1988.


\bibitem{GoldwasserMicaliRackoff89}
S. Goldwasser, S. Micali and C. Rackoff.
\newblock The Knowledge Complexity of Interactive Proof Systems.
\newblock {\em Siam J. Comput.}, Vol 18 (1), pages {186--208}, 1989.


\bibitem{QuisquaterGuillouCrypto89}
J-J Quisquater, L. Guillou, et al.
\newblock How to explain Zero-Knowledge Protocols to Your Children.
\newblock In {\em Advances in Cryptology -- Crypto '89}, 
Lecture Notes in Computer Science \#435, 
\newblock G. Brassard ed., Springer-Verlag, Berlin 1990,
pages {628--631}.


\bibitem{Telegraph}
The Daily Telegraph. University don solves the last puzzle left by the
Greeks. April 1, 1997.
%Not an April fools-day prank.
 
\end{thebibliography}

\end{document}

