Improved Zero-knowledge Proofs From Symmetric-Key Primitives

With the rapid development of Internet,people pay more and more attention to privacy and security.The main aim of cryptography,which is the key sup-port of cyberspace security,is to protect the users' privacy while ensuring the efficiency of related functionalities.But the rise of quantum computers poses a huge threat to the widely used cryptographic technology.In order to resi,st the attack of quantum computer,NIST,European Union,etc have initialized the project of post-quantum cryptography.Since the zero-knowledge proof is a typi-cal cryptographic primitive for privacy protection,the research of post-quantum zero-knowledge proof is not only of great theoretical significance to the design of post-quantum cryptography,but also one of the practical security solutions of electronic currency,blockchain,etc.Among the post-quantum cryptograph-ic technologies,the zero-knowledge proof based on symmetric cryptography,the security of which depends on symmetric cryptography rather than classical hard mathematical problems,takes a novel approach and receives more attentions.We focus the zero-knowledge proof based on symmetric-key primitives,and improves the”MPC in the head" technology of KKW zero-knowledge proof in the preprocessing model.In order to reduce the size of the proof,we decompose the corresponding circuit F into f1 and f2,in which f1 and f2 can be made public,according to the special structure of symmetric-key algorithm.By increasing the number of executions of the f2 proof which is much smaller than that of F,we can reduce the overall cost of proofs dramatically.For concrete construction,we propose the random mask reuse technique to provide the zero knowledge property when running f2 proof many times,and ensure the correctness and the consistency with f1.Compared with KKW zero-knowledge proof,our improved protocol can reduce the proof size when the number of simulation participants n is small.For a security level of 2-128,the proof size is reduced by 31.6%,25.6%and 7.7%when n=3,4 and 8,respectively.For a security level of 2-256,the proof size is reduced by 34.6%,28.9%and 10%when n=3,4 and 8,respectively.