Cryptology ePrint Archive: Report 2021/1264

Verifiably-Extractable OWFs and Their Applications to Subversion Zero-Knowledge

Prastudy Fauzi and Helger Lipmaa and Janno Siim and Michal Zajac and Arne Tobias Ødegaard

Abstract: An extractable one-way function (EOWF), introduced by Canetti and Dakdouk (ICALP 2008) and generalized by Bitansky et al. (SIAM Journal on Computing vol. 45), is an OWF that allows for efficient extraction of a preimage for the function. We study (generalized) EOWFs that have a public image verification algorithm. We call such OWFs verifiably-extractable and show that several previously known constructions satisfy this notion. We study how such OWFs relate to subversion zero-knowledge (Sub-ZK) NIZKs by using them to generically construct a Sub-ZK NIZK from a NIZK satisfying certain additional properties, and conversely show how to obtain them from any Sub-ZK NIZK. Prior to our work, the Sub-ZK property of NIZKs was achieved using concrete knowledge assumptions.

Category / Keywords: foundations / zkSNARK, subversion zero-knowledge, NIZK, EOWF, Generalized EOWF

Original Publication (with minor differences): IACR-ASIACRYPT-2021

Date: received 21 Sep 2021, last revised 22 Sep 2021

Contact author: m p zajac at gmail com, arne tobias at gmail com, helger lipmaa at gmail com, prastudy fauzi at gmail com, jannosiim at gmail com

Available format(s): PDF | BibTeX Citation

Note: This is a full version of our Asiacrypt 2021 paper.

Version: 20210922:154102 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]