Post-quantum zk-SNARKs from QAPs

Abstract

In recent years, the zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) have drawn significant attention as privacy-enhancing technologies in various domains. A post-quantum designated verifier type zk-SNARK for Boolean circuits was proposed by Gennaro et al. in ACM CCS '18. However, this scheme does not include arithmetic circuits and they claim that a construction of post zk-SNARKs for arithmetic circuits as open problem. In this paper we give answers to this problem. Our first proposal is based on the data structure used in Pinocchio, a previous study, and can be easily implemented using the existing Pinocchio-based systems. In our second proposal, which also employs QAPs, the zero-knowledge proof comprises three learning with errors (LWE) ciphertexts, and the size of the proof is smaller compared with that of the first proposal. Our second proposal is also more efficient than the first one or all other known post-quantum zk-SNARKs.