Blackbox Verifiable Computation Scheme Overview
This summarized content discusses the concept of blackbox verifiable computation, focusing on the challenges faced by clients and servers, the role of helper oracles, positive results utilizing homomorphic encryption, and background information on Random Self Reducible (RSR) functions. The protocol outlined highlights the steps involved in achieving efficient verification while ensuring soundness in the computation process.
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
Blackbox Verifiable Computation Amit Agarwal, Navid Alamati, Dakshita Khurana Srinivasan Raghuraman, Peter Rindal
Motivation Problem Description 1. Client not willing to go through the burden of auditing the server s code. Server making frequent code updates. Server wishing to keep it s code private. 2. 3. Server (??) ? ? (?1, ,??) Client (?1, ,??) Aim : Client would like to outsource the computation of function ? on a batch of ? inputs. Properties Black-box verification Completeness Soundness Efficient verification The client s running time should be sublinear in ? ??, where ?? is the time complexity of computing ? If the server is malicious, then y1, ,??= ? ?1, ,? ?? OR Client aborts with high probability If the server is honest, then y1, ,??= ? ?1, ,? ?? always The client s protocol should be oblivious of the server s circuit ??
Helper oracles Function oracle ? ?? ?1 . . . Server (??) ? (?1, ,??) Client (?1, ,??) Aim : Client would like to outsource the computation of function ? on a batch of ? inputs. Non-triviality: The combined time complexity of helper oracle functions, ?1 ,?? , is asymptotically smaller than the time complexity of the function ? 1. Number of oracle queries made by Client to the function oracle is ?(?) Efficient verification: 2. Number of oracle queries made by Client to each helper oracle is ?(? ?) 3. Running time of the client is ?? ? ? ??where ? is some fixed constant.
Positive Result Assuming Homomorphic encryption (HE), there exists a Blackbox verifiable computation scheme for the class of Random Self Reducible (RSR) functions. Inspired from Program testing/correcting literature [BLR90] High level Idea : Use RSR property to achieve blackbox verification. Use cut-and-chose check + Homomorphic Encryption + RSR to get efficient verification while retaining soundness.
Background on RSR ?-RSR for a function ? is defined by 2 algorithms : RSR.Encode RSR.Decode Uniformly Random ?1 ?1 ? . . . . . . . . . ? = ?(?) RSR.Decode ? RSR.Encode ?? ?? ? ? ? 1 DLOG Much simpler than ? : 2 All linear functions 2 Legendre ????.??????+ ????.?????? ?? 2 sine, cosine 2 Integer division 2 Modular exponentiation Matrix Multiplication over ? 4 4 Polynomial multiplication over ?
Protocol Let s assume ? has ? = 1 RSR RSR.Encode RSR.Decode ?? column is formed by invoking RSR.Encode on ?? independently ? times ? Server (??) Client (?1, ,??) ?1,1 ??,1 ? = Shuffle ?1,? ??,? ? Apply ?? individually to each entry of ? ? = If this check passes, ALL columns in ? have majority correct values w.h.p ? ? = Reverse_Shuffle(? ) Apply Cut and choose check on ? ??(?) For each ? : check ? = ?1,1 ??,1 ? = Apply RSR.Decode on every cell Perform majority decoding on each column to get (?1, ,??) ?1,? ??,?
Observations The client-side verification is completely oblivious of the server circuit ?? Known SNARG techniques require Client and Server to agree on a fixed circuit for ? (and hence are not black- box) How big should the size of cut-and-choose set should be ? log2? sized set suffices for negligible soundness error Total workload on the verifier side: log2? queries to ? ? queries to ?(? ?) local computation (shuffling, majority decoding)
Extending to ?-RSR functions (? > 1) Main challenge: The outputs of RSR.Encode are not jointly random Malicious prover can cheat by figuring out which ? values originated from which ? values. Solution: Encrypt each ? under a fresh public key and send shuffled encrypted ? values to the server. To enable the prover to apply ? on the encrypted values, we need the encryption scheme to be homomorphic. Verifier locally decrypts and performs cut-and-choose check as before. Soundness Proof: Non-trivial (need to formalize a no-signaling guarantee)
Impossibility Result Wishful aim : Tightly characterize the class of functions that admit OBVC scheme and those that do not. Weaker aim : Show that a large enough function class cannot admit OBVC scheme. Consider the function class ?? { 0,1? 0,1?} We show that there does not exist a OBVC scheme for ?? Proof technique: Turns out to be non-trivial as the helper oracles might contain arbitrary information about the function ? ?? We use techniques based on prior work [CDGS18] to carefully formalize an impossibility proof.
Extending to ?-RSR functions (? > 1) Uniformly Random ?1 Joint distribution is NOT uniformly random . . . ? RSR.Encode ?? Uniformly Random Shuffling these two values loses information about which ? each ? originated from Shuffling these four values does not lose information about which ? each ? originated from K=2 RSR K=1 RSR 1 ?1 RSR.Encode ?1 1 2 ?1 ?1 RSR.Encode ?1 1 ?2 RSR.Encode ?2 1 2 ?2 ?2 RSR.Encode ?2
Idea Encrypt each ? under a fresh public key and send shuffled encrypted ? values to the server. To enable the prover to apply ? on the encrypted values, we need the encryption scheme to be homomorphic. Verifier locally decrypts and performs cut-and-choose check as before.
Protocol RSR.Encode RSR.Decode ?? column is formed by invoking RSR.Encode on ?? independently ? times ? Server (??) Client (?1, ,??) ?1,1 ??,1 ? = Shuffle ?1,? ??,? ? Apply ?? individually to each entry of ? ? = If this check passes, ALL columns in ? have majority correct values w.h.p ? ? = Reverse_Shuffle(? ) Apply Cut and choose check on ? ??(?) For each ? : check ? = ?1,1 ??,1 ? = Apply RSR.Decode on every cell Perform majority decoding on each column to get (?1, ,??) ?1,? ??,?
Soundness Proof Non-communicating Servers (??) No-signaling Servers (??) Client (?1, ,??) Client (?1, ,??) . . . . . . Homomorphic Encryption Client (?1, ,??) Server (??)
Impossibility Result Wishful aim : Tightly characterize the class of functions that admit OBVC scheme and those that do not. Weaker aim : Show that a large enough function class cannot admit OBVC scheme. Consider the function class ?? { 0,1? 0,1?} We now consider an experiment where a function ? is sampled randomly from this class and OBVC scheme is executed on it This experiment can be analyzed in the Random Oracle Model
? ?? { 0,1? 0,1?} ? ?? ?1 . . . Server (??) Client (?1, ,??) Idea : Switch to a world where the prover reprograms the value of ? at a random ??. If the client doesn t query at ?? , then the change will go un-noticed and prover will be able to cheat. Issue: Helper oracles might contain auxiliary information about ?
Impossibility of OBVC Impossibility in the Bit-fixing Random Oracle model [CDGS18] Impossibility in the Auxiliary-input Random Oracle model Auxiliary input Random Oracle Model (AIRO) : The adversary is allowed to contain any arbitrary information about the Random Oracle as a preprocessing information. Bit fixing Random Oracle Model (BFRO) Introduced by [CDGS18] to aid the analysis of cryptographic protocols where adversary might have some preprocessing information about the Random Oracle. Relaxes the AIRO by only allowing the preprocessing information to be dependent on some fixed number of Random Oracle points.
What is Verifiable Computation ? ? Server (??) Client ? ? ? ?(?) Proof ? Issue : Proof ?is tied to the circuit/code ?? that the server is using Proof of correct computation of ?" Completeness: If the server is honest, then the proof ? is accepted by the client. Soundness: If the server is malicious, then the proof ? is rejected by the client. Efficiency: Work done by the verifier to check the proof ? must be less than recomputing the function from scratch
Extending to 1,? RSR functions Client simply encrypts each cell using Homomorphic Encryption (HE) under a unique ?? , the server computes the function homomorphically, and then the client decrypts and performs cut-and-chose check. A leveled HE scheme will suffice as we are only interested in outsourcing some fixed function ? at a time Total running time of the verifier: ? ? ?RSR.Encode+ ?RSR.Decode+ ?HE.Encrypt+ ?HE.Decrypt + ? log2? ?? Ongoing work: Remove the need for HE using statistical mixing properties Extending to larger classes of functions Impossibility results for general class of functions
