1. Introduction
Traditionally, information security needed encryption, authentication, key management, nonrepudiation and authorization which were being met using several techniques. Standardization of algorithms by National Institute of Standards and Technology (NIST) has facilitated international communication for banking and information transfer using these standards. Encryption can be carried out using Advanced Encryption Standard (AES) using variable block lengths (128, 192 or 256 bits) and variable key lengths (128, 192 or 256 bits). Solutions for light weight applications such as those for Internet of Things (IoT) are also being standardized. Message integrity is possible using host of hash algorithms such as SHA1, SHA2 etc., and more recently using SHA3 algorithm. Authentication is possible using well known RivestShamirAdleman (RSA) algorithm needing 2048/4096 bit operations. Elliptic Curve Cryptography (ECC) is also quite popular and used in several practical systems such as WhatsApp, Blackberry etc. Key exchange is possible using DiffieHellman algorithm and its variations. Digital Signatures can be carried out using RSA algorithm or Elliptic Curve Digital Signature Algorithm (ECDSA) or DSA (Digital Signature Algorithm). All these algorithms derive security from difficulty in solving some mathematical problems such as factorization problem or discrete logarithm problem. Though published literature gives evidence of solving factorization problem upto 768 bits only, it is believed that using Quantum computers, these problems could be solved by the end of this decade. This is due to availability of the pioneering work of Shor and Grover [1]. For factoring an integer of N bits, Shor’s algorithm takes quantum gates. As such, there is ever growing interest in being ready for the next decade with algorithms that may resist attacks in the quantum computer era. NIST has foreseen this need and has invited proposals from researchers all over the world. In the first round, about 66 submissions were received which have been scrutinized for completeness of submissions , novelty of the approach and security and 25 of these were promote to second round to improve based on the comments received on the first round submission. These will be analyzed for security and some will be selected for final recommendation for use by industry. These are for encryption/decryption, key agreement, hashing and Digital Signatures for both hardware and software implementations. In this paper, we present a brief survey of the state of the art in postQuantum Cryptography (PQC) followed by study of one of technique referred to as Learning With Errors (LWE) in some detail.
There are five areas into which PQC algorithms can be classified. These are as follows:
Public Key Encryption(PKE) Key Encapsulation Mechanism (KEM) 

Code based 
Lattice based 
BIKE 
CRYSTALS – KYBER 
Classic McEliece 
Frodo KEM 
HQC 
LAC 
LEDAcrypt (merger of LEDAkem/LEDApkc) 
New Hope 
NTSKEM 
NTRU (merger of NTRU Encrypt/NTRUHRSSKEM) 
ROLLO (merger of LAKE/LOCKER/OuroborosR) 
NTRU Prime 
RQC Codebased 
Round5 (merger of Hila5/Round2) 

SABER 

Three Bears 
Key Exchange supersingular Elliptic curve 
SIKE 
Digital Signatures 

Lattice based 
Hash based 
Multivariate 
CRYSTALSDILITHIUM 
SPHINCS

GeMSS 
FALCON 

LUOV 
qTESLA 

MQDSS 


Rainbow 
Table I. Second round submissions of PQC competition of NIST
In this article, we focus on Ring – LWE (Ring – Learning with errors) based Encryption, Key exchange and KEM operations using one of the PQC entries referred to as New Hope.
This is based on the difficulty of finding a solution for the shortest vector problem in a lattice. Given a number of independent vectors b_{1}, b_{2},.., b_{n}, the lattice is defined as for all a_{i} belonging to set Z. The set is called a basis of the lattice.
We first describe integer mode LWE and then we deal with RingLWE. Initially we create a secret key value (s) and another value (e) and choose a prime p. Next we select a number of values (A[ ]) and calculate B[ ] = A[ ] × s + e. The values of A[ ] and B[ ] become our public key. If s is a single value, A and B are one dimensional matrices. Note that e is error column matrix. The difficult problem to be solved is given A and B, finding s. This is called search problem. Given enough samples, can we find the secret? On the other hand, there is another problemdecisioncan we distinguish a random sample and m independent samples of LWE. The decision problem aims to find whether there is a secret in the samples. Note that without the error vector e (i.e. e = 0), we can easily solve the system of linear equations. In the presence of errors with some distribution say discrete Gaussian distribution (mean zero and standard deviation σ), solving the system is believed to be quantum hard. Note that error distribution in fact hides the characteristic of the plain text. Consider an example of small dimensions with chosen prime p =13:
We next consider LWE in a polynomial ring. In this technique, A, s and B are n– th degree polynomials given as
Note that all operations are modulo (x^{n}+1). This means that when we multiply two polynomials, the degree will be (2n2) and this result needs to be reduced mod (x^{n}+1). This is simple by noting that x^{4} = 1, x^{5} = –x etc. Note also that the polynomials coefficients are multiplied mod q, where q is a chosen prime. Evidently all coefficients will be less than q. We next consider an example with q=13.
We compute (A x s) first and reduce mod (x^{4}+1).



10 
11 
1 
4 



11 
11 
9 
6 



60 
66 
6 
24 


90 
99 
9 
36 
90 

110 
121 
11 
44 
110 
121 
110 
121 
11 
44 
110 
121 
11 



214 
9 
189 
189 


e 
1 
1 
1 
0 


Mod13 
7 
10 
5 
10 
Finally, we get from the last row, the result polynomial as .
Evidently n^{2} modulo multiplications and addition of all these products together with e mod q is required.
We next consider Key exchange using RWE which is similar to DiffieHellman Key exchange. We use subscripts A and B to indicate their respective parameters. We consider Alice and Bob as the two sharing the key and describe the steps involved.
Note that all the computation is done in ring of polynomials. Since Alice and Bob use different error vectors, the shared keys will have different rounding errors. This can be resolved by using a process called ‘reconciliation’. In this method, one user sends a hint to the other and both Alice and Bob can use the hint to arrive at the correct shared key.
We next describe how a message can be encrypted. We generate 20 random numbers for our public key A. We also generate an error vector e of 20 samples and we choose a prime q = 97. We also choose a secret key s = 5.
A = [80, 86, 19, 62, 2, 83, 25, 47, 20, 58, 45, 15, 30, 68, 4, 13, 8, 6, 42, 92]
e = [3, 3, 4, 1, 3, 3, 4, 4, 1, 4, 3, 3, 2, 2, 3, 2, 4, 4, 1, 3]
Next we compute B = (A. s + e) mod q as shown below:
B = [15, 45, 2, 20, 13, 30, 32, 45, 4, 3, 34, 78, 55, 51, 23, 67, 44, 34, 17, 75]
Not that B is also public key. Now we can distribute lists A and B to anyone. Suppose we want to encrypt a message bit m.
We pick from our lists A and B few samples and compute u and v as follows:
u=∑(Asamples)(mod q) and v=∑(Bsamples) + (q/2)m(mod q)
The encrypted message is (u, v). To decrypt, we calculate:
Dec = v−su(mod q)
If Dec is less than q/2, the message is a zero, else it is a 1.
For our example we choose from A and B the entries in the five locations [18, 5, 8, 13, 11] and compute u and v as u=34 and v = 83. The encrypted message is (34, 83). We get Dec = (83 5 × 34) mod 97 = 10. Since Dec is less than q/2, we get m = 0. The reader may note however that just for sending one bit we have to transmit two number of size q.
In practice RLWE encryption has three steps: Key generation, Encryption and Decryption.These are as follows:
KeyGen (a): Choose two polynomials r_{1} and r_{2} and compute p = r_{1 }– ar_{2}.The public key is (a, p) and private key is r_{2}.the polynomial r_{1} is noise and is no longer required after key generation.
Encrypt (a, p, m): The message m is encoded as a polynomial m′ in the ring. Three polynomials e_{1}, e_{2} and e_{3} are sampled from a distribution. Compute c_{1} = ae_{1}+ e_{2} and c_{2} = pe_{1}+ e_{3 }+ m′. The final cipher text is (c_{1}, c_{2}).
Dec(c1,c2,r2): Compute m′ = c_{1}r_{2 }+ c_{2} and recover the original message.
The message is encoded first by writing 1 as (q1)/2 and retaining ‘0’ as ‘0’. The decoding is done by following the rule:
if (q1)/4 ≤ m′ ≤ 3(q1)/4, return 1, otherwise return 0. Note that e_{1}, e_{2}, e_{3} will not affect the decrypted text if a, q, e, r1 and r2 are properly chosen.
Four primitives will be needed in the implementation: (a) Discrete Gaussian sampler (b) Polynomial multiplier (c) countermeasures against side channel attacks (d) True Random number generator. Different approaches may be used in different algorithms regarding these four aspects. We consider for illustration New Hope next.
With the above background, we describe briefly New Hope Key Encapsulation Mechanism (KEM) and public key encryption (PKE) which uses lot of steps in the generation of A, s and e for meeting the security requirements. Two versions of New hope one with N = 512 and another with 1024 are available. The prime q chosen for N=1024 is 12259. Evidently this means that all coefficients in the 1024 degree polynomials are of 14 bit length. Now the reader may get an idea of the key length needed. The Table II gives the parameters recommended. CPA and CCA mean Chosen Plain Text attacks and Chosen Cipher Text attacks.
Table II. Parameter sets for New Hope KEM for CPA and CCA. 

Parameter set 

New Hope512CPAKEM 
928 
869 
1088 
New Hope1024CPAKEM 
1824 
1792 
2176 
New Hope 512CCAKEM 
928 
1888 
1120 
New Hope 512CCAKEM 
1824 
3680 
2208 
Table II: Two versions of New hope one with N = 512 and
another with 1024 are available as shown.
Parameters q = 12289 < 2^{14}, n = 1024 Error distribution: ψ_{16} 

Alice (Server) 

Bob(client) 
$ seed ← {0,1}^{256} 


a←Parse(SHAKE128(seed)) 


$ s,e ← ψ^{n}_{16} 

$ s′,e′,e′′ ← ψ^{n}_{16} 
b←as+e 
(b,seed) 
a←Parse(SHAKE128(seed)) 


u←as′+e′′ 


v←bs′+e′′ 
v′←us 
(u,r) ← 
$ r ← HelpRec(v) 
ν←Rec(v′,r) 

ν←Rec(v,r) 
μ←SHA3256(ν) 

μ←SHA3256(ν) 
Figure 1: New Hope Algorithm in simplified form
In the above code, the symbol ψ stands for distributions from which the coefficients of various polynomials are taken. The HelpRec step helps for reconciliation so that both the users arrive at the same key. The parameter μ indicates the final key obtained by hashing v. Since the polynomials are of degree 1024, multiplication in the ring with coefficients reduced mod q is a complex process. This can be solved by using Number Theoretic Transforms (NTT). Both the polynomials A and B to be multiplied mod (x^{n}+1) are transformed using NTT and the resulting 1024 values can be multiplied pointwise and inverse NTT can be applied to get the actual product. This needs initial transformation of the polynomial coefficients of A and B using a primitive root ω defined as ω^{N} = 1mod p. As an illustration, for N = 1024, p = 12277, we have ω = 49. Note that New Hope uses SHAKE256 hash function (SHA3 variation) for various functions, which takes a seed of 256 bits and outputs several bytes as desired.
Post Quantum Cryptographic (PQC) algorithms are more difficult to understand than conventional cryptographic algorithms like AES, RSA etc. It may be noted that while quantum computers need different environment, PQC algorithms will still be implemented in FPGAs, GPUs and embed processors and ASICs. Attempts also have been made to incorporate suite of PQC algorithms in Web browsers and other applications and even in IoT devices with limited resources.
[1] P. Shor, Algorithms for Quantum computation: Discrete logarithms and Factoring, Foundations of Computer Science, 1994 Proceedings, 35^{th} Annual Symposium, pp.124134, Nov.1994.
[2] V. Lyubashevsky, C. Piekert and O. Regev, On ideal lattices and Learning with Errors over Rings, Cryptology ePrint Archive, Report 2012/230, 2012.
[3] S.S. Roy, F. Vercauteren and I. Verbauwhede, High precision Discrete Gaussian sampling on FPGAs, Selected Areas in CryptologySAC 2013, pp 383401, 2014.
[4] S.S. Roy, F.Vercauteren, N.Mentens, D.D.Chen and I. Verbauwhede, Compact Ring LWE cryptoprocessor, Cryptographic Hardware and Embedded Systems, CHES 2014, Vol 8731, pp 371391.
[5] A. Mariano et al., A practical view of the stateoftheart of Latticebased Cryptanalysis, IEEE Access, Vol5, pp 2418424202, 2017.
[6] D. Liu et al. A resourceefficient and sidechannel secure Hardware implementation of RingLWE cryptographic processor, IEEE Transactions on Circuits and SystemsI, Regular Papers, Vol.66, pp 14741483, 2019.
[7] E. Alkim, L.Ducas, T.Poppelmann and P.Scwabe, PostQuantum Key Exchange – a New Hope, https://eprint.iacr.org/2015/1092.
[8] E. Alkim et al, New Hope: Algorithm Specification and syupporting Documentation, NIST, Post Quantum Cryptography web site, Round 2 submissions, pp 146, 2019.
[9] Bill Buchanan, Learning with Errors and Ring learning with Errors, https://medium.com/a security sitewghenbobmeets Alice, 2019