On the existence of extractable one-way functions
By Nir Bitansky, Ran Canetti, Omer Paneth, Alon Rosen. 2014
137 citations recorded by the source corpus.
A function f is extractable if it is possible to algorithmically "extract," from any adversarial program that outputs a value y in the image of f; a preimage of y. When combined with hardness properties such as one-wayness or collision-resistance, extractability has proven to be a powerful tool. However, so far, extractability has not been explicitly shown. Instead, it has only been considered as a non-standard knowledge assumption on certain functions. We make two headways in the study of the existence of extractable one-way functions (EOWFs). On the negative side, we show that if there exist indistinguishability obfuscators for a certain class of circuits then there do not exist EOWFs where extraction works for any adversarial program with auxiliary-input of unbounded polynomial length. On the positive side, for adversarial programs with bounded auxiliary input (and unbounded polynomial running time), we give the first construction of EOWFs with an explicit extraction procedure, based on relatively standard assumptions (e.g., sub-exponential hardness of Learning with Errors). We then use these functions to construct the first 2-message zero-knowledge arguments and 3-message zero-knowledge arguments of knowledge, against the same class of adversarial verifiers, from essentially the same assumptions.
Subfields: Artificial Intelligence, Computational Theory and Mathematics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Eike Kiltz
- Jens Groth
- Julian Loss
- Srinath T. V. Setty
- Dan Boneh
- Justin Thaler
- Helger Lipmaa
- Markulf Kohlweiss
In Computational Theory and Mathematics
- Eike Kiltz
- Jens Groth
- Julian Loss
- Srinath T. V. Setty
- Octavian Catrina
- Marcel Keller
- Markulf Kohlweiss
- Brent Waters
Citations in the corpus
- Geppetto: Versatile Verifiable Computation (2015, neutral): “In the bootstrapping theorem we avoid controversial auxiliary input [13], contrary to [23].”
- The Algebraic Group Model and its Applications (2018, background): “A promising line of research related to this question has recently been initiated by Bitansky et al. [BCPR16].”
- On the Size of Pairing-Based Non-interactive Arguments (2016, background): “Bitansky et al. [BCPR14] show that indistin-guishability obfuscation implies that for every candidate SNARK there are auxiliary output distributions that enable the adversary to create a valid proof without it being possible to extract the witness.”