後量子金鑰交換

Post-Quantum Key Exchange

賴奕甫(Yi-Fu Lai)

指導教授 ： 陳君明

國立臺灣大學/理學院/數學研究所/碩士(2017年)

https://doi.org/10.6342/NTU201704317

摘要

量子計算近年來的進展，使後量子密碼學受到關注。晶格密碼學是後量子密碼學的分支之一。晶格密碼學已被發現其蘊含諸多優美的性質，例如能建構多種密碼系統的底蘊，穩健的安全性保障，而當中首屈一指的莫過於抗量子計算的能力。於西元2015 年，Alkim 等人利用新型error-reconciliation 機構，改良Peikert 的密碼系統，建立出新的後量子金鑰交換密碼系統，NEWHOPE。甚至於翌年Google 實驗性的採納Canary 瀏覽器上數月之久。受到Alkim 等人工作之啟發，我們運用錯誤更正碼中的奇偶檢查矩陣，構築了新的error-reconciliation 機構、建立在丁等人的密碼系統上，架構新的後量子金鑰交換系統。我們的金鑰交換系統，需要較大的訊息傳輸量(在與NEWHOPE 相同安全性下多出768 位元)，少於NEWHOPE-simple 的訊息傳輸量(在與NEWHOPE 相同安全性下多出1024 位元)，但能夠與NEWHOPE 所有參數相容、並有相同的安全性。因此也能做為另一項可實行後量子金鑰交換的選擇。

關鍵字

環-LWE ； 後量子金鑰交換 ； 晶格密碼學

並列摘要

The advances in quantum computing in recent years draw attention to the post-quantum cryptography. Lattice-based cryptography is a branch of the post-quantum cryptography. Lattice-based cryptography has been discovered several attractive properties such as its versatility and strong provable security guarantees but the most of all is its resistance against the quantum computing. In 2015, Erdem Alkim, Leo Ducas, Thomas Poppelmann, and Peter Schwabe introduced a post-quantum key exchange protocol, NEWHOPE, with a new error-reconciliation mechanism which ameliorated Peikert's key exchange protocol (PQCrypto 2014) with not only better efficiency but better security margin. Moreover, the NEWHOPE had even been experimented on Google Canary browser in the specific connection in 2016 for a few months. Inspired by the work of Alkim et al., we would like to present a new error-reconciliation mechanism based on the protocol of Ding et al. Our protocol requires a little larger message size ($768$ bits more under the same security level with NEWHOPE) and less than NEWHOPE-simple ($1024$ bits more than NEWHOPE under the same security level) but being compatible with all parameters in NEWHOPE under the same security level and thus can also be regarded as an alternative choice of practical post-quantum key exchange.

並列關鍵字

ring-LWE ； post-quantum key exchange ； lattice-based cryptography

參考文獻

[1] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2):303–332, 1999.

[5] Daniel Augot, Lejla Batina, Daniel J. Bernstein, Joppe Bos, Johannes Buchmann, Wouter Castryck, Orr Dunkelman, Tim Güneysu, Shay Gueron, Andreas Hülsing, Tanja Lange, Mohamed Saied Emam Mohamed, Christian Rechberger, Peter Schwabe, Nicolas Sendrier, Frederik Vercauteren, and Bo-Yin Yang. Initial recommendations of long-term secure post-quantum systems, 2015. https://pqcrypto.eu.org/docs/initial-recommendations.pdf.

[8] Daniele Micciancio and Salil P. Vadhan. Statistical zero-knowledge proofs with efficient provers: Lattice problems and more. In Annual International Cryptology Conference, pages 282–298. Springer, 2003.

[9] Vadim Lyubashevsky. Lattice-based identification schemes secure under active attacks. In International Workshop on Public Key Cryptography, pages 162–179. Springer, 2008.

[11] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In In STOC, 2005.