A Practical Post-Quantum Public-Key Cryptosystem Based on \(\textsf {spLWE}\)

详细信息    查看全文

• 关键词：Practical ; Post ; quantum ; IND ; CCA ; PKE ; Sparse secret ; \(\textsf {LWE}\) ; Quantum random oracle model
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10157
• 期：1
• 页码：51-74
• 丛书名：Information Security and Cryptology ?ICISC 2016
• ISBN：978-3-319-53177-9
• 卷排序：10157

文摘

The Learning with Errors (\(\textsf {LWE}\)) problem has been widely used as a hardness assumption to construct public-key primitives. In this paper, we propose an efficient instantiation of a PKE scheme based on LWE with a sparse secret, named as \(\textsf {spLWE}\). We first construct an IND-CPA PKE and convert it to an IND-CCA scheme in the quantum random oracle model by applying a modified Fujisaki-Okamoto conversion of Unruh. In order to guarantee the security of our base problem suggested in this paper, we provide a polynomial time reduction from \(\textsf {LWE}\) with a uniformly chosen secret to \(\textsf {spLWE}\). We modify the previous attacks for \(\textsf {LWE}\) to exploit the sparsity of a secret key and derive more suitable parameters. We can finally estimate performance of our scheme supporting 256-bit messages: our implementation shows that our IND-CCA scheme takes 313 \(\upmu \)s and 302 \(\upmu \)s respectively for encryption and decryption with the parameters that have 128-quantum bit security.