Paper 2019/586

Simulation-Extractable zk-SNARK with a Single Verification

Jihye Kim
Jiwon Lee
Hyunok Oh
Abstract

This revised paper improves the previous simulation-extractable zk-SNARK (SE-SNARK) in terms of performance efficiency and the security. It removes the G_2 operation in verification, without degrading performance and size, and analyze the security of the nested hash collision more deeply to strengthen the security. The simulation-extractable zk-SNARK (SE-SNARK) introduces a security notion of non-malleability. The existing pairing-based zk-SNARKs designed from linear encoding are known to be vulnerable to algebraic manipulation of the proof. The latest SE-SNARKs check the proof consistency by increasing the proof size and the verification cost. In particular, the number of pairings increases almost doubles due to further verification. In this paper, we propose two novel SE-SNARK constructions with a single verification. The consistency check is subsumed in a single verification through employing a hash function. The proof size and verification time of the proposed SE-SNARK schemes are minimal in that it is the same as the state-of-the-art zk-SNARK without non-malleability. The proof in our SE-SNARK constructions comprises only three group elements (type III) in the QAP-based scheme and two group elements (type I) in the SAP-based scheme. The verification time in both requires only 3 pairings. The soundness of the proposed schemes is proven under the hash-algebraic knowledge (HAK) assumption and the collision-resistant hash assumption.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. IEEE ACCESS
DOI
10.1109/ACCESS.2020.3019980
Keywords
pairing-based zk-SNARK simulation-extractability quadratic arithmetic program square arithmetic program
Contact author(s)
jihyek @ kookmin ac kr
jiwonlee @ hanyang ac kr
hoh @ hanyang ac kr
History
2022-11-06: last of 6 revisions
2019-05-30: received
See all versions
Short URL
https://ia.cr/2019/586
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/586,
      author = {Jihye Kim and Jiwon Lee and Hyunok Oh},
      title = {Simulation-Extractable zk-SNARK with a Single Verification},
      howpublished = {Cryptology ePrint Archive, Paper 2019/586},
      year = {2019},
      doi = {10.1109/ACCESS.2020.3019980},
      note = {\url{https://eprint.iacr.org/2019/586}},
      url = {https://eprint.iacr.org/2019/586}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.