Article Contents
Article Contents

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

• * Corresponding author: Xinwei Gao
• 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.

Mathematics Subject Classification: Primary: 94A60, 11T71; Secondary: 14G50.

 Citation:

• 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 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] 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.

Figures(5)

Tables(1)