International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Arne Tobias Ødegaard , Simula UiB, Bergen, Norway
Helger Lipmaa , Simula UiB, Bergen, Norway
Michał Zając , Clearmatics, London, UK
Prastudy Fauzi , Simula UiB, Bergen, Norway
Janno Siim , University of Tartu, Tartu, Estonia
Download:
DOI: 10.1007/978-3-030-92068-5_21
Search ePrint
Search Google
Conference: ASIACRYPT 2021
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.
Video from ASIACRYPT 2021
BibTeX
@inproceedings{asiacrypt-2021-31471,
  title={Verifiably-Extractable OWFs and Their Applications to Subversion Zero-Knowledge},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-92068-5_21},
  author={Arne Tobias Ødegaard and Helger Lipmaa and Michał Zając and Prastudy Fauzi and Janno Siim},
  year=2021
}