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

Xinwei Gao

doi:10.3934/amc.2019015

Article Contents

2019, Volume 13, Issue 2: 221-233. Doi: 10.3934/amc.2019015

This issue Previous Article Self-dual additive $ \mathbb{F}_4 $-codes of lengths up to 40 represented by circulant graphs Next Article Type-preserving matrices and security of block ciphers

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

Xinwei Gao^,

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

Received: December 31, 2017

Revised: April 30, 2018

Published: January 2019

Abstract Full Text(HTML) Figure(5) / Table(1) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

Figure 1. DING12 RLWE key exchange protocol

Download: Full-size image PowerPoint slide

Figure 2. NewHope RLWE key exchange protocol

Download: Full-size image PowerPoint slide

Figure 3. Illustrated figure of simplified NewHope error reconciliation ($ d = 2 $)

Download: Full-size image PowerPoint slide

Figure 4. NewHope-Simple RLWE key exchange protocol

Download: Full-size image PowerPoint slide

Figure 5. Illustrated figure of NewHope-Simple and DING12 signal value computation

Download: Full-size image PowerPoint slide

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)

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.