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

doi:10.11896/jsjkx.230300127

Abstract

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

CLC Number:

TP309

GUO Chuntong, WU Wenyuan. Verifiable Decryption Scheme Based on MLWE and MSIS[J].Computer Science, 2024, 51(5): 331-345.

References

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Verifiable Decryption Scheme Based on MLWE and MSIS

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 9

Metrics

Comments

Recommended 0

[1]	LI Yi-cong, ZHOU Kuan-jiu, WANG Zi-zhong, XU Lin. ZKFERP:Universal and Efficient Range Proof Scheme with Constant Computational Cost [J]. Computer Science, 2022, 49(10): 335-343.
[2]	FU Zhen-hao, LIN Ding-kang, JIANG Hao-chen, YAN Jia-qi. Survey of Anonymous and Tracking Technology in Zerocash [J]. Computer Science, 2021, 48(11): 62-71.
[3]	NI Liang, WANG Nian-ping, GU Wei-li, ZHANG Qian, LIU Ji-zhao, SHAN Fang-fang. Research on Lattice-based Quantum-resistant Authenticated Key Agreement Protocols:A Survey [J]. Computer Science, 2020, 47(9): 293-303.
[4]	LI Shu-quan,LIU Lei,ZHU Da-yong,XIONG Chao,LI Rui. Protocol of Dynamic Provable Data Integrity for Cloud Storage [J]. Computer Science, 2020, 47(2): 256-261.
[5]	KE Cheng-song, WU Wen-yuan, FENG Yong. Low Expansion Rate Encryption Algorithm Based on MLWE [J]. Computer Science, 2019, 46(4): 144-150.
[6]	ZHANG Xiang-song and LIU Zhen-hua. Non-trapdoors Lattice Signature Scheme with Message Recovery [J]. Computer Science, 2014, 41(9): 165-168.
[7]	LI Lin and YUE Jian-hua. Anonymous Authentication Mechanisms Based on Zero-knowledge Proof [J]. Computer Science, 2013, 40(12): 197-199.
[8]	. Research on Hash Proof System and its Applications [J]. Computer Science, 2012, 39(Z6): 18-23.
[9]	. Improved Scheme of DAA Authentication Based on Proof Mechanism of a Committed [J]. Computer Science, 2012, 39(8): 111-114.