University:
Boston University
Course:
MET CS 201 | Introduction to Programming
Academic year:

2021
Views:

81

Pages:

26
Author:

Orvonin2y6

Onion ORAM: Constant Bandwidth ORAM with Server Computation Current art and where to go next • State of the art schemes – Bandwidth: O(log N) – Client storage: O(1) ( Path ORAM = O(log N) ) – Server storage: O(N) • Is “optimal” ORAM possible? O(1) bandwidth, O(1) client storage, O(N) server storage • Goldreich-Ostrovsky lower bound [1987, 1996] Given a program that runs in T time and an N block ORAM with O(1) client storage, the program+ORAM must run in Ω(T log N) time • 𝛀(T log N) doesn’t mean 𝛀(T log N) bandwidth! 2 ORAM with Server Computation • Example: Outsourced storage (Honest but curious) Server Client Trust boundary Arbitrary messages (insecure) (insecure) (insecure) Processor Processor Processor Storage (ORAM tree) limited storage, compute • “Read X, Y, Z, return F(X, Y, Z)” • Message stream must be oblivious 3 Server comp. in previous ORAMs • XORing reads [Dautrich et al.], PIR+ORAM [Mayberry et al.] • XOR + Ring ORAM – Permuted buckets à one real block touched / read – B, d1, d2, d3, … – E(B, r), E(0, r1), E(0, r2), E(0, r3) … – Server sends: E(B, r) ⊕ E(0, r1) ⊕ E(0, r2) ⊕ E(0, r3) ⊕ … – Client computes: E(0, r1) ⊕ E(0, r2) ⊕ E(0, r3) ⊕ … • Both schemes make read bandwidth O(log N) ! O(1) • Does not help on evictions! 4 Can we make evictions O(1) Bandwidth? FHE + ORAM • Example: Ring ORAM – ORAM on server is encrypted under FHE scheme EFHE – Reads Client Server leaf, EFHE(address) EFHE(d) = Select(EFHE(address), Path(leaf)) RemoveBlock(EFHE(address), Path(leaf)) EFHE(d) – Evictions Path(leafg)’ = EvictPath(Path(leafg)) Read bandwidth is O(1), no bandwidth for evictions! Eviction circuit for FHE Path(leafg)’ = EvictPath(Path(leafg)) mA = metadata for block A mA 𝜋i = A B mB MoveBlock(mA … mF) Block C can get stuck Select(𝜋C, mA, mB, mC) à mC C ß Select(𝜋C, A, B, C) Select(𝜋D, mA, mB, mD) à mD D ß Select(𝜋D, A, B, D) mE E ß Select(𝜋E, A, B, C, D, E) mF F ß Select(𝜋F, A, B, C, D, F) • Only Select() touches blocks • Server computation: polylog(N) • Bootstrap to manage noise [Apon et al., Mayberry et al.] 7 *Discuss later: Does the previous scheme achieve optimal Bandwidth/storage? Do we need bootstrapping? Do we need FHE? Do we need FHE? • Additive-HE (e.g., Paillier) – Addition: EAHE(a) ⊕ EAHE(b) = EAHE(a + b) – Scalar multiplication: EAHE(a) ⊗ c = EAHE(ca) • Select from (X, Y): EAHE(0)⊗X ⊕ EAHE(1)⊗Y = EAHE(0+Y) = EAHE(Y) • Y = EAHE(plaintext) • Select op ! EAHE(EAHE(plaintext)) Block gets extra layer of encryption – Client decrypts twice – (Possible) ciphertext blowup per layer • Layers(output) = max( Layers(Blocki) : Blocks ) + 1 9 ORAM Read + Additive-HE • ORAM encrypted using 1 layer of EAHE (abbreviated E) Client leaf E(metadata for Path(leaf)) Server Decrypt metadata Compute 𝜋= E(0), E(0), … E(1), … E(0) 𝜋, E(updated metadata for Path(leaf)) Block i Write updated metadata ⊗ ⊗ ⊗ ⊗ ⊗ ↓𝑖 ↓𝑖 𝜋↓𝑖 𝜋 𝜋↓𝑖 𝜋↓𝑖 𝜋 Compute E(E(d)) = Select(𝜋, Path(leaf)) E(E(d)) Decrypt d = E(E(d)) Update d à d’ E(d’) Path(leaf)[root].append(E(d’)) ORAM Evict + Additive-HE • Problem: Continuous reshuffling ! Unbounded layers • Reason: Blocks can get stuck in buckets after evictions Layers(output) = max( Layers(Blocki) : Blocks ) + 1 A1 = Block A with 1 layer A1 B1 C2435 ß Select(𝜋C, B1, A1, C2431) t… lec e s t x Ne O(T) evictions ! Slot with C gets O(T) layers ORAM with O(1) bandwidth, O(1) client storage, O(N) server storage …with only additive-HE Onion ORAM Design our ORAM eviction algorithm such that buckets are guaranteed to be empty regularly A B C ß Select(𝜋C, B, A, C) 13 Onion ORAM Design our ORAM eviction algorithm such that buckets are guaranteed to be empty regularly 1. Evict over reverse-lexicographic order of paths 2. Also evict to sibling buckets 3. Set Z, A s.t. Pr[bucket overflow] = negl(security parameter) 4. Evict to 1 bucket triplet at a time Empty! Example: evict to leaf 6 Informal guarantee: Max layers = 𝑶(𝐥𝐨𝐠 𝑵) 1 2 3 4 5 6 7 0 Which A, Z work? Theorem: 𝒁≥𝑨, 𝑵≤𝑨 ∗𝟐↑𝑳−𝟏 ! Pr[bucket overflow] = 𝒆↑−(𝟐𝒁−𝑨)↑𝟐 /𝟔𝑨 • 𝒁=𝑨= 𝜽(𝐥𝐨𝐠 𝑵)𝝎(𝟏) ! Pr[bucket overflow] = 𝑵↑−𝝎(𝟏) 𝑵𝒐𝒕𝒆: 𝑵=𝐩𝐨𝐥𝐲(𝒔𝒆𝒄𝒖𝒓𝒊𝒕𝒚 𝒑𝒂𝒓𝒂𝒎𝒆𝒕𝒆𝒓) • Asymptotics w/o server computation – Bandwidth = 𝑂(log↑2 𝑁)𝜔(1) blocks – Client storage = 𝑂(log 𝑁)𝜔(1) blocks – Server storage = 𝑂(𝑁) blocks • Not competitive w/o server computation 15 Onion ORAM read w/ Additive-HE • Same as previous proposal – Client sends leaf – Server sends metadata – Client sends 𝜋=E(0), E(0), … E(1), … E(0) – Server sends block Assume layers à ciphertext blowup • Simple scheme factoring in layers – Elements of 𝜋 have 1 layer – Pad blocks on path to S = Max( |Blocki| : Blocks ) bits – Split each padded block into C chunks s.t. S / C = Plaintext(𝜋↓𝑖 ) = P Block 1 Block 2 P 16 Eviction Terminology Source Triplet 0 Destination Sibling Path(leaf)[ i ] = Path(leaf)[ i ].dest[ j ] = ith triplet on path jth block in ith triplet’s dest. bucket Layer Analysis • Useful properties: 1. At eviction start: non-leaf sibling buckets are empty 2. At eviction end: non-leaf destination buckets are empty empty empty Leaves: – Blocks get stuck in the leaves – Non-leaves empty at regular intervals 18 Layer Analysis • Analyze: Layers on destination bucket at start of select Key intuition: destination bucket was sibling on last eviction i Prev ou icti v e s on iple r t o t t # Layers? Theorem: buckets at level 𝒌<𝑳 have ≤𝒄 ∗𝒌+𝟏 layers • 𝒄 is constant, 𝒄=𝟏 in our final scheme 19 Onion ORAM evict w/ Additive-HE Client Server leafg (eviction path) known by server E(metadata for Path(leafg)) Compute Π={𝜋↓0 …𝜋↓𝑍∗𝐿 } (|𝜋↓𝑖 |=𝑂(𝑍) encrypted coefficients) Π, E(updated metadata for Path(leafg)) ⊕ For triplet i: ⊕ Path(leafg)[i].sibling = Path(leafg)[i].src For slot j: args = {Path(leafg)[i].dst[j] , Path(leafg)[i].src} Path(leafg)[i].dst[j] = Select(𝜋↓𝑍∗𝑖+𝑗 , args) Eviction Post-Processing Problem: layers in leaves are not bounded • At end of each eviction… Client Server E(dj) = Path(leafg)[L].dst[j] Decrypt E(dj) to a constant number of layers, yielding ej Compute E(ej) E(ej) • Layer theorem now applies to all levels • Adds constant amortized bandwidth if Z ~ A For j = 0 … Z - 1 Setting parameters Which Additive-HE scheme? Problem: each layer can add ciphertext blowup • Layer bound = 𝑶(𝐥𝐨𝐠 𝑵) • Paillier (1999): 𝒏 →𝒏↑𝟐 (n = RSA modulus) • Damgård-Jurik (2001): 𝒏↑𝒔 →𝒏↑𝒔+𝟏 – s = free parameter – Strategy: set 𝑠↓0 =log⁠𝑁 , log⁠𝑁 layers à 𝒏↑s0+log⁠𝑁 = 𝒏↑O(log⁠𝑁) • Operations are like Paillier: 𝐸(𝑎)⊕𝐸(𝑏)=𝐸(𝑎)𝐸(𝑏) 𝐸(𝑎)⊗𝑏=𝐸(𝑎)↑𝑏 • Best attack: factor 𝒏, complexity 𝐞𝐱𝐩(|𝒏|↑𝟏/𝟑 (𝐥𝐨𝐠 | 𝒏|)↑𝟐/𝟑 ) ∴|𝒏|= 𝜽(𝐥𝐨𝐠↑𝟑 𝑵) ! defeat attacks w/ complexity 𝑵↑𝝎(𝟏) Optimization: Hierarchical PIR ⊕ • So far … Select = 𝝅↓𝒊 ⨂𝑩𝒍𝒐𝒄𝒌↓𝒊 𝑖 PIR” “trivial linear – Each select adds 1 layer layer bound=log⁠𝑁 – 𝑍 inputs à |𝜋|=𝑍 ∗layer bound ∗|𝑛|= 𝑙𝑜𝑔↑5 𝑁𝜔(1) A • Hierarchical PIR [Lipmaa 2005] – Multiplexer tree – 𝑍 inputs à |𝜋|=log⁠𝑍 coefficients E(π0) B 2-‐1 sel E(π0) E(π1) C 2-‐1 sel 2-‐1 sel à select adds log⁠𝑍 layers – ∴layer bound↑′ =log⁠𝑁log⁠log⁠𝑁 – 𝑍 inputs à |𝜋|=log⁠𝑍 ∗layer bound↑′ ∗|𝑛| =log↑4 𝑁 log↑2 log⁠𝑁 D At least better in theory Parameterization • Strategy: set |𝚷|= |{𝝅↓𝟎 …𝝅↓𝒁 ∗𝑳 }|=𝑶(𝑩) • I.e., 𝚷 contributes constant (amortized) bandwidth • Let 𝑍=A= log⁠𝑁 𝜔(1) • |𝜋↓𝑟𝑒𝑎𝑑 |=|𝑛| ∗log↑2 𝑁𝜔(1) • |𝜋↓𝑒𝑣𝑖𝑐𝑡 |=|𝑛| ∗log 𝑁 log↑2 log⁠𝑁 (n = RSA modulus) (mux tree) • |𝚷↓𝒆𝒗𝒊𝒄𝒕 |= |𝑛|∗log↑2 𝑁 log↑2 log⁠𝑁 =log↑5 𝑁 log↑2 log⁠𝑁 • Final asymptotics: – Block size B = Ω(log↑5 𝑁 log↑2 log⁠𝑁) – Bandwidth = 𝑂(𝐵) – Client storage = 𝑂(𝐵) – Server storage = 𝑂(𝐵𝑁) Ongoing/Future work • Decrease block size B= Ω(𝑘∗log↑2 𝑁 log↑2 log⁠𝑁 ) – Modern schemes w/o computation: B= O(log↑2 𝑁) • How? – Server computation is O(log↑2 𝑁)𝜔(1) blocks - is O(log 𝑁) possible? – Is there a suitable additive-HE scheme with 𝑘=o(log↑3 𝑁)? • Protect against malicious servers – Server performs select incorrectly • Improve Garbled RAM schemes? – Use ORAM as a blackbox • Parameterization for SWHE for Onion ORAM – No bootstrapping needed 26