# American Institute of Mathematical Sciences

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=822760596 [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. [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. [4] M. R. Albrecht, R. 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. [5] E. Alkim, L. Ducas, T. Pöppelmann and P. Schwabe, Newhope without reconciliation, IACR Cryptology ePrint Archive, 2016 (2016), 1157. [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. [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. [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. [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. [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. [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. [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. [13] X. Gao, J. Ding, L. 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. [14] X. Gao, J. Ding, L. Li, S. 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. [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. [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. [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. [18] S. González, L. Huguet, C. 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. [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. [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. [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. [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. [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. [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. [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. [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. [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.

show all references

##### References:
 [1] 24-cell, Page Version ID: 822760596. https://en.wikipedia.org/w/index.php?title=24-cell&oldid=822760596 [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. [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. [4] M. R. Albrecht, R. 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. [5] E. Alkim, L. Ducas, T. Pöppelmann and P. Schwabe, Newhope without reconciliation, IACR Cryptology ePrint Archive, 2016 (2016), 1157. [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. [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. [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. [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. [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. [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. [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. [13] X. Gao, J. Ding, L. 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. [14] X. Gao, J. Ding, L. Li, S. 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. [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. [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. [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. [18] S. González, L. Huguet, C. 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. [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. [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. [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. [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. [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. [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. [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. [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. [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.
DING12 RLWE key exchange protocol
NewHope RLWE key exchange protocol
Illustrated figure of simplified NewHope error reconciliation ($d = 2$)
NewHope-Simple RLWE key exchange protocol
Illustrated figure of NewHope-Simple and DING12 signal value computation
Summary Chart of DING12, BCNS15, NewHope, NewHope-Simple
 DING12 BCNS15 NewHope NewHope-Simple Signal computation ● Divide $\mathbb{Z}_q$ into 2 regions. Different region givescorresponding 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 givescorresponding 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] 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 [2] 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 [3] 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 [4] 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 [5] 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 [6] 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 [7] 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 [8] 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 [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] 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 [13] 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 [14] 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 [15] 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 [16] 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 [17] 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 [18] 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 [19] 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 [20] Georg Vossen, Stefan Volkwein. Model reduction techniques with a-posteriori error analysis for linear-quadratic optimal control problems. Numerical Algebra, Control & Optimization, 2012, 2 (3) : 465-485. doi: 10.3934/naco.2012.2.465

2017 Impact Factor: 0.564