Private Outsourcing RAM Computation Using Garbled RAM
Learn about the innovative approach to private outsourcing RAM computation using reusable garbled RAM circuits. This method allows clients to efficiently leverage the resources of powerful servers while maintaining data privacy. Explore the concepts of Fully Homomorphic Encryption (FHE) circuits, RAM complexity, and the goals and solutions involved in this secure computing 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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Outsourcing Private RAM Computation Daniel Wichs Northeastern University with: Craig Gentry, Shai Halevi, Mariana Raykova
Problem Overview ? ? = ?(?) Server Client Weak client wants to leverage resources of a powerful server to compute ?(?) without revealing ?. Efficiency Requirements: Client does much less work than computing ?(?) Server does about as much work as computing ?(?)
Use FHE! Done? Private outsourcing is possible using Fully Homomorphic Encryption (FHE). [RAD78,Gen09, ] But FHE works over circuits rather than RAM programs. I m very efficient!
Circuits vs. RAM Private outsourcing is possible using Fully Homomorphic Encryption (FHE). [RAD78,Gen09, ] But FHE works over circuits rather than RAM programs. RAM complexity ? circuit or TM complexity ?2 For programs with initial data in memory , efficiency gap can be exponential (e.g., Google search).
Goals ? ? = ?(?) Server Client Client s work: ?( ? + |?|) Server s work: ?(RAM run-time of P). May allow client pre-processing of P. Client does one-time computation in O(RAM run-time of P). Later, outsource many executions of P. Amortized efficiency.
Goals ? ? ? = ?(?) Server Client Basic scenario: client wants to run independent executions of ? on inputs ?1, ?2, ?3, Persistent Memory Data: Client initially outsources large private memory data D. Program executions ??(??) can read/write to D.
Goals Server Client Non-interactive solution: reusable garbled RAM .
Garbled Computation Reusable Garbled Circuits [GKPVZ 13a,b] Garbled Circuits [Yao82] Persistent Memory Data: Can garble many inputs per circuit. Garble Data: ? ? Garble circuit: ? ? Garble input: ? ? Efficiently outsource circuit comp. Extension to TM. Can execute many programs with read/write access to data. Given ?, ? only reveals ?(?) Secure on one input ?. Reusable Garbled RAM This Talk! Garbled RAM [LO13, GHLORW14] Garble RAM: ? ? Garble input: ? ? Can garble many inputs per program. Efficiently outsource RAM comp. Size of ?, run-time ?( ?) is O(RAM run-time ?).
Main Results 1-time Garbled RAM + Reusable Garbled RAM Reusable Garbled Circuits New security/efficiency requirements. Instantiate with iO or Functional Rnc.
Main Result with persistent data 1-time Garbled RAM with persistent data + Reusable Garbled RAM with persistent data Reusable Garbled Circuits Stronger security requirements. Instantiate with strong diO (heuristic obf)
1-Time Garbled RAM Definition without persistent data View can be simulated given y GProg ?,? ? O(run-time) O(|x|,|y|) GInput(?, ?) ? Client secret: k Server Eval( ?, ?) ? O(run-time)
Reusable Garbled RAM Definition without persistent data View can be simulated given ?1,?2 GProg ?,? ? { GInput(??, ?) ?? : i=1, } Client secret: k Server Eval( ?, ??) ??
Construct reusable garbled RAMby combining: one-time garbled RAM (GProg1, GInput1, GEval1) reusable garbled circuits Reusable Gprog ? ?????? reusable circuit-garbling of ?[?] ????, ???? ?[?] { Reusable Ginput ? ? Choose fresh one-time key ? garble input ?,? for ?[?] GProg1(?; ?) ???? GInput1(?, ?) ???? } Size of ?[?] = (RAM run-time of ?) |input| = O(|x|) |output| = (RAM run-time of ?) ?,?
Construct reusable garbled RAMby combining: one-time garbled RAM (GProg1, GInput1, GEval1) reusable garbled circuits Problem: In reusable garbled circuits of [GKPVZ13], size of garbled input always exceeds size of circuit output. ????, ???? ?[?] { Unfortunately: This is inherent. Cannot do better if want simulation security. GProg1(?; ?) ???? GInput1(?, ?) ???? } Size of ?[?] = (RAM run-time of ?) |input| = O(|x|) |output| = (RAM run-time of ?) ?,?
Construct reusable garbled RAMby combining: one-time garbled RAM (GProg1, GInput1, GEval1) reusable garbled circuits Solution: Show that we do not need simulation-security for reusable garbled-circuits. A weaker notion suffices. Construct reusable garbled-circuits with weaker security notion but better efficiency needed in construction.
Distributional Indistinguishability Aweaker security notion for garbled circuits. Circuit ? and independent input distributions ??,?? If ?? ??, {?? Then ?, ?1, ?2, , ?? ?, ? 1, ? 2, , ? ? : ?? } satisfy ? ?? ? ?? Can get huge output, small garbled input. Follows from indistinguishability obfuscation, or functional encryption for circuits.
Real-or-Dummy program ?+(flag,x,y ) { if flag=1 // real output P(x) else //dummy output y } ????, ???? ????, ???? ?[?+] { GProg1(?+; ?) ???? GInput1(?, ?) ???? ?, } User: garbles inputs (u=(flag=1, ?,? = ) , ?) Simulator: garbles inputs ( u=(flag=0,? = ,?), ?) ?,? (u=(flag,?,?),?)
1-time Garbled RAM Definition with persistent data View can be simulated given ?1,?2, GData ?,? ? O(|D|) GProg ?,?,? ?? O(run-time) GInput(??, ?,?) ?? Client secret: k Server Eval l ?( ??, ??) ?? O(run-time)
Reusable Garbled RAM Definition with persistent data View can be simulated given ?1,?2, GData ?,? ? GProg ?,? ? GInput(??, ?,?) ?? Client secret: k Server Eval l ?( ?, ??) ??
? Use 1-time G-RAM to garble data: ? GData1(D,k) ????, ???? ????, ???? Crucial difference: Before: fresh key k each time. Now: same key k, index ?. ?[?+] { GProg1(?+, ?, ?) ???? GInput1(?, ?,?) ???? ?, } Inputs aren t independent! Cannot rely on dis. ind security of reusable garbled circuits. ?,? (u=(flag,?,?),?,?)
Correlated Distributional Indistinguishability Circuit ? and correlated input distributions w1, wn ?, ?1 If [? ?1, ,?(??)] [? ?1 Then ?, ?1, ?2, , ?? ?, ? 1, ? 2, , ? ? , ,?? ? : , ,?(?? )] Follows from strong differing-inputs obf. (heuristic). Can garble circuits with huge output, small garbled input.
Theorem: Get reusable garbled RAM where: Garble, evaluate program: O(RAM run-time P). Garble input = O( input + output size). assuming ind. obfuscation + stat. sound NIZK. Theorem: Get reusable garbled RAM with persistent memory where: garble data = O( data size) garble program = O( description size P ) garble input = O( input + output size) evaluate = O( RAM run-time P) assuming strong differing-inputs obfuscation (heuristic).
Outsourcing via Reusable G-RAM ? ? ?? Server Client ??= ?(??) Client garbles program ? ? Pre-processing = ?( run-time ?) [ data ? ? ]. Client repeatedly garbles inputs ?? ?? . Server evaluates ? on ?? to get ??. Evaluation time = ?( run-time ?) [ using ? ]
Outsourcing via Reusable G-RAM ? ? ?? ?? Server Client ??= ?(??) Client learns ??. Server sends it back (+1 round = optimal). Output privacy: set ?? = encryption of real output. Server sends back ??. Verifiability: ?? includes (one-time) MAC of real output.
Thank You! Don t turn me into a circuit!
