Paper 2020/1421

Weakly Extractable One-Way Functions

Nir Bitansky, Noa Eizenstadt, and Omer Paneth


A family of one-way functions is extractable if given a random function in the family, an efficient adversary can only output an element in the image of the function if it knows a corresponding preimage. This knowledge extraction guarantee is particularly powerful since it does not require interaction. However, extractable one-way functions (EFs) are subject to a strong barrier: assuming indistinguishability obfuscation, no EF can have a knowledge extractor that works against all polynomial-size non-uniform adversaries. This holds even for non-black-box extractors that use the adversary’s code. Accordingly, the literature considers either EFs based on non-falsifiable knowledge assumptions, where the extractor is not explicitly given, but it is only assumed to exist, or EFs against a restricted class of adversaries with a bounded non-uniform advice. This falls short of cryptography’s gold standard of security that requires an explicit reduction against non-uniform adversaries of arbitrary polynomial size. Motivated by this gap, we put forward a new notion of weakly extractable one-way functions (WEFs) that circumvents the known barrier. We then prove that WEFs are inextricably connected to the long standing question of three-message zero knowledge protocols. We show that different flavors of WEFs are sufficient and necessary for three-message zero knowledge to exist. The exact flavor depends on whether the protocol is computational or statistical zero knowledge and whether it is publicly or privately verifiable. Combined with recent progress on constructing three message zero-knowledge, we derive a new connection between keyless multi-collision resistance and the notion of incompressibility and the feasibility of non-interactive knowledge extraction. Another interesting corollary of our result is that in order to construct three-message zero knowledge arguments, it suffices to construct such arguments where the honest prover strategy is unbounded.

Available format(s)
Publication info
Published by the IACR in TCC 2020
Extractable FunctionsKnowledge ExtractionZero-KnowledgeNon-Black-Box Techniques
Contact author(s)
nirbitan @ tau ac il
noa eizenstadt @ gmail com
omerpa @ gmail com
2020-11-15: received
Short URL
Creative Commons Attribution


      author = {Nir Bitansky and Noa Eizenstadt and Omer Paneth},
      title = {Weakly Extractable One-Way Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1421},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.