1 of 40

Efficient Verification of Computation on Untrusted Platforms�

Yael Tauman Kalai

MSR and MIT

2 of 40

Computation Goes Remote

Local Trusted Platform

Remote Untrusted Platform

3 of 40

Computation Goes Remote

Local Trusted Platform

Remote Untrusted Platform

4 of 40

Challenges

Economics

Privacy

Integrity

5 of 40

Efficient Verification of Computation

If adv succeeds

then it can break a

cryptographic assumption

6 of 40

Efficient Verification of Computation

If adv succeeds

then it can break a

cryptographic assumption

7 of 40

Efficient Verification of Computation

Common Random String (CRS)

computational

If adv succeeds

then it can break a

cryptographic assumption

8 of 40

Efficient Verification of Computation

Common Random String (CRS)

Succinct Non-interactive Argument (SNARG)

computational

9 of 40

Constructions

First SNARG construction [Kilian92, Micali94]

Verifying correctness of computation: IP, MIP, PCPs

Focus: High complexity classes, and statistical soundness

[GMR85, B85, LFKN90, S90, BGKW88, BLR89, BFL90, FRS88, FGLS, BFLS91, AS92, ALMSS92,…]

Security issues…

The area of verifiable computation started to flourish in the late 80’s and early 90’s, way before the practical need arose.
There is a beautiful line of work, starting with the introduction of interactive proofs, multi-prover interactive proofs, and leading to the beautiful line of work on probabilistically checkable proofs.
The focus of this line of work was on high complexity classes, such as exponential time, where the verifier is always modeled as being polynomial time. So, the goal was to prove to a poly-time verifier the correctness of increasingly complex computations such as exponential time computations.
Typically, the prover is thought of as being all powerful and soundness is statistical, namely, the guarantee is that even an “all powerful” cheating prover cannot cheat.
Kilian and Micali proposed the first SNARG construction, building on this beautiful line of work. This SNARG requires a lot of computational resources from the prover, and hence was never used in practice. In addition, it has some security issues that I will discuss later.
15 years later, we proposed the first doubly efficient interactive proof, where the focus was on real world computations, and the prover was required to be relatively efficient.
Our scheme is very efficient and can easily be converted into a SNARG (as I explain shortly)

[Goldwasser-Micali-Rackoff85, Babai85, Lund-Fortnow-Karloff-Nissan90, Shamir90, BenOr-Goldwasser-Kilian-Wigderson88, Babai-Fortnow-Lund90, Fortnow-Rompel-Sipser88, Feige-Goldwasser-Lovazs-Szegedy, Babai-Fortnow-Levin-Szegedy91, Arora-Safra92, Arora-Lund-Mutwani-Sudan-Szegedy92,…]

10 of 40

Doubly Efficient Interactive Proof (IP) �[Goldwasser-K-Rothblum08]

Focus: On real world computations

Goal: Verifier is super efficient, and generating a proof incurs a

minimal overhead

[GKR]: Construction of doubly efficient IP for all bounded depth computations

SNARG

Known as GKR

Fiat-Shamir

heuristic

11 of 40

Follow-up Work

K-Raz09, Groth10, Gennaro-Gentry-Parno2010 , Chung-K-Vadhan2010, Applebaum-Ishai-Kushilevitz2010, Parno-Raykova-Vaikuntanathan2011,Goldwasser-Lin-Rubinstein11, Damgard-Faust -Hazay11, Lipma12, Bitanski-Canetti12, Gennaro-Gentry-Parno-Raykova12, Bitansky-Canetti-Chiesa-Tromer12a, Bitansky-Canetti-Chiesa-Tromer12b, Bitansky-Chiesa-Ishai-Ostrovsky-Paneth13, K-Raz-Rothblum13, Thaler13, K-Raz-Rothblum14, Bitansky-Sanjam-Lin-Pass-Telang14, Canetti-Holmgren-Jain-Vaikuntanathan14, Koppula-Lewko-Waters14,K-Paenth15, Canetti-Holmgren16, Chen-Chow-Chung-Lai16, Bootle-Cerulli-Chaidos-Growth-Petit16, Giacomelli-Madsen-Orlandi16, K-Rothblum-Rothblum16, Paneth-Rothblum17, Wahby-Ji-Blumberg-shelat-Thaler-Walfish-Wies17, Ames-Hazay-Ishai-Venkitasubramaniam17 Brakerski-Holmgren-K17, Holmgren-Rothblum17, Zhang-Genkin-Katz-Papadopoulos-Papamanthou17 ,Reingold-Rothblum-Rothblum17, Badrinarayanan-K-Khurana-Sahai-Wichs18, Bunz-Bootle-Boneh-Poelstra-Wuille-Maxwell18, Canetti-Chen-Reyzin-Rothblum18, Zhang-Genkin-Katz-Papadopoulos-Papamanthou18, Wahby-Tzialla-shelat-Thaler-Walfish18, Katz-Kolesnikov-Wang18, Holmgren-Lombardi18, Bootle-Lyubashevsky-Seiler19, Canetti-Chen-Holmgren-Lombardi-Rothblum-Rothblum-Wichs19, K-Paneth-Yang19, Ben-Sasson-Bentov-Horesh-Riabzev19, Xie-Zhang-Zhang-Papamanthou-Song19, Ben-Sasson-Chiesa-Riabzev-Spooner-Virza-Ward19, Boschini-Camenisch-Ovsiankin-Spooner20, Chiesa-Ojha-Spooner20, Baum-Nof20, Setty-Lee20, Bhadauria-Fang-Hazay-Venkitasubramaniam-Xie-Zhang20, Setty20, Esgin-Nguyen-Seiler20, Zhang-Xie-Zhang-Song20, Bunz-Fisch-Szepieniec20, Chiesa-Hu-Maller-Mishra-Vesely-Ward20,Boneh-Drake-Fisch-Gabizon21, Baum-Malozemoff-Rosen-Scholl21, Dittmer-Ishai-Ostrovsky21, Jawale-K-Khurana-Zhang21, K-Vaikuntanathan-Zhang21, Weng-Yang-Katz-Wang21, Zhang-Liu-Wang-Zhang-Song-Xie-Zhang21, Chiesa-Yogev21

12 of 40

From Theory to Practice

13 of 40

From Theory to Deployment

Securing Information for Encrypted

Verification and Evaluation (SIEVE)

14 of 40

Until Very Recently…

All SNARGs were only

heuristically secure

Goal: Provable security!

You cannot fake certificates under a standard hardness assumption (Factoring, LWE,…)

15 of 40

Today: Provably Secure SNARGs

Doubly-efficient

Interactive Proof�[GKR08]

Multi-Prover

Interactive Proof

[KRR14, BHK17,…]

SNARG

(for any det. computation)

[KRR13]

SNARG

(for bounded depth comp.)

[KRR16, …, JKKZ21, KLV23]

Part 1:

Part 2:

Sound against

non-signaling strategies

16 of 40

Reflections on the Journey

Quantum complexity

[KRR14, HK20]

Hardness of approximating the value of Linear Program

[KRR16]

Hardness of finding a Nash Equilibrium

[JKKZ21, KLV22]

Connections to other areas of Theory of Computation:

Applications in cryptography:

Fiat-Shamir Paradigm

[GK03, KRR16, JKKZ21, KLV22]

Aggregate signatures

[DGKV22]

Zero-testable encryption

[KPY19]

Non-signaling

[KRR13]

Quantum supremacy

[KLVY23]

17 of 40

From Succinct Doubly-Efficient IP to SNARGs

Statistical soundness

Fiat-Shamir heuristic

[FS86]

SNARG

Interactive proofs (for bounded space computations)

[GMR85, B85, LFKN90, Sha90]

Public

coin

The basic idea is to first construct an interactive proof (GKR), and then apply the FS heuristic to covert it into a SNARG.
The FS heuristic is a popular method for converting any IP into a non-interactive one, assuming the original IP is “public-coin”; i.e., the verifier’s messages are simply random.
It is beautiful in its simplicity, and works as follows: Suppose the original IP has messages (𝜶,𝜷,𝜸,𝜹, 𝝐).
To convert it to a SNARG the prover will send the entire transcript, so will also send the verifier’s messages.
To obtain security we tie his hands, and don’t let him choose the verifier’s msgs freely. Rather the verifier’s messages are a hash H of the transcript so far.
So, 𝜷=𝑯(𝜶) and 𝜹=𝑯(𝜶,𝜷,𝜸).
We will talk about the security of the FS heuristic in a bit. But first you may ask: Why do we need GKR, we alreadya said that we had IPs from the early 90s.
It turns out in these early works there is a huge overhead in the prover’s runtime.
Stepping back: IPs were defined in the mid 80s for the sake of constructing ZK proofs.
Shortly after this model was introduced it was noticed that it is very expressive, in that a poly-time verifier can verify much more than 𝑵𝑷, but can verify any PSPACE computation. But this required a huge overhead in the prover’s runtime.

18 of 40

Statistical soundness

Fiat-Shamir heuristic

[FS86]

SNARG

Doubly efficient interactive proofs

[GKR08]

Public

coin

From Succinct Doubly-Efficient IP to SNARGs

The basic idea is to first construct an interactive proof (GKR), and then apply the FS heuristic to covert it into a SNARG.
The FS heuristic is a popular method for converting any IP into a non-interactive one, assuming the original IP is “public-coin”; i.e., the verifier’s messages are simply random.
It is beautiful in its simplicity, and works as follows: Suppose the original IP has messages (𝜶,𝜷,𝜸,𝜹, 𝝐).
To convert it to a SNARG the prover will send the entire transcript, so will also send the verifier’s messages.
To obtain security we tie his hands, and don’t let him choose the verifier’s msgs freely. Rather the verifier’s messages are a hash H of the transcript so far.
So, 𝜷=𝑯(𝜶) and 𝜹=𝑯(𝜶,𝜷,𝜸).
We will talk about the security of the FS heuristic in a bit. But first you may ask: Why do we need GKR, we alreadya said that we had IPs from the early 90s.
It turns out in these early works there is a huge overhead in the prover’s runtime.
Stepping back: IPs were defined in the mid 80s for the sake of constructing ZK proofs.
Shortly after this model was introduced it was noticed that it is very expressive, in that a poly-time verifier can verify much more than 𝑵𝑷, but can verify any PSPACE computation. But this required a huge overhead in the prover’s runtime.

19 of 40

Bounded Depth Computations

20 of 40

Fiat-Shamir heuristic

[FS86]

.

1

Reduction:

ECC

SNARG

SNARG for Bounded Depth Computations�[GKR08, JKKZ21, KLV23]

21 of 40

Fiat-Shamir heuristic

[FS86]

.

1

Reduction:

SNARG

ECC

SNARG for Bounded Depth Computations�[GKR08, JKKZ21, KLV23]

22 of 40

Fiat-Shamir heuristic

[FS86]

.

1

Reduction:

Verifier can check

SNARG

Reduction:

Sum-check

Protocol

[LFKN90]

Secure?

Secure under sub-exp. LWE or DDH�[JKKZ21, KLV23]

SNARG for Bounded Depth Computations�[GKR08, JKKZ21, KLV23]

23 of 40

The (In)Security of the Fiat-Shamir Heuristic�[FS86]

In practice:

In theory:

Proposed as a heuristic for converting identification schemes into signature schemes.

One of the most widely used signature scheme (ECDSA)

is based on this heuristic

24 of 40

The (In)Security of the Fiat-Shamir Heuristic�[FS86]

In practice:

In theory:

[GK03] (based on [Barak01])

First SNARG construction: Kilian92, Micali94

[FS86]

SNARG

[BBHMR19]

Computational soundness

Proposed as a heuristic for converting identification schemes into signature schemes.

25 of 40

The (In)Security of the Fiat-Shamir Heuristic�[FS86]

Is this heuristic secure when applied to statistically sound proofs??

26 of 40

The (In)Security of the Fiat-Shamir Heuristic�[FS86]

Theorem [JKKZ21, KLV23]: The FS-Heuristic is secure when applied to the GKR protocol under sub-exponential LWE or DDH.

Theorem [KRR16]: The FS-Heuristic is secure when applied to any statistically sound proofs under a strong hardness assumptions.

Building upon [CCHLRRW19, PS19]

27 of 40

Doubly Efficient Interactive Proof for bounded depth computations [GKR08]

Convert into a SNARG using the Fiat-Shamir heuristic

Resulting SNARG is secure under sub-exponential LWE/DDH [JKKZ21, KLV23]

Many implementations

Bonus 1: Deeper understanding of the security of the Fiat-Shamir heuristic

Bonus 2: Application to complexity theory:

Finding a Nash Equilibrium is sub-exponentially hard under sub-exponential LWE/DDH.

Takeaways from Part 1

unique and updatable SNARGs can be embedded in PPAD problem

[CHKPRR19]

Nash is PPAD complete [Papadimitriou94, DGP09]

28 of 40

Beyond Bounded Depth

[K-Raz-Rothblum13, KRR14, KP16, BHK17, BKKSW18, KPY19, KVZ21, CJJ21, DGKV22, WW22, HJKS22, KLVW23]

SNARGs for any deterministic computation,

any RAM, or space-bounded non-deterministic computation,

provably secure under LWE or DLIN or DDH & QR

29 of 40

From MIPs to SNARGs

Multi-Prover Interactive Proof

[BGKW88]

[Biel-Meyer-Wetzel99]

BMW

heuristic

Fully Homomorphic Encryption (LWE)

1. It is not a SNARG

It is a 2-message privately verifiable protocol!

2. It is not secure! [DLNN01, DHRW16]

The starting point of the KRR-SNARG is again an information theoretic object, this time a multi-prover interactive proof.
This model of multi-prover interactive proofs was proposed by BenOr et al.
Their goal was to get perfect zero-knowledge.
But shortly after these proof systems were introduced, Babai et al noticed that this proof system is very powerful!
In particular, they showed that…
The power of such proof systems stems from the assumption that the 2 provers cannot interact!
For example, think of two suspects that cannot interact: It is much harder for two suspects to lie consistently than for a single suspect to lie.

About a decade later BMW proposed a beautiful heuristic for converting such proofs systems to a single prover protocol.
The idea is simple! The verifier will send both queries to the same prover!
Doing that will clearly destroy the soundness (since it is like allowing the two provers to interact).
So, their proposal was to encrypt each these queries, each one with a different (fresh) key, using a FHE.
The prover will compute the answers homomorphically, the important point being that when he computes the answer to 𝑞_1 he does not know what 𝑞_2is since it is encrypted using a fresh key. And similarly for computing 𝑎_2.
The verifier will decrypt the communication and will accept iff the original verifier would have accepted.

30 of 40

From MIPs to SNARGs

Multi-Prover Interactive Proof

[BGKW88]

[Biel-Meyer-Wetzel99]

BMW

heuristic

Fully Homomorphic Encryption (LWE)

Local strategies

Non-signaling strategies

The starting point of the KRR-SNARG is again an information theoretic object, this time a multi-prover interactive proof.
This model of multi-prover interactive proofs was proposed by BenOr et al.
Their goal was to get perfect zero-knowledge.
But shortly after these proof systems were introduced, Babai et al noticed that this proof system is very powerful!
In particular, they showed that…
The power of such proof systems stems from the assumption that the 2 provers cannot interact!
For example, think of two suspects that cannot interact: It is much harder for two suspects to lie consistently than for a single suspect to lie.

About a decade later BMW proposed a beautiful heuristic for converting such proofs systems to a single prover protocol.
The idea is simple! The verifier will send both queries to the same prover!
Doing that will clearly destroy the soundness (since it is like allowing the two provers to interact).
So, their proposal was to encrypt each these queries, each one with a different (fresh) key, using a FHE.
The prover will compute the answers homomorphically, the important point being that when he computes the answer to 𝑞_1 he does not know what 𝑞_2is since it is encrypted using a fresh key. And similarly for computing 𝑎_2.
The verifier will decrypt the communication and will accept iff the original verifier would have accepted.

31 of 40

From MIPs to SNARGs

Multi-Prover Interactive Proof

[BGKW88]

Fully Homomorphic Encryption (LWE)

[Biel-Meyer-Wetzel99]

BMW

heuristic

1. If the MIP has non-signaling soundness then the 2-msg protocol is secure [KRR13]

The starting point of the KRR-SNARG is again an information theoretic object, this time a multi-prover interactive proof.
This model of multi-prover interactive proofs was proposed by BenOr et al.
Their goal was to get perfect zero-knowledge.
But shortly after these proof systems were introduced, Babai et al noticed that this proof system is very powerful!
In particular, they showed that…
The power of such proof systems stems from the assumption that the 2 provers cannot interact!
For example, think of two suspects that cannot interact: It is much harder for two suspects to lie consistently than for a single suspect to lie.

About a decade later BMW proposed a beautiful heuristic for converting such proofs systems to a single prover protocol.
The idea is simple! The verifier will send both queries to the same prover!
Doing that will clearly destroy the soundness (since it is like allowing the two provers to interact).
So, their proposal was to encrypt each these queries, each one with a different (fresh) key, using a FHE.
The prover will compute the answers homomorphically, the important point being that when he computes the answer to 𝑞_1 he does not know what 𝑞_2is since it is encrypted using a fresh key. And similarly for computing 𝑎_2.
The verifier will decrypt the communication and will accept iff the original verifier would have accepted.

32 of 40

From MIPs to SNARGs

SNARG!

[KPY19]:

zero-testable encryption

(from bilinear maps)

33 of 40

From MIPs to SNARGs

SNARG!

CRS

[CJJ21, KVZ21]:

Assuming a BARG

(SNARG for BatchNP)

SNARG

BARG

For all comp. with non-signaling MIP

34 of 40

Boosting BARGs

[KLVW23]

[DGKV22]

BARG composition

Applications: Aggregate signature scheme and incremental verifiable computation (IVC)

35 of 40

Takeaways from Part 2

used for quantum supremacy

[KLVY23]

36 of 40

Interactive Proof

[GKR]

SNARG

[JKKZ21, KLV23]

Fiat-Shamir heuristic

[FS86]

BMW heuristic

[BMW99]

SNARG for bounded depth

SNARG for arbitrary comp.

SNARG

[KPY19, KVZ21, CJJ21, WW22, HJKS22, KLVW23]

NS-soundness

[KRR13+14,…]

BARG

37 of 40

Success for theory of cryptography!

38 of 40

39 of 40

Grand Challenge

SNARGs for NP

1 of 40

2 of 40

3 of 40

4 of 40

5 of 40

6 of 40

7 of 40

8 of 40

9 of 40

10 of 40

11 of 40

12 of 40

13 of 40

14 of 40

15 of 40

16 of 40

17 of 40

18 of 40

19 of 40

20 of 40

21 of 40

22 of 40

23 of 40

24 of 40

25 of 40

26 of 40

27 of 40

28 of 40

29 of 40

30 of 40

31 of 40

32 of 40

33 of 40

34 of 40

35 of 40

36 of 40

37 of 40

38 of 40

39 of 40

40 of 40