Cryptology ePrint Archive: Report 2019/586

QAP-based Simulation-Extractable SNARK with a Single Verification

Jihye Kim and Jiwon Lee and Hyunok Oh

Abstract: The pairing-based simulation-extractable succinct non-interactive arguments of knowledge (SE-SNARKs) are attractive since they enable a prover to generate a proof with the knowledge of the witness to an instance in a manner which is succinct - proofs are short and the verifier's computation is small, zero-knowledge - proofs do not reveal the witness, and simulation-extractable - it is only possible to prove instances to which a witness is known although a number of simulated proofs are provided. The state-of-the-art pairing-based SE-SNARK is based on a square arithmetic program (SAP), instead of a more generalized quadratic arithmetic program (QAP). In order to add simulation extractability, the SE-SNARK requires to verify an additional equation compared to the state-of-the-art SNARKs.

In this paper, we propose a QAP-based SE-SNARK which consists of only 3 group elements for a QAP circuit and a single verification equation in asymmetric groups (Type III pairing). The proposed scheme is secure under concrete intractability assumptions in the random oracle model. Moreover, we propose a scheme with two elements as a proof and a single verifying equation, based on SAP in a symmetric group (Type I pairing).

Category / Keywords: cryptographic protocols / SNARK, non-interactive zero-knowledge proof, simulation-extractability, quadratic arithmetic program, square arithmetic program

Date: received 28 May 2019, last revised 1 Jun 2019

Contact author: jihyek at kookmin ac kr,jiwonlee@hanyang ac kr,hoh@hanyang ac kr

Available format(s): PDF | BibTeX Citation

Version: 20190601:131307 (All versions of this report)

Short URL: ia.cr/2019/586


[ Cryptology ePrint archive ]