Paper 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).