Equivalence between GWEF and 3-message ZKA

Generalized Weakly Extractable One-way Functions (GWEF)

• Definition (GEF [BCPR16]). A polynomial-time computable family of functions

associated with an efficient key sampler  is a generalized extractable one-way function with respect to a polynomial-time relation  if the following holds:

 -Hardness: For any non-uniform family of polynomial-size circuits  and every 

 -Extractability: There exists a PPT extractor  such that for any non-uniform family of polynomial size circuits  and every ,

• Definition (GWEF). An efficiently computable family of functions

associated with an efficient key sampler  and NP relation  is a generalized weakly extractable one-way function with respect to a polynomial-time relation  if the following holds:

Worst-case  -Hardness: For any non-uniform family of polynomial-size circuits  every  and every 

Weak  -Extractability: There exists a PPT extractor  such that for any non-uniform family of polynomial-size circuits  we have:

Extraction: For all 

Key Indistinguishability:

Validity: For all 

From Three-Message ZK to GWEF

!! Assuming publicly verifiable three-message zero-knowledge argument system for NP and non-interactive commitments, there exists a GWEF.

Sampler :

• Sample 
• Let  be the zero-knowledge simulator, and let  be the honest verifier circuit with hardwired randomness  Sample 
• Return 

Key relation :  iff  such that 

Function  in family :

• Parse 
• Emulate the verifier  with statement  first prover message  and randomness  Let  be the produced verifier message.
• Output 

:

•  iff
• Parsing  and 
• The transcript  with respect to statement  is accepting.

From GWEF to Three-Message ZK

!! Assume there exist GWEF, non-interactive commitments, and two-message witness indistinguishable arguments. Then there exists a publicly verifiable three-message ZK argument.

•  off  on  off  on  an offline-online WIAOK system for NP with two offline messages and a single online message. (Recall that such systems follow from non-interactive commitments. We denote its corresponding messages by wi 
•  off  an offline-online  system for  with a single offline (verifier) message and a single online (prover) message. We denote its corresponding messages by 

Common Input: statement . 

Prover Input: witness