Weakly Extractable One-Way Functions

An extractable one-way function (EF) is a family of functions  that satisfies two properties:

• One-wayness: Given an image  for random key  and input  it is hard to find a corresponding pre-image 
• Extraction: Given a random key , it is hard to produce an image  obliviously, without knowing a corresponding preimage 

This is formalized by requiring that for any efficient algorithm  that given  produces an image  there is an efficient extractor  (that depends on  ) that given the same key , extracts a preimage . While their extraction property is reminiscent of proofs of knowledge , EFs are essentially different — they draw their power from the fact that extraction can be done without interaction.

Without interaction, traditional black-box extraction techniques, like rewinding, (provably) do not work. Accordingly, extraction must use the code of the adversary in a non-black-box way. Assuming indistinguishability obfuscation, no efficient extractor can work against all polynomial-size non-uniform adversaries; that is, even when the extractor is given the adversary’s code.

One approach that avoids the above barriers is to simply assume the existence of an extractor for every adversary, without giving an explicit extraction strategy. An EF with such non-explicit extractors follows, for example, from the knowledge of exponent assumption. Such* knowledge assumptions* translate in applications to security reductions that are, at least in part, non-explicit. Knowledge assumptions are arguably unsatisfying, and in particular are not falsifiable.

Another way to circumvent known barriers is to restrict the class of adversaries. To construct EFs with an explicit extractor against adversaries with bounded non-uniform advice, under standard assumptions.

Is there hope for explicit extraction from general non-uniform adversaries?

• weakly extractable one-way functions (WEFs)

WEFs are deeply connected to three-message zero knowledge protocols, establishing a loose equivalence between the two notions.

Instead of requiring that the extractor  given a random key  and the code of the adversary  is able to find a preimage  for the adversary's image  we allow the extractor to sample a simulated key  on its own together with an extracted preimage  for  The simulated key  must be indistinguishable from a randomly sampled key .

Assuming WEFs, two-message witness-indistinguishable arguments, and non-interactive commitments, there exist three-message ZK arguments for NP.

• equivalence between generalized WEFs (GWEFs) and three-message zero knowledge arguments

Assuming two-message witness-indistinguishable and non interactive commitments arguments, GWEFs exist if and only if publicly verifiable three-message zero knowledge arguments exist.

• privately verifiable GWEFs

Assuming privately verifiable GWEFs and secure function evaluation, there exist privately verifiable three-message computational zero-knowledge arguments for NP.

Assuming privately verifiable three-message statistical zero-knowledge arguments for NP and noninteractive commitments, there exist privately verifiable GWEFs.

Demonstrating, under standard assumptions, a WEF with an explicit extractor against non-uniform adversaries is left as an open question.