计算机科学

计算机科学 ›› 2024, Vol. 51 ›› Issue (5): 331-345.doi: 10.11896/jsjkx.230300127

• 信息安全 • 上一篇    下一篇

基于MLWE和MSIS的可验证解密方案

郭春彤1,2, 吴文渊1   

  1. 1 中国科学院重庆绿色智能技术研究院自动推理与认知重庆市重点实验室 重庆 400714
    2 中国科学院大学重庆学院 重庆 400714
  • 收稿日期:2023-03-14 修回日期:2023-05-25 出版日期:2024-05-15 发布日期:2024-05-08
  • 通讯作者: 吴文渊(wuwenyuan@cigit.ac.cn)
  • 作者简介:(gchuntong@163.com)
  • 基金资助:
    国家重点研发专项(2020YFA0712300);重庆市在渝院士牵头科技创新引导专项(2022YSZX-JCX0011CSTB,cstc2021yszx-jcyjX0004,CSTB2023YSZX-JCX0008)

Verifiable Decryption Scheme Based on MLWE and MSIS

GUO Chuntong1,2, WU Wenyuan1   

  1. 1 Chongqing Key Laboratory of Automated Reasoning & Cognition, Chongqing Institute of Green, Intelligent Technology, Chinese Academy of Sciences, Chongqing 400714,China
    2 Chongqing School,University of Chinese Academy of Sciences,Chongqing 400714,China
  • Received:2023-03-14 Revised:2023-05-25 Online:2024-05-15 Published:2024-05-08
  • About author:GUO Chuntong,born in 1998,postgra-duate.Her main research interests include homomorphic encryption and lattice cryptography.
    WU Wenyuan,born in 1976,Ph.D,professor.His main research interests include lattice based cryptography,automated reasoning and symbolic computation.
  • Supported by:
    National Key Research and Development Program of China(2020YFA0712300) and Chongqing Science and Technology Bureau Project(2022YSZX-JCX0011CSTB,cstc2021yszx-jcyjX0004,CSTB2023YSZX-JCX0008).

PDF (PC)

319

摘要： 两方安全计算中涉及的可验证解密技术可以应用在医疗研究数据共享、机构间合作进行模型训练等有隐私保护需求的现实场景中,有助于进一步打破数据孤岛、保障数据安全。但是目前已有的为基于格密码或其他后量子加密方案正确解密所构造的零知识证明的效率不高。面对这一现状,文中针对 Kyber 提出了一个基于模容错学习问题(MLWE) 和模小整数解问题(MSIS) 的可验证解密方案。首先,根据 Kyber 的加解密特性,在利用证明者和验证者所持数据构造相等关系时存在差异,该方案提出了一种利用误差估计结合 Kyber 的压缩函数,使证明者提供给验证者一部分所持数据的信息,从而消除差异的方法,进而提供可以用于验证的相等关系,把该关系与 Dilithium 签名方案无公钥压缩版本的框架相结合,构造非交互式零知识证明,将可验证解密问题转变为证明环中短向量满足的线性关系。其次,在理论上分析了方案的正确性、安全性、通信开销和计算复杂度,将方案的合理性和零知识性规约到 MSIS 困难假设,并提供了 2 组不同安全等级的建议参数设置。最后,通过编写 C 语言程序测试了所提方案的正确性和效率。实验结果与理论分析结果基本一致,与现有方案相比,所提方案在对单个密文的证明大小和证明时间上有显著优势,更加简洁、高效。

关键词: 可验证解密, 格密码, MLWE, MSIS, 零知识证明

Abstract: The verifiable decryption technology involved in the two-party secure computing can be applied in real-world scenarios that require privacy protection,such as medical research data sharing,and inter-institutional cooperation for model training,which can help further break down the data isolation problem and ensure data security.However,the existing zero-knowledge proofs constructed for correct decryption based on lattice cryptography or other post-quantum encryption schemes are less efficient.Facing this situation,this paper proposes a verifiable decryption scheme based on the module learning with errors(MLWE) and module short integer solution(MSIS) for Kyber.Firstly,based on the encryption and decryption properties of Kyber,there is a difference in constructing the equivalence relation using the data held by the prover and the verifier.The scheme proposes a me-thod that uses error estimation combined with Kyber compression function to enable the prover to provide the verifier with some information about his own data to eliminate the difference,and then provides an equivalence relation that can be used for verification,and combines this relation with the framework of the Dilithium signature scheme without public key compression version to construct a non-interactive zero-knowledge proof,which transforms the verifiable decryption problem into proving a linear relation satisfied by short vectors in the ring.Secondly,the correctness,security,communication overhead and computational complexity of the scheme are theoretically analyzed,the soundness and zero-knowledge of the scheme are reduced to the hardness assumptions of MSIS,and two groups of suggested parameters with different security levels are provided.Finally,the correctness and efficiency of this scheme are tested by writing a C program.Experimental results are consistent with the theoretical analysis results,and compared with the existing schemes,the scheme in this paper has significant advantages in terms of proof size and proof time for a single ciphertext,which is more concise and efficient.

Key words: Verifiable decryption, Lattice-based cryptography, MLWE, MSIS, Zero-knowledge proof

中图分类号: 

  • TP309
[1]CAMENISCH J,SHOUP V.Practical verifiable encryption and decryption of discrete logarithms[C]//Annual International Cryptology Conference.2003:126-144.
[2]LUO F,WANG K.Verifiable decryption for fully homomorphic encryption[C]//International Conference on Information Secu-rity.2018:347-365.
[3]CARR C,COSTACHE A,DAVIES G T,et al.Zero-knowledge proof of decryption for FHE ciphertexts[J].IACR Cryptology ePrint Archive 2018,2018:26.
[4]BRAKERSKI Z,GENTRY C,VAIKUNTANATHAN V.(Le-veled) fully homomorphic encryption without bootstrapping[C]//Proceedings of the 3rd Innovations in Theoretical Computer Science Conference.2012:309-325.
[5]LYUBASHEVSKY V.Fiat-Shamir with aborts:Applications to lattice and factoring-based signatures[C]//International Confe-rence on the Theory and Application of Cryptology and Information Security.2009:598-616.
[6]LYUBASHEVSKY V.Lattice signatures without trapdoors[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques.2012:738-755.
[7]GROTH J.A verifiable secret shuffe of homomorphic encryp-tions[C]//International Workshop on Public Key Cryptography.2003:145-160.
[8]ESPITAU T,FOUQUE P-A,GÉRARD B,et al.Side-channel attacks on BLISS lattice-based signatures:Exploiting branch tracing against strongswan and electromagnetic emanations in microcontrollers[C]//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security.2017:1857-1874.
[9]BOOTLE J,DELAPLACE C,ESPITAU T,et al.LWE withoutmodular reduction and improved side-channel attacks against BLISS[C]//International Conference on the Theory and Application of Cryptology and Information Security.2018:494-524.
[10]BOSCHINI C,CAMENISCH J,OVSIANKIN M,et al.Efficient post-quantum SNARKs for RSIS and RLWE and their applications to privacy[J].PQCrypto,2020,12100:247-267.
[11]BLUM M,FELDMAN P,MICALI S.Non-interactive zero-knowledge and its applications[C]//Proceedings of theTwen-tieth Annual ACM Symposium on Theory of Computing.1988:103-112.
[12]GJØSTEEN K,HAINES T,MÜLLER J,et al.Verifiable decryption in the head[C]//Australasian Conference on Information Security and Privacy.Cham:Springer International Publi-shing,2022:355-374.
[13]SILDE T.Short Paper:Verifiable Decryption for BGV[C]//International Conference on Financial Cryptography and Data Security.Cham:Springer International Publishing,2022:381-390.
[14]LYUBASHEVSKY V,NGUYEN N K,SEILER G.Shorter lattice-based zero-knowledge proofs via one-time commitments[C]//IACR International Conference on Public-Key Cryptography.2021:215-241.
[15]LYUBASHEVSKY V,NGUYEN N K,SEILER G.Practicallattice-based zero-knowledge proofs for integer relations[C]//Proceedings of the 2020 ACM SIGSAC Conference on Compu-ter and Communications Security.2020:1051-1070.
[16]BAI S,DUCAS L,KILTZ E,et al.Crystals-dilithium algorithmspecifications and supporting documentation(version 3.1)[EB/OL].https://pq-crystals.org/dilithium/resources.shtml.
[17]AVANZI R,BOS J,DUCAS L,et al.Crystals-kyber algorithm specifications and supporting documentation(version 3.02)[EB/OL].https://pq-crystals.org/kyber/resources.shtml.
[18]MICCIANCIO D.Generalized compact knapsacks,cyclic lat-tices,and efficient one-way functions[J].Computational Complexity,2007,16(4):365-411.
[19]LANGLOIS A,STEHLÉ D.Worst-case to average-case reductions for module lattices[J].Designs,Codes and Cryptography,2015,75(3):565-599.
[20]BOS J,DUCAS L,KILTZ E,et al.CRYSTALS-Kyber:a CCA-secure module-lattice-based KEM[C]//2018 IEEE European Symposium on Security and Privacy(EuroS&P).2018:353-367.
[21]LYUBASHEVSKY V,NEVEN G.One-shot verifiable encryption from lattices[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques.2017:293-323.
[22]KE C S,WU W Y,FENG Y.MLWE-based homomorphic innerproduct scheme[J].Ruan Jian Xue Bao/Journal of Software,2021,32(11):3596-3605.
[23]GENTRY C.Fully homomorphic encryption using ideal lattices[C]//Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing.2009:169-178.
[24]BAI S,LANGLOIS A,LEPOINT T,et al.Improved securityproofs in lattice-based cryptography:using the Rényi divergence rather than the statistical distance[C]//Proceedings,Part I,of the 21st International Conference on Advances in Cryptology.2015:3-24.
[25]ATTEMA T,LYUBASHEVSKY V,SEILER G.Practical pro-duct proofs for lattice commitments[C]//Annual International Cryptology Conference.2020:470-499.
[26]POINTCHEVAL D,STERN J.Security arguments for digitalsignatures and blind signatures[J].Journal of Cryptology,2000,13:361-396.
[27]BELLARE M,NEVEN G.Multi-signatures in the plain public-Key model and a general forking lemma[C]//Proceedings of the 13th ACM Conference on Computer and Communications Secu-rity.2006:390-399.
[28]POINTCHEVAL D,STERN J.Security proofs for signatureschemes[C]//International Conference on the Theory and Applications of Cryptographic Techniques.1996:387-398.
[29]BAI S,GALBRAITH S D.An improved compression technique for signatures based on learning with errors[C]//Cryptographers' Track at the RSA Conference.2014:28-47.
[30]RÜCKERT M.Lattice-based blind signatures[C]//InternationalConference on the Theory and Application of Cryptology and Information Security.2010:413-430.
[31]KILTZ E,LYUBASHEVSKY V,SCHAFFNER C.A concretetreatment of Fiat-Shamir signatures in the quantum random-oracle model[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques.2018:552-586.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发