μ-Hope : 오류 정정 부호를 사용한 RLWE 기반의 경량 KEM
μ-Hope : Compact Size RLWE Based KEM Using Error Correcting Code
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문에서는 RLWE 기반 암호 알고리즘인 NewHope에 Error Correcting Code(ECC)를 적용한 RLWE기반의 암호 알고리즘 μ-Hope를 제안한다. 기존의 NewHope는 소수로 12289를 사용하여, 공개키, 개인키, 암호문 사이즈가 각각 928-byte, 1888-byte, 1120-byte로 다른 RLWE 기반 알고리즘에 비하여 그 사이즈가 크다고할 수 있다. 본 논문에서는 공개키, 개인키, 암호문 크기를 줄이기 위하여 소수 12289를 769로 변경한 -Hope를제안하며 소수의 변경으로부터 발생하는 복호화 실패율을 줄이기 위해 ECC로 XE1을 채택하였다. 그 결과NewHope 대비 공개키, 개인키, 암호문의 사이즈가 각각 928-byte, 1888-byte, 1120-byte 감소했다. 또한, 키 사이즈가 줄 뿐만아니라, ECC의 사용으로 인한 성능 저하보다 작은 소수를 사용하면서 발생하는 연산 효율성이 더 커서 한 번의 키를 교환하는 과정에서 총 25%의 성능 향상도 이룰 수 있었다.
Abstract
In this paper, we propose a new RLWE-based scheme named μ-Hope that exploits Error Correcting Code(ECC) onNewHope. The previous parameters of NewHope uses 12289 as a prime modulus, and the size of the public key, privatekey, and ciphertext is 928-byte, 1888-byte, and 1120-byte respectively, which can be said to be larger than other RLWEbased algorithms. In this paper, we propose μ-Hope, which changes modulus 12289 to 769 to reduce the size of the publickey, private key, and ciphertext. Also, we adopts XE1 as an Error Correcting Code(ECC) to solve the increased decryptionfailure rate caused by using a small prime modulus. As a result, the size of the public key, private key, and ciphertextdecreased by 928-byte, 1888-byte and 1120-byte respectively. As the computational efficiency caused by using a small prime modulusexceeds the performance degradation by exploiting ECC, this result in 25% performance improvement for a single keyexchange
참고문헌 (20)
- P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer", SIAM review, 41(2), pp.303~332 (1999)
- V. Lyubashevsky, "On ideal lattices and learning with errors over rings", Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp.1~23 (2010)
- D. Stehlé, "Efficient public key encryption based on ideal lattices", International Conference on the Theory and Application of Cryptology and Information Security, pp.617~635 (2009)
- E. Alkım, "Compact and simple RLWE based key encapsulation mechanism", International Conference on Cryptology and Information Security in Latin America, pp.237~256 (2019)
- Y. Zhu, "When NTT Meets Karatsuba: Preprocess-then-NTT Technique Revisited", IACR Cryptology ePrint Archive, 2019, pp.1079~ (2019)
- X. Lu, "LAC:Practical Ring-LWE Based Public-Key Encryption with Byte-Level Modulus", IACR Cryptology ePrint Archive, 2018 (2018)
- E. Alkim, "Post-quantum key exchange—a new hope", 25th {USENIX} Security Symposium ({USENIX} Security 16), pp.327~343 (2016)
- C. Peikert, "Pseudorandomness of ring-LWE for any ring and modulus", Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp.461~473 (2017)
- J. P. D’Anvers, "On the impact of decryption failures on the security of LWE", LWR based schemes, 2018, pp.2018, 1089~
- E. Alkim, "NewHope - algorithm specifications and supporting documentation", NIST PQC Round 2, 2, pp.4~11 (2019)
- Dworkin, "SHA-3standard: Permutation-based hash and extendable-output functions", NIST FIPS-202, ~ (2015)
- D.J. Bernstein, "Multidigit multiplication for mathematicians", Citeseer, ~ (2001)
- J. Bos, "CRYSTALS-Kyber: a CCA -secure module-lattice-based KEM", 2018 IEEE European Symposium on Security and Privacy (EuroS&P), pp.353~367 (2018)
- V. Lyubashevsky, "NTTRU: truly fast NTRU using NTT", IACR Transactions on Cryptographic Hardware and Embedded Systems, pp.180~201 (2019)
- M. J. O. Saarinen, "HILA5: On reliability, reconciliation, and error correction for Ring-LWE encryption", International Conference on Selected Areas in Cryptography, pp.192~212 (2017)
- H. Baan, "Round5: Compact and fast post-quantum public-key encryption", International Conference on Post-Quantum Cryptography, pp.83~102 (2019), Springer
- A. Weimerskirch, "Generalizations of the Karatsuba Algorithm for Efficient Implementations", IACR Cryptology ePrint Archive, 2006, pp.224~ (2006)
- M. R. Albrecht, "On the concrete hardness of learning with errors", Journal of Mathematical Cryptology, 9(3), pp.169~203 (2015)
- C. P. Schnorr, "Lattice basis reduction: Improved practical algorithms and solving subset sum problems", Mathematical programming, 66(1-3), pp.181~199 (1994)
- E. Alkim, "NewHope without reconciliation", IACR Cryptology ePrint Archive, 2016, pp.1157~ (2016)