Feature

Public Key Cryptography,
Number Theory and Applications
Preda Mihăilescu (University of Göttingen, Germany) and Michael Th. Rassias (ETH Zürich, Switzerland)
In this article we review the advent and development of public key cryptography. The exposition is driven by the application aspect, while providing more details for certain issues inwhich beautiful number theory is involved.

1

Introduction

In the early 1970s, the US army entertained the ARPA-net, anancestor of the internet, and between 1972 and 1974 a numberof universities on the East and West Coast were connected tothis net for research and experimental purposes. The notionof remote computer-communication became tangible for theusers of the net. It is conceivable that, under these conditions,the question of how to communicate in a secure way in a wide
area net – like the ARPA – became an actual reality for thoseusing the net. In fact, the concept of public-key cryptography,
which gives the simple conceptual frame for algorithms successfully solving this problem, was born in Stanford from thejoint work of W. Die and R. Hellman who studied public
key infrastructures and R. Merkle who studied secret key distribution. Here is the way Die and Hellman presented the
problem in [DH], a paper which mentions the joint work with
Merkle: “In turn, such applications (fast computers) create aneed for new types of cryptographic systems which minimize
the necessity of secure key distribution channels and supply
the equivalent of a written signature.”
Public Key Cryptography arises
The idea was remarkably simple and ecient. Traditionally, a
protected communication was established by using secret key
cryptography. Two major characteristics of this craft, whichstill played an important role during the Second World War,are that the sender and receiver must agree upon a common secret key prior to communication and that it was awidespread conception that keeping the encryption method
secret was a sensible method for increasing security. In a wide
area communication network, in which numerous peers cancommunicate over large distances, the chance of establishinga common secret key prior to communication are low. Thiswas more than just an abstract realisation of the inventors of
public key cryptography; it was a fact of which all users of
the ARPA-net were aware.
The new concepts are widely known and are currently
taught in school. We will briefly review them in order to introduce notation which will be useful when discussing someinteresting instances, allowing us to bring in more mathematics. If X is any peer who wants to engage in secure network
communication, he should start by generating a set of data,
which is bundled into his own secret key S X . A subset of thisdata, bundled in the public key PX will be made public to all

EMS Newsletter December 2012

peers with whom he might wish to communicate. The two
keys should have the following two properties:
1. Both keys can be used for encrypting texts according tosome algorithm yet to be defined; messages encrypted by
S X can be decrypted by PX and vice versa. Moreover,the keys should be suciently random: the chance of two
peers accidentally generating the same secret key should
be close to zero.
2. It should be computationally unfeasible to derive S X fromPX .
On the basis of these premises, if two peers A and B – cryptographers like using names so these peers are often called
Alice and Bob – want to communicate, then Alice sends to
Bob messages encrypted by PB , which she may retrieve fromthe public key repository. However, only Bob can decrypt themessage so the communication is secure. On the basis of thisidea, a further application emerged: it is often useful to be able
to certify the ownership of some message, to sign the message
in a unique and non-repudiable way. In this case, secrecy isless of a concern than ownership. The solution consists of associating a short cryptographic hash-value H to the message,
which is encrypted by the secret key S A . Any receiver willthen be able to regenerate the hash value on their own, decrypt
the encrypted hash with PA and then compare the two results.
If they match, Bob has a proof that it was Alice who has sent
the message. It was in the same context that the paradigm
was set that security of encryption algorithms is increased bytheir becoming public and not the contrary, as had been previously perceived. The reasoning behind this is that algorithms
known to the scientific community would be well analysed
and the process of academic scrutiny would help select themost secure and ecient algorithms. Security lays solely inthe secrecy of the keys is the slogan of this paradigm. In fact
this sensible point of view quickly spread within the scientificcommunity. Public key cryptography changed not only theconcept of secret communication but also the way of perceiving security: an algorithm is more reliable when it has longresisted public scrutiny by the cryptographic community andnot when it is based on sophisticated “secret tricks". Within
the next 20 years this point of view probably reached mostof the banks. In the late ’90s, manufacturers of cryptographic
hardware had only a precious few customers insisting on the“privilege" of purchasing machines which ran according tosome unique and “secret" algorithm.
The invention of the classical systems: DH and RSA
In the next two years after the abstract definition of publickey cryptography, two major algorithms that implement thisidea and are still in use today were invented. The first is basedon the diculty in solving the discrete logarithm problem inthe multiplicative group of finite fields and it was proposed25

Featureby Die, Hellman and Merkle, the inventors of public key
cryptography. The algorithm was initially meant to serve fora variant of the public key cryptography idea, in which Alice and Bob only wish to establish a shared secret key – they
do not wish to encrypt with the same algorithm; rather, they
will proceed by using the secret key for some classical, fastersecret key encryption scheme. Incidentally this two-step approach to encryption is the core idea in the TSL protocol, developed between 1992 and 2002 and currently used in all confidential https communications on the internet – for instancewhen you book a flight or buy a book from Amazon.
If Fq is some large finite field and g Fq is a generator of
the multiplicative group of the field – both being public data –then Alice and Bob start by choosing some random one timekeys AR  BR which are elements of Z ((q  1)  Z). Then Alicesends to Bob MA  gAR and receives from Bob MB  g BR .
The reader can verify that by using the private data and thedata received, both Alice and Bob may retrieve S  gAR BR ,which is the data from which the common secret key is extracted. However, an eavesdropper, who is always called Eve1
in cryptography, would only know gAR and gBR but not AR
or BR . The problem of recovering these secret data from theones communicated on the net is the discrete logarithm problem in finite fields, which is known to be a hard problem.2 It
is however not hard in the strong sense of complexity theory,
since it is not known to reduce to any NP complete problem;the same holds in fact for the problem of factoring integers.
The procedure is widely known as the Die-Hellman key exchange algorithm and it does not provide a direct solution to
the problem of public key encryptiondecryption and of signatures.
This was provided one year later, in 1977, by R. Rivest,
A. Shamir and L. Adleman at MIT. Their algorithm, widely
known as RSA after the initials of their names, uses the problem of factoring integers as the problem intended to prevent
recovery of the secret key from the public ones. A secret key
consists of S A  p q d, where p q are two large primes
satisfying some additional randomness conditions and0  d  (p  1)(q  1)
is a random number; ifwith (d pq(p  1)(q  1))  1

e N such that ed  1 mod (p  1)(q  1)
the public key consists only of PA  (n e), with n  p  q.
In some instances e is a fixed number for the whole system,so d will be determined by the holder of the secret key using the same defining congruence. With these prerequisites,
if M is a short message, it will be identified with a number in
Z (n Z) and its public key encryption Me  M e mod n can becomputed in the open but can only be decrypted by Alice, theholder of d, since M  Med  M ed mod n. Conversely, if Alice encrypts M with d, then anyone can recover M and upon
doing so will have proof of Alice having produced the encryption; indeed, only the owner of the secret key could produce
this encryption, which can thus act as a private signature of
Alice.
In 1978, Hellman and Merkle invented a public key cryptosystem that did not rely on number theory but rather on the
NP-complete knapsack problem. In 1983, J. L. Massey and J.
K. Omura developed a variant of the Die-Hellman key exchange, which works as a public key encryption scheme too.

26

It has the advantage that, like for the key exchange, a single
public key can be used by a whole domain – the public key
consists of a large prime p and a generator g Fp .
Despite initial attempts of the NSA to inhibit the publicising of the ideas of public key encryption and RSA, these hadalready been brought to public perception in 1977 by Martin
Gardner in his widely read column Mathematical Games in
the Scientific American magazine and were eventually published in the communications of the ACM [RSA]: the way topublic key cryptography was open! While the NSA tried tostop the diusion of the public key idea, it turned out that theidea had already been invented in 1970 by a researcher for
MI6’s General Communication Head-Quarters GCHQ, who
had also discovered the DH and RSA algorithms in 1971
and 1972 . . . but in the reverse order, with RSA discovered
first. The information was declassified and made public in
2000 and the director of RSA’s research team Dr Burt Kaliski
confirmed the truth of the information. This news was accepted with some reticence by the community, which speculated upon an a posteriori wish for academic acknowledgement from a person who had accepted working in secrecy.
However, both the idea and the most widely spread instancesof public key cryptography have the making of good mathematical work - they were discovered independently by people
working on the same question.
2

Cryptanalysis

The first major success of public key cryptography was thatthe expectation came true and the domain of cryptanalysis –concerned with the analysis of possible attacks against cryptographic schemes – became a flourishing academic domain
of investigation. One of the most spectacular successes wasdue to the development of the lattice reduction algorithm by
A. Lenstra, H. Lenstra Jr. and L. Lòvasz, the LLL-algorithm.
Given a lattice Zn , there exists a base consisting of
shortest vectors. Classical algorithms for finding such a base
are known from the work of Charles Hermite. Only, in thecase when the base is presented by an initial generating system of very large vectors, the process is exponential. The algorithm was developed from techniques used by Lòvasz ininteger programming; the idea was to use an approximate
Gram-Schmidt-reduction which provides some close to minimal vectors in . The advantage is that the algorithm runsin polynomial time and has therefore a wide variety of applications both in cryptography and in number theory itself.
One of the first applications of LLL was in showing that thekeys of the knapsack cryptosystem could be cracked in polynomial time: in order to do that, one had only to solve a particularly simple subfamily of problems belonging to the knapsack family. This result showed the advantage of public academic scrutiny of cryptographic schemes, since it had only
taken five years to reveal the weaknesses of one of them, but it
also blocked the way for applications of the knapsack. Some
improved versions have been presented that could never be
attacked – but they never made it to public applications.
The most important eect of cryptanalysis was less visible. The community quickly developed its own language anddefined a variety of subtle attack scenarios, in which theeavesdropper Eve was oered increasing levels of advantages:

EMS Newsletter December 2012

Feature
Eve can simply tap a wire communication or she might alsocollect large amounts of data signed by Alice or even induce
her into signing a chosen suite of messages. Later, the encryption hardware began being regarded as a point of attack, as it
was observed that physical measurements on a chip while it iscomputing an RSA encryption may reveal some bits of the secret key. In this way, well defined attack scenarios are used forchecking the security of various cryptosystems and protocols.
This is a good place to mention the fact that cryptographyadvances with a tension between the needs for security and foreciency. It has happened repeatedly that the latter has led tothe usage of particular constellations of keys that allow for
faster computations. But eventually, when simplification hasreached too far, an attack has been discovered; certain keys,
or even whole cryptographic schemes, are then discarded. It is
for instance useful to have a universal, short public exponent
e for the RSA scheme and this had also been used in practicein the late 1980s. But D. Coppersmith showed that if e is too
small, it is easy to gather suciently many messages signedby the same key S A and then use simple arithmetic in orderto crack that key. Therefore, the smallest fixed key currently
allowed by standards is e  216  1 and this may change withthe growth of computing and storage capacities.
It is easy to verify that an ecient method for factoring
integers breaks the RSA scheme and a solution to the discrete logarithm problem breaks the DH key exchange and theMassey-Omura cryptosystem. On the other hand, there is no
proof either for the expectation that ecient attacks on RSA
are equivalent (in a complexity theory understanding) to factoring integers, or that breaking the DH scheme is equivalent to solving the discrete logarithm problem. In fact various
scenarios of cryptanalysis investigate conditions under which
successful attacks can be completed without solving the underlying hard problems.
The closest mathematical problem is the DH-problem:
given a prime p and a generator g Fp , let
A  ga  B  gb  C  gab

Fp

be given for unknown a b Z ((p  1)  Z); find the values ofa and b. It is used for theoretic analysis of provable securityof cryptographic schemes, the investigation of which was initiated by Maurer [Ma] and established by Shoup and various
coauthors, e.g., in [CS].
Dickman’s Theorem and its impact
In the 1930s, J. Dickson considered the question of estimating the largest prime factors of some random integer n. Using heuristic estimates on the repartition of primes he foundfor instance that if pn is the largest prime dividing n thenp  O(nln 2 ). More generally, an integer n 1 is y-smooth if
none of its prime factors exceeds y. The function
(x y)   1  n  x : n is y - smooth 

counts the smooth numbers less than x. Dickman also provedthat for all u 0 there is a real number (u) such that
(x x1 u )  (u)xThe function (u) was described in terms of a dierential
equation, in which u was fixed for x. Half a century
later, the gap was filled by Canfield, Erdős and Pomerance[CEP], who proved thatEMS Newsletter December 2012

Theorem 1 (Canfield, Erdős and Pomerance).
(x x1 u )uxuuo(u) uniformly, for

(1)(1  ) ln x ln ln x when uThis theorem is at the heart of all the state-of-the-art algorithms for factoring integers and discrete logarithm in multiplicative groups. The classical application to factoring integers is the quadratic sieve method and it has its origin in thefollowing simple observation of Fermat: if m is a composite
integer then the congruence x2  c mod m will have at least
four solutions and there are x y such that x  y mod m but
x2  y2 mod m. Then (x  y m) is a nontrivial factor of m.
Theorem 1 helps find such pairs x y, as follows: for numbersx(i) in some interval  n  i 0  i  B, one computes theremainder3
r(i)  x(i)2 rem m
and retains only those values of x for which r is a B-smooth
number. By choosing B accordingly, it is possible to factoriser(i) eciently. After gathering suciently many such relations, one may hope that the product of some r(i) is a square:
namely, that there is an index subset J  [0 B] such thatr(i)  R2  R Zi JThen letting X  i J x(i), we obtain the congruence X 2 
R2 mod m. If, in addition, X  R mod m, which should happen with probability  1 2, then (X  R m) is a nontrivial factor of m. The method relies on some empirical assumptions
on the repartition of factors of r(i): namely, that the distribution of these residues is such that one may apply the relation(1) for estimating the probability that one of these numbers is
B-smooth. These allow one to establish an optimal boundB  exp( ln(m) ln ln(m))
This and similar functions occur often in algorithms usingsmoothness, so it received a name:
L(n; a) : exp ln(n)a ln ln(n)1a In our case B  L(n; 1 2) and the quadratic sieve runs in timepolynomial in B – experience having so far confirmed the underlying heuristical assumptions. The following nice example
is taken from the book of R.
 Crandall and C. Pomerance [CP]:let m  1649, with 41   m. We find412  32 mod m;

422  115 mod m;

432  200 mod mSince 32200  253 52  802 , we let R  80 and X  4143 
422  1  114 mod m, finding that 1142  802 mod m andeventually 17  (114  80 1649), which is a nontrivial factor.
For the discrete logarithm problem in Fp , which consists of determining x such that g x  b mod p, one uses
smooth numbers as follows. Fix a smoothness bound y andlet q1      qr  y be all the primes up to y. For random values of m, one computes u  gm rem p and keeps only thosevalues of u which are y-smooth. After collecting suciently
many relations, one will then be able to compute the discrete
logarithms li such that qi  gli mod p. Next, one tries random
values of k searching such ones that make v  bgk rem p bea y-smooth number. The precomputed values li will then help
determine x  k  log p (v) from the prime decomposition of27

Feature
the v. This algorithm also relies on heuristic assumptions,onthe basis of which the running time is L(p 1 2) 2 .
At the end of the 1980s, John Pollard found a way of applying the idea of the quadratic sieve to integers in number
fields rather than Q. The method was first applied to the fac9
torisation of the Fermat number F9  22  1. In the following
years, it was generalised and improved by a series of mathematicians, starting with A. Lenstra and M. Manasse. The
resulting number field sieve is currently the asymptoticallyfastest factoring method and it runs in time O(L[n; 1 3]). Similar methods are known for the discrete logarithm method:they use number fields in case of larger characteristics andfunction fields for small characteristics. Like in the case offactoring, their running time is also O(L[n; 1 3]). Current
records reach as high as 7–800 binary digits for factoring
composites of general form and  5–600 for the discrete logarithm in prime fields.
3

Elliptic curves

In 1984, René Schoof opened the way for discovery of a polynomial time algorithm for counting the number of points onan elliptic curve over a finite field. This brought the groupsof algebraic geometry to the realm of applications and algorithms. Within one year, H. W. Lenstra Jr. proposed an important variant of Pollard’s rho-method for factoring, basedon elliptic curves: the ellptic curve method or ECM. Also,
V. Miller and N. Koblitz proposed independently the use of
elliptic curves for cryptography. The ECM method has a runtime comparable to the quadratic sieve but it behaves particularly well for numbers m which have some small prime factors(i.e. sensibly
smallerthanm: the runtime is estimated to be
L(p; 1 2) 2 , where p is the smallest prime dividing m).
Counting points
The idea of Schoof is both elegant and important, beyond eventhe immediate algorithmic and cryptographic applications: it
led to an area of research for practical algorithms for counting points on finite varieties. This research area is still growing, while the main domain of application has ceased to be
cryptography for at least a decade. The algorithms are more
and more used for larger computations related to mathematical questions such as the Birch Swinnerton-Dyer conjecture
and other properties of L-series. See also [Ra] for an interesting elementary theoretical application of point counting.
Initially, Schoof [Sc1] started from the following simple
remark: if E p (a b) : Y 2  X 3  aX  b is an elliptic curve
defined over the finite field F p , of which one assumes that itis ordinary, then Riemann’s conjecture for elliptic curves implies that, in End(E p  F p ), the Frobenius verifies the quadratic
equation2  t  p  0

(2)

Since E p is fixed by , we have E p (a b)  pt1. Counting
the points is thus equivalent to determining the value of the
trace of the Frobenius t; since the Hasse inequality states thatt  2 p, it suces to determine the remainder t rem forsome small primes with


L
2 p

28

Therefore, the core step of the algorithm consists of modellingthe -torsion E p [ ] into an algebraB  F p [X Y]  (X) Y 2  (X 3  aX  b) P  X  ( (X)) Y  (Y 2  (X 3  aX  b)) B

in which  (X) is the -division polynomial which has as roots
all the x-coordinates of -division points. Therefore, any such
point enjoys the properties which define the generic -torsion
point P B. It is then a straightforward computation to determine t rem from the identity
2 P  pP  tP

The seminal idea of Schoof to determine the parameters of
the Riemann -function from projections in torsion spaces,
and thus counting points on varieties over finite fields, wasboth improved for simple varieties, such as elliptic curves,and extended to more general abelian varieties. In the firstcase, the primary thing to do was to reduce the size of thealgebra B – which can be done by finding smaller factors of (X) mod p.
The breakthrough in this direction was indicated by Noam
Elkies (see [Sc2]), who brought in modular forms, thus showing how to find in half of the cases some factors f (X) (X) of
linear degree, compared to the quadratic degree in of the division polynomial. The -torsion E p [ ]  F2 as a vector space,fixing two linear independent points P Q E p [ ], we see thatG : Gal (B F p ) acts on the vector space E p [ ] by acting on
the base P Q. We obtain a representation  : G
GL2 (F ),with respect to which () verifies the same quadratic equation. If  is the discriminant of this  equation, according to
the value of the Legendre symbol 
1 0 1, the matrix
() is diagonalisable, has normal upper triangular form or
has eigenvalues in F 2 . In the first case, there are two eigenpoints P Q of the Frobenius and the orbit of their x coordinates under multiplication on the curve is galois invariant. We
obtain the eigenpolynomialsfP (X) 

(
1) 2
k1

where

(X  ([k]P) x )   (X)deg( fP )  (  1) 2 anddeg( )  ( 2  1) 2

together with a new algebra B , obtained by replacing with fP . For the computation of F P , Elkies considered thefunction field C[[ j(q)]]. Some classical arguments on Eisenstein series and 0 ( )-modular forms imply that for each jinvariant jm of an -isogenous curve to E p – or, also, foreach zero of the modular equation  (X j(q)) – there is apolynomial f j (X) C[[ j(q)]][X] which has the x-coordinatesof the kernel of the respective isogeny as zeroes. The polynomials can be constructed in the function field by manipulations of q-expansions and they have the useful property
that all the coecients are algebraic integers. The insight of
Elkies was to show that one can substitute for jm the valueof some zero  (X j(E p )) mod p and reduce the coecientsof f j (X) modulo p, thus obtaining some eigenpolynomial corresponding to the value of jm . Indeed, if E is any curve overQ which reduces to E p at some prime ideal above p then its
j-invariant reduces to the one of E p and so do the invariants

EMS Newsletter December 2012

Featureof its -isogenies. Therefore, if the modular equation has linear factors jm over F p , by inserting these in the expression
for f j (X), upon reduction at the same prime, the coecientsof the polynomial f j map to the ones of some eigenpolynomial. Using improved algorithms for manipulation of series [BMSS], one can compute the eigenpolynomials in timeO(log3 (p)), the running time being dominated by the computation of zeroes of  (X j(E p )) mod p. Further improvements
can be achieved by using the galois structure of the resulting
algebras [MV].
For curves defined over finite fields of small characteristic p, it is possible to project to pN -torsion. Using dierent
flavours of cohomology combined with Newton iterations,various authors starting with T. Satoh, K. Kedlaya and A.
Lauder have developed the most ecient point counting algorithms for elliptic curves. Some of them are generalised tosuper elliptic curves, elliptic surfaces, etc.
Cryptography
The elliptic curve based cryptographic schemes which havesurvived scrutiny and become part of current standards on
public key cryptography are essentially variants of the DieHellman key exchange scheme and are based on the dicultyof solving the discrete logarithm problem: find x such that[x]P  Q

for

P Q

E p (a b)being points on an elliptic curve, such that Q is known togenerate a cyclic group of high order. Unlike in finite fields,
the DL problem on elliptic curves is not known to allow any
sub-exponential time solutions. The best known methods have
runtime O( p), where p is the characteristic of the (prime)
field over which E p is defined. As a consequence, one canwork in much smaller groups than in the case of the multiplicative groups of finite fields, still achieving the same estimated security of a scheme, with respect to state-of-the-art
attacks. This advantage led to a new wave of interest for elliptic curve cryptography in connection with security of mobile
phones. Over the last two decades, the evolution in this direction oscillated between the search of special curves with mostecient group operations4 and the care required to maintain security, when using special cases. The core problem inthis respect is the reduction to the discrete logarithm in finite
fields, using Weil pairings and descent methods. The use of
the Weil pairing for the discrete logarithm on some special
elliptic curves was pointed out for the first time by Gerhard
Frey. The problem came to light when Frey was asked to estimate software using special curves with fast group operation for its security. He was able to show that for the specificcurves, the Weil pairing reduced the elliptic curve logarithm
problem to one in finite fields of critically small size. The
idea was taken over by A. J. Menezes, P. C. van Oorschot
and S. A. Vanstone and is currently known in the literature
under the name of MOV attack. Much experience has beengathered in this field yet, even nowadays, the attraction of efficient arithmetic for mobile phones leads to the use of special
curves – e.g. the so-called Koblitz curves, defined over fields
F p of small characteristic and having a b F p – which areclose to the critical area where one may expect that reduction to some feasible discrete logarithm in finite fields is justone idea away. Despite standardisation, which made crypto-

EMS Newsletter December 2012

graphic developments obsolete on the internet, there are thus
reasons why research in this particular area is still very fertile. We recommend the detailed and lively survey of Heß etal. [HeSSL].
4

Quantum cryptography and other interesting
applications

The main intensively used public key cryptography methods
rely on the number theoretic problems described above. There
have been numerous interesting attempts to use the large listof NP complete problems in order to derive some trapdoor
function (the one allowing the concealment of the secret key
behind the public ones) – the knapsack problem is only oneof the most famous ones. We can hardly go into the detailnecessary in order to pay justice both to the interest of theattempts and the reasons for their failure or restricted use.
One cannot complete even a brief survey of public key
cryptography without mentioning several examples whichhave withstood the test of time and do have either a theoretical interest or even a practical niche of application. Since
the early 1980s the Canadian mathematicians G. Brassard and
C. Crépeau have suggested the use of quantum eects for security applications: the simple idea was that Eve could not
tap a quantum communication wire without destroying the information content transmitted, so security would be provided
by a self-destruction mechanism introduced by quantum mechanics in the confidential information transmitted. The physical and cryptographical aspects of the idea have been in active research ever since and, in the first decade of this century, several practical implementations of quantum5 cryptography have been announced, reaching over distances of up to
100 km.
Public key cryptography is much slower than secret key
encryption – by at least a factor of 1000, as a rule of thumb.
This has led to the wish to design some fast asymmetricschemes, even at the cost of, say, very large keys. A successful solution in this respect was invented by three number theorists: J. Hostein, J. Pipher and J. H. Silverman, who called
their method “Number Theorists aRe Us”: NTRU [HPS]. The
method found a niche of applications and has the intriguing
property that lattice reductions are used both for legitimate decryptions as well as for attacks. The asymmetry is thus not one
between polynomial and exponential algorithms but is rather
due to the high dimensions of lattices in which reduction must
happen for the attacker.
A further family of interesting public key schemes uses
non commutative groups – such as, for instance, braid groups(e.g., see [MSU]). Their developers make a point out of thefact that, if one day quantum computing is feasible, all number theoretic schemes can be broken in short polynomial time.
However, using the current models of quantum computing, noattack to braid group cryptography is known.

Notes
1. This is one of the few instances of which we are aware in whicha politically incorrect denomination introduced in the ’70s, wasneither revindicated nor changed up to the present. The reason

29

Feature
may possibly lay in the fact that political correctness lacks fantasy, so people can hardly imagine Adam oering the apple toEve.
2. It has been neither proved nor disproved that solving the discrete
logarithm problem is the only way for Eve to recover the secretkey S . Since this is an independent problem of interest on its
own, it has received more recently a name: the DH - Problem,
after Die-Hellman.
3. In computational algebra, the notation x rem y stands for theunique representative of the equivalence class of x mod y which
lays in the interval [0 y).
4. On the one hand, the base fields are much smaller – 200 bits
for the size of the base fields is still a very safe bound, which
compares well, in terms of security, to RSA moduli of over 1000
bits – but on the other hand additions on a curve require more
operations than a mere multiplication in Z (n  Z). This explains
the reason for the eciency struggle.
5. The reader should not confuse quantum cryptography with quantum computing, where quantum eects are used to help computations and not only secure information transmission: the physicalchallenges are even larger in the latter case.

Bibliography[BMSS]
[CEP]
[CS]
[CP]
[DH]
[EL]

[HeSSL]
[HPS]
[Kb1]
[Kb2]
[Len]
[Ma]

[MV]
[ML]

[MSU]

30

A. Bostan, F. Morain, B. Salvy and É Schost: Fast
algorithms for computing isogenies between elliptic
curves, Math. Comp. 77 (2008), 1755–1778.
E. R. Canfield, P. Erdős, C. Pomerance, On a problem
of Oppenheim concerning Factorisatio Numerorum, J.
Number Theory 17 (1983) 1–28.
R. Cramer and V. Shoup, Signature Schemes based onstrong RSA assumptions, Extended abstract in Proc.
ACM CCS 1999.
R. Crandall and C. Pomerance, Prime Numbers – A
Computational Perspective, Springer, 2004.
Whitfield Die and Martin Hellman, New Directions
in Cryptography, IEEE Transactions on Information
Theory; Nov. 1976.
N. D. Elkies, Elliptic and modular curves over finite
fields and related computational issues, Computational
Perspectives on Number Theory: Proc. Conf. in honourof A. O. L. Atkin (D. A. Buell and J. T. Teitelbaum,eds.), AMSInternational Press, 1998, 21–76.
F. Heß, A. Stein, S. Stein and M. Lochter, The Magic ofElliptic Curves and Public Key Cryptography, Jahresbericht Deutsch Math.-Ver. 114 (2012), 59–88.
J. Hostein, J. Pipher and J.H. Silverman: An Introduction to Mathematical Cryptography, Springer (2008)
N. Koblitz, Elliptic curve cryptosystems, Math. Comp.,
48(1987), 203–209.
N. Koblitz, Course in Number Theory and Cryptography, Springer-Verlag, New York, 1994.
H. W. Lenstra, Factoring integers with elliptic curves,
Annals Math., 126(3)(1987), 649–673.
U. Maurer: Towards the equivalence of breaking
the Die-Hellman protocol and computing discrete
logarithms. Advances in Cryptology – Crypto ’94,
Springer-Verlag, (1994), 271–281.
P. Mihăilescu and V. Vuletescu, Elliptic Gauss sums
and applications to point counting. J. Symb. Comput.
45, 8(2010), 825–836.
V. Miller, Uses of elliptic curves in cryptography,
Advances in Cryptology: Proc. of Crypto ’85, Lecture Notes in Computer Science, 218(1986), SpringerVerlag, New York, pp. 417–426.
A. Myasnikov, V. Shpilrain and A. Ushakov, Group-

[Ra]
[RSA]
[Sc1]
[Sc2]
[Sil]
[Was]

based Cryptography, Advanced Courses in Math.
CRM Barcelona, Birkhäuser Verlag (2008).
M. Th. Rassias, On the representation of the numberof integral points of an elliptic curve modulo a prime
number, http:arxiv.orgabs1210.1439.
R. Rivest, A. Shamir and L. Adleman, A method for obtaining signatures and public key cryptography, Communications of the ACM, 21 (1978), 121–126.
R. Schoof, Elliptic Curves over Finite Fields andComputation of Square Roots mod p, Math. Comp.
43(1985), 483–494.
R. Schoof, Counting Point on Elliptic Curves over Finite Fields, Journal de Th. des Nombres Bordeaux,J. Silverman, The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics 106, Springer-Verlag, New
York, 1986.
L. C. Washington, Elliptic Curves-Number Theory and
Cryptography, CRC Press, London, New York, 2008.

Preda Mihăilescu [preda@uni-math.gwdg.
de] was born in Bucharest, 1955. He studied
mathematics and computer science in Zürich
receiving his PhD from ETH-Zürich. He wasactive during 15 years in the industry, as
a numerical analyst and cryptography specialist. In 2002, Mihăilescu proved Catalan’sconjecture. This number theoretical conjecture, formulated by
the French mathematician E. C. Catalan in 1844, had stoodunresolved for over a century. The result is known as Mihăilescu’s Theorem. He is currently a professor at the Instituteof Mathematics of the University of Göttingen.
Michael Th. Rassias [michail.rassias@math.
ethz.ch] was born in Athens, 1987. He received his school education in Athens, during which he participated at various mathematical contests; he has received two gold
medals at the Pan-Hellenic Mathematical
Olympiads of 2002 and 2003, a silver medal
at the Balkan Mathematical Olympiad of2002 and a silver medal at the 44th International Mathematical Olympiad of 2003. He holds a Diploma from the School ofElectrical and Computer Engineering of the National Technical University of Athens and a Master of Advanced Study inMathematics from the University of Cambridge. He is currently a PhD student in Mathematics at ETH-Zürich, under
the supervision of Professor E. Kowalski.

EMS Newsletter December 2012