SEPARATING
SUCCINCT NON-INTERACTIVE
ARGUMENTS
FROM
ALL FALSIFIABLE ASSUMPTIONS
Craig Gentry
Daniel Wichs
IBM
NYU
MIT Seminar (Dec’ 10).
Non-Interactive Argument
Succinct?
Prove Language Membership

Language L µ {0,1}*. Want to show x 2 L.

NP = Non-Interactive Proofs with Efficient Verifier.

Question: How succinct can proofs for NP be?

If L has witness-size t(n) then L 2 DTIME( 2t(n)poly(n)).
 Sub-linear

proofs for all NP ) NP 2 DTIME( 2o(n)).
Generalizes to interactive proofs [GH98, GVW02].
Succinct Arguments for NP

Arguments = Comp Sound Proofs.
[Kilian92, Micali 94]
 Cannot
prove false statements x efficiently.
 Can prove true statements x efficiently given witness w.
 Succinct: size is poly(n)polylog(|x| + |w|).
n = security parameter.

What we know:
 Interactive
(4 rounds): Assuming CRHFs [Kilian 92].
 Non-interactive: Random Oracle model [Micali 94].
* Ignore: better efficiency for prover/verifier, languages outside of NP.
Succinct Non-Interactive Arguments


Question: Can we get Succinct Non-Interactive Arguments
(SNARGs) in the standard model?
Problem: 9 small adversary with hard-coded false
statement x and verifying proof ¼.
 Same

reason why un-keyed CRHFs don’t exist.
Rest of talk:
SNARGs initialized with a common reference string (CRS).
Do SNARGS exist?

Positive Evidence: Take [Micali 94] construction, replace
RO with “complicated hash function” H (set CRS = H).
 Don’t

Can we prove any SNARG construction secure under
OWFs, DDH, RSA, LWE,… ?


know how to break it. Can conjecture security.
“q-decisional-augmented-bilinear-Diffie-Hellman-exponent-assumption” ?
This work: NO*.
* Restrictions apply.
Main Result

No Black-Box-Reduction proof of
security for any SNARG construction
under any
Assumption.
q-ABDHE,…
DDH,Falsifiable
RSA, LWE,…
Defining SNARGs
CRS Ã Gen(1n)
¼ Ã Prove(CRS, x, w)

x, ¼
Verify(CRS, x, ¼)
Completeness: Correctly generated proofs verify with
overwhelming probability.
Defining SNARGs
CRS Ã Gen(1n)
¼ Ã Prove(CRS, x, w)

x, ¼
Verify(CRS, x, ¼)
Public Verifiability: any party can verify proofs.
Defining SNARGs
(CRS, SK) Ã Gen(1n)
¼ Ã Prove(CRS, x, w)


Verify(CRS, SK, x, ¼)
Public Verifiability: any party can verify proofs.
Designated Verifier: only verifier that knows SK can verify.


x, ¼
All our results hold for Designated Verifier SNARGs.
Syntactically same as two-round interactive arguments.
 Challenge = CRS, Response = ¼.
Security of SNARGs
(CRS, SK) Ã Gen(1n)
(x, ¼) Ã Adv (CRS)



x, ¼
Verify(CRS, SK, x, ¼)
(Adaptive) Soundness: For efficient Adv if (x, ¼)Ã Adv(CRS)
Pr[ Verify(CRS, SK, x, ¼) = accept and x 2 L ] = negligible(n)
Natural for SNARGs.
For 2-round arguments traditionally consider static soundness.
Succinct Arguments: What we know?
Doesn’t Exist
May exist (RO Heuristic)
but cannot prove secure
via BB reduction from
falsifiable assumption.
??
Exist assuming CRHFs
SNARG without CRS
Publically Verifiable SNARG (CRS)
Designated Verifier SNARG (CRS)
(adaptive soundness)
2 round
3 round
4 round
(static soundness)
Main Result

No Black-Box-Reduction proof of
security for any SNARG construction
under any Falsifiable Assumption.
Falsifiable Assumptions

Falsifiable Assumption (in spirit of [Naor 03]):
Interactive game between an efficient challenger and
adversary; challenger decides if adversary wins.
 For

PPT Adv
Pr[Adv wins] · negl(n).
Examples: DDH, RSA, LWE, QR,…, q-ABDHE,…
“RSA Signatures (Full-Domain-Hash) with SHA-1 are secure”.

Not Falsifiable:
 “This
Proof System is ZK”. (Not a game - requires Simulator)
 “This SNARG construction is secure”. (Inefficient Challenger)
 “Knowledge-of-Exponent” (KoE) Assumptions. [Dam91, HT98]
Main Result

No Black-Box-Reduction proof of
security for any SNARG construction
under any Falsifiable Assumption.
Black-Box Reductions
SNARG
Attack
Assumption
Assumption
Attack
SNARG
Security
Black-Box Reductions
SNARG
Attack
Assumption
Attack
Reduction

Assumption
Challenger
Black-Box Reduction: Constructive Proof.
 Efficient
Reduction Algorithm. Given Black-Box access to any
SNARG-Attacker becomes an Assumption-Attacker.
 Should work even if SNARG-Attacker is inefficient.
 (If SNARG-Attacker is stateless can ignore rewinding).
Main Result

No Black-Box-Reduction proof of
security for any SNARG construction
under any Falsifiable Assumption.
•
•
Assuming the falsifiable assumption isn’t false.
Assuming sub-exponentially hard OWFs exist.
Main Result

If there is a Black-Box-Reduction proof for some
SNARG construction under some Falsifiable
Assumption then one of the following holds:

The falsifiable assumption is false!

There are no sub-exponentially hard OWFs.
Main Idea: Simulatable Attacker
SNARG
Attack

soundness (outputs false statements, “proofs”).
Efficient Simulator.
 Does

Simulator
Inefficient Attacker.
 Breaks

≈
not break soundness (outputs true statements, proofs).
No efficient distinguisher can tell them apart.
Separation via Simulatable Attack

Existence of Simulatable Attack for any SNARG.

Simulatable Attack implies Black-Box Separation.
Simulatable Attack ) Separation
SNARG
Attack
Assumption
Attack
Reduction

Attacker
WINS
Assumption
Challenger
Given access to the “Simulatable Attacker” reduction
breaks assumption.
Simulatable Attack ) Separation
SNARG
Attack
Efficient
Reduction

Attacker
WINS
Assumption
Challenger
Given access to the “Simulatable Attacker” reduction
breaks assumption.
Simulatable Attack ) Separation
Simulator
Efficient
Reduction


Attacker
WINS
Assumption
Challenger
Given access to the “Simulatable Attacker” reduction
breaks assumption.
Replace “Simulatable Attacker” with efficient Simulator.
Simulatable Attack ) Separation
Simulator
Efficient Attack
on Assumption
Reduction

Attacker
WINS
Assumption
Challenger
There is an efficient attack on the assumption.

) Assumption is false!
Separation via Simulatable Attack

Existence of Simulatable Attack for any SNARG.

Simulatable Attack implies Black-Box Separation.
 BB
Reduction under Falsifiable Assumption
) Assumption false.
Existence of Simulatable Attack


If NP has poly-logarithmic witnesses, there may not be any
attacks at all!
Assumption: Sub-exponentially-hard subset-membership
problems in NP.
 An
NP language L. Distributions: G µ L , B µ {0,1}*\L.
 Can efficiently sample x à G along with a witness w.
±
±
 Cannot distinguish G from B in time 2n with probability 2-n .

Implied by sub-exponentially secure PRGs, OWFs.
Existence of Simulatable Attack
SNARG
Attack
≈
CRS
xÃB
Simulator
(x, ¼)
How to sample ¼ ?

Naïve Idea: try all ¼ until one verifies.
 Might

x à G witness w
¼ Ã Prov(CRS, x, w)
not look at all like correct distribution!
Show: Way to sample “correct looking” ¼ for
x à B.
Existence of Simulatable Attack
8 efficient Prov w/ short output 9 inefficient function Prov*:
x à G witness w
¼ Ã Prov(x, w)
xÃB
¼ Ã Prov*(x)
(x, ¼)
≈
(x, ¼)
Indisitinguishability w/ Auxiliary Info
8 inefficient Prov w/ short output 9 inefficient function Prov*:
xÃG
¼ Ã Prov(x)
xÃB
¼ Ã Prov*(x)
(x, ¼)
≈
(x, ¼)
(s*, ²*)
coming up soon.
If G, B are Proof
(s, ²)-indistinguishable
then
|¼| ²), ²* = 2²
s* = s/poly(2
Assuming
the Lemma…
Existence of Simulatable Attack
SNARG
Attack
xÃB
¼ Ã Prov*(CRS, x)

≈
CRS
(x, ¼)
Simulator
x à G witness w
¼ Ã Prov(CRS, x, w)
Security of G,B exponential in size of proof.
nc polylog(|x| + |w|) = o(nc+1).
c+1
n
 Choose large enough statements to get security 2
.
 Proof-size

Distinguisher can ask many queries – hybrid argument.
Existence of Simulatable Attack
SNARG
Attack
≈
Sec = m CRS
xÃB
¼ Ã Prov*(CRS, x)

D(n)
x à G witness w
¼ Ã Prov(CRS, x, w)
Problem: Who gets which security parameter?
D

(x, ¼)
Simulator
can “lie” about security parameter to “oracle”.
Solution: Simulator gives false statements when m ¼ log(n).
 Annoying
and messy! Simulator gets n and depends on D.
Existence of Simulatable Attack
SNARG
Attack
≈
Sec = m CRS
xÃB
¼ Ã Prov*(CRS, x)

Simulator
(x, ¼)
D(n)
x à G witness w
¼ Ã Prov(CRS, x, w)
Why is this a legitimate attack? Do proofs verify?
 Set
D to be the verifier of the SNARG.
Separation via Simulatable Attack

Existence of Simulatable Attack for any SNARG.
 Any
SNARG for a sub-exp hard membership problem.
 Any SNARG for NP assuming sub-exp hard OWF.

Simulatable Attack implies Black-Box Separation.
 BB
reduction under falsifiable assumption
) Assumption false.

Returning to:
Indisitinguishability
with
Auxiliary Information
Indisitinguishability w. Auxiliary Info
8 short inefficient Aux 9 inefficient Aux*:
xÃG
¼ Ã Aux(x)
xÃB
¼ Ã Aux*(x)
(x, ¼)
≈
(x, ¼)
(s*, ²*)
If G, B are
(s, ²)-indistinguishable
then
) L-bit
leakage
of
PRG
Proof
relatedontoseed
Nisan’s
proofreduces
of
|¼| ²), ²* = 2²
s* = s/poly(2
HILLImpagliazzo
entropy of output
Hardcore
by LLemma.
bits. [DP08]
Proof:
Indisitinguishability w. Auxiliary Info
9 short inefficient Aux
8 inefficient function Aux* 9 D of size s*
Pr[ D(x, ¼)=1] - Pr[D(x, ¼)=1] > ²*
xÃB
¼ Ã Aux*(x)
xÃG
¼ Ã Aux(x)
Task:
Distinguish G, B with
s = s* poly(2|¼|Goal:
²) switch
² =quantifiers
²* /2 with Min-Max theorem.
Proof:
Indisitinguishability w. Auxiliary Info
9 short inefficient Aux
min Aux* max D of size s*
Pr[ D(x, ¼)=1] - Pr[D(x, ¼)=1] > ²*
xÃB
¼ Ã Aux*(x)
xÃG
¼ Ã Aux(x)
Goal: switch quantifiers with Min-Max theorem.
Proof:
Indisitinguishability w. Auxiliary Info
9 short inefficient Aux
min Aux* max Dist(over D of size s*)
Pr[ D(x, ¼)=1] - Pr[D(x, ¼)=1] > ²*
xÃB
¼ Ã Aux*(x)
D Ã Dist
xÃG
¼ Ã Aux(x)
D Ã Dist
Goal: switch quantifiers with Min-Max theorem.
Proof:
Indisitinguishability w. Auxiliary Info
9 short inefficient Aux
min Aux* max Dist(over D of size s*)
Pr[ D(x, ¼)=1] - Pr[D(x, ¼)=1] > ²*
xÃB
¼ Ã Aux*(x)
D Ã Dist
xÃG
¼ Ã Aux(x)
D Ã Dist
[von Neumann 28]
Proof:
Indisitinguishability w. Auxiliary Info
9 short inefficient Aux, Dist(over D of size s*)
min Aux*
Pr[ D(x, ¼)=1] - Pr[D(x, ¼)=1] > ²*
xÃB
xÃG
¼ Ã Aux(x)
D Ã Dist
¼ Ã Aux*(x)
D Ã Dist
Val(x) := min¼ Pr[D(x, ¼) = 1]
E[Val(x)]
xÃB
Goal: get rid of auxiliary information.
-
E[Val(x)] > ²*
xÃG
Proof:
Indisitinguishability w. Auxiliary Info
9 short inefficient Aux, Dist(over D of size s*)
To distinguish if x comes from G, or B:
 Get estimate for Val(x).
Try all possible values of ¼.
size = poly(2|¼|²).
Run many D on each choice.
 Output “B” with that probability.
Val(x) := min¼ Pr[D(x, ¼) = 1]
E[Val(x)]
xÃB
-
E[Val(x)] > ²*
xÃG
Main Result
Slightly succinct: sub-linear arguments.

If there is a Black-Box-Reduction proof for some
SNARG construction under some Falsifiable
Assumption then one of the following holds:

The falsifiable assumption is false!

There are no sub-exponentially hard OWFs.
No exponentially hard subset-membership problems.
Main Result
(sub)-exponential

If there is a Black-Box-Reduction proof for some
SNARG construction under some Falsifiable
Assumption then one of the following holds:

The falsifiable assumption is false!

There are no sub-exponentially hard OWFs.
(sub)-exponential version of
Comparison to other BB Separations

Notion A is not sufficient to realize B in a “black-box way”.
[Impagliazzo Rudrich 89]: Separate KA from OWP.
 [Sim98]: Separate CRHFs from OWP.
 [GKM+00, GKTRV00, GMR01, RTV04, BPR+08 …]



Usually: Notion A is generic e.g. “existence of some OWP”.
Construction of B using a generic instance of A as black-box.
(Reduction uses adversary as a black-box.)
Our result: Notion A can be a specific assumption e.g. “RSA
is a OWP”. Reduction uses adversary as a black-box.

Similar to: [DOP05, AF07,HH09].
BB Reductions for Succinct Arguments



[Rothblum-Vadhan 10] : Any interactive succinct
argument with a black-box proof of security under a
falsifiable assumption can be easily converted into a
“PCP System”.
Not a separation since PCPs exist unconditionally.
Shows: heavy PCP machinery inherent in succinct args.
Summary & Open Problems




Black-box separation of SNARGs from Falsifiable
Assumptions.
Non-black-box techniques? Only know [Bar01].
SNARGs under non-falsifiable assumptions
(e.g. Knowledge of Exponent). Some results by [Gro10].
Succinct arguments with long CRS? Succinct in witness but
not statement? Constructions of 2 or 3 round arguments?
 Or,
do black-box separations extend?
THANK YOU!
Descargar

Separating succinct non-interactive arguments from all