Quantum and Post Quantum Cryptography
Abderrahmane Nitaj
Laboratoire de Mathématiques Nicolas Oresme
Université de Caen, France
nitaj@math.unicaen.fr
http://www.math.unicaen.fr/~nitaj

Abstract
Public key cryptography is widely used for signing contracts, electronic voting, encryption, andto secure transactions over the Internet. The discovery by Peter Shor, in 1994, of an efficientalgorithm based on quantum mechanics for factoring large integers and computing discrete logarithms undermined the security assumptions upon which currently used public key cryptographic
algorithms are based, like RSA, El Gamal and ECC. However, some cryptosystems, called post
quantum cryptosystems, while not currently in widespread use are believed to be resistant to quantum computing based attacks. In this paper, we provide a survey of quantum and post quantum
cryptography. We review the principle of a quatum computer as well as Shor’s algorithm and quantum key distribution. Then, we review some cryptosystems undermined by Shor’s algorithm as well
as some post quantum cryptosystems, that are believed to resist classical and quantum computers.

1

Introduction

The purpose of cryptography is to protect the secrets of parties communicating in the presence ofadversaries. Many current public key cryptosystems depend upon classical intractable problems, suchas factoring large integers and solving the discrete logarithm. In 1994, Shor discovered a very importantalgorithm that would efficiently solve very hard problems if applied with a quantum computer. Thisshows that quantum computing will deliver unbelievable performance compared to classical computers.
A typical example is the factorization of integers problem. While this problem is believed hard forclassical computers, Shor’s algorithm can solve this type of problem relatively easily with linear timewith a quantum computer. So far, the best classical algorithm for factoringis the number field sieve [2],

1/3
2/3
which runs in sub-exponential time O exp c(log n) (log log n)
for some constant c. In contrast
Shor’s algorithm runs in time O ((log n)2 (log log n)(log log log n)) on a quantum computer, and thenmust perform O (log n) steps of post processing on a classical computer. Shor’s algorithm encouraged
the design and construction of quantum computers and was a motivator for the study of new quantum
computer algorithms and new cryptosystems that are secure from quantum computers, called postquantum cryptosystems.
In this paper, we will consider two kinds of cryptography: classical cryptography and quantum cryptography. Classical cryptography has many applications such as secure communication, identification
and authentication, key exchange, digital signatures, authentication and data integrity, electronic voting, electronic funds transfer, electronic commerce, certification authority, zero-knowledge and secret1sharing. The security of all these applications are based on some often believable hard problems. Typical examples of such hard problems are number theoretic problems. In the present days, two majorfamilies of cryptographic primitives dominate public key cryptography.
1. Primitives whose security is believed to be based on the difficulty of the integer factorization
problem. Typical examples are• The RSA cryptosystem [14] and a series of variants.
• The Rabin cryptosystem [12].
• The KMOV Cryptosystem [9].
2. Primitives whose security is believed to be based on the difficulty of the discrete logarithm problem
such as• The Diffie-Hellman key exchange [4].
• The El Gamal cryptosystem [5].
• The the Digital Signature Algorithm (DSA) [6].
• The elliptic curve cryptography (ECC) [8] and [11].
However, advances in quantum computers threaten to undermine most of these security assumptions.
Therefore, cryptographers have been led to investigate other mathematical problems to see if they canbe applied in cryptography. This makes post-quantum cryptography an important topic of research.
The organization of the paper is as follows. In Section 2, we review the principle of quantum
computers. In Section 3, we review two quantum algorithms, Shor’s algorithm for factorization and
the BB84 protocol for key distribution. In Section 4, we present two cryptosystems that are vulnerable
to quantum computers: RSA and El Gamal. In Section 5, we present three of the post quantum
cryptosystems, two are based on lattices, namely NTRU and LWE and one is based on codes, McEliece.
We conclude the paper in Section 6.

2

Quantum Computers

In this section we present a basic overview of a quantum computer.

2.1

Qubits

While classical computers operate on bits, a quantum computer operates on qubits, or quantum bits.
In physics, a qubit can be thought as one of the systems presented in Table 1.
SystemElectron
PhotonQubit state
Spin
Polarization

Table 1: Examples of physical qubits
For example, a qubit can be thought of as an electron in a Hydrogen atom with two state system,
the ground and the excited state or spin-up and spin-down. Quantum mechanics assert that a two state2

system can be in any superposition of the two basis states. The state of a qubit can be represented as avector |ψi in a two-dimensional vector space with orthonormal basis {|0i, |1i} and complexe coefficients:|ψi = a|0i + b|1i,|a|2 + |b|2 = 1.

a, b ∈ C,
|0i
b

|ψ
a

In column matrix formulation, the basis states are
 
1
|1i =
,
0

|1i

 
0
|0i =
.
1

Mathematically, a qubit is a 2-dimensional Hilbert space H2 so that the state of the qubit is an associatedunit length vector in H2 . A qubit can be in state |0i or in state |1i or in a superposition of the twostates, that is a|0i + b|1i. If a qubit is in state |0i or |1i, we say it is a pure state. Otherwise, we say it
is a superposition of the pure states |0i and |1i.
A classical bit can only be in one of two states, 0 or 1, but a qubit can be in any superposition
state. However a measurement of a bit will reveal the bit with probability 1 and will not change the bit.
Comparatively, a measurement of a qubit in the state a|0i + b|1i will yield |0i with probability |a|2 or |1iwith probability |b|2 . After measurement, the state will definitely be |0i or |1i. Hence a measurementof a qubit will irreversibly destroy the superposition.

2.2

Multiple Qubits

While the state of a qubit can be represented by a vector in the two dimensional complex vector space
H2 , spanned by |0i and |1i, a n-qubit system can be represented by a vector in a 2n -dimensional complex
vector space. For n = 2, the a2-qubit system corresponds to the tensor product H2 ⊗ H2 which is defined
to be the Hilbert space with basis |i1 i|i2 i with i1 ∈ {0, 1} and i2 ∈ {0, 1}. The possible basis states are|0i|0i = |00i, |0i|1i = |01i, |1i|0i = |10i and |1i|1i = |11i. In column matrix formulation, the basis
states are
 
 
 
 
0
0
1
0
0
1
0
0

 
 
 
|00i = 0 , |01i = 0 , |10i = 1 , |11i = 0 .
0
0
01
The basis state |i1 i2 i means that the first qubit is in its state |i1 i and the second qubit is in its state|i2 i. Consider a 2 quantum systems A1 and A2 , with A1 in state ψ1 = a1 |0i + b1 |1i and and A2 in stateψ2 = a2 |0i + b2 |1i. Then the 2 quantum systems is in stateψ1 ⊗ ψ2 = (a1 |0i + b1 |1i) ⊗ (a2 |0i + b2 |1i) = a1 a2 |00i + a1 b2 |01i + b1 a2 |10i + b1 b2 |11i,
with |a1 a2 |2 + |a1 b2 |2 + |b1 a2 |2 + |b1 b2 |2 = 1. Hence, an arbitrary state of a 2 qubit system can be
represented byXX
ai1 i2 |i1 i2 i, ai1 i2 ∈ C,
|ai1 i2 |2 = 1.
i1 i2 ∈{0,1}2

i1 i2 ∈{0,1}23This scheme can be generalized for a n-qubit system. An arbitrary state can be represented byXX
ai1 i2 ...in |i1 i2 . . . in i, ai1 i2 ...in ∈ C,
|ai1 i2 ...in |2 = 1.
i1 i2 ...in ∈{0,1}ni1 i2 ...in ∈{0,1}nHence a n-qubit has 2n basis states.

3

Quantum Cryptography

In this section, we present two quantum algorithms, Shor’s famous polynomial time quantum algorithm
for factoring integers and the BB84 protocol for key distribution.

3.1

Shor’s Algorithm

In 1994, Shor [16] proposed an algorithm on quantum computers for the integer factorization problem.
Shor also proposed an efficient quantum algorithm for the discrete logarithm problem. This illustrates
that quantum adversaries would break most of the widely used cryptosystems. The factoring algorithm
uses a well known reduction of the factoring problem to the problem of finding the period of a certain
function, and it uses the quantum Fourier transform to find the period, which is infeasible with classicalcomputers.
Shor’s algorithms have potentially important implications for many cryptosystems when their security is based on the assumption that factoring large numbers is difficult or on the difficulty of computing
discrete logarithms. Shor’s algorithm consists of two parts: a classical and a quantum part.
The classical part of Shor’s algorithm is as follows.
Input: An integer N .
Output: A non trivial factor of N .
1. If gcd(N, 2) = 2, then return 2.
2. Pick a random integer a with 2 ≤ a ≤ N − 1.
(a) If gcd(N, a) = a, then return a. This may be done using the Euclidean algorithm.
(b) Find the order r of a modulo N , that is the least positive integer r such that ar ≡ 1 (mod N ).
i. If r is odd, then go back to step 2.
ii. If ar/2 ≡ −1 (mod N ), then go back to step 2.

iii. Else return gcd ar/2 − 1 (mod N ), N and gcd ar/2 + 1 (mod N ), N .
The quantum part of Shor’s algorithm is as follows.
Input: A composite integer N and an integer a with 2 ≤ a ≤ N − 1.
Output: The order r of a modulo N .
1. Find a number Q = 2t such that N 2 ≤ Q < 2N 2 .
2. Start with a pair of input and output qubit registers with t qubits each, and initialize them to thestate|0i|0i = |00 . . . 00i|00 . . . 00i.
4

3. Apply a Hadamard gate to each qubit in the first register to obtain the state
Q−1

1 X
√
|xi|0iQ x=0This state represents a uniform superposition of all the computational basis states in the firstregister.
4. For each number x in the first register, calculate the quantity ax (mod N ) and store the result inthe second register. This produces the following state
Q−1

1 X
√
|xi|axQ x=0(mod N )i.

5. Measure the state of the second register. This reveals a particular value |ax0 (mod N )i for thecontents of the second register for some smallest value x0 , and simultaneously projects the stateof the first register into a superposition values of |x0 + bri with x0 ≤ x0 + br < Q, that is
Q − x00≤b≤,rwhere bxc is the greatest integer less than or equal to x. DefineQ − x0+ 1.
M=rThus the new state is

M −1

1 X
√
|x0 + bri|ax0
M b=0(mod N )i.

6. Apply the quantum Fourier transform to the first register. The quantum Fourier transform takes
the state |xi to the stateQ−1
1 X 2πiyx/Q
√
e
|yi.
Q y=0
Hence, the quantum Fourier transform changes the state
M −1

1 X
√
|x0 + bri|ax0
M b=0

5

(mod N )i.

to the state
M −1

1 X
√
M b=0

!
Q−1
1 X 2πiy(x0 +br)/Q√e|yi |ax0
Q y=0

M −1 Q−1
1 X X 2πiy(x0 +br)/Q=√e|yi|ax0
M Q b=0 y=0(mod N )i(mod N )i

M −1 Q−1
1 X X 2πiyx0 /Q 2πiybr/Q=√ee|yi|ax0 (mod N )i
M Q b=0 y=0
!
Q−1
M −1
1 X 2πiyx0 /Q X 2πiybr/Q|yi|ax0 (mod N )i.
ee=√
M Q y=0b=0

7. Perform a measurement on the first register. This yields the state |yi with probability
M −1
1 X 2πiybr/Q
Prob(y) =e
M Q b=02

1 1 − e2πiyM r/Q=
M Q 1 − e2πiyr/Q
2 πyM r
sin
Q
1
  .
=
M Q sin2 πyr

2Q

8. Define m to be the closest integer to yr, that is
Q



yr
m=
.
Q
Then






yr−mQ
yr−mQ
2
2
sin
πM
sin
πM
+
m
Q
Q
1
1
 
 =

 .
Prob(y) =M Q sin2 π yr−mQ + m
M Q sin2 π yr−mQ
Q

Q

Observe that Prob(y) is as higher as |yr − mQ| is small. Indeed,


yr−mQ
2
sin
πM
Q
1
M

 =
lim Prob(y) =lim.
|yr−mQ|→0|yr−mQ|→0 M Q
Q
sin2 π yr−mQ
Q

Q
Suppose that |yr − mQ| ≤ 2r
. Then

y
m
1
−
≤ 2.
Q
r
2r
It follows that mr , in lowest terms, is a convergent of the continued fraction expansion of Qy .
Consequently, the probability Prob(y) is large when mr is computed from Qy by the continued
fraction algorithm.
69. Compute the convergents of Qy . Let mr be a convergent with r < N . This procedure yields r if m
and r are coprime, but it fails if m and r have any common factors.
10. If y r 6≡ 1 (mod N ), then return to Step 1. On average, this procedure outputs the correct order rin log N number of repetitions for large N .
Shor showed that the quantum part runs in time O ((log n)2 (log log n)(log log log n)) on a quantum
computer, and then must perform O (log n) steps of post processing on a classical computer to executethe continued fraction algorithm.

3.2

Quantum Cryptography

Since the negative impact on public-key cryptography of Shor’s algorithms, quantum cryptography has
been developed from several points of view. Prior to Shor’s work, Bennett and Brassard [1] proposed
in 1984 a quantum key distribution scheme using quantum communication, called BB84. It concerns
three main characters, A and B, who try to share a secret key, and E, whose objective is to obtainsome information about the secret key. A and B have access to a quantum channel as well as a classicalchannel. We suppose that E has full access to the quantum channel but it is impossible for him tomodify the information sent through the classical channel. According to quantum machanic principles,
it is impossible to duplicate the quantum information. A sends single particles to B across the quantum
channel. The particles are produced in two different orthonormal bases, e.g. the rectilinear basis{|0i+ , |1i+ } and the diagonal basis {|0i× , |1i× } where1|0i× = √ (|0i+ − |1i+ ) .
2

1|1i× = √ (|0i+ + |1i+ ) ,2

In the BB84 protocol, to exchange a secret key, A and B must proceed as follows.
1. To send a sequence of n bits to B, A encodes each bit in the quantum state of a photon as in
Table 2: each bit is encoded in a random basis among the two bases.

Basis ⊕ = {| ↑i, | →i}
Basis ⊗ = {| -i, | %i}

0
↑
-

1
→
%

Table 2: Encoding bits
Then, A sends the n photons to B, each in one of the states | →i, | ↑i, | %i or | -i.
2. For each photon that B receives, he randomly chooses a basis among {| ↑i, | →i} and {| -i, | %i}
and measures the qubit with respect to the basis.
3. B informs A the basis he used via a classical authentication channel.
4. A checks whether his basis coincides with the basis he received. When both basis coincide, A
keeps the corresponding bit.
5. A tells B which bases were correct.

7

6. A and B can reconstitute a part of the random bit string created previously by A. Statistically,
the bases of A and B coincide in 50% of all cases, and the measurements of B agree with the bitsof A perfectly. Hence A and B continue with approximately n/2 outcomes for which the same
basis was used.
7. A and B verify measurement outcomes on random approximately n/4 bits of the n/2 common bits.
Hence, any attempt by E will be detected since E can not copy the qubits and any measurementof a qubit will disturb the state.
8. A and B obtain a common secret key from the remaining about n/4 bits.
The BB84 protocol can be shown as in the following example.
A’s bits
A’s bases
A’s polarizations
B’s bases
B’s measurements
B’s bits
Comparison of bases
Shared secret bits

0
⊗
⊕
↑
0
6=

0
⊕
↑
⊕
↑
0
=
0

1
⊗
%
⊕
↑
0
6=

0
⊗
⊗
0
=
0

0
⊗
⊕
↑
0
6=

1
⊕
→
⊕
→
1
=
1

0
⊕
↑
⊕
↑
0
=
0

0
⊕
↑
⊕
↑
0
=
0

0
⊗
⊕
→
1
6=

0
⊗
⊗
0
=
0

0
⊗
⊕
→
1
6=

0
⊕
↑
⊗
0
6=

Table 3: A BB84 simulation
The following Maple procedures show a simulation of the BB84 protocol.
Maple: A’s procedure
bb84A:=proc(n);local k,b,ba,pola;
global Abits,Abases,Apol;
Abits:=[];Abases:=[];Apol:=[];
for k from 1 to n do
b:=rand(0..1)();Abits:=[op(Abits), b]:ba:=rand(0..1)();
if ba=0 thenAbases:=[op(Abases),"+"] else Abases:=[op(Abases),"x"]:fi;
if b=0 then if ba=0 then pola:="V";Apol:=[op(Apol), pola]:fi;fi;
if b=0 then if ba=1 then pola:="LV";Apol:=[op(Apol), pola]:fi;fi;
if b=1 then if ba=0 then pola:="H";Apol:=[op(Apol), pola]:fi;fi;
if b=1 then if ba=1 then pola:="RV";Apol:=[op(Apol), pola]:fi;fi;
end do:return Abits,Abases,Apol;end proc:

8

0
⊕
↑
⊕
↑
0
=
0

1
⊕
→
⊗
%
1
6=

1
⊕
→
⊕
→
1
=
1

Maple: B’s procedurebb84B:=proc(n);local k,b,bb,polb,pola;
global Bbits,Bbases,Bpol;
Bbits:=[];Bbases:=[];Bpol:=[];
for k from 1 to n do
bb:=rand(0..1)();
if bb=0 thenBbases:=[op(Bbases), "+"] else Bbases:=[op(Bbases), "x"]:fi;
pola:=Apol[k];if bb=0 thenif pola="V" thenpolb:="V";Bpol:=[op(Bpol), polb]:else
if pola="H" thenpolb:="H";Bpol:=[op(Bpol), polb]:
else polb:=rand(0..1)();
if polb=0 then polb:="V";Bpol:=[op(Bpol), polb]:
else polb:="H";Bpol:=[op(Bpol), polb]:
fi;
fi;
fi;
fi;
if bb=1 thenif pola="RV" thenpolb:="RV";Bpol:=[op(Bpol), polb]:else
if pola="LV" thenpolb:="LV";Bpol:=[op(Bpol), polb]:
else polb:=rand(0..1)();
if polb=0 then polb:="RV";Bpol:=[op(Bpol), polb]:
else polb:="LV";Bpol:=[op(Bpol), polb]:
fi;
fi;
fi;
fi;
if Bpol[k]="V" then Bbits:=[op(Bbits), 0]:fi;
if Bpol[k]="H" then Bbits:=[op(Bbits), 1]:fi;
if Bpol[k]="LV" then Bbits:=[op(Bbits), 0]:fi;
if Bpol[k]="RV" then Bbits:=[op(Bbits), 1]:fi;
end do:return Bbases,Bpol,Bbits;
end proc:9

Maple: Comparison of the bases
bb84Comp:=proc(n);local k,ba,bb;
global Comp;
Comp:=[];
for k from 1 to n do
ba:=Abases[k];bb:=Bbases[k];if ba=bb then Comp:=[op(Comp), "Y"];else Comp:=[op(Comp), "N"];end if;end do;return Comp;end proc:
Maple: The shared key
bb84key:=proc(n);local k,ans;
global Key,Ratio;
Key:=[];
Ratio:=0;
for k from 1 to n do
ans:=Comp[k];if ans="Y" then Key:=[op(Key), Bbits[k]];Ratio:=Ratio+1;
end if;end do;Ratio:=evalf(Ratio/n,3);
return Key,[Ratio];end proc:10

Maple: The BB84 protocol
bb84:=proc(n);local L;
L:=[];
L:=[op(L),bb84A(n)];L:=[op(L),bb84B(n)];L:=[op(L),bb84Comp(n)];L:=[op(L),bb84key(n)];print(’A bits are’ L[1]);print(’A bases are’ L[2]);print(’A polarizations are’ L[3]);print(’B bases are’ L[4]);print(’B polarizations are’ L[5]);print(’B bits are’ L[6]);print(’Comparison ’ L[7]);print(’Shared key is ’ L[8]);print(’Ratio is ’ L[9]);end proc:bb84(10);4

Cryptosystems Vulnerable to Quantum Computers

Factorization and the discrete logarithm problem have been by far the most productive hard problems
in cryptography. These problems will not be difficult if Shor’s algorithm is implemented in quantum
computers. Consequently, some of the popular cryptosystems will not resist to quantum computers.
Table 1 shows some of these cryptosystems as well as the underlying hard problems.
SystemRSA
Rabin’s cryptosystem
KMOV
Diffie-Hellman key exchange
El GamalElliptic Curve Cryptography (ECC)
Digital Signature Algorithm (DSA)

Underlying hard problem
Factorization
Factorization
Factorization
Discrete Logarithm Problem
Discrete Logarithm Problem
Discrete Logarithm Problem
Discrete Logarithm Problem

Table 4: Cryptosystems broken by Shor’s algorithm

4.1

Cryptosystems Based on Factorization: RSA

Factoring is the underlying presumably hard problem upon which several public-key cryptosystems are
based. This includes RSA[14], Rabin’s cryptosystem[12], LUC[15] and KMOV[15].
Factorization: Given a positive integer n, find its prime factorization, that is write n = pe11 pe22 · · · pekk
where the pi are pairwise distinct primes and each ei is a positive integer.
11Factoring is widely believed to be a hard problem and the best algorithm for solving it is the Number
Field Sieve with a sub-exponential running time. The principal threat comes from a quantum computeron which factoring can be solved efficiently using Shor’s algorithm. The most popular cryptosystem
based on factorization is RSA. RSA was invented by Rivest, Shamir and Adelman in 1978. It can besummarized as follows:
1. Key generation• Choose two large primes p and q and compute the RSA modulus N = pq.
• Choose an integer e that is coprime to (p − 1)(q − 1).
• Compute d using ed ≡ 1 (mod (p − 1)(q − 1)).
• Publish the public key (N, e) and keep the private key (N, d).
2. Encryption• Represent the message to be transmitted as a positive integer m < N .
• Encrypt m with the public key (N, e) using c ≡ me (mod N ).
3. Decryption• The receiver decrypts the message using m ≡ cd (mod N ).
• Transform the positive integer m into the original message.
The idea of breaking RSA with a quantum computer using Shor’s algorithm was a powerful motivator
for the design and construction of quantum computers and for the study of new quantum computer
algorithms and cryptosystems that are secure from quantum computers.

4.2

Cryptosystems Based on Discrete Logarithms: El Gamal

In 1985, El Gamal described a cryptosystem based on the difficultly of finding a solution to the discrete
logarithm in Fp .
DLP:Given a primitive element g of Fp and another element a of Fp , the discrete logarithm problem(DLP) is the computational problem of finding x such that a ≡ g x (mod p).
The El Gamal cryptosystem can be summarized as follows:
1. Key generation• Choose a large prime p and a generator g of the group (Z/pZ)∗ .
• Randomly choose an integer a with 2 ≤ a ≤ p − 2.
• Compute b ≡ g a (mod p).
• Publish the public key (p, g, b) and keep the private key a.
2. Encryption• Represent the message to be transmitted as a positive integer m < p.
• Randomly choose an integer k with 2 ≤ k ≤ p − 2.

12• Encrypt m with the public key (p, g, b) using the ruleγ ≡ gk(mod p),δ ≡ mbk(mod p).

3. Decryption• The receiver decrypts the message using the rule m ≡ γ −a δ (mod p).
• Transform the positive integer m into the original message.
The correctness of the decryption in the El Gamal cryptosystem is as follows. We have
−a k
−a
γ −a δ ≡ g k
mb ≡ g km (g a )k ≡ m (mod p).
The main known attack on an El Gamal cryptosystem is to solve the discrete logarithm problem. There
are three basic types of discrete logarithm algorithm solvers: Pollard’s rho algorithm, the Pohlig-Hellman
algorithm, and the index calculus algorithm. The complexity of Pollard’s rho algorithm and the PohligHellman algorithm
are exponential
while the expected running time of the index calculus algorithm is√O exp c log n log log n with a constant c > 0. For comparison, the running time of Shor’s algorithm
for discrete logarithm on a quantum computer is O ((log n)2 (log log n)(log log log n)).

5

Post Quantum Cryptosystems

In this section, we present two types of cryptosystems that are believed to resist to quantum computers.
Two of them are based on lattices and one is based on codes.

5.1

Cryptosystems Based on Lattices

Lattice-based cryptography is a novel and promising type of cryptography based on the mathematicalobjects called lattices. In this section, we review two of these developments: the NTRU cryptosystemand the LWE cryptosystem.
Let B = (b1 , · · · , bn ) be a set of n linearly independent vectors of Rn . The lattice L(B) associatedto B is the set of all integer combinations
( n
)
n
X
X
L=
Zbi =
x i bi | x i ∈ Z .
i=1

i=1

NTRU was first proposed in 1996 as a very fast public key cryptosystem by Hoffstein, Pipher andSilverman. The security of NTRU is based on the hardness of some lattice problems, namely theshortest and closest vector problems.
• Shortest Vector Problem (SVP): Given a lattice basis B, find the shortest nonzero vector in L(B).
• Closest Vector Problem (CVP): Given a lattice basis B and a target vector v0 not necessarily inthe lattice, find the vector v ∈ L(B) closest to v0 .
Both these problems have been studied extensively, and are known to be NP-hard. On the other hand,a number of connections have been established between quantum computation and SVP and CVP.
Nevertheless, there are no efficient quantum algorithms for solving SVP and CVP.
13

5.1.1NTRU

Let N be an odd
 prime. NTRU [7] operations take place in the quotient ring of polynomials R =Z[X]/ X N − 1 . Addition of two elements in R is defined as pairwise addition of coefficients of thesame degree and multiplication is defined by the cyclic convolution product, denoted by ∗. The NTRU
cryptosystem works with many parameters.
• Two relatively prime integers p and q.
• Four subsets Lf , Lg , Lr , Lm of R used for key generation and encryption. The polynomials inthese subsets have a few and very small coefficients.
In NTRU, the key generation, encryption and decryption primitives are as follows:
1. Key generation• Randomly choose a polynomial f ∈ Lf such that f is invertible in R modulo p and moduloq.
• Compute Fp ≡ f −1 (mod p) and Fq ≡ f −1 (mod q).
• Randomly choose a polynomial g ∈ Lg .
• Compute h ≡ p ∗ g ∗ fq (mod q).
• Publish the public key (N, h) and the set of parameters p, q, Lf , Lg , Lr and Lm .
• Keep the private key (f, Fp ).
2. Encryption• Represent the message as a polynomial m ∈ Lm .
• Randomly choose a polynomial r ∈ Lr .
• Encrypt m with the public key (N, h) using the rule e ≡ r ∗ h + m (mod q).
3. Decryption• The receiver computes a ≡ f ∗ e (mod q).
• Using a centering procedure, try to recover the integer polynomial p ∗ r ∗ g + f ∗ m (mod q)
from a.
• Compute m ≡ fp ∗ a (mod p).
In NTRU, the correctness of the decryption is as follows. We have
a ≡
≡
≡
≡
≡

f ∗ e (mod q)f ∗ (r ∗ h + m) (mod q)
f ∗ r ∗ (p ∗ g ∗ fq ) + f ∗ m (mod q)
p ∗ r ∗ g ∗ f ∗ fq + f ∗ m (mod q)
p ∗ r ∗ g + f ∗ m (mod q).

14



Then, if p ∗ r ∗ g + f ∗ m is an integer polynomial with coefficients in − 2q , 2q , thenfp ∗ a ≡ fp ∗ (p ∗ r ∗ g + f ∗ m) ≡ fp ∗ p ∗ r ∗ g + fp ∗ f ∗ m ≡ m(mod p).

In some situations (see[3]), lattice attacks can be applied to recover the private key (f, Fp ) in NTRU.
To this end, a lattice L is derived from the public key (N, h) and the private key (f, g) can be recovered
as likely the shortest vector in L. Hence, if an attacker could solve the shortest vector problem (SVP),
then he would be able to recover the secret key (f, g) and then (f, Fp ). Nevertheless, when the NTRU
parameters are properly chosen, NTRU is resistant to this attack.
5.1.2

LWE

In 2005, Regev [13] invented a new cryptosystem, called learning with errors (LWE). Moreover, hefound a proof of security for LWE, namely a remarkable connection between lattices and LWE: thesearch version of LWE is at least as hard as quantumly approximating two problems in lattices in theworst case, GapSVP and SIVP. LWE key generation, encryption and decryption are as follows.
1. Key generation• Choose integers n, m, t, r, q and a real α > 0.
• Choose an error distribution χ over Z.
• Choose a matrix S ∈ Zn×l
uniformly at random.
q• Choose a matrix A ∈ Zm×n
uniformly at random.
q
by choosing each entry according a probability distribution χ on
• Choose a matrix E ∈ Zm×l
q
Zq , typically taken to be a normal distribution.
• Compute B = AS + E ∈ Zm×l
q
• Publish the public key (A, B) and the set of parameters n, m, t, r, q and the real α.
• Keep the private key S.
2. Encryption• Represent the message as a vector m ∈ Zlt .
• Choose a uniformly random vector v0 ∈ {−r, . . . , r}.
• Encrypt m with the public key (A, B) using the rule
U = AT v0 ∈ Znq ,V = B T v0 + f (m) ∈ Zlq ,where f is the function
f : Zlt−→ Zlq(x1 , . . . , xl ) 7−→ ([x1 q/t] , . . . , [xl q/t]),and [x] is the nearest integer to x. The encrypted message is (U, V ).
3. Decryption

15

• Given the encrypted
message (U, V ), the receiver uses the private key S and computes m =−1Tf
V − S U , where f −1 is the inverse function:−→ Zltf −1 : Zlq(y1 , . . . , yl ) 7−→ ([y1 t/q] , . . . , [yl t/q]).
When we perform f −1 V − S T U , we get
f −1 V − S T U = f −1 B T v0 + f (m) − S T AT v0= f −1 (AS + E)T v0 + f (m) − S T AT v0= f −1 E T v0 + f (m) .

Since v0 ∈ {−r, . . . , r} and the entries of the matrix E ∈ Zm×l
are very small, thenqf −1 E T v0 + f (m) = f −1 (f (m)) = m.
Informally, in the LWE-problem we are given a uniformly chosen matrix A ∈ Zm×n
and a vector
q
n×l
m×l
B = AS + E ∈ Zm×l
where
S
∈
Z
is
an
unknownmatrix
and
E
∈
Z
is
a
vectorconsistingof smallqqq
errors, chosen uniformly based on the normal probability distribution. The problem is then to recover
the vector S. The set of parameters n, m, t, r, q and α are chosen to guarantee the security and theefficiency of the LWE cryptosystem.

5.2

Cryptosystems Based on Codes: McEliece

In 1978, McEliece[10] proposed a public-key cryptosystem built over Goppa codes. Since then, many
McEliece-type cryptosystems have been proposed. Decoding attacks and direct attacks on the private key
are the main known attacks against the McEliece-type cryptosystems. McEliece suggested using Goppa
codes, which are linear codes with a fast decoding algorithm. Although the McEliece cryptosystem isfaster than RSA for encryption and decryption, it is not currently used due to the relatively large public
key and low data rate. Let Fq be a finite field. A linear code C is a k-dimensional subspace of ann-dimensional vector space over Fq and is called an [n, k] code. A generator matrix G of C is a k × n
matrix such thatC = C = xG, x ∈ Fkq .
A Goppa code is a linear code constructed by using an algebraic curve over the finite field Fq . Goppa
codes are linear codes with a fast decoding algorithm. Nevertheless, any linear code with a good decoding
algorithm can be used in the system. The McEliece cryptosystem can be summarized as follows:
1. Key generation• Choose two security parameters k and n.
• Choose a random invertible k × k matrix S.
• Choose a random permutation n × n matrix P .
• Choose a k × n generator matrix G of a Goppa code.
b = SGP which is a k × n matrix.
• Publish the public key G• Keep the secret key (S, P ).
16

2. Encryption• Represent the message to be transmitted as blocks mi of k bits.
b + e.
• For every block mi , randomly choose a vector e of size n and compute ci = mi G
3. Decryption• The receiver decrypts the message usingb −1 + eP −1 = mi SG + eP −1
c0i = ci P −1 = mi GP• Transform c0i into mS using a fast decoding algorithm for the Goppa code.
• Compute m = mSS −1 .
The security of the McEliece-type cryptosystems is based on the difficulty decoding the unknown errorcorrecting code as well as the difficulty of recovering the matrices S and P and are considered classicallysecure but they are rarely used in practice because of their comparatively large public key.

6

Conclusion

Post Quantum Cryptography is a promising area of research that had emerged after the discovery of
Shor’s algorithm. The prominent cryptosystems like RSA and El Gamal will be totally obsolete with aquantum computer. Nevertheless, some cryptosystems, called post quantum cryptosystems, are believed
to resist classical computers and quantum computers. The most known candidates belong to Hash-based
cryptosystems, Code-based cryptosystems and Lattice-based cryptosystems.

References[1] C.H. Bennett and G. Brassard. Quantum cryptography: Public-key distribution and coin tossing.
In Proceedings of IEEE International Conference on Computers, Systems and Signal Processing,IEEE Press, pp. 175–179, Bangalore, India, 1984. 1984.
[2] J.P. Buhler, H.W. Lenstra, and C. Pomerance, The development of the number field sieve, Volume1554 of Lecture Notes in Computer Science, Springer-Verlag, 1994, pp. 50–94.
[3] D. Coppersmith and A. Shamir, Lattice attacks on NTRU. In Advances in cryptology—EUROCRYPT ’97, volume 1233 of Lecture Notes in Comput. Sci., pp. 52–61. Springer, Berlin,
1997.
[4] W. Diffie, E. Hellman, New Directions in Cryptography, IEEE Transactions on Information Theory,22, 5 (1976), pp. 644–654.
[5] T. El Gamal, A public key cryptosystem and signature scheme based on discrete logarithms. IEEE
Transactions on Information Theory IT-31, 496-473, 1976.
[6] FIPS 186-2. Digital Signature Standard (DSS). National Institute of Standards and Technology,
Jan. 2000.
17

[7] J. Hoffstein, J. Pipher, and J. H. Silverman, NTRU: A Ring Based Public Key Cryptosystem
in Algorithmic Number Theory. Lecture Notes in Computer Science 1423, Springer-Verlag, pp.
267–288, 1998.
[8] N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation 48, 1987, pp. 203–209.
[9] K. Koyama, U. M. Maurer, T. Okamoto and S. A. Vanstone, New public-key schemes based on
elliptic curves over the ring Zn , Advances in Cryptology - Crypto’91, Lecture Notes in Computer
Science, Springer-Verlag, 252-266 (1991).
[10] McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. The Deep Space
Network Progress Report 42–44, Jet Propulsion Laboratory, Pasadena, CA, (1978), 114–116.
[11] V.S. Miller, Use of elliptic curves in cryptography, CRYPTO 85, 1985.
[12] M. O. Rabin. Digitalized signatures and public-key functions as intractable as factorization. Technical Report MIT/LCS/TR-212, MIT Laboratory for Computer Science, Jan. 1979.
[13] O. Regev, On lattices, learning with errors, random linear codes, and cryptography, STOC 2005,
ACM (2005) p. 84–93.
[14] R. Rivest, A. Shamir, L. Adleman, A Method for Obtaining Digital Signatures and Public-Key
Cryptosystems, Communications of the ACM, Vol. 21 (2), 120–126 (1978)[15] P. J. Smith, G. J. J. Lennon, LUC: a new public–key cryptosystem, Ninth IFIP Symposium on
Computer Science Security, Elseviver Science Publishers, 103–117 (1993).
[16] P.W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Computing 26, pp. 1484-1509 (1997).

18