Advancements in Interactive Proofs for Efficient Computation
Doubly Efficient Interactive Proofs
Ron Rothblum
Outsourcing Computation
Weak client outsources computation to the cloud.
Outsourcing Computation
We do not want to blindly trust the cloud.
•
Correctness:
why should we trust the server’s
answer?
•
Privacy:
keep client’s sensitive data secret (closely
related to homomorphic encryption)
K
e
y
s
e
c
u
r
i
t
y
c
o
n
c
e
r
n
s
:
Interactive Proofs to the Rescue?
Doubly Efficient Interactive Proof
[GKR08]
S
o
u
n
d
n
e
s
s
h
o
l
d
s
a
g
a
i
n
s
t
a
n
y
(
c
o
m
p
u
t
a
t
i
o
n
a
l
l
y
u
n
b
o
u
n
d
e
d
)
c
h
e
a
t
i
n
g
p
r
o
v
e
r
.
Doubly Efficient Interactive Proofs:
The State of the Art
Constant-Round Doubly Efficient
Interactive Proofs
N
o
c
r
y
p
t
o
g
r
a
p
h
i
c
a
s
s
u
m
p
t
i
o
n
s
o
r
o
p
e
r
a
t
i
o
n
s
I
n
h
e
r
e
n
t
(
u
n
d
e
r
r
e
a
s
o
n
a
b
l
e
c
o
n
j
e
c
t
u
r
e
s
)
Roadmap: A Taste of the Proof
Iterative construction:
1.
Start with interactive proof for short
computations.
2.
Build interactive proof for slightly longer
computations.
3.
Repeat.
Iterative Construction
Divide & Conquer
Conquer?
recurse on all subcomputations.
Problem:
verification blows up, no savings.
Divide & Conquer
Conquer?
Choose a few at random and recurse.
Problem:
huge soundness error.
Best of Both Worlds?
Tool: Probabilistically Checkable Proofs
Furthermore, query locations don’t depend on input.
Totally insecure – soundness of PCP is only
guaranteed if PCP proof is written in advance.
Batch Verification via Checksums
Single Deviation Provers
I
n
t
u
i
t
i
v
e
l
y
t
h
e
h
a
r
d
e
s
t
c
a
s
e
U
n
j
u
s
t
i
f
i
a
b
l
e
a
s
s
u
m
p
t
i
o
n
!
Soundness vs. Single-Deviation Provers
Soundness vs. Single-Deviation Provers
Soundness vs. Single-Deviation Provers
Soundness vs. Single-Deviation Provers
Handling General Cheating Provers
Since there is a unique PCP – verifier
will notice deviation and reject
Constant-Round Doubly Efficient
Interactive Proofs
Open Problems
•
Research directions:
–
Bridge theory and practice.
–
Sublinear
time
verification.
•
Concrete questions:
–
IP=PSPACE
with “efficient” prover.
–
Batch verification for
all of
NP
.
–
[GR17]:
Simpler and more efficient protocols (even
for smaller classes).
Start with some motivation and introduce the problem, then we will discuss some of the results and in the last part of the talk we will go into the details of a recent result.
Recent developments in interactive proofs focus on enhancing the efficiency of computations outsourced to untrusted servers, addressing concerns related to correctness and privacy. Solutions like doubly efficient interactive proofs offer a secure way to delegate computations while minimizing reliance on cloud services.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Doubly Efficient Interactive Proofs Ron Rothblum
Outsourcing Computation Weak client outsources computation to the cloud. ? ? = ?(?)
Outsourcing Computation We do not want to blindly trust the cloud. ? ? = ?(?) Key security concerns: Correctness: why should we trust the server s answer? Privacy: keep client s sensitive data secret (closely related to homomorphic encryption)
Interactive Proofs to the Rescue? Interactive Proof [GMR85]: prover ? tries to interactively convince a polynomial-time verifier ? that ? ? = ?. ? ? = ? ? convinces ?. ? ? ? no ? can convince ? wp 1/2. Key Problem: in classical results complexity of proving is actually exponential: IP=PSPACE [LFKN90,Shamir90]: Interactive Proofs for space ? computations with 2poly ?prover, poly(?,?) verification, poly(?) rounds.
Doubly Efficient Interactive Proof [GKR08] Interactive proof for ? ? = ? where the prover is efficient, and the verifier is super efficient. Proportional to complexity of ? Much faster than complexity of ? Soundness holds against any (computationally unbounded) cheating prover.
Doubly Efficient Interactive Proofs: The State of the Art Logspace uniform ?? 1) [GKR08]: Bounded Depth Any bounded-depth circuit. (Almost) linear time verifier, poly-time prover. Number of rounds proportional to circuit depth. 2) [RRR16]: Bounded Space Any bounded-space computation. (Almost) linear time verifier, poly-time prover. ? ? rounds.
Constant-Round Doubly Efficient Interactive Proofs Theorem [RRR16]: ? > 0 s.t. every language computable in poly(?) time and ??space has an unconditionally sound interactive proof where: 1. Verifier is (almost) linear time. 2. Prover is polynomial-time. 3. Constant number of rounds. No cryptographic assumptions or operations Inherent (under reasonable conjectures)
Roadmap: A Taste of the Proof Iterative construction: 1. Start with interactive proof for short computations. 2. Build interactive proof for slightly longer computations. 3. Repeat.
Iterative Construction Suppose we have interactive proofs for time ?/? and space ? computations. Consider a time ? and space ? computation. ? ? ? ?
Divide & Conquer Divide: Prover sends Turing machine configuration in ? ? intermediate steps. ? ? ?(? 1)?/? ??/? ?2?/? Conquer? recurse on all subcomputations. Problem: verification blows up, no savings.
Divide & Conquer Divide: Prover sends Turing machine configuration in ? ? intermediate steps. ? ? ?(? 1)?/? ??/? ?2?/? Conquer? Choose a few at random and recurse. Problem: huge soundness error.
Best of Both Worlds? Can we batch verify ? instances much more efficiently than ? independent executions. Goal: Suppose ? ? can be verified in time ?. Want to verify ?1, ,?? ? in ? ? time.
Warmup: Batch Verification for ?? ?? ?? are all relations with unique accepting witnesses. Theorem [RRR16]: Every ? ??, has an interactive proof for verifying that ?1, ,?? ? with ? ???????(?) + ?(?) communication. ? = witness length
Tool: Probabilistically Checkable Proofs PCP Theorem [ ,ALMSS92, ]: Every NP witness ? has a PCP encoding ? = ???(?,?) that can be verified with a constant number of queries. ? = ??? ?,? ?(?) Furthermore, query locations don t depend on input.
PCPs Batch Verification? ?(??, ,??) ?(??,?? ,??,??) 1. Generate PCP queries ? ?1= ??? ?1,?1 ? ?2= ??? ?2,?2 ?? ? = 2. Accept if PCP verifier accepts all ? statements. ??= ??? ??,?? Extremely efficient just ?(? + ??? ?) communication! Totally insecure soundness of PCP is only guaranteed if PCP proof is written in advance.
Batch Verification via Checksums ?(??, ,??) ?(??,?? ,??,??) ? ?1= ??? ?1,?1 ?2= ??? ?2,?2 ? 1. Generate PCP queries ? ? = ?? 2. Check that PCP verifier accepts all ? statements. ??= ??? ??,?? 3. Check ??consistent with ?. ? = ? ???
Single Deviation Provers In general: not sound. Intuitively the hardest case Relaxed soundness: make two assumptions only one ?? ?. single-deviation ? : in answering queries ?, ? must answer honestly on all rows ? ? . Unjustifiable assumption!
Soundness vs. Single-Deviation Provers ?(??, ,?? , ,??) ? (??,??, ,?? , .??,??) ?
Soundness vs. Single-Deviation Provers ?(??, ,?? , ,??) ? (??,??, ,?? , .??,??) ? ?1= ??? ?1,?1 ?? = ? + ? ? ?? ? = ??= ??? ??,?? ? = ? ??? ? ???
Soundness vs. Single-Deviation Provers ?(??, ,?? , ,??) ? (??,??, ,?? , .??,??) ? ?1= ??? ?1,?1 ?? = ? + ? ? ?? ? 1. Generate PCP queries ? ? = ??= ??? ??,?? ? = ? ??? ? ???
Soundness vs. Single-Deviation Provers ?(??, ,?? , ,??) ? (??,??, ,?? , .??,??) ? ?1= ??? ?1,?1 ?? = ? + ? ? ?? ? 1. Generate PCP queries ? ? = ?? ??= ??? ??,?? 2. Check that PCP verifier accepts all ? statements. ? = 3. Check ??consistent with ?. ? ??? ? ??? Single-deviation ? must answers row ? by ?? ?? defined before queries ? were specified PCP soundness ? can t cheat
Handling General Cheating Provers For ? deviation prover: use fancy checksum of size ? ?. Consider ? = ?. Cheating prover has two options: 1. deviate on ? rows ? deviation, we re fine. 2. deviate on > PCPs of more than ? of rows. ? rows answers disagree with unique Since there is a unique PCP verifier will notice deviation and reject ? selects 100 ? rows at random and asks prover to send the entire PCP for these rows.
Batch Verification for ?? This gives ? multiplicative overhead. Can be improved to polylog ? by recursion. For batch verification of interactive proofs we introduce interactive analogs of ?? and ???.
Constant-Round Doubly Efficient Interactive Proofs Theorem [RRR16]: ? > 0 s.t. every language computable in poly(?) time and ??space has an unconditionally sound interactive proof where: 1. Verifier is (almost) linear time. 2. Prover is polynomial-time. 3. Constant number of rounds.
Open Problems Research directions: Bridge theory and practice. Sublinear time verification. Concrete questions: IP=PSPACE with efficient prover. Batch verification for all of NP. [GR17]: Simpler and more efficient protocols (even for smaller classes).
