1 of 61

Oblivious RAM Constructions and Applications

Kate Highnam, Samee Zahur, Matthew Irvine

2 of 61

Server

Client

3 of 61

Server

Client

4 of 61

Server

Client

I don’t trust him….

5 of 61

Client

Server

80% of search string

6 of 61

ORAM

Server

Client

7 of 61

Goal of ORAM

In this situation, the server is unable to determine the difference between any given sequence of requests from the protocol and some random sequence of requests.

Server

?

8 of 61

Naive Approach

1. Grab each block

2. Edit (if need to)

3. Fresh re-encrypt

4. Push back

Server

Client

9 of 61

Here’s the Plan...

Types of ORAM:

Path ORAM
Onion ORAM

Application of ORAM

3. Garbled RAM

10 of 61

Path ORAM: An Extremely Simple Oblivious RAM Protocol

Emil Stefanov , Marten van Dijk , Elaine Shi , T-H. Hubert Chan, Christopher Fletcher , Ling Ren , Xiangyao Yu , Srinivas Devadas

11 of 61

Notations

Stash

&

Position Map

Binary Tree with Buckets

(See next slide)

Client

Server

Block = B bits

N blocks

12 of 61

TREE!

L levels

Z blocks

P(x)

x

dummy data

Server Side

dummy data

……..

N leaves

0 | block data

2 | block data

1 | block data

9 | block data

3 | block data

13 of 61

Stash and Position Map

0 1 2 3 4 5 6 7 8 9 10 ……………...

0 3 1 2 … ... … … … … … … … ...

Stash (usually empty after access)

Position Map

Index representing Path where block lies

Array Index = Address of block

Client Side

14 of 61

Let’s get started…….

Server

Client

15 of 61

Big Picture

Server

Client

Read block…

Write block...

Path ORAM

Protocol

16 of 61

Path ORAM Protocol (1/4)

1. Store current position of block a, remap block to new random position

0 1 2 3 4 5 ……………………………………………..

0 3 1 2 ... ... … … … … … … … ...

x = 1

0

17 of 61

Path ORAM Protocol (2/4)

2. Read all blocks along P(x) into client’s stash (decrypting along the way)

Server

6442875487 83978 74395 74387 59792 35849

Stash (usually empty after access)

Client

18 of 61

ORAM Protocol Overview (3/4)

3. If the original instruction was to write in a block, do so in the data stored within the client’s stash.

64428 75487 83978 74395 74387 59792 35849

Stash (usually empty after access)

Client

12345

19 of 61

ORAM Protocol Overview (4/4)

4. Write the blocks from the path back into the tree in the server while shifting blocks between buckets.

Server

64428 75487 83978 74395 12345 59792 35849

Stash (usually empty after access)

Client

20 of 61

1

3 | block data

1 | block data

0 | block data

2 | block data

0

2

3

dummy data

21 of 61

1

3 | block data

1 | block data

0 | block data

2 | block data

0

2

3

22 of 61

Problems…...

Large amounts of client memory
Possibility of bucket overflow

Client

23 of 61

Recursive Option

Remember: Client has limited memory…..

Client

?

24 of 61

Recursive Option

Remember: Client has limited memory…..

FIX: store position map on server encrypted with smaller recursive ORAM protocol.

Client

25 of 61

Bucket Overflow

What happens if all nodes go to the root or leaves?

Client

?

26 of 61

Bucket Overflow

What happens if all nodes go to the root or leaves?

FIX: Eviction process and overflow into the Stash in the Client

27 of 61

Onion ORAM: A Constant Bandwidth and Constant Client Storage ORAM (without FHE or SWHE)

Srinivas Devadas, Marten van Dijk, Christopher W. Fletcher, Ling Ren, Elaine Shi, Daniel Wichs

28 of 61

Server-side Selection

Previous Approach

Client fetches multiple blocks from server, then selects the one needed.

OnionORAM

Let the server select the one client wants, without requiring client to reveal its choice. Use homomorphic selection.

29 of 61

Comparison with Notable Prior Work

30 of 61

Selection with Additive HE

A

B

C

D

Server-side

Client-side

Enc(0)

Enc(1)

Enc(0)

A Enc(0) + B Enc(0) + C Enc(1) + D Enc(0)

Enc(C)

Doesn’t quite work:

We are still transferring the same amount of data
Multiplication only works with unencrypted blocks

31 of 61

Reducing Data Transfer : Chunks

E(0)

A_i E(0) + B_i E(0) + C_i E(1) + D_i E(0)

Server-side

Client-side

E(0)

E(1)

E(0)

chunk

block

Doesn’t quite work:

We are still transferring the same amount of data
Multiplication only works with unencrypted blocks

32 of 61

Selecting Blocks

A_x

Selecting A_x

Using notation 𝛿_xi = 1 if x = i, 𝛿_xi = 0 if x ≠ i

∑_iA_iE(𝛿_xi) = E(∑_iA_i𝛿_xi) = E(A_x)

∑_iE(A_i)E(𝛿_xi) = E(∑_iE(A_i)𝛿_xi) = E(E(A_x)) = E²(A_x)

∑_iE^l(A_i)E(𝛿_xi) = E(∑_iE^l(A_i)𝛿_xi) = E(E^l(A_x)) = E^l⁺¹(A_x)

33 of 61

Layers during ORAM Ops

3 block data

0 block data

1 block data

2 block data

34 of 61

Layers during ORAM Ops

3 block data

0 block data

1 block data

2 block data

35 of 61

Layers during ORAM Ops

3 block data

0 block data

⊥ block data

2 block data

1 block data

36 of 61

Layers during ORAM Eviction

3 block data

0 block data

⊥ block data

2 block data

1 block data

37 of 61

ORAM in Θ(1) Bandwidth

B bandwidth overhead per access.

Server performs select(). Enough for

Read/write access
Eviction

38 of 61

How to Garble RAM Programs: Secure Multi-Party Computation with ORAM

Steve Lu and Rafail Ostrovsky

39 of 61

Secure Two-Party Computation

Two parties Alice and Bob

Program 𝜋

Private inputs I_A and I_B

Output Z

Alice

𝜋

Bob

?

Z

I_A

I_B

40 of 61

ORAM and Two-Party Computation

Client

Server

ORAM

Secure Two-Party Computation

Alice

𝜋

Bob

?

Z

I_A

I_B

41 of 61

Secure Two-Party Computation

Usual approach: Yao’s Garbled Circuits

Problem: Conversion from program to circuit

RAM Program (Runtime) O(T)	Circuit (Size) - From RAM O(T³ log T)

Cost of conversion from RAM program to Circuit via Turing Machine

42 of 61

Overview of Garbled RAM

Goal: Secure Two-Party Computation with lower overhead

Restriction: No conversion to circuit, no interactivity

How? ORAM and

Garbled Circuits

Runtime of interactive Garbled RAM scheme

(Gordon, et al. 2012)

43 of 61

A Brief Introduction to Garbled Circuits

Building Block of Garbled RAM

44 of 61

Step 1: Convert program to circuit

Inputs come from the parties

45 of 61

Step 2: Randomly relabel the wires

Name	Original	New Value
W_X⁰	0	be8961fe
W_X¹	1	e9d99c9a

X

Y

Z

46 of 61

Step 3: Modify gates to match new labels

X

Y

Z

Input X	Input Y	Output
W_X⁰	W_Y⁰	W_Z⁰
W_X⁰	W_Y¹	W_Z¹
W_X¹	W_Y⁰	W_Z¹
W_X¹	W_Y¹	W_Z¹

47 of 61

Problem...

Computing output labels without revealing inputs

Input	Input	Output	Garbled Output
W_X⁰	W_Y⁰	W_Z⁰	E_Wx0(E_Wy0(W_Z⁰)
W_X⁰	W_Y¹	W_Z¹	E_Wx0(E_Wy1(W_Z¹)
W_X¹	W_Y⁰	W_Z¹	E_Wx1(E_Wy0(W_Z¹)
W_X¹	W_Y¹	W_Z¹	E_Wx1(E_Wy1(W_Z¹)

Z

X

Y

48 of 61

Yao’s Garbled Circuits Overview

Two Parties: Gen and Eval

Gen

Eval

𝛤, X

𝛤 ← G(C)

X ← GI(x)

z

Y ← GI(y)

z ← GE(𝛤, X, Y)

1/3

49 of 61

Yao’s Garbled Circuits Overview

Two Parties: Gen and Eval

Three algorithms: G, GI, GE

G garbles circuit
GI garbles input
GE evaluates garbled circuit

Gen

Eval

𝛤, X

𝛤 ← G(C)

X ← GI(x)

z

Y ← GI(y)

z ← GE(𝛤, X, Y)

2/3

50 of 61

Yao’s Garbled Circuits Overview

Two Parties: Gen and Eval

Three algorithms: G, GI, GE

G garbles circuit
GI garbles input
GE evaluates garbled circuit

Output: z

For correctness, z = C(x, y)

Gen

Eval

𝛤, X

𝛤 ← G(C)

X ← GI(x)

z

Y ← GI(y)

z ← GE(𝛤, X, Y)

3/3

51 of 61

Garbled Circuits and Garbled RAM

How do we construct these algorithms for Garbled RAM?

Garbled Circuits	Garbled RAM
Algorithms: (G, GI, GE)	Algorithms: (G, GI, GE)
G(C) → 𝛤	G(𝜋_t) → garbled program 𝛱_t
GI(x) → garbled input X	GI(x) → garbled input X
GE(𝛤, X) evaluates circuit 𝛤 on input X	GE(𝛱_t, X) evaluates 𝛱_t on X
Correctness: C(x) = GE(G(C), GI(x))	Correctness: 𝜋_t(x) = GE(G(𝜋_t), GI(x))

52 of 61

Algorithm for G (Program Garbling)

Main Idea: Create a virtual machine with corresponding CPU and ORAM client

1/2

53 of 61

Algorithm for G (Program Garbling)

Main Idea: Create a virtual machine with corresponding CPU and ORAM client

For each time step i = 1 … t:

Create GC(C_ORAM)
Create GC(C_CPU)

C_ORAM

C_CPU

C_ORAM

C_CPU

0

1

t

...

Time

2/2

54 of 61

Previous Garbled ORAM Schemes

Problem: Communication between ORAM client and server requires interactivity

Solution: Evaluating party acts as ORAM server

C_ORAM

C_CPU

C_ORAM

C_CPU

0

1

t

...

Time

ORAM Server

55 of 61

Constructing C_ORAM

Input: Read/write query V

Output: Garbled circuit GC_ORAM

GC_ORAM executes ORAM query

C_ORAM

C_CPU

GC_ORAM

X

V

56 of 61

Constructing C_CPU

Inputs: (𝛴, X) the CPU state and last memory contents read

Outputs: New state 𝛴’, next read/write query V’

C_CPU

X

𝛴

𝛴’

V’

57 of 61

Algorithms for GI and GE

GI: Map inputs to proper encodings

GE: For each time step i = 1 … t:

Evaluate GC(C_ORAM) to get GC_ORAM
Execute GC_ORAM to obtain garbled output X_i
Evaluate GC(C_CPU)

GI

x

GE

X

C(x)

𝛱

C_ORAM

C_CPU

X

58 of 61

ORAM and Garbled RAM

Client

Server

ORAM

Garbled RAM

Gen

Eval

𝛱, X

𝛱 ← G(𝜋)

X ← GI(x)

z

Y ← GI(y)

z ← GE(𝛱, X, Y)

59 of 61

Garbled Circuits and Garbled RAM

Garbled RAM

Gen

Eval

𝛱, X

𝛱 ← G(𝜋)

X ← GI(x)

z

Y ← GI(y)

z ← GE(𝛱, X, Y)

Gen

Eval

𝛤, X

𝛤 ← G(C)

X ← GI(x)

z

Y ← GI(y)

z ← GE(𝛤, X, Y)

Garbled Circuits

60 of 61

Results

Mirrors Yao’s garbled circuits

Runs in O(t ∙ polylog(t))

No need for interactivity

Secure 2-party computation through ORAM

S. Lu and R. Ostrovsky. How to Garble RAM Programs. Cryptology ePrint Archive, Report 2012/601 (2012)

z

Gen

𝛱, X

Eval

61 of 61

The End