# Portable Implementation of Postquantum Encryption Schemes and Key Exchange Protocols on JavaScript-Enabled Platforms

Authors: Ye Yuan; Junting Xiao; Kazuhide Fukushima; Shinsaku Kiyomoto; Tsuyoshi Takagi
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Quantum computers have the potential to solve some difficult mathematical problems efficiently and thus will inevitably exert a more significant impact on the traditional asymmetric cryptography. The National Institute of Standards and Technology (NIST) has opened a formal call for the submission of proposals of quantum-resistant public-key cryptographic algorithms to set the next-generation cryptography standards. Compared to powerful machines with ample amount of hardware resources such as racks of servers and IoT devices, including the massive number of microcontrollers, smart terminals, and sensor nodes with limited computing capacity, should also have some postquantum cryptography features for security and privacy. To ensure the correct execution of encryption algorithms on any platforms, the portability of implementation becomes more important. As distinguished from C/C++, JavaScript is a popular cross-platform language that can be used for the web applications and some hardware platforms directly, and it could be one of the solutions of portability. Therefore, we investigate and implement several recent lattice-based encryption schemes and public-key exchange protocols including Lizard, ring-Lizard, Kyber, Frodo, and NewHope in JavaScript, which are the active candidates of postquantum cryptography due to their applicabilities and efficiencies. We show and compare the performance of our JavaScript implementation on web browsers, embedded device Tessel2, Android phone, and several JavaScript-enabled platforms on PC and Mac. Our work shows that implementing lattice-based cryptography on JavaScript-enabled platforms is achievable and results in desirable portability.


---

## Body

## 1. Introduction

The rapid development of quantum computing coupled with Shor’s algorithm [1] brings a significant threat to widely used RSA and elliptic curve cryptography (ECC) based on the integer factorization and the discrete logarithm problems. Hence, postquantum cryptography (PQC) has generated a lot of attention among researchers. In the IoT era, tons of things or devices will get connected to the Internet, and they require efficient quantum-resistant approaches to protect the security and privacy. IoT software should work correctly on any architecture; therefore, the portability of software becomes more important. Besides, web browsers serve as an essential platform for web applications and should also have postquantum cryptographic features. As a favorite cross-platform/browser language, JavaScript is one of the solutions of the portability because its performance has improved considerably over the past few years.Lattice-based cryptography, which is thought to be secure against attacks by quantum computers [2], has gained wide attention and deep researches from academia to industry due to its efficiency and applicability. In recent years, some derivatives of encryption schemes and key exchange protocols of lattice-based cryptography were presented, such as [3–7]. Implementations of those cryptosystems have been reported in some literature [8–12]. However, as of now, there is very little research on lattice-based cryptography in JavaScript [13, 14]. Therefore, we would like to investigate the performance of several recent lattice-based cryptosystems on modern computing platforms with JavaScript implementation. We hope to contribute to the practical implementation of PQC.We implemented and tested five recent lattice-based encryption schemes and public-key exchange protocols on four web browsers, a microcontroller Tessel2, an Android phone Xperia XZ, and other JavaScript-enabled platforms on PC and Mac. We chose an encryption scheme “Lizard” which is based on the learning with errors (LWE) and the learning with rounding (LWR) problems and its ring variant “ring-Lizard” [15], a modulo-LWE based encryption scheme “Kyber” [16], and two quantum secure key exchange protocols “Frodo” [17] and “NewHope” [18], which are based on the LWE problem and the ring-LWE problem, respectively. All the cryptosystems above were implemented in JavaScript. The source code of our implementationcan be found at https://github.com/FuKyuToTo/lattice-based-cryptography.To provide a fair comparison, we selected the parameters which have 128 bits of postquantum security from the estimation of Jung Hee Cheon et al. [15], Joppe Bos et al. [16, 17], and Erdem Alkim et al. [18], summarized in Table 1. However, there are many different models to estimate the secure parameters of lattice-based cryptography [19]. The analysis of the concrete quantum security levels of those parameters is beyond the scope of this paper, more detailed security estimation algorithms can be found in [20–22]. Our parameters should be rescaled after finalizing the secure parameters in NIST PQC standardization project (NIST Postquantum Cryptography Standardization. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography).Table 1
Summary of the selected parameters that provide about 128-bit security.
Lizard m n l = p q t α - 1 960 608 256 1024 2 182  Ring-Lizard n = q p α - 1 – – – – – – 1024 256 154 – – – – – –  Kyber k n q η d b = d c 1 d c 2 3 256 7681 4 11 3  Frodo b l m n q σ 4 8 8 752 32768 1.3229  NewHope k n q – – – – – – 16 1024 12289 – – – – – –The primary reason we chose those five cryptosystems is that they cover a majority of the variants of the LWE-based cryptography, which we will introduce in Section2. In addition, the parameters and key sizes of those cryptosystems above are not too large and suitable for implementing on web browsers and small devices using JavaScript.Contributions of this paper can be summarized as follows:(i)
We first implement the five lattice-based encryption schemes and key exchange protocols mentioned above using JavaScript. We observe running time of our implementation and find that the performance of the ring-LWE based cryptosystems is much higher than that of others. For example, on the web browsers, the entire calculation process of Kyber and NewHope can be accomplished within milliseconds; even the IoT device Tessel2 is fast enough to perform all of those operations in merely two seconds. Our implementation will be improved further for the NIST PQC standardization project in a future work.(ii)
We refactor our implementation to accelerate polynomial operations for ring-LWE based cryptographic algorithms. By implementing the improved number-theoretic transform (NTT) and inverse NTT (see [23, 24]) and reducing the memory overhead of creating temporary instances, we vastly improve the efficiency of polynomial operations compared with our previous work (see [13]).(iii)
Our implementation has good portability and scalability. Our JavaScript code can be directly executed on any JavaScript runtime environment without modification. More importantly, by comparing and analyzing these performance difference, we can further improve our implementation for particular platforms.The rest of this paper is organized as follows. We will explain the notation, give a brief introduction of the mathematical background, and introduce the implemented cryptosystems in Section2. We will introduce our experimental platforms in Section 3 and describe our implementation techniques in Section 4. We will then present the performance reports on web browsers in Section 5 and on IoT device Tessel2, Android phone, and other platforms in Section 6. Finally, we conclude this paper in Section 7. The appendix section contains an example of the usage of our source code.


## 2. Lattice-Based Cryptography

In this section, we introduce the relevant mathematical background for the LWE, ring-LWE, and LWR problems and summarize the postquantum cryptographic schemes based on those problems.


### 2.1. Notation

Letn,q be positive integers; we denote Zq as the set of integers {0,1,…,q-1} and R=Z[x]/(xn+1), Rq=Zq[x]/(xn+1) as the polynomial rings. Polynomials are denoted by bold italic letters such as a, while vectors are denoted by bold small letters such as v and matrices and bold large letters such as A. For an integer m∈N, we define the modulo operation b≡amodm in the range [0,m)∩Z.


### 2.2. LWE, Ring-LWE, and LWR Problems

Regev proposed the original LWE problem [3] using integer matrix in 2005. Let m,n,q be positive integers; the search LWE problem is required to find a secret vector s∈Zqn by inputting a pair of matrices (A,b=As+e)∈Zqm×n×Zqm. The decision LWE problem is to distinguish b between a uniformly distributed random vector from Zqm and a noisy inner product b=As+e. Usually, the elements of A are randomly selected from Zq, and the so-called error vector e∈Zm is sampled from a target probability distribution χ. The cryptography based on the LWE problem uses an unusual structure lattice which is called q-ary lattice:(1)Lq⊥A=v∈Zn∣Av≡0mod⁡q;LqA=v∈Zn,s∈Zm∣v≡ATsmod⁡q;all the elements of the q-ary lattice are obtained using an integer modulo of q.The ring-LWE problem (see [5]) is a variant of Regev’s original LWE problem. Rq is an ideal lattice if each polynomial over Rq has a bijective mapping to an ideal Zqn. Given polynomials a, b∈Rq, the search version of the ring-LWE problem is to recover the secret s∈Rq, where a is chosen uniformly and b=a·s+e with an “error’’ e∈R sampled from a target probability distribution χ. The decision ring-LWE problem is similar to the decision LWE problem: given a, b∈Rq, we distinguish whether b is also chosen uniformly, or there exists a polynomial s∈Rq such that b=a·s+e. If there were not any error adding, the LWE and ring-LWE problems would be the simple linear algebra computation and easy to solve. In the worst-case, such LWE and ring-LWE problems can be reduced to the approximate versions of NP-hard shortest vector problem (α-SVP) on ideal lattices.Given a matrixA={a1,…,an}∈Zqm×n and an inner product with rounding b=Asp∈Zpm, the LWR problem (see [25]) is to find the vector s∈Zqn, where p≪q. The information hiding technique or so-called derandomization technique of LWR is different from LWE: each value of the inner product b times a rounded value q/p over Zp, instead of adding a random error value; therefore, the error in LWR is deterministic.


### 2.3. Discrete Gaussian Sampling

For a realσ>0, the Gaussian distribution evaluated at x∈R is defined by ρσ=exp(-πx/s2), where the Gaussian parameter s=σ2π. A discrete version of Gaussian distribution over Z is defined by Dσ(x)=ρσ(x)/ρσ(Z). In order to find out where to drop the negligible probability of far samples, a tail-cut factor t>0 is set to determine the range of sampled values. Choosing a suitable length of the tail-cut factor for a target discrete Gaussian distribution is necessary; otherwise, no sampling algorithm could cover it. The tail-bound is closely related to the maximum statistical distance allowed by the security discrete Gaussian parameters [26, 27]. Note that sampling values from the discrete Gaussian distribution are different to sampling from a normal distribution [28]. We implement modified Knuth-Yao algorithm [27, 29] and modified discrete Ziggurat algorithm [30] to perform such a sampling. The sampling methods will be discussed in Section 4.1.


### 2.4. Binomial Distribution

The binomial distribution is a discrete probability distribution of the successful number inn Bernoulli trials. In this paper, we follow the definition in [16, 18] and denote Bk as the centered binomial distribution for a positive integer k:Input: a binary string (a0,a1,…,ak-1,b0,b1,…,bk-1)←{0,1}2kOutput: an integer ∑i=0k-1(ai-bi)For the convenience of calculations, we only sample and compute integers overZq.


### 2.5. Lizard and Ring-Lizard

Lizard encryption scheme [15] is parameterized by positive integers h,m,n,l,t,p,q∈Z and an error rate α∈R, where the moduli t,p,q satisfy t∣p∣q. For a real number 0<ρ<1, we sample values (v1,v2,…,vn)←{-1,0,1}n from the distribution ZOn(ρ) such that each value vi(i=1,2,…,n) is chosen satisfying Pr[vi=0]=1-ρ and Pr[vi=1]=Pr[vi=-1]=ρ/2. For an integer 0≤h≤m, we sample the values (v1,v2,…,vn)←{-1,0,1}m from the distribution HWTm(h) such that it has exactly h nonzero entries in those values.In key generation, we choose a matrixS={s1,…,sl}∈Zqn×l by sampling column vectors si∈Zqn(i=1,2,…,l) independently from the distribution ZOn(1/2). Input a matrix A∈Zqm×n whose elements are chosen uniformly from Zq; then we can compute the matrix B=AS+E∈Zqm×l, where the error matrix E∈Zqm×l is chosen according to DZ,αq. The secret key is S and the public key is the pair (A,B)∈Zqm×n×∈Zqm×l. In encryption, by choosing a random vector r∈Zm from the distribution HWTm(128), we compute a pair (c1,c2)=(ATr,BTr)∈Zqn×Zql. Given a message m∈Ztl, the cipher text is the pair (c1′,c2′) where c1′=(p/q)∗c1∈Zpn and c2′=(p/t)∗m+(p/q)∗c2∈Zpl. Lastly, we output the vector m′=(t/p)∗(c2′-STc1′)∈Ztl in decryption.Ring-Lizard encryption scheme [15] is a variant of Lizard and based on the hardness of the ring-LWE and the ring-LWR problems. It exploits better key sizes and delivers faster speed of encryption and decryption compared with Lizard. The following procedures define the ring-lizard scheme.Key Generation.Sample e←DZ,αq; choose a “small” random polynomial s from HWTn(128) and a uniformly random polynomial a∈Rq; then output the public key (a,b=a·s+e)∈Rq×Rq and the secret key s∈R.Encryption.Choose a random polynomial r from HWTn(128); given a plaintext m∈{0,1}n, then compute c1=(p/q)∗(a·r)∈Rp and c2=(p/2)∗m+(p/q)∗(b·r)∈Rp. The ciphertext is the pair (c1,c2).Decryption.Output (2/p)∗(c2-c1·s)∈{0,1}n.


### 2.6. Kyber

Kyber [16] is a recent module-LWE [31, 32] based CPA- (Chosen Plaintext Attack-) secure encryption scheme and can be applied to build CCA- (Chosen Ciphertext Attack-) secure key encapsulation mechanism (KEM). In this paper, we focus on the former, implementing the Kyber’s public-key encryption scheme. For positive integers db,dc1,dc2,k,n,η and modulus q∈Z, Kyber needs to generate matrices with small dimension, and each matrix contains several polynomials with coefficients in Rq as its elements. The compression and decompression functions of Kyber are defined as follows:(2)Compressqx,d=2dq∗xmod⁡2d;Decompressqx,d=q2d∗x.In key generation, a binary stringα is chosen uniformly at random from {0,1}n. The matrix A∈(Rq)k×k can be pregenerated by methodSHAKE-128(α), and two vectors s,e are sampled from (Bη)k. We compute =Compressq(As+e,db). The secret key is s and the public key is the pair (A,b). In encryption, we generate vectors r,e1←(Bη)k and e2←Bη. Then we obtain the vector b1 from b by method Decompressq(b,db). Given a message m∈Z2n, the cipher text is the pair (c1,c2), where c1=Compressq(ATr+e1,dc1) and c2=Compressq(b1Tr+e2+q/2∗m,dc2). In decryption, we compute u=Decompressq(c1,dc1) and v=Decompressq(c2,dc2) and then output the result Compressq(v-sTu,1).


### 2.7. Frodo

Frodo [17], the key-exchange protocol based on the LWE problem, has parameters b,d,l,m,n,q∈Z and a real number σ>0. The matrix A∈Zqn×n is generated from seedA via a pseudorandom generating function Gen().In this paper, we focus on the main computation process in Figure1: we skip the generating function Gen() and precompute the matrix A. Let b′=(log2q)-b, for a matrix M∈Zqx×y, the rounding function M2b and the cross-rounding function 〈M〉2b are defined as follows, respectively:(3)rounding:M2b=2-b′∗Mmod⁡2b;cross-rounding:M2b=21-b′∗Mmod2.The reconciliation function rec2b() is defined in [33]. The output v is the closest element to w∈Zq such that 〈v〉2b=0 or 1. Alice and Bob can obtain the same shared key K via this reconciliation mechanism.Figure 1
Quantum-secure key exchange protocol Frodo.


### 2.8. NewHope

Compared with another ring-LWE based key exchange protocol BCNS [7], NewHope [18] achieves some improvement in the parameters selecting, errors sampling, and reconciliation mechanism. NewHope is a famous ring-LWE based key exchange protocol due to its experiment which is taking place in Google Canary channel; the result shows that NewHope operates well for Google’s postquantum TLS experiment while still being computationally inexpensive (https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html). We would like to know its performance on web browsers or other IoT devices in JavaScript.Letk, n, and the modular q be positive integers; as with the definition of polynomial ring in Kyber, the keys and errors are all over Rq. A seedA is a component of the exchange and generated from a binary string. It is designed to output a polynomial a∈Rq bySHAKE-128 method. NewHope also needs to sample random values from a binomial distribution Bk. For reconciliation mechanism, we follow the method in [18] and may use non-floating-point arithmetic [34] in our future work. The overview of NewHope is described in Figure 2.Figure 2
Ring-LWE based public-key exchange protocol NewHope.


## 2.1. Notation

Letn,q be positive integers; we denote Zq as the set of integers {0,1,…,q-1} and R=Z[x]/(xn+1), Rq=Zq[x]/(xn+1) as the polynomial rings. Polynomials are denoted by bold italic letters such as a, while vectors are denoted by bold small letters such as v and matrices and bold large letters such as A. For an integer m∈N, we define the modulo operation b≡amodm in the range [0,m)∩Z.


## 2.2. LWE, Ring-LWE, and LWR Problems

Regev proposed the original LWE problem [3] using integer matrix in 2005. Let m,n,q be positive integers; the search LWE problem is required to find a secret vector s∈Zqn by inputting a pair of matrices (A,b=As+e)∈Zqm×n×Zqm. The decision LWE problem is to distinguish b between a uniformly distributed random vector from Zqm and a noisy inner product b=As+e. Usually, the elements of A are randomly selected from Zq, and the so-called error vector e∈Zm is sampled from a target probability distribution χ. The cryptography based on the LWE problem uses an unusual structure lattice which is called q-ary lattice:(1)Lq⊥A=v∈Zn∣Av≡0mod⁡q;LqA=v∈Zn,s∈Zm∣v≡ATsmod⁡q;all the elements of the q-ary lattice are obtained using an integer modulo of q.The ring-LWE problem (see [5]) is a variant of Regev’s original LWE problem. Rq is an ideal lattice if each polynomial over Rq has a bijective mapping to an ideal Zqn. Given polynomials a, b∈Rq, the search version of the ring-LWE problem is to recover the secret s∈Rq, where a is chosen uniformly and b=a·s+e with an “error’’ e∈R sampled from a target probability distribution χ. The decision ring-LWE problem is similar to the decision LWE problem: given a, b∈Rq, we distinguish whether b is also chosen uniformly, or there exists a polynomial s∈Rq such that b=a·s+e. If there were not any error adding, the LWE and ring-LWE problems would be the simple linear algebra computation and easy to solve. In the worst-case, such LWE and ring-LWE problems can be reduced to the approximate versions of NP-hard shortest vector problem (α-SVP) on ideal lattices.Given a matrixA={a1,…,an}∈Zqm×n and an inner product with rounding b=Asp∈Zpm, the LWR problem (see [25]) is to find the vector s∈Zqn, where p≪q. The information hiding technique or so-called derandomization technique of LWR is different from LWE: each value of the inner product b times a rounded value q/p over Zp, instead of adding a random error value; therefore, the error in LWR is deterministic.


## 2.3. Discrete Gaussian Sampling

For a realσ>0, the Gaussian distribution evaluated at x∈R is defined by ρσ=exp(-πx/s2), where the Gaussian parameter s=σ2π. A discrete version of Gaussian distribution over Z is defined by Dσ(x)=ρσ(x)/ρσ(Z). In order to find out where to drop the negligible probability of far samples, a tail-cut factor t>0 is set to determine the range of sampled values. Choosing a suitable length of the tail-cut factor for a target discrete Gaussian distribution is necessary; otherwise, no sampling algorithm could cover it. The tail-bound is closely related to the maximum statistical distance allowed by the security discrete Gaussian parameters [26, 27]. Note that sampling values from the discrete Gaussian distribution are different to sampling from a normal distribution [28]. We implement modified Knuth-Yao algorithm [27, 29] and modified discrete Ziggurat algorithm [30] to perform such a sampling. The sampling methods will be discussed in Section 4.1.


## 2.4. Binomial Distribution

The binomial distribution is a discrete probability distribution of the successful number inn Bernoulli trials. In this paper, we follow the definition in [16, 18] and denote Bk as the centered binomial distribution for a positive integer k:Input: a binary string (a0,a1,…,ak-1,b0,b1,…,bk-1)←{0,1}2kOutput: an integer ∑i=0k-1(ai-bi)For the convenience of calculations, we only sample and compute integers overZq.


## 2.5. Lizard and Ring-Lizard

Lizard encryption scheme [15] is parameterized by positive integers h,m,n,l,t,p,q∈Z and an error rate α∈R, where the moduli t,p,q satisfy t∣p∣q. For a real number 0<ρ<1, we sample values (v1,v2,…,vn)←{-1,0,1}n from the distribution ZOn(ρ) such that each value vi(i=1,2,…,n) is chosen satisfying Pr[vi=0]=1-ρ and Pr[vi=1]=Pr[vi=-1]=ρ/2. For an integer 0≤h≤m, we sample the values (v1,v2,…,vn)←{-1,0,1}m from the distribution HWTm(h) such that it has exactly h nonzero entries in those values.In key generation, we choose a matrixS={s1,…,sl}∈Zqn×l by sampling column vectors si∈Zqn(i=1,2,…,l) independently from the distribution ZOn(1/2). Input a matrix A∈Zqm×n whose elements are chosen uniformly from Zq; then we can compute the matrix B=AS+E∈Zqm×l, where the error matrix E∈Zqm×l is chosen according to DZ,αq. The secret key is S and the public key is the pair (A,B)∈Zqm×n×∈Zqm×l. In encryption, by choosing a random vector r∈Zm from the distribution HWTm(128), we compute a pair (c1,c2)=(ATr,BTr)∈Zqn×Zql. Given a message m∈Ztl, the cipher text is the pair (c1′,c2′) where c1′=(p/q)∗c1∈Zpn and c2′=(p/t)∗m+(p/q)∗c2∈Zpl. Lastly, we output the vector m′=(t/p)∗(c2′-STc1′)∈Ztl in decryption.Ring-Lizard encryption scheme [15] is a variant of Lizard and based on the hardness of the ring-LWE and the ring-LWR problems. It exploits better key sizes and delivers faster speed of encryption and decryption compared with Lizard. The following procedures define the ring-lizard scheme.Key Generation.Sample e←DZ,αq; choose a “small” random polynomial s from HWTn(128) and a uniformly random polynomial a∈Rq; then output the public key (a,b=a·s+e)∈Rq×Rq and the secret key s∈R.Encryption.Choose a random polynomial r from HWTn(128); given a plaintext m∈{0,1}n, then compute c1=(p/q)∗(a·r)∈Rp and c2=(p/2)∗m+(p/q)∗(b·r)∈Rp. The ciphertext is the pair (c1,c2).Decryption.Output (2/p)∗(c2-c1·s)∈{0,1}n.


## 2.6. Kyber

Kyber [16] is a recent module-LWE [31, 32] based CPA- (Chosen Plaintext Attack-) secure encryption scheme and can be applied to build CCA- (Chosen Ciphertext Attack-) secure key encapsulation mechanism (KEM). In this paper, we focus on the former, implementing the Kyber’s public-key encryption scheme. For positive integers db,dc1,dc2,k,n,η and modulus q∈Z, Kyber needs to generate matrices with small dimension, and each matrix contains several polynomials with coefficients in Rq as its elements. The compression and decompression functions of Kyber are defined as follows:(2)Compressqx,d=2dq∗xmod⁡2d;Decompressqx,d=q2d∗x.In key generation, a binary stringα is chosen uniformly at random from {0,1}n. The matrix A∈(Rq)k×k can be pregenerated by methodSHAKE-128(α), and two vectors s,e are sampled from (Bη)k. We compute =Compressq(As+e,db). The secret key is s and the public key is the pair (A,b). In encryption, we generate vectors r,e1←(Bη)k and e2←Bη. Then we obtain the vector b1 from b by method Decompressq(b,db). Given a message m∈Z2n, the cipher text is the pair (c1,c2), where c1=Compressq(ATr+e1,dc1) and c2=Compressq(b1Tr+e2+q/2∗m,dc2). In decryption, we compute u=Decompressq(c1,dc1) and v=Decompressq(c2,dc2) and then output the result Compressq(v-sTu,1).


## 2.7. Frodo

Frodo [17], the key-exchange protocol based on the LWE problem, has parameters b,d,l,m,n,q∈Z and a real number σ>0. The matrix A∈Zqn×n is generated from seedA via a pseudorandom generating function Gen().In this paper, we focus on the main computation process in Figure1: we skip the generating function Gen() and precompute the matrix A. Let b′=(log2q)-b, for a matrix M∈Zqx×y, the rounding function M2b and the cross-rounding function 〈M〉2b are defined as follows, respectively:(3)rounding:M2b=2-b′∗Mmod⁡2b;cross-rounding:M2b=21-b′∗Mmod2.The reconciliation function rec2b() is defined in [33]. The output v is the closest element to w∈Zq such that 〈v〉2b=0 or 1. Alice and Bob can obtain the same shared key K via this reconciliation mechanism.Figure 1
Quantum-secure key exchange protocol Frodo.


## 2.8. NewHope

Compared with another ring-LWE based key exchange protocol BCNS [7], NewHope [18] achieves some improvement in the parameters selecting, errors sampling, and reconciliation mechanism. NewHope is a famous ring-LWE based key exchange protocol due to its experiment which is taking place in Google Canary channel; the result shows that NewHope operates well for Google’s postquantum TLS experiment while still being computationally inexpensive (https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html). We would like to know its performance on web browsers or other IoT devices in JavaScript.Letk, n, and the modular q be positive integers; as with the definition of polynomial ring in Kyber, the keys and errors are all over Rq. A seedA is a component of the exchange and generated from a binary string. It is designed to output a polynomial a∈Rq bySHAKE-128 method. NewHope also needs to sample random values from a binomial distribution Bk. For reconciliation mechanism, we follow the method in [18] and may use non-floating-point arithmetic [34] in our future work. The overview of NewHope is described in Figure 2.Figure 2
Ring-LWE based public-key exchange protocol NewHope.


## 3. Experimental Runtime Environments

### 3.1. Web Browsers

Implementing postquantum cryptographic primitives on web browsers is necessary and urgent because web browsers are one of the essential platforms for NIST PQC standardization project. In this paper, we choose Mozilla Firefox 57.0.2 as our benchmark platform and propose an open-source projectAlea (available URL: https://github.com/nquinlan/better-random-numbers-for-javascript-mirror) to be our secure pseudorandom number generator (PRNG). For comparison, we execute same programs on Google Chrome 63.0.3239.108, Opera 53.0.2907.68, and Microsoft Edge 42.17134.1.0. What we want to see is the performance difference between those web browsers. We will show the running time of several lattice-based cryptosystems on web browsers in Section 5.


### 3.2. Tessel2

Similar to its old model, Tessel2 is a JavaScript-enabled embedded system with on-board WiFi capabilities designed for IoT developers. Tessel2 features a 580 MHz Mediatek MT7620n router-on-a-chip + 48MHz Atmel SAMD21 coprocessor, running Linux built on OpenWRT with 64MB of DDR2 RAM, and 32MB of Flash memory. Tessel2 is compatible with Node.js and runs JavaScript programs directly for controlling a wide variety IoT modules; it allows developers to easily control modules via a pair of multipurpose ports. Tessel2 is also programmable in other programming languages; however, a part of browser-side JavaScript libraries or objects is not supported.


### 3.3. Android WebView, PC, and Mac

Android has a built-in browser-like activity which is called WebView. It can be used to display web pages or HTML files as a part of UI. Developers can build a WebView activity to show online content or user data within applications. Android 4.4 has replaced the rendering engine of WebView with Chromium’s V8 engine to deliver improved JavaScript performance. We chose WebView in Android 4.4 (KitKat) to benchmark our JavaScript implementation and ran our implementation on an Android phone Xperia XZ SOV34 (Android version 8.0.0 (Oreo)).Some operating systems also provide tools to execute plain text files within a shell/script. The Microsoft Windows Script Host (WSH) is described as an administration tool to provide a scripting environment for batch files. The Active Scripting language engines of WSH can interpret and run script files such as JScript or VBScript. Similarly, Mac users can run JavaScript files by using osascript command, which works with AppleScripts or other Open Scripting Architecture (OSA) language scripts on macOS.In addition, some nonbrowser software such as Node.js or Pacifista also provide JavaScript runtime environment. Like Google Chrome and Android WebView, Node.js is also built on the Google V8 JavaScript engine and offers a rich variety of JavaScript modules which will be of benefit to development. Pacifista is a simple Java-based open-source project that builds a Linux environment and can upgrade OpenSSL using JavaScript; it can be downloaded athttps://github.com/ukiuni/pacifista.Our implementation is measured on a test PC and a MacBook Pro. The test PC has the following specification: CPU: Intel(R) Core(TM) i5-8250U @1.6GHz; 8GB DDR3 RAM; 256GB SSD; Windows 10 build 17134 Home x64. The MacBook Pro (15-inch, 2017 model) features quad-core Intel(R) Core(TM) i7 @2.8GHz, 16GB 2133MHz LPDDR3 memory, and 512GB SSD with macOS High Sierra 10.13.5. Node.js 8.11.2 and Pacifista 0.0.30 are installed on the test PC and MacBook Pro, respectively. We tested our implementation on the four JavaScript run-time environments above. We ran the code on WSH and Node.js for PC and ran on osascript and Pacifista for Mac (see Appendix for the commands).


## 3.1. Web Browsers

Implementing postquantum cryptographic primitives on web browsers is necessary and urgent because web browsers are one of the essential platforms for NIST PQC standardization project. In this paper, we choose Mozilla Firefox 57.0.2 as our benchmark platform and propose an open-source projectAlea (available URL: https://github.com/nquinlan/better-random-numbers-for-javascript-mirror) to be our secure pseudorandom number generator (PRNG). For comparison, we execute same programs on Google Chrome 63.0.3239.108, Opera 53.0.2907.68, and Microsoft Edge 42.17134.1.0. What we want to see is the performance difference between those web browsers. We will show the running time of several lattice-based cryptosystems on web browsers in Section 5.


## 3.2. Tessel2

Similar to its old model, Tessel2 is a JavaScript-enabled embedded system with on-board WiFi capabilities designed for IoT developers. Tessel2 features a 580 MHz Mediatek MT7620n router-on-a-chip + 48MHz Atmel SAMD21 coprocessor, running Linux built on OpenWRT with 64MB of DDR2 RAM, and 32MB of Flash memory. Tessel2 is compatible with Node.js and runs JavaScript programs directly for controlling a wide variety IoT modules; it allows developers to easily control modules via a pair of multipurpose ports. Tessel2 is also programmable in other programming languages; however, a part of browser-side JavaScript libraries or objects is not supported.


## 3.3. Android WebView, PC, and Mac

Android has a built-in browser-like activity which is called WebView. It can be used to display web pages or HTML files as a part of UI. Developers can build a WebView activity to show online content or user data within applications. Android 4.4 has replaced the rendering engine of WebView with Chromium’s V8 engine to deliver improved JavaScript performance. We chose WebView in Android 4.4 (KitKat) to benchmark our JavaScript implementation and ran our implementation on an Android phone Xperia XZ SOV34 (Android version 8.0.0 (Oreo)).Some operating systems also provide tools to execute plain text files within a shell/script. The Microsoft Windows Script Host (WSH) is described as an administration tool to provide a scripting environment for batch files. The Active Scripting language engines of WSH can interpret and run script files such as JScript or VBScript. Similarly, Mac users can run JavaScript files by using osascript command, which works with AppleScripts or other Open Scripting Architecture (OSA) language scripts on macOS.In addition, some nonbrowser software such as Node.js or Pacifista also provide JavaScript runtime environment. Like Google Chrome and Android WebView, Node.js is also built on the Google V8 JavaScript engine and offers a rich variety of JavaScript modules which will be of benefit to development. Pacifista is a simple Java-based open-source project that builds a Linux environment and can upgrade OpenSSL using JavaScript; it can be downloaded athttps://github.com/ukiuni/pacifista.Our implementation is measured on a test PC and a MacBook Pro. The test PC has the following specification: CPU: Intel(R) Core(TM) i5-8250U @1.6GHz; 8GB DDR3 RAM; 256GB SSD; Windows 10 build 17134 Home x64. The MacBook Pro (15-inch, 2017 model) features quad-core Intel(R) Core(TM) i7 @2.8GHz, 16GB 2133MHz LPDDR3 memory, and 512GB SSD with macOS High Sierra 10.13.5. Node.js 8.11.2 and Pacifista 0.0.30 are installed on the test PC and MacBook Pro, respectively. We tested our implementation on the four JavaScript run-time environments above. We ran the code on WSH and Node.js for PC and ran on osascript and Pacifista for Mac (see Appendix for the commands).


## 4. Efficient Algorithms for JavaScript Implementation

### 4.1. Discrete Gaussian Sampling

Letl∈Z be the precision of binary expansion of the probabilities and n∈Z; there are n binary probabilities p0,p1,…,pn-1∈Z2l. A probability matrix Pmat=[p0,p1,…,pn-1]∈Z2l×n is composed of all the computed probabilities, and each column stores one probability. Let k0,k1,…,kl-1∈Z2n be all the rows of Pmat; hence, Pmat can be stored as a one-dimensional array k=(k0,k1,…,kl-1)∈Z2ln for Algorithm 1.Algorithm 1:Knuth-Yao algorithm.
Input: l,n∈Z, a probability array k = ( k 0 , k 1 , … , k l - 1 ) ∈ Z 2 l n Output: Sample value s∈Z∩[-tσ,tσ] 1 Letd=0, x=0, sign=0; 2while  true  do 3r←{0,1} uniformly at random; 4d=2d+r; 5for  i=n down to 0 by 1  do 6d=d-ki; 7 if  d=-1  then 8if  i=0  then  sign←{0,1} uniformly at random; 9else 10sign←{-1,1} uniformly at random; 11return  s=sign∗row; 12endif 13if  sign=1  then return  s=i; 14else 15d=0; 16r←{0,1} uniformly at random; 17d=2d+r; 18x=0; 19continue 20endif 21endif 22endfor 23x+=1; 24endwhileWith limited computing capacity, the computation of probabilities would become a time-consuming operation for some programming languages or platforms. In general, discrete Gaussian sampling requires a high-precision floating-point operation or large storage requirement [35] to ensure the security level. Inspired by the idea of implementing Knuth-Yao algorithm in FPGAs [27], we modify and implement the algorithm in JavaScript. Moreover, discrete Ziggurat algorithm [30] which allows for a time-memory trade-off has been changed to be portable in chosen platforms. In this case, Knuth-Yao algorithm shows better performance than modified discrete Ziggurat algorithm. In fact, with different features, the performance of those two sampling algorithms varies on different platforms. Therefore, we choose Knuth-Yao algorithm to speed up discrete Gaussian sampling.


### 4.2. Number Theoretic Transform

NTT is an efficient approach of generalization of fast Fourier transforms (FFT) doing a transform over the finite fieldZq(q>0) instead of the complex number field C. It has lower asymptotic complexity O(nlog⁡n) for multiplying polynomials with higher degrees.Forn being a power of 2 and q a prime number with q≡1mod⁡2n, NTT accepts a polynomial a∈Rq, whose coefficients are in the standard order as input, and outputs another polynomial a′=NTT(a). a′ can be defined as ai′=∑j=0n-1ajωijmod⁡q(i=0,1,…,n-1), where ω is a n-th primitive root of unity in Zq. Similarly, we denote the inverse NTT as NTT-1 that a=NTT-1(a′), where ai=n-1∑j=0n-1‍aj′ω-ijmod⁡q(i=0,1,…,n-1), such that the output of NTT-1 satisfies NTT-1(NTT(a))=a.We have implemented iterative forward NTT [11, 36] algorithm in our previous works [12, 13]. Both Kyber and NewHope are required to perform polynomial multiplication, and some literature such as [23, 24] provided efficient polynomial multiplication methods to combine bit reversal with NTT computation; hence, in this paper, we follow the state-of-the-art and implement optimized NTT/NTT-1 as shown in Algorithms 2 and 3.Algorithm 2:Cooley-Tukey(CT) forward number theoretic transform (NTT).
Input: Polynomial a∈Rq=Zq[x]/(xn+1), and a LUT Ψrev∈Zqn in bit-reversed order Output: Polynomial a′=NTT(a)∈Rq 1t=n; 2for  m=1  to  n-1 by m=2m  do 3t=t/2; 4for  i=0  to  m-1  do 5j1=2∗i∗t; 6j2=j1+t-1; 7S=Ψrev[m+i]; 8for  j=j1  to  j2  do 9U=aj; 10V=aj+t∗S; 11aj=U+Vmod⁡q; 12aj+t=U-Vmod⁡q; 13endfor 14endfor 15endfor 16return  a.Algorithm 3:Gentleman-Sande (GS) inverse number theoretic transform (NTT-1).
Input: Polynomial a′∈Rq=Zq[x]/(xn+1), and a LUT Ψrev-1∈Zqn in bit-reversed order Output: Polynomial a=NTT-1(a′)∈Rq 1t=1; 2for  m=n to 2 by m=m/2 do 3h=m/2,j1=0; 4for  i=0  to  h-1  do 5j2=j1+t-1; 6S=Ψrev-1[h+i]; 7for  j=j1  to  j2  do 8U=aj; 9V=aj+t; 10aj=U+Vmodq; 11aj+t=(U-V)∗Smodq; 12endfor 13j1=j1+2t; 14endfor 15t=2t; 16endfor 17for  i=0  to  n-1  do 18ai=ai∗n-1mod⁡q; 19endfor 20return  a.Letψ∈Zq be a primitive 2n-th root of unity such that ω=ψ2. We write two polynomials f=(f0,f1,…,fn-1) and f-=(f0,ψf1,…,ψn-1fn-1)∈Rq. To compute the polynomial multiplication c=a·b∈Rq, first we precompute all 2n powers of ψ and ψ-1 and then store n powers of ψ and ψ-1 with bit-reversed order in look-up tables Ψrev, Ψrev-1∈Zqn, respectively. So the bit-reverse operation for input polynomial can be merged into precomputation. Then we obtain the negative wrapped convolution c=(1,ψ-1,…,ψ-(n-1))∘NTT-1(NTT(a-)∘NTT(b-)), where ∘ denotes the point-wise multiplication.


## 4.1. Discrete Gaussian Sampling

Letl∈Z be the precision of binary expansion of the probabilities and n∈Z; there are n binary probabilities p0,p1,…,pn-1∈Z2l. A probability matrix Pmat=[p0,p1,…,pn-1]∈Z2l×n is composed of all the computed probabilities, and each column stores one probability. Let k0,k1,…,kl-1∈Z2n be all the rows of Pmat; hence, Pmat can be stored as a one-dimensional array k=(k0,k1,…,kl-1)∈Z2ln for Algorithm 1.Algorithm 1:Knuth-Yao algorithm.
Input: l,n∈Z, a probability array k = ( k 0 , k 1 , … , k l - 1 ) ∈ Z 2 l n Output: Sample value s∈Z∩[-tσ,tσ] 1 Letd=0, x=0, sign=0; 2while  true  do 3r←{0,1} uniformly at random; 4d=2d+r; 5for  i=n down to 0 by 1  do 6d=d-ki; 7 if  d=-1  then 8if  i=0  then  sign←{0,1} uniformly at random; 9else 10sign←{-1,1} uniformly at random; 11return  s=sign∗row; 12endif 13if  sign=1  then return  s=i; 14else 15d=0; 16r←{0,1} uniformly at random; 17d=2d+r; 18x=0; 19continue 20endif 21endif 22endfor 23x+=1; 24endwhileWith limited computing capacity, the computation of probabilities would become a time-consuming operation for some programming languages or platforms. In general, discrete Gaussian sampling requires a high-precision floating-point operation or large storage requirement [35] to ensure the security level. Inspired by the idea of implementing Knuth-Yao algorithm in FPGAs [27], we modify and implement the algorithm in JavaScript. Moreover, discrete Ziggurat algorithm [30] which allows for a time-memory trade-off has been changed to be portable in chosen platforms. In this case, Knuth-Yao algorithm shows better performance than modified discrete Ziggurat algorithm. In fact, with different features, the performance of those two sampling algorithms varies on different platforms. Therefore, we choose Knuth-Yao algorithm to speed up discrete Gaussian sampling.


## 4.2. Number Theoretic Transform

NTT is an efficient approach of generalization of fast Fourier transforms (FFT) doing a transform over the finite fieldZq(q>0) instead of the complex number field C. It has lower asymptotic complexity O(nlog⁡n) for multiplying polynomials with higher degrees.Forn being a power of 2 and q a prime number with q≡1mod⁡2n, NTT accepts a polynomial a∈Rq, whose coefficients are in the standard order as input, and outputs another polynomial a′=NTT(a). a′ can be defined as ai′=∑j=0n-1ajωijmod⁡q(i=0,1,…,n-1), where ω is a n-th primitive root of unity in Zq. Similarly, we denote the inverse NTT as NTT-1 that a=NTT-1(a′), where ai=n-1∑j=0n-1‍aj′ω-ijmod⁡q(i=0,1,…,n-1), such that the output of NTT-1 satisfies NTT-1(NTT(a))=a.We have implemented iterative forward NTT [11, 36] algorithm in our previous works [12, 13]. Both Kyber and NewHope are required to perform polynomial multiplication, and some literature such as [23, 24] provided efficient polynomial multiplication methods to combine bit reversal with NTT computation; hence, in this paper, we follow the state-of-the-art and implement optimized NTT/NTT-1 as shown in Algorithms 2 and 3.Algorithm 2:Cooley-Tukey(CT) forward number theoretic transform (NTT).
Input: Polynomial a∈Rq=Zq[x]/(xn+1), and a LUT Ψrev∈Zqn in bit-reversed order Output: Polynomial a′=NTT(a)∈Rq 1t=n; 2for  m=1  to  n-1 by m=2m  do 3t=t/2; 4for  i=0  to  m-1  do 5j1=2∗i∗t; 6j2=j1+t-1; 7S=Ψrev[m+i]; 8for  j=j1  to  j2  do 9U=aj; 10V=aj+t∗S; 11aj=U+Vmod⁡q; 12aj+t=U-Vmod⁡q; 13endfor 14endfor 15endfor 16return  a.Algorithm 3:Gentleman-Sande (GS) inverse number theoretic transform (NTT-1).
Input: Polynomial a′∈Rq=Zq[x]/(xn+1), and a LUT Ψrev-1∈Zqn in bit-reversed order Output: Polynomial a=NTT-1(a′)∈Rq 1t=1; 2for  m=n to 2 by m=m/2 do 3h=m/2,j1=0; 4for  i=0  to  h-1  do 5j2=j1+t-1; 6S=Ψrev-1[h+i]; 7for  j=j1  to  j2  do 8U=aj; 9V=aj+t; 10aj=U+Vmodq; 11aj+t=(U-V)∗Smodq; 12endfor 13j1=j1+2t; 14endfor 15t=2t; 16endfor 17for  i=0  to  n-1  do 18ai=ai∗n-1mod⁡q; 19endfor 20return  a.Letψ∈Zq be a primitive 2n-th root of unity such that ω=ψ2. We write two polynomials f=(f0,f1,…,fn-1) and f-=(f0,ψf1,…,ψn-1fn-1)∈Rq. To compute the polynomial multiplication c=a·b∈Rq, first we precompute all 2n powers of ψ and ψ-1 and then store n powers of ψ and ψ-1 with bit-reversed order in look-up tables Ψrev, Ψrev-1∈Zqn, respectively. So the bit-reverse operation for input polynomial can be merged into precomputation. Then we obtain the negative wrapped convolution c=(1,ψ-1,…,ψ-(n-1))∘NTT-1(NTT(a-)∘NTT(b-)), where ∘ denotes the point-wise multiplication.


## 5. Performance on Web Browsers

We implemented three encryption schemes: Lizard, ring-Lizard [15], Kyber [16], and two key exchange protocols: Frodo [17] and NewHope [18] in JavaScript. Again, it should be noted that we mainly focus on the computation process and discrete Gaussian sampling in this paper. Hence, we omitted some steps about the generation, encoding/decoding functions for uniformly chosen public key component or binary seeds. We will go into detail of our implementation performance in this section. The simple usage of our implementation is described in the Appendix.For comparison, we implemented those five lattice-based cryptosystems corresponding to about 128-bit postquantum security level (see Table1). Figure 3 shows the performance results of our implementation executed on the Firefox browser. As we expected, the ring-LWE based cryptosystems including Kyber and NewHope are apparently very efficient. The key size of Kyber is smaller than that of Lizard, although Kyber has large moduli. Key generation of Kyber runs over 400 times faster than that of Lizard, but decryption of Lizard is the fastest. Key generation and encryption of ring-Lizard are over 60 and 4 times faster than that of Lizard; however, Kyber is still much more efficient than ring-Lizard. Compared with Frodo, both Alice’s and Bob’s sides of NewHope run over 8 times and 13 times faster, respectively.Figure 3
Running time (ms) of lattice-based cryptosystems Lizard, ring-Lizard, Kyber, Frodo, and NewHope on Firefox.For Lizard, we stored the matrices in two-dimensional arrays, to reduce the running time of matrix multiplication due to the row-major order matrix convention in JavaScript. Specifically, we computed the product of a vector with a matrix transpose instead of calculating the matrix-vector product. In addition, the elements ofs in key generation and r in encryption only contain the values from the set {0,±1}; hence, we could replace integer multiplication with addition and subtraction if multiplicand equals ±1. For ring-Lizard, we computed polynomial multiplication by using Karatsuba algorithm because the moduli of ring-Lizard are powers of 2.For Kyber, we skipped the generation of binary seeds and polynomials. In key generation and encryption, we precomputedA and NTT(q/2∗m) and sampled the error vectors from a binomial distribution B4. Each element of matrices and vectors in Kyber is a polynomial over Rq with degree equal to n-1 (q≡1mod⁡2n); hence, NTT can be applied to Kyber to effectively compute polynomial multiplication. Let i,j,k be positive integers; we assume a matrix A=(aij)∈(Rq)k×k is in NTT domain, and the coefficients of each element aij are in bit-reversed order. In key generation, we performed NTT on error vectors such that the component of public key b=NTT-1(ANTT(s)+NTT(e)), only 6 calls ofNTT and 3 calls of NTT-1 are necessary if k=3. Similarly, we computed NTT-1(NTT(AT)NTT(r)+NTT(e1)) and NTT-1(NTT(bT)NTT(r)+NTT(e2)+NTT(q/2∗m)) by invoking NTT 10 times and NTT-1 4 times in encryption and outputted NTT-1(NTT(s)Tu) by invoking NTT 4 times and NTT-1 1 time in decryption.For Frodo, we skipped the generation of theseedA from a binary string and precomputed the matrix A on both Alice’s and Bob’s sides. There is no problem to perform floating-point arithmetic on the JavaScript-enabled platforms, but we replace floating point arithmetic to integer arithmetic in therounding/cross-rounding andreconciliation functions considering our follow-up development on memory-constrained devices. To sample the error matrices, we performed our modified Knuth-Yao algorithm as shown in Algorithm 1.For NewHope, we also performedNTT/NTT-1 to speed up the polynomial multiplication which is a bottleneck for ring-LWE based cryptography in JavaScript (e.g., see [13, 14]). In this case, we implemented NewHope following [18] (Section 7.1, Protocol 3) but skippedSHAKE-128 method, hash functionSHA3-256, and key encoding/decoding functions. We precomputed the polynomial a on both Alice’s and Bob’s sides and sent polynomials b,u,r directly. Comparing our implementation with the approach in [24], we only computed NTT-1(b∘NTT(s1))+e2 on Bob’s side so that the computation of NTT(e2) has been omitted.Figure4 shows the decomposition of computation time of our implementation. Although each implementation technique and performance is different, polynomial and matrix multiplication are still the most time-consuming computation. In Lizard and Frodo, matrix multiplication accounts for at least 70%. In Kyber and NewHope, more than 50% of the running time is spent in NTT/NTT-1. Except for ring-Lizard, the error elements generation including discrete Gaussian sampling and binomial sampling costs little running time in the calculations, accounting about 20% for Frodo and about 10% in Lizard, Kyber, and NewHope; discrete Gaussian sampling accounts for about 50% in key-generation of ring-Lizard.Figure 4
Decomposition of computation time (ms) of Lizard, ring-Lizard, Kyber, Frodo, and NewHope on Firefox.We executed the same JavaScript programs on other desktop PC browsers including Google Chrome, Opera, and Edge. Taking Kyber and NewHope as examples, Figure5 shows the running time on those web browsers. It appears that the performance of our implementation executed on both Chrome and Opera is quite similar, and Firefox delivers the better performance than Edge.Figure 5
Running time (ms) of Kyber and NewHope on Firefox, Google Chrome, Opera, and Microsoft Edge.


## 6. Performance on Other JavaScript-Enabled Platforms

In this section, we present the implementation performance comparison on IoT device Tessel2, Android phone, Windows, and macOS. Our implementation is designed to be portable and can be executed on those experimental platforms directly without modification. In this case, we precomputed random values generation and discrete Gaussian sampling because of the difficulty of implementing cryptographic secure PRNG in JavaScript on microcontrollers such as Tessel2 (see [13]).


### 6.1. Tessel2

Figure6 shows the performance of our implementation executed on Tessel2 (for Lizard, the sizes of keys are too large to be generated on Tessel2). Note that the running time is measured in seconds. We have implemented the ring-LWE based encryption scheme [5] on the old model of Tessel (see [13]). As in our previous work, the performance results achieved on Tessel2 are several orders of magnitude slower than that on web browsers. However, Tessel2 has upgraded hardware specification with better computing capacity. For example, encryption and decryption of Kyber are over 1000 times slower than that of running on Firefox. But the performance of Kyber and NewHope is still unexpectedly high, and the calculation process can be completed within 1 or 2 seconds. Even though the computation of Kyber/NewHope is more complicated than [5], noticeable effects can be achieved in hardware performance and memory costs with our improved implementation.Figure 6
Running time (second) of lattice-based cryptosystems Lizard, ring-Lizard, Kyber, Frodo, and NewHope on Tessel2.


### 6.2. Android Phone

WebView is an extension of Android’s View class to display web pages and applications. It provides different performance from other web browsers on Android framework. We ran our implementation on Android phone Xperia XZ au SOV34, which is equipped with Qualcomm Snapdragon 820 MSM8996/2.2GHz DualCore + 1.6GHz DualCore and 3GB RAM. We created an HTML file that includes our JavaScript code and loaded it as a local file into WebView.Table2 shows the running time of our implementation on Android phone. From the performance results, it is clear that the performance of ring-LWE based cryptosystems is also acceptable. For encryption schemes, Kyber runs about 3 times faster than ring-Lizard, as well as over 4 times faster than Lizard. For key-exchange protocols, Frodo runs about 10 times slower than NewHope; matrix multiplication accounts for about 80% in Alice’s side and 90% in Bod’s side; the ratio is higher than that of on Firefox. Overall, the running speed achieved on Xperia XZ au SOV34 is at least 5 times slower than that on Firefox.Table 2
Performance results on Android phone.
Average running time (ms) Key Generation Encryption Decryption Lizard 1575.91 38.62 9.63 Ring-Lizard 13.24 15.05 5.61 Kyber 3.57 5.78 2.14  Average running time (ms) Alice0 Bob Alice1  Frodo 38.10 88.03 0.79 NewHope 5.14 10.08 2.68


### 6.3. Other JavaScript Run-Time Environments on Windows and macOS

For comparison, we investigated the performance of our JavaScript implementation on PC and Mac. It is not difficult to execute our code on other JavaScript run-time environments directly since our implementation has excellent portability. Those environments rely on specific platforms or OS for scripting. For example, JavaScript files (.js type) can be run in GUI mode via WScript.exe and Windows Command Prompt by calling CScript.exe; running Pacifista requires the installation of Java Runtime Environment (JRE). As of now, the performance of postquantum cryptography in JavaScript on those platforms has rarely been studied. To the best of our knowledge, this work is the first. In this case, we used WSH and Node.js on Windows 10 Home and used osascript and Pacifista on macOS High Sierra.From Tables3, 4, 5, and 6, we can see that there is a huge performance gap in running the JavaScript code on WSH with other platforms. The running speed of WSH is the slowest; e.g., key generation of Lizard on WSH is about 100 times slower than that on osascript, encryption is over 250 times slower, and decryption is over 150 times slower. Running NewHope on WSH is about 15 times slower than that on Firefox (without consideration of the cost of random values generation).Table 3
Performance results on WSH.
Average running time (ms) Key Generation Encryption Decryption Lizard 27021.1 372.2 72.3 Ring-Lizard 145.44 283.19 140.37 Kyber 9.89 15.76 6.15  Average running time (ms) Alice0 Bob Alice1  Frodo 827.03 1102.92 12.70 NewHope 8.85 17.51 6.67Table 4
Performance results on Node.js.
Average running time (ms) Key Generation Encryption Decryption Lizard 271.08 6.54 1.47 Ring-Lizard 1.86 2.48 1.22 Kyber 0.44 0.67 0.27  Average running time (ms) Alice0 Bob Alice1  Frodo 7.04 14.73 0.13 NewHope 0.20 0.64 0.19Table 5
Performance results on osascript.
Average running time (ms) Key Generation Encryption Decryption Lizard 209.99 1.43 0.41 Ring-Lizard 3.10 4.66 2.44 Kyber 0.80 1.20 0.49  Average running time (ms) Alice0 Bob Alice1  Frodo 6.88 10.46 0.09 NewHope 0.75 1.32 0.43Table 6
Performance results on Pacifista.
Average running time (ms) Key Generation Encryption Decryption Lizard 1301.54 24.67 5.76 Ring-Lizard 43.77 34.24 17.97 Kyber 7.39 4.49 1.78  Average running time (ms) Alice0 Bob Alice1  Frodo 35.80 43.96 0.75 NewHope 2.57 9.27 3.08Node.js delivers almost the best performance for ring-LWE based cryptosystems. For example, Kyber runs about 2 times faster than that on osascript, and ring-Lizard runs over 10 times faster than that on Pacifista. The performance of Node.js is almost the same as on Google Chrome, which also uses Google’s V8 JavaScript engine.Osascript is also an effective platform for macOS; e.g., running Frodo on osascript is slightly faster than that on Firefox; encryption of ring-Lizard is about 3 times and 5000 times faster than that on Xperia XZ au SOV34 and Tessel2, respectively.The running speed of Pacifista is less than Node.js and osascript, but still higher than WSH and can be comparable to Android WebView; hence, its performance is acceptable to the developers. The exception for all three encryption schemes is that the running time of key generation is longer than that of encryption.


## 6.1. Tessel2

Figure6 shows the performance of our implementation executed on Tessel2 (for Lizard, the sizes of keys are too large to be generated on Tessel2). Note that the running time is measured in seconds. We have implemented the ring-LWE based encryption scheme [5] on the old model of Tessel (see [13]). As in our previous work, the performance results achieved on Tessel2 are several orders of magnitude slower than that on web browsers. However, Tessel2 has upgraded hardware specification with better computing capacity. For example, encryption and decryption of Kyber are over 1000 times slower than that of running on Firefox. But the performance of Kyber and NewHope is still unexpectedly high, and the calculation process can be completed within 1 or 2 seconds. Even though the computation of Kyber/NewHope is more complicated than [5], noticeable effects can be achieved in hardware performance and memory costs with our improved implementation.Figure 6
Running time (second) of lattice-based cryptosystems Lizard, ring-Lizard, Kyber, Frodo, and NewHope on Tessel2.


## 6.2. Android Phone

WebView is an extension of Android’s View class to display web pages and applications. It provides different performance from other web browsers on Android framework. We ran our implementation on Android phone Xperia XZ au SOV34, which is equipped with Qualcomm Snapdragon 820 MSM8996/2.2GHz DualCore + 1.6GHz DualCore and 3GB RAM. We created an HTML file that includes our JavaScript code and loaded it as a local file into WebView.Table2 shows the running time of our implementation on Android phone. From the performance results, it is clear that the performance of ring-LWE based cryptosystems is also acceptable. For encryption schemes, Kyber runs about 3 times faster than ring-Lizard, as well as over 4 times faster than Lizard. For key-exchange protocols, Frodo runs about 10 times slower than NewHope; matrix multiplication accounts for about 80% in Alice’s side and 90% in Bod’s side; the ratio is higher than that of on Firefox. Overall, the running speed achieved on Xperia XZ au SOV34 is at least 5 times slower than that on Firefox.Table 2
Performance results on Android phone.
Average running time (ms) Key Generation Encryption Decryption Lizard 1575.91 38.62 9.63 Ring-Lizard 13.24 15.05 5.61 Kyber 3.57 5.78 2.14  Average running time (ms) Alice0 Bob Alice1  Frodo 38.10 88.03 0.79 NewHope 5.14 10.08 2.68


## 6.3. Other JavaScript Run-Time Environments on Windows and macOS

For comparison, we investigated the performance of our JavaScript implementation on PC and Mac. It is not difficult to execute our code on other JavaScript run-time environments directly since our implementation has excellent portability. Those environments rely on specific platforms or OS for scripting. For example, JavaScript files (.js type) can be run in GUI mode via WScript.exe and Windows Command Prompt by calling CScript.exe; running Pacifista requires the installation of Java Runtime Environment (JRE). As of now, the performance of postquantum cryptography in JavaScript on those platforms has rarely been studied. To the best of our knowledge, this work is the first. In this case, we used WSH and Node.js on Windows 10 Home and used osascript and Pacifista on macOS High Sierra.From Tables3, 4, 5, and 6, we can see that there is a huge performance gap in running the JavaScript code on WSH with other platforms. The running speed of WSH is the slowest; e.g., key generation of Lizard on WSH is about 100 times slower than that on osascript, encryption is over 250 times slower, and decryption is over 150 times slower. Running NewHope on WSH is about 15 times slower than that on Firefox (without consideration of the cost of random values generation).Table 3
Performance results on WSH.
Average running time (ms) Key Generation Encryption Decryption Lizard 27021.1 372.2 72.3 Ring-Lizard 145.44 283.19 140.37 Kyber 9.89 15.76 6.15  Average running time (ms) Alice0 Bob Alice1  Frodo 827.03 1102.92 12.70 NewHope 8.85 17.51 6.67Table 4
Performance results on Node.js.
Average running time (ms) Key Generation Encryption Decryption Lizard 271.08 6.54 1.47 Ring-Lizard 1.86 2.48 1.22 Kyber 0.44 0.67 0.27  Average running time (ms) Alice0 Bob Alice1  Frodo 7.04 14.73 0.13 NewHope 0.20 0.64 0.19Table 5
Performance results on osascript.
Average running time (ms) Key Generation Encryption Decryption Lizard 209.99 1.43 0.41 Ring-Lizard 3.10 4.66 2.44 Kyber 0.80 1.20 0.49  Average running time (ms) Alice0 Bob Alice1  Frodo 6.88 10.46 0.09 NewHope 0.75 1.32 0.43Table 6
Performance results on Pacifista.
Average running time (ms) Key Generation Encryption Decryption Lizard 1301.54 24.67 5.76 Ring-Lizard 43.77 34.24 17.97 Kyber 7.39 4.49 1.78  Average running time (ms) Alice0 Bob Alice1  Frodo 35.80 43.96 0.75 NewHope 2.57 9.27 3.08Node.js delivers almost the best performance for ring-LWE based cryptosystems. For example, Kyber runs about 2 times faster than that on osascript, and ring-Lizard runs over 10 times faster than that on Pacifista. The performance of Node.js is almost the same as on Google Chrome, which also uses Google’s V8 JavaScript engine.Osascript is also an effective platform for macOS; e.g., running Frodo on osascript is slightly faster than that on Firefox; encryption of ring-Lizard is about 3 times and 5000 times faster than that on Xperia XZ au SOV34 and Tessel2, respectively.The running speed of Pacifista is less than Node.js and osascript, but still higher than WSH and can be comparable to Android WebView; hence, its performance is acceptable to the developers. The exception for all three encryption schemes is that the running time of key generation is longer than that of encryption.


## 7. Conclusions

We first implemented five new lattice-based encryption schemes (Lizard, ring-Lizard, Kyber) and key exchange protocols (Frodo, NewHope) in JavaScript and tested their performances on web browsers, Tessel2, Android phone, and other platforms on PC and Mac. Our code can be executed on any JavaScript-enabled platforms since it has good portability. We used NTT to improve the speed of polynomial multiplication and modified Knuth-Yao algorithm for discrete Gaussian sampling. We reported the performance results of our implementation on multiple JavaScript-enabled platforms; by contrast, the ring-LWE based cryptosystems show better performance than others. Our proof-of-concept implementation demonstrates that some of the lattice-based cryptosystems can be implemented efficiently in JavaScript. Hence, our work could be a good reference for lattice-based cryptography in the standardization process of NIST. In our future work, we expect to improve the implementation for particular platforms and investigate more lattice-based public-key encryption schemes and KEM on more platforms for the NIST PQC standardization project.



---

*Source: 9846168-2018-09-13.xml*