Paper 2021/1264

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

Prastudy Fauzi, Helger Lipmaa, Janno Siim, 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.

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

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in ASIACRYPT 2021
Keywords
zkSNARKsubversion zero-knowledgeNIZKEOWFGeneralized EOWF
Contact author(s)
m p zajac @ gmail com
arne tobias @ gmail com
helger lipmaa @ gmail com
prastudy fauzi @ gmail com
jannosiim @ gmail com
History
2021-09-22: last of 2 revisions
2021-09-22: received
See all versions
Short URL
https://ia.cr/2021/1264
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1264,
      author = {Prastudy Fauzi and Helger Lipmaa and Janno Siim and Michal Zajac and Arne Tobias Ødegaard},
      title = {Verifiably-Extractable OWFs and Their Applications to Subversion Zero-Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1264},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1264}},
      url = {https://eprint.iacr.org/2021/1264}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.