May  2019, 13(2): 221-233. doi: 10.3934/amc.2019015

Comparison analysis of Ding's RLWE-based key exchange protocol and NewHope variants

Beijing Key Laboratory of Security and Privacy in Intelligent Transportation, Beijing Jiaotong University, No.3 ShangYuanCun, Haidian District, Beijing 100044, China

* Corresponding author: Xinwei Gao

Received  January 2018 Revised  May 2018 Published  February 2019

In this paper, we present a comparison study on three RLWE key exchange protocols: one from Ding et al. in 2012 (DING12) and two from Alkim et al. in 2016 (NewHope and NewHope-Simple). We compare and analyze protocol construction, notion of designing and realizing key exchange, signal computation, error reconciliation and cost of these three protocols. We show that NewHope and NewHope-Simple share very similar notion as DING12 in the sense that NewHope series also send small additional bits with small size (i.e. signal) to assist error reconciliation, where this idea was first practically proposed in DING12. We believe that DING12 is the first work that presented complete LWE & RLWE-based key exchange constructions. The idea of sending additional information in order to realize error reconciliation and key exchange in NewHope and NewHope-Simple remain the same as DING12, despite concrete approaches to compute signal and reconcile error are not the same.

Citation: Xinwei Gao. Comparison analysis of Ding's RLWE-based key exchange protocol and NewHope variants. Advances in Mathematics of Communications, 2019, 13 (2) : 221-233. doi: 10.3934/amc.2019015
References:
[1]

24-cell, Page Version ID: 822760596. https://en.wikipedia.org/w/index.php?title=24-cell&oldid=822760596Google Scholar

[2]

M. R. Albrecht, On dual lattice attacks against small-secret lwe and parameter choices in helib and seal, in Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 10211 (2017), 103–129. Google Scholar

[3]

M. R. Albrecht, F. Göpfert, F. Virdia and T. Wunderer, Revisiting the expected cost of solving usvp and applications to lwe, in International Conference on the Theory and Application of Cryptology and Information Security, Springer, 10624 (2017), 297–322. Google Scholar

[4]

M. R. AlbrechtR. Player and S. Scott, On the concrete hardness of learning with errors, Journal of Mathematical Cryptology, 9 (2015), 169-203. doi: 10.1515/jmc-2015-0016. Google Scholar

[5]

E. Alkim, L. Ducas, T. Pöppelmann and P. Schwabe, Newhope without reconciliation, IACR Cryptology ePrint Archive, 2016 (2016), 1157.Google Scholar

[6]

E. Alkim, L. Ducas, T. Pöppelmann and P. Schwabe, Post-quantum key exchange-a new hope, in USENIX Security Symposium, 2016,327–343.Google Scholar

[7]

J. Bos, C. Costello, L. Ducas, I. Mironov, M. Naehrig, V. Nikolaenko, A. Raghunathan and D. Stebila, Frodo: Take off the ring! practical, quantum-secure key exchange from lwe, in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, ACM, 2016, 1006–1018. doi: 10.1145/2976749.2978425. Google Scholar

[8]

J. W. Bos, C. Costello, M. Naehrig and D. Stebila, Post-quantum key exchange for the tls protocol from the ring learning with errors problem, in Security and Privacy (SP), 2015 IEEE Symposium on, IEEE, 2015,553–570. doi: 10.1109/SP.2015.40. Google Scholar

[9]

W. Diffie and M. Hellman, New directions in cryptography, IEEE transactions on Information Theory, 22 (1976), 644-654. doi: 10.1109/tit.1976.1055638. Google Scholar

[10]

J. Ding, S. Alsayigh, J. Lancrenon, S. RV and M. Snook, Provably secure password authenticated key exchange based on rlwe for the post-quantum world, in Cryptographers Track at the RSA Conference, Springer, 10159 (2017), 183–204. Google Scholar

[11]

J. Ding, X. Xie and X. Lin, A simple provably secure key exchange scheme based on the learning with errors problem., IACR Cryptology EPrint Archive, 2012 (2012), 688.Google Scholar

[12]

M. S. Dousti and R. Jalili, Forsakes: A forward-secure authenticated key exchange protocol based on symmetric key-evolving schemes, Advances in Mathematics of Communications, 9 (2015), 471-514. doi: 10.3934/amc.2015.9.471. Google Scholar

[13]

X. GaoJ. DingL. Li and J. Liu, Practical randomized rlwe-based key exchange against signal leakage attack, IEEE Transactions on Computers, 67 (2018), 1584-1593. doi: 10.1109/TC.2018.2808527. Google Scholar

[14]

X. GaoJ. DingL. LiS. RV and J. Liu, Efficient implementation of password-based authenticated key exchange from rlwe and post-quantum tls, International Journal of Network Security, 20 (2018), 923-930. Google Scholar

[15]

X. Gao, J. Ding, J. Liu and L. Li, Post-quantum secure remote password protocol from rlwe problem, in International Conference on Information Security and Cryptology, Springer, 10726 (2017), 99–116. Google Scholar

[16]

X. Gao, J. Ding, S. RV, L. Li and J. Liu, Comparison analysis and efficient implementation of reconciliation-based rlwe key exchange protocol, IACR Cryptology ePrint Archive, 2017 (2017), 1178.Google Scholar

[17]

X. Gao, L. Li, J. Ding, J. Liu, S. RV and Z. Liu, Fast discretized gaussian sampling and post-quantum tls ciphersuite, in International Conference on Information Security Practice and Experience, Springer, 2017,551–565. doi: 10.1007/978-3-319-72359-4_33. Google Scholar

[18]

S. GonzálezL. HuguetC. Martínez and H. Villafañe, Discrete logarithm like problems and linear recurring sequences, Advances in Mathematics of Communications, 7 (2013), 187-195. doi: 10.3934/amc.2013.7.187. Google Scholar

[19]

V. Lyubashevsky, C. Peikert and O. Regev, On ideal lattices and learning with errors over rings, in Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 6110 (2010), 1–23. doi: 10.1007/978-3-642-13190-5_1. Google Scholar

[20]

G. Micheli, Cryptanalysis of a noncommutative key exchange protocol, Advances in Mathematics of Communications, 9 (2015), 247-253. doi: 10.3934/amc.2015.9.247. Google Scholar

[21]

C. Peikert, Public-key cryptosystems from the worst-case shortest vector problem, in Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, ACM, 2009,333–342. Google Scholar

[22]

C. Peikert, Lattice cryptography for the internet, in International Workshop on Post-Quantum Cryptography, Springer, 8772 (2014), 197–219. doi: 10.1007/978-3-319-11659-4_12. Google Scholar

[23]

C. Peikert et al., A decade of lattice cryptography, Foundations and Trends® in Theoretical Computer Science, 10 (2014), 283–424. doi: 10.1561/0400000074. Google Scholar

[24]

T. Pöppelmann and T. Güneysu, Towards practical lattice-based public-key encryption on reconfigurable hardware, in International Conference on Selected Areas in Cryptography, Springer, 2013, 68–85.Google Scholar

[25]

O. Regev, On lattices, learning with errors, random linear codes, and cryptography, Journal of the ACM (JACM), 56 (2009), Art. 34, 40 pp. doi: 10.1145/1568318.1568324. Google Scholar

[26]

P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Review, 41 (1999), 303-332. doi: 10.1137/S0036144598347011. Google Scholar

[27]

J. Zhang, Z. Zhang, J. Ding, M. Snook and Ö. Dagdelen, Authenticated key exchange from ideal lattices, in EUROCRYPT (2), 9057 (2015), 719–751. doi: 10.1007/978-3-662-46803-6_24. Google Scholar

show all references

References:
[1]

24-cell, Page Version ID: 822760596. https://en.wikipedia.org/w/index.php?title=24-cell&oldid=822760596Google Scholar

[2]

M. R. Albrecht, On dual lattice attacks against small-secret lwe and parameter choices in helib and seal, in Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 10211 (2017), 103–129. Google Scholar

[3]

M. R. Albrecht, F. Göpfert, F. Virdia and T. Wunderer, Revisiting the expected cost of solving usvp and applications to lwe, in International Conference on the Theory and Application of Cryptology and Information Security, Springer, 10624 (2017), 297–322. Google Scholar

[4]

M. R. AlbrechtR. Player and S. Scott, On the concrete hardness of learning with errors, Journal of Mathematical Cryptology, 9 (2015), 169-203. doi: 10.1515/jmc-2015-0016. Google Scholar

[5]

E. Alkim, L. Ducas, T. Pöppelmann and P. Schwabe, Newhope without reconciliation, IACR Cryptology ePrint Archive, 2016 (2016), 1157.Google Scholar

[6]

E. Alkim, L. Ducas, T. Pöppelmann and P. Schwabe, Post-quantum key exchange-a new hope, in USENIX Security Symposium, 2016,327–343.Google Scholar

[7]

J. Bos, C. Costello, L. Ducas, I. Mironov, M. Naehrig, V. Nikolaenko, A. Raghunathan and D. Stebila, Frodo: Take off the ring! practical, quantum-secure key exchange from lwe, in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, ACM, 2016, 1006–1018. doi: 10.1145/2976749.2978425. Google Scholar

[8]

J. W. Bos, C. Costello, M. Naehrig and D. Stebila, Post-quantum key exchange for the tls protocol from the ring learning with errors problem, in Security and Privacy (SP), 2015 IEEE Symposium on, IEEE, 2015,553–570. doi: 10.1109/SP.2015.40. Google Scholar

[9]

W. Diffie and M. Hellman, New directions in cryptography, IEEE transactions on Information Theory, 22 (1976), 644-654. doi: 10.1109/tit.1976.1055638. Google Scholar

[10]

J. Ding, S. Alsayigh, J. Lancrenon, S. RV and M. Snook, Provably secure password authenticated key exchange based on rlwe for the post-quantum world, in Cryptographers Track at the RSA Conference, Springer, 10159 (2017), 183–204. Google Scholar

[11]

J. Ding, X. Xie and X. Lin, A simple provably secure key exchange scheme based on the learning with errors problem., IACR Cryptology EPrint Archive, 2012 (2012), 688.Google Scholar

[12]

M. S. Dousti and R. Jalili, Forsakes: A forward-secure authenticated key exchange protocol based on symmetric key-evolving schemes, Advances in Mathematics of Communications, 9 (2015), 471-514. doi: 10.3934/amc.2015.9.471. Google Scholar

[13]

X. GaoJ. DingL. Li and J. Liu, Practical randomized rlwe-based key exchange against signal leakage attack, IEEE Transactions on Computers, 67 (2018), 1584-1593. doi: 10.1109/TC.2018.2808527. Google Scholar

[14]

X. GaoJ. DingL. LiS. RV and J. Liu, Efficient implementation of password-based authenticated key exchange from rlwe and post-quantum tls, International Journal of Network Security, 20 (2018), 923-930. Google Scholar

[15]

X. Gao, J. Ding, J. Liu and L. Li, Post-quantum secure remote password protocol from rlwe problem, in International Conference on Information Security and Cryptology, Springer, 10726 (2017), 99–116. Google Scholar

[16]

X. Gao, J. Ding, S. RV, L. Li and J. Liu, Comparison analysis and efficient implementation of reconciliation-based rlwe key exchange protocol, IACR Cryptology ePrint Archive, 2017 (2017), 1178.Google Scholar

[17]

X. Gao, L. Li, J. Ding, J. Liu, S. RV and Z. Liu, Fast discretized gaussian sampling and post-quantum tls ciphersuite, in International Conference on Information Security Practice and Experience, Springer, 2017,551–565. doi: 10.1007/978-3-319-72359-4_33. Google Scholar

[18]

S. GonzálezL. HuguetC. Martínez and H. Villafañe, Discrete logarithm like problems and linear recurring sequences, Advances in Mathematics of Communications, 7 (2013), 187-195. doi: 10.3934/amc.2013.7.187. Google Scholar

[19]

V. Lyubashevsky, C. Peikert and O. Regev, On ideal lattices and learning with errors over rings, in Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 6110 (2010), 1–23. doi: 10.1007/978-3-642-13190-5_1. Google Scholar

[20]

G. Micheli, Cryptanalysis of a noncommutative key exchange protocol, Advances in Mathematics of Communications, 9 (2015), 247-253. doi: 10.3934/amc.2015.9.247. Google Scholar

[21]

C. Peikert, Public-key cryptosystems from the worst-case shortest vector problem, in Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, ACM, 2009,333–342. Google Scholar

[22]

C. Peikert, Lattice cryptography for the internet, in International Workshop on Post-Quantum Cryptography, Springer, 8772 (2014), 197–219. doi: 10.1007/978-3-319-11659-4_12. Google Scholar

[23]

C. Peikert et al., A decade of lattice cryptography, Foundations and Trends® in Theoretical Computer Science, 10 (2014), 283–424. doi: 10.1561/0400000074. Google Scholar

[24]

T. Pöppelmann and T. Güneysu, Towards practical lattice-based public-key encryption on reconfigurable hardware, in International Conference on Selected Areas in Cryptography, Springer, 2013, 68–85.Google Scholar

[25]

O. Regev, On lattices, learning with errors, random linear codes, and cryptography, Journal of the ACM (JACM), 56 (2009), Art. 34, 40 pp. doi: 10.1145/1568318.1568324. Google Scholar

[26]

P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Review, 41 (1999), 303-332. doi: 10.1137/S0036144598347011. Google Scholar

[27]

J. Zhang, Z. Zhang, J. Ding, M. Snook and Ö. Dagdelen, Authenticated key exchange from ideal lattices, in EUROCRYPT (2), 9057 (2015), 719–751. doi: 10.1007/978-3-662-46803-6_24. Google Scholar

Figure 1.  DING12 RLWE key exchange protocol
Figure 2.  NewHope RLWE key exchange protocol
Figure 3.  Illustrated figure of simplified NewHope error reconciliation ($ d = 2 $)
Figure 4.  NewHope-Simple RLWE key exchange protocol
Figure 5.  Illustrated figure of NewHope-Simple and DING12 signal value computation
Table 1.  Summary Chart of DING12, BCNS15, NewHope, NewHope-Simple
DING12 BCNS15 NewHope NewHope-Simple
Signal
computation
● Divide $ \mathbb{Z}_q $ into 2 regions.
Different region gives
corresponding value
● Signal value $ \in\{0, 1\} $
● Function: Sig()
● Divide $ \mathbb{Z}_q $ into 2 regions.
Different region gives corresponding value
● Signal value $ \in\{0, 1\} $
● Function: $ \langle\cdot\rangle_{q, 2} $
Difference vector between coefficient vector and center of closest Voronoi cell
● Signal value $ \in\{0, 1, 2, 3\} $
● Function: HelpRec()
● Divide $ \mathbb{Z}_q $ into 8 regions.
Different region gives corresponding value
● Signal value $ \in\{0, \cdots, 7\} $
● Function: NHSCompress()
Error
reconciliation
● Add then mod 2 on each coefficient
● Extract least significant bit
● Function: Mod$ _2() $
● Multiply, round then mod 2 on each coefficient
● Extract most significant bit
● Function: rec(), $ \lfloor\cdot\rceil_{q, 2} $
● Add signal vector onto coefficient vector
● Decide key bit according to location of the sum vector
● Function: Rec()
● Variant of RLWE decryption
● Recovers encapsulated key
● Function: NHSDecode()
Degree $ n $ of $ R_q $ 1024 1024 1024 1024
Signal size ● 1-bit per coefficient
$ 1\cdot n = 1024 $ bits
● 1-bit per coefficient
$ 1\cdot n = 1024 $ bits
● 2-bit per coefficient
$ 2\cdot n = 2048 $ bits
● 3-bit per coefficient
$ 3\cdot n = 3072 $ bits
Key size $ n $ bits $ n $ bits 256 bits 256 bits
Category Diffie-Hellman-like Diffie-Hellman-like Diffie-Hellman-like KEM (Encryption)
DING12 BCNS15 NewHope NewHope-Simple
Signal
computation
● Divide $ \mathbb{Z}_q $ into 2 regions.
Different region gives
corresponding value
● Signal value $ \in\{0, 1\} $
● Function: Sig()
● Divide $ \mathbb{Z}_q $ into 2 regions.
Different region gives corresponding value
● Signal value $ \in\{0, 1\} $
● Function: $ \langle\cdot\rangle_{q, 2} $
Difference vector between coefficient vector and center of closest Voronoi cell
● Signal value $ \in\{0, 1, 2, 3\} $
● Function: HelpRec()
● Divide $ \mathbb{Z}_q $ into 8 regions.
Different region gives corresponding value
● Signal value $ \in\{0, \cdots, 7\} $
● Function: NHSCompress()
Error
reconciliation
● Add then mod 2 on each coefficient
● Extract least significant bit
● Function: Mod$ _2() $
● Multiply, round then mod 2 on each coefficient
● Extract most significant bit
● Function: rec(), $ \lfloor\cdot\rceil_{q, 2} $
● Add signal vector onto coefficient vector
● Decide key bit according to location of the sum vector
● Function: Rec()
● Variant of RLWE decryption
● Recovers encapsulated key
● Function: NHSDecode()
Degree $ n $ of $ R_q $ 1024 1024 1024 1024
Signal size ● 1-bit per coefficient
$ 1\cdot n = 1024 $ bits
● 1-bit per coefficient
$ 1\cdot n = 1024 $ bits
● 2-bit per coefficient
$ 2\cdot n = 2048 $ bits
● 3-bit per coefficient
$ 3\cdot n = 3072 $ bits
Key size $ n $ bits $ n $ bits 256 bits 256 bits
Category Diffie-Hellman-like Diffie-Hellman-like Diffie-Hellman-like KEM (Encryption)
[1]

Jintai Ding, Sihem Mesnager, Lih-Chung Wang. Letters for post-quantum cryptography standard evaluation. Advances in Mathematics of Communications, 2020, 14 (1) : i-i. doi: 10.3934/amc.2020012

[2]

Giacomo Micheli. Cryptanalysis of a noncommutative key exchange protocol. Advances in Mathematics of Communications, 2015, 9 (2) : 247-253. doi: 10.3934/amc.2015.9.247

[3]

Mohamed Baouch, Juan Antonio López-Ramos, Blas Torrecillas, Reto Schnyder. An active attack on a distributed Group Key Exchange system. Advances in Mathematics of Communications, 2017, 11 (4) : 715-717. doi: 10.3934/amc.2017052

[4]

Mohammad Sadeq Dousti, Rasool Jalili. FORSAKES: A forward-secure authenticated key exchange protocol based on symmetric key-evolving schemes. Advances in Mathematics of Communications, 2015, 9 (4) : 471-514. doi: 10.3934/amc.2015.9.471

[5]

Xiaoying Han, Jinglai Li, Dongbin Xiu. Error analysis for numerical formulation of particle filter. Discrete & Continuous Dynamical Systems - B, 2015, 20 (5) : 1337-1354. doi: 10.3934/dcdsb.2015.20.1337

[6]

Anders C. Hansen. A theoretical framework for backward error analysis on manifolds. Journal of Geometric Mechanics, 2011, 3 (1) : 81-111. doi: 10.3934/jgm.2011.3.81

[7]

Walter Allegretto, Yanping Lin, Ningning Yan. A posteriori error analysis for FEM of American options. Discrete & Continuous Dynamical Systems - B, 2006, 6 (5) : 957-978. doi: 10.3934/dcdsb.2006.6.957

[8]

G.A.K. van Voorn, D. Stiefs, T. Gross, B. W. Kooi, Ulrike Feudel, S.A.L.M. Kooijman. Stabilization due to predator interference: comparison of different analysis approaches. Mathematical Biosciences & Engineering, 2008, 5 (3) : 567-583. doi: 10.3934/mbe.2008.5.567

[9]

Ahmad Ahmad Ali, Klaus Deckelnick, Michael Hinze. Error analysis for global minima of semilinear optimal control problems. Mathematical Control & Related Fields, 2018, 8 (1) : 195-215. doi: 10.3934/mcrf.2018009

[10]

M. González, J. Jansson, S. Korotov. A posteriori error analysis of a stabilized mixed FEM for convection-diffusion problems. Conference Publications, 2015, 2015 (special) : 525-532. doi: 10.3934/proc.2015.0525

[11]

Johannes Eilinghoff, Roland Schnaubelt. Error analysis of an ADI splitting scheme for the inhomogeneous Maxwell equations. Discrete & Continuous Dynamical Systems - A, 2018, 38 (11) : 5685-5709. doi: 10.3934/dcds.2018248

[12]

Rod Cross, Hugh McNamara, Leonid Kalachev, Alexei Pokrovskii. Hysteresis and post Walrasian economics. Discrete & Continuous Dynamical Systems - B, 2013, 18 (2) : 377-401. doi: 10.3934/dcdsb.2013.18.377

[13]

Marko Filipović, Ivica Kopriva. A comparison of dictionary based approaches to inpainting and denoising with an emphasis to independent component analysis learned dictionaries. Inverse Problems & Imaging, 2011, 5 (4) : 815-841. doi: 10.3934/ipi.2011.5.815

[14]

Annalisa Pascarella, Alberto Sorrentino, Cristina Campi, Michele Piana. Particle filtering, beamforming and multiple signal classification for the analysis of magnetoencephalography time series: a comparison of algorithms. Inverse Problems & Imaging, 2010, 4 (1) : 169-190. doi: 10.3934/ipi.2010.4.169

[15]

Serap Ergün, Sirma Zeynep Alparslan Gök, Tuncay Aydoǧan, Gerhard Wilhelm Weber. Performance analysis of a cooperative flow game algorithm in ad hoc networks and a comparison to Dijkstra's algorithm. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1085-1100. doi: 10.3934/jimo.2018086

[16]

Gerard Gómez, Josep–Maria Mondelo, Carles Simó. A collocation method for the numerical Fourier analysis of quasi-periodic functions. II: Analytical error estimates. Discrete & Continuous Dynamical Systems - B, 2010, 14 (1) : 75-109. doi: 10.3934/dcdsb.2010.14.75

[17]

Norikazu Saito. Error analysis of a conservative finite-element approximation for the Keller-Segel system of chemotaxis. Communications on Pure & Applied Analysis, 2012, 11 (1) : 339-364. doi: 10.3934/cpaa.2012.11.339

[18]

Xiaofeng Yang. Error analysis of stabilized semi-implicit method of Allen-Cahn equation. Discrete & Continuous Dynamical Systems - B, 2009, 11 (4) : 1057-1070. doi: 10.3934/dcdsb.2009.11.1057

[19]

Kim S. Bey, Peter Z. Daffer, Hideaki Kaneko, Puntip Toghaw. Error analysis of the p-version discontinuous Galerkin method for heat transfer in built-up structures. Communications on Pure & Applied Analysis, 2007, 6 (3) : 719-740. doi: 10.3934/cpaa.2007.6.719

[20]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2n-periodic binary sequences. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1743-1757. doi: 10.3934/jimo.2017016

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (94)
  • HTML views (350)
  • Cited by (0)

Other articles
by authors

[Back to Top]