Secure Computation Techniques in RAM Models with Efficient Automation
Automating Efficient RAM-
Model Secure Computation
Chang Liu
, Yan Huang, Elaine Shi, Jonathan Katz, Michael Hicks
University of Maryland, College Park
Secure Computation
My age is 16
I do not want
Bob to know
My age is 12
I do not want
Alice to know
Who is the oldest?
S
e
c
u
r
e
C
o
m
p
u
t
a
t
i
o
n
T
r
a
d
i
t
i
o
n
a
l
s
o
l
u
t
i
o
n
s
u
s
e
c
i
r
c
u
i
t
a
b
s
t
r
a
c
t
i
o
n
>=16?
12
No, I am older
than Bob
OT
[Yao, 1982] Garbled Circuit
[Yao, 1982] Garbled Circuit
Binary Search Example
int bs(
alice
int* a,
bob
int key,
public
int n) {int left=0, right=n;
while(n>0) {int mid = (left+right)/2;
if(a[mid]<key)
left = mid + 1;
else
right = mid;
n = (n+1)/2;
}
return left;
}
How to
translate to
circuit?
Binary Search Example
int bs(
alice
int* a,
bob
int key,
public
int n) {int left=0, right=n;
while(n>0) {int mid = (left+right)/2;
if(
a[mid]
<key)
left = mid + 1;
else
right = mid;
n = (n+1)/2;
}
return left;
}
RAM-to-circuit compiler incurs
O(N)
cost
for each
dynamic memory access
!
Question: can we securely
compute this in sub-linear time?
Binary Search Example
int bs(
alice
int* a,
bob
int key,
public
int n) {int left=0, right=n;
while(n>0) {int mid = (left+right)/2;
if(
a[mid]
<key)
left = mid + 1;
else
right = mid;
n = (n+1)/2;
}
return left;
}
RAM-to-circuit compiler incurs
O(N)
cost
for each
dynamic memory access
!
Yes!
Using
Oblivious RAM
Oblivious RAM
•
Hide access patterns
•
Poly-logarithmic
cost
per access
ORAM
Scheme
Read
M[
i
]
Implemented as
secure computation
ORAM
Scheme
[Goldreich and Ostrovsky, 1996] Hierarchical ORAM
[Goldreich and Ostrovsky, 1996] Hierarchical ORAM
[Shi et al., 2011] Binary tree-based ORAM
[Shi et al., 2011] Binary tree-based ORAM
R
A
M
-
m
o
d
e
l
S
e
c
u
r
e
C
o
m
p
u
t
a
t
i
o
n
B
i
n
a
r
y
S
e
a
r
c
h
E
x
a
m
p
l
e
int bs(
alice
int* a,
bob
int key,
public
int n) {int left=0, right=n;
while(n>0) {int mid = (left+right)/2;
if(a[mid]<key)
left = mid + 1;
else
right = mid;
n = (n+1)/2;
}
return left;
}
ORAM
initialization of
a
ORAM
initialization of
a
R
A
M
-
m
o
d
e
l
S
e
c
u
r
e
C
o
m
p
u
t
a
t
i
o
n
B
i
n
a
r
y
S
e
a
r
c
h
E
x
a
m
p
l
e
int bs(
alice
int* a,
bob
int key,
public
int n) {int
left=0, right=n
;
while(n>0) {int mid = (left+right)/2;
if(a[mid]<key)
left = mid + 1;
else
right = mid;
n = (n+1)/2;
}
return left;
}
left=0
right=n
left=0
right=n
R
A
M
-
m
o
d
e
l
S
e
c
u
r
e
C
o
m
p
u
t
a
t
i
o
n
B
i
n
a
r
y
S
e
a
r
c
h
E
x
a
m
p
l
e
int bs(
alice
int* a,
bob
int key,
public
int n) {int left=0, right=n;
while(n>0) {int
mid = (left+right)/2
;
if(a[mid]<key)
left = mid + 1;
else
right = mid;
n = (n+1)/2;
}
return left;
}
Securely compute
mid=(left+right)/2
Securely compute
mid=(left+right)/2
R
A
M
-
m
o
d
e
l
S
e
c
u
r
e
C
o
m
p
u
t
a
t
i
o
n
B
i
n
a
r
y
S
e
a
r
c
h
E
x
a
m
p
l
e
int bs(
alice
int* a,
bob
int key,
public
int n) {int left=0, right=n;
while(n>0) {int mid = (left+right)/2;
if(
a[mid]
<key)
left = mid + 1;
else
right = mid;
n = (n+1)/2;
}
return left;
}
ORAM access
a[mid]
ORAM access
a[mid]
R
A
M
-
m
o
d
e
l
S
e
c
u
r
e
C
o
m
p
u
t
a
t
i
o
n
B
i
n
a
r
y
S
e
a
r
c
h
E
x
a
m
p
l
e
int bs(
alice
int* a,
bob
int key,
public
int n) {int left=0, right=n;
while(n>0) {int mid = (left+right)/2;
if(
a[mid]<key
)
left = mid + 1;
else
right = mid;
n = (n+1)/2;
}
return left;
}
Compare
a[mid]<key
Compare
a[mid]<key
RAM-Model Secure Computation: 2 scenarios
Run-once tasks
(e.g. Dijkstra
Algorithm)
Repeated
Sublinear-time
queries
[Gordon et al., 2012]
A
u
t
o
m
a
t
i
n
g
R
A
M
-
m
o
d
e
l
S
e
c
u
r
e
C
o
m
p
u
t
a
t
i
o
n
SCVM
Intermediate
Representation
Program
in source
language
Secure
computation
protocol
Programmer
Crypto Non-Expert
Type Checker
A
u
t
o
m
a
t
i
n
g
R
A
M
-
m
o
d
e
l
S
e
c
u
r
e
C
o
m
p
u
t
a
t
i
o
n
SCVM
Intermediate
Representation
Program
in source
language
Secure
computation
protocol
Programmer
Type Checker
A
u
t
o
m
a
t
i
n
g
R
A
M
-
m
o
d
e
l
S
e
c
u
r
e
C
o
m
p
u
t
a
t
i
o
n
SCVM
Intermediate
Representation
Program
in source
language
Secure
computation
protocol
Programmer
Type Checker
Toward generating efficient protocol
Instruction-trace
obliviousness
Memory-trace
obliviousness
Mixed-mode execution
Toward generating efficient protocol
Instruction-trace
obliviousness
Program counter leaks information
•
The instructions being executed leak information
if(a[mid] <key)
l = mid + 1;
else
r = mid;
Program counter leaks information
•
The instructions being executed leak information
if(
a[mid] <key
)
l = mid + 1;
else
r = mid;
Program counter leaks information
•
The instructions being executed leak information
if(
a[mid] <key
)
l = mid + 1;
else
r = mid;
Program counter leaks information
•
The instructions being executed leak information
if(a[mid] <key)
l = mid + 1;
else
r = mid;
Universal Circuit
Instruction
E
x
e
c
u
t
e
A
L
L
i
n
s
t
r
u
c
t
i
o
n
s
!
INEFFICIENT!
new pc
value
Instruction-trace obliviousness
if(a[mid] <key)
l = mid + 1;
else
r = mid;
t1=a[mid];
t1=a[mid];
cmp = t1<key;
cmp = t1<key;
t2=mid+1;
t2=mid+1;
l=
l=
mux
mux
(cmp, t2, l);
(cmp, t2, l);
r=
r=
mux
mux
(cmp, r, mid);
(cmp, r, mid);
Instruction-trace
oblivious programs,
e.g. straight-line
programs, can avoid
the universal circuit
Toward generating efficient protocol
Instruction-trace
obliviousness
Memory-trace
obliviousness
Memory Trace Obliviousness
int count(public int n, alice int*
data
, bob int T) {int
count
= 0;
for(int i=0; i<n; ++i) {if(
data
[
i
]==T)
count
=
count+1
;
}
}
data
need
not
be
stored in an
ORAM
RAM
Linear scan
Memory Trace Obliviousness: SCVM Typing
int count(
public
int n,
alice
int* data,
bob
int T) {int count = 0;
for(int i=0; i<n; ++i) {if(data[i]==T)
count = count+1;
}
}
int count(
P
int n,
A
int* data,
B
int T) {O
int count = 0;
for(
P
int i=0; i<n; ++i) {if(data[i]==T)
count = count+1;
}
}
Security Lattice and Type System
P
A
B
O
Source Program:
if(data[i]==T)
count = count+1;
Security Lattice and Type System
P
A
B
O
Source Program:
if(
data
[
i
]==T)
count = count+1;
Toward generating efficient protocol
Instruction-trace
obliviousness
Memory-trace
obliviousness
Mixed-mode execution
Mix-mode Execution
When code can be computed locally or publicly, a secure
computation protocol is not necessary
E.g. sorting the array before performing binary search.
Formal results
Evaluated Programs
Implementation
•
Compiler
•
Implemented in Java
•
A type checker that checks the output of the compiler
•
Backend
•
Garbled Circuit Simulator
•
ORAM
•
Binary tree-based ORAM from [Shi et al., 2011]
P
e
r
f
o
r
m
a
n
c
e
R
e
s
u
l
t
s
Dijkstra’s
Shortest Distance
Performance
Results
More results can be found
in the paper
Conclusion and Future Work
•
The first automated approach for RAM-model secure computation
•
Intermediate Language SCVM for generating efficient secure
computation protocol
•
Evaluation shows a speedup of 1-2 orders of magnitude
•
Future work
•
Multiparty
•
Malicious model
Thank you!
Explore the automation of efficient RAM-model secure computation techniques, including examples such as secure binary search. Discover how traditional solutions using circuit abstractions can be improved for sub-linear time computation through methods like Oblivious RAM. Learn about techniques such as ORAM, garbled circuits, and hierarchical ORAM for secure data access and computation.
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
Automating Efficient RAM- Model Secure Computation Chang Liu, Yan Huang, Elaine Shi, Jonathan Katz, Michael Hicks University of Maryland, College Park
Secure Computation My age is 16 I do not want Bob to know My age is 12 I do not want Alice to know Who is the oldest?
Secure Computation Traditional solutions use circuit circuit abstraction >=16? 12 OT No, I am older than Bob [Yao, 1982] Garbled Circuit
Binary Search Example How to translate to circuit? int bs( alice int* a, bob int key, public int n) { int left=0, right=n; while(n>0) { int mid = (left+right)/2; if(a[mid]<key) else n = (n+1)/2; } return left; } left = mid + 1; right = mid;
Binary Search Example RAM-to-circuit compiler incurs O(N) cost for each dynamic memory access! int bs( alice int* a, bob int key, public int n) { int left=0, right=n; while(n>0) { int mid = (left+right)/2; if(a[mid]<key) else n = (n+1)/2; } return left; } left = mid + 1; right = mid; Question: can we securely compute this in sub-linear time?
Binary Search Example RAM-to-circuit compiler incurs O(N) cost for each dynamic memory access! int bs( alice int* a, bob int key, public int n) { int left=0, right=n; while(n>0) { int mid = (left+right)/2; if(a[mid]<key) else n = (n+1)/2; } return left; } left = mid + 1; right = mid; Yes! Using Oblivious RAM
Oblivious RAM ?(????log?) Hide access patterns Poly-logarithmic cost per access ? [?] Read M[i] Scheme Scheme ORAM ORAM [?[?]] Implemented as secure computation [Goldreich and Ostrovsky, 1996] Hierarchical ORAM [Shi et al., 2011] Binary tree-based ORAM
RAM RAM- -model model Secure Computation Binary Search Example int bs(alice int* a, bob int key, public int n) { int left=0, right=n; while(n>0) { int mid = (left+right)/2; if(a[mid]<key) else n = (n+1)/2; } return left; } ORAM ORAM initialization of a initialization of a left = mid + 1; right = mid;
RAM RAM- -model model Secure Computation Binary Search Example int bs(alice int* a, bob int key, public int n) { int left=0, right=n; while(n>0) { int mid = (left+right)/2; if(a[mid]<key) else n = (n+1)/2; } return left; } left=0 right=n left=0 right=n left = mid + 1; right = mid;
RAM RAM- -model model Secure Computation Binary Search Example int bs(alice int* a, bob int key, public int n) { int left=0, right=n; while(n>0) { int mid = (left+right)/2; if(a[mid]<key) else n = (n+1)/2; } return left; } Securely compute mid=(left+right)/2 Securely compute mid=(left+right)/2 left = mid + 1; right = mid;
RAM RAM- -model model Secure Computation Binary Search Example int bs(alice int* a, bob int key, public int n) { int left=0, right=n; while(n>0) { int mid = (left+right)/2; if(a[mid]<key) else n = (n+1)/2; } return left; } ORAM access a[mid] ORAM access a[mid] left = mid + 1; right = mid;
RAM RAM- -model model Secure Computation Binary Search Example int bs(alice int* a, bob int key, public int n) { int left=0, right=n; while(n>0) { int mid = (left+right)/2; if(a[mid]<key) else n = (n+1)/2; } return left; } Compare a[mid]<key Compare a[mid]<key left = mid + 1; right = mid;
RAM-Model Secure Computation: 2 scenarios Repeated Sublinear-time queries [Gordon et al., 2012] Run-once tasks (e.g. Dijkstra Algorithm)
Automating Automating RAM-model Secure Computation Programmer Crypto Non-Expert Usability Secure computation protocol Type Checker Formal Security Program in source language Efficiency SCVM Intermediate Representation Front-end compiler Back-end compiler
Automating Automating RAM-model Secure Computation Programmer Usability Secure computation protocol Type Checker Formal Security Program in source language Efficiency SCVM Intermediate Representation Front-end compiler Back-end compiler
Automating Automating RAM-model Secure Computation Programmer Usability Secure computation protocol Type Checker Formal Security Program in source language Efficiency SCVM Intermediate Representation Front-end compiler Back-end compiler
Toward generating efficient protocol Instruction-trace obliviousness Memory-trace obliviousness Mixed-mode execution
Toward generating efficient protocol Instruction-trace obliviousness
Program counter leaks information The instructions being executed leak information if(a[mid] <key) l = mid + 1; else r = mid;
Program counter leaks information The instructions being executed leak information if(a[mid] <key) l = mid + 1; else r = mid;
Program counter leaks information The instructions being executed leak information if(a[mid] <key) l = mid + 1; else r = mid;
Program counter leaks information The instructions being executed leak information Universal Circuit Execute ALL instructions! if(a[mid] <key) l = mid + 1; else r = mid; new pc value Instruction INEFFICIENT!
Instruction-trace obliviousness if(a[mid] <key) l = mid + 1; else r = mid; t1=a[mid]; cmp = t1<key; t2=mid+1; l=mux(cmp, t2, l); r=mux(cmp, r, mid); Instruction-trace oblivious programs, e.g. straight-line programs, can avoid the universal circuit
Toward generating efficient protocol Instruction-trace obliviousness Memory-trace obliviousness
Memory Trace Obliviousness int count(public int n, alice int* data, bob int T) { int count = 0; for(int i=0; i<n; ++i) { if(data[i]==T) count = count+1; } } data need not be stored in an ORAM RAM Linear scan
Memory Trace Obliviousness: SCVM Typing int count(public int n, alice int* data, bob int T) { int count = 0; for(int i=0; i<n; ++i) { if(data[i]==T) count = count+1; } } int count(P int n, A int* data, B int T) { O int count = 0; for(P int i=0; i<n; ++i) { if(data[i]==T) count = count+1; } }
Security Lattice and Type System Source Program: if(data[i]==T) count = count+1; O A B P
Security Lattice and Type System Source Program: if(data[i]==T) count = count+1; Typing Constraints (part): Implicit flow ?? ????? ? ? O A B P
Toward generating efficient protocol Instruction-trace obliviousness Memory-trace obliviousness Mixed-mode execution
Mix-mode Execution When code can be computed locally or publicly, a secure computation protocol is not necessary E.g. sorting the array before performing binary search.
Formal results Typed programs are progressive Typed programs are -simulatable -simulatable programs hybrid protocol secure w.r.t. [Canetti, 2000]
Evaluated Programs Run-once tasks Repeated query KMP string matching algorithm Dijkstra s shortest distance algorithm Inverse Permutation Aggregation over sliding windows Binary Search Heap Data Structure
Implementation Compiler Implemented in Java A type checker that checks the output of the compiler Backend Garbled Circuit Simulator ORAM Binary tree-based ORAM from [Shi et al., 2011]
Performance Performance Results Results Dijkstra s Shortest Distance
Performance Results More results can be found in the paper
Conclusion and Future Work The first automated approach for RAM-model secure computation Intermediate Language SCVM for generating efficient secure computation protocol Evaluation shows a speedup of 1-2 orders of magnitude Future work Multiparty Malicious model
