Title: Post-quantum zk-SNARKs from QAPs

Authors: Ken Naganuma; Masayuki Yoshino; Noboru Kunihiro; Atsuo Inoue; Yukinori Matsuoka; Mineaki Okazaki

Addresses: Hitachi, Ltd. 292 Yoshidacho, Totsuka, Yokohama, Kanagawa, Japan ' Hitachi, Ltd. 292 Yoshidacho, Totsuka, Yokohama, Kanagawa, Japan ' Department of Computer Science, University of Tsukuba, Ibaraki 305-8577, Japan ' Hitachi Solutions Ltd., 4-12-7 Shinagawa, Tokyo, Japan ' Hitachi Solutions Ltd., 4-12-7 Shinagawa, Tokyo, Japan ' Hitachi Business Solution Co., Ltd., 4-12-6 Shinagawa, Tokyo, Japan

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.

Keywords: zero-knowledge proof; zk-SNARKs; LWE encryption; blockchain technology; post-quantum cryptography.

DOI: 10.1504/IJICS.2024.143917

International Journal of Information and Computer Security, 2024 Vol.25 No.3/4, pp.203 - 233

Accepted: 11 Jun 2022
Published online: 14 Jan 2025 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article