Fully Homomorphic Encryption in Information Security
undefined
I
n
f
o
r
m
a
t
i
o
n
S
e
c
u
r
i
t
y
–
T
h
e
o
r
y
v
s
.
R
e
a
l
i
t
y
0
3
6
8
-
4
4
7
4
,
W
i
n
t
e
r
2
0
1
5
-
2
0
1
6
L
e
c
t
u
r
e
1
1
:
F
u
l
l
y
h
o
m
o
m
o
r
p
h
i
c
e
n
c
r
y
p
t
i
o
n
Lecturer:
Eran Tromer
Including presentation material by
Vinod Vaikuntanathan, MIT
undefined
Fully Homomorphic Encryption
Confidentiality of static data: plain encryption
x
1
Confidentiality of data inside computation:
Fully Homomorphic Encryption
v=x+y;
w=f(v);
return w;
Fully Homomorphic Encryption
•
Goal: delegate computation on data without
revealing it
•
A
confidentiality
goal
Example 1: Private search
Delegate
processing
of data
without
revealing
it
►
Y
o
u
:
E
n
c
r
y
p
t
t
h
e
q
u
e
r
y
,
s
e
n
d
t
o
G
o
o
g
l
e
(Google does not know the key,
cannot “see” the query)
►
G
o
o
g
l
e
:
E
n
c
r
y
p
t
e
d
q
u
e
r
y
→
E
n
c
r
y
p
t
e
d
r
e
s
u
l
t
s
(You decrypt and recover the
search results)
Example 2: Private Cloud Computing
Delegate
processing
of data
without
revealing
it
(Input: x)
(Program: P)
(Enc(x), P) → Enc(P(x))
Encrypt x
Fully Homomorphic Encryption
E
n
c
r
y
p
t
e
d
x
,
P
r
o
g
r
a
m
P
→
E
n
c
r
y
p
t
e
d
P
(
x
)
D
e
f
i
n
i
t
i
o
n
:
(
K
e
y
G
e
n
,
E
n
c
,
D
e
c
,
E
v
a
l
)
(as in regular public/private-key encryption)
–
I
f
c
=
E
n
c
(
P
K
,
x
)
a
n
d
c
′
=
E
v
a
l
(
P
K
,
c
,
P
)
,
C
o
m
p
a
c
t
n
e
s
s
:
L
e
n
g
t
h
o
f
c
′
i
n
d
e
p
e
n
d
e
n
t
o
f
s
i
z
e
o
f
P
S
e
c
u
r
i
t
y
:
s
e
m
a
n
t
i
c
s
e
c
u
r
i
t
y
/
i
n
d
i
s
t
i
n
g
u
i
s
h
a
b
i
l
i
t
y
[
G
M
8
2
]
C
o
r
r
e
c
t
n
e
s
s
o
f
E
v
a
l
:
F
o
r
e
v
e
r
y
i
n
p
u
t
x
,
p
r
o
g
r
a
m
P
t
h
e
n
D
e
c
(
S
K
,
c
’
)
=
P
(
x
)
.
History of Fully Homomorphic Encryption
–
F
i
r
s
t
D
e
f
i
n
e
d
:
“
P
r
i
v
a
c
y
h
o
m
o
m
o
r
p
h
i
s
m
”
[
R
i
v
e
s
t
A
d
l
e
m
a
n
D
e
r
t
o
u
z
o
s
7
8
]
m
o
t
i
v
a
t
i
o
n
:
s
e
a
r
c
h
i
n
g
e
n
c
r
y
p
t
e
d
d
a
t
a
•
N
o
n
-
c
o
m
p
a
c
t
h
o
m
o
m
o
r
p
h
i
c
e
n
c
r
y
p
t
i
o
n
:
•
Based on Yao garbled circuits
•
[SYY 99] [MGH 08]: c* grows exp with degree/depth
•
[IP 07] branching programs
Fully Homomorphic Encryption
–
using just integer addition and multiplication
►
Full-semester course
►
Today: an alternative construction
[DGHV 10]
–
easier to understand, implement and improve
Constructing
fully-homomoprhic encryption
assuming
hardness of approximate GCD
A Roadmap
1
.
S
e
c
r
e
t
-
k
e
y
“
S
o
m
e
w
h
a
t
”
H
o
m
o
m
o
r
p
h
i
c
E
n
c
r
y
p
t
i
o
n
(
u
n
d
e
r
t
h
e
a
p
p
r
o
x
i
m
a
t
e
G
C
D
a
s
s
u
m
p
t
i
o
n
)
2
.
P
u
b
l
i
c
-
k
e
y
“
S
o
m
e
w
h
a
t
”
H
o
m
o
m
o
r
p
h
i
c
E
n
c
r
y
p
t
i
o
n
(
u
n
d
e
r
t
h
e
a
p
p
r
o
x
i
m
a
t
e
G
C
D
a
s
s
u
m
p
t
i
o
n
)
3
.
P
u
b
l
i
c
-
k
e
y
F
U
L
L
Y
H
o
m
o
m
o
r
p
h
i
c
E
n
c
r
y
p
t
i
o
n
(
u
n
d
e
r
a
p
p
r
o
x
G
C
D
+
s
p
a
r
s
e
s
u
b
s
e
t
s
u
m
)
(a simple transformation)
(borrows from Gentry’s techniques)
12
Secret-key
Homomorphic Encryption
S
e
c
r
e
t
k
e
y
:
a
l
a
r
g
e
n
2
-
b
i
t
o
d
d
n
u
m
b
e
r
p
T
o
E
n
c
r
y
p
t
a
b
i
t
b
:
–
p
i
c
k
a
r
a
n
d
o
m
“
l
a
r
g
e
”
m
u
l
t
i
p
l
e
o
f
p
,
s
a
y
q
·
p
–
p
i
c
k
a
r
a
n
d
o
m
“
s
m
a
l
l
”
e
v
e
n
n
u
m
b
e
r
2
·
r
–
C
i
p
h
e
r
t
e
x
t
c
=
q
·
p
+
2
·
r
+
b
T
o
D
e
c
r
y
p
t
a
c
i
p
h
e
r
t
e
x
t
c
:
–
c
(
m
o
d
p
)
=
2
·
r
+
b
(
m
o
d
p
)
=
2
·
r
+
b
–
read off the least significant bit
(q ~ n
5
bits)
(r ~ n bits)
“noise”
(sec. param = n)
Secret-key Homomorphic Encryption
How to Add and Multiply Encrypted Bits:
–
Add/Mult two near-multiples of p gives a near-multiple of p.
–
c
1
=
q
1
·
p
+
(
2
·
r
1
+
b
1
)
,
c
2
=
q
2
·
p
+
(
2
·
r
2
+
b
2
)
–
c
1
+
c
2
=
p
·
(
q
1
+
q
2
)
+
2
·
(
r
1
+
r
2
)
+
(
b
1
+
b
2
)
«
p
–
c
1
c
2
=
p
·
(
c
2
·
q
1
+
c
1
·
q
2
-
q
1
·
q
2
)
+
2
·
(
r
1
r
2
+
r
1
b
2
+
r
2
b
1
)
+
b
1
b
2
«
p
P
r
o
b
l
e
m
s
C
i
p
h
e
r
t
e
x
t
g
r
o
w
s
w
i
t
h
e
a
c
h
o
p
e
r
a
t
i
o
n
N
o
i
s
e
g
r
o
w
s
w
i
t
h
e
a
c
h
o
p
e
r
a
t
i
o
n
Useless for many applications (cloud computing,
searching encrypted e-mail)
–
C
o
n
s
i
d
e
r
c
=
q
p
+
2
r
+
b
←
E
n
c
(
b
)
2r+b
–
c (mod p) = r’ ≠ 2r+b
r’
–
lsb(r’) ≠ b
P
r
o
b
l
e
m
s
C
i
p
h
e
r
t
e
x
t
g
r
o
w
s
w
i
t
h
e
a
c
h
o
p
e
r
a
t
i
o
n
N
o
i
s
e
g
r
o
w
s
w
i
t
h
e
a
c
h
o
p
e
r
a
t
i
o
n
Useless for many applications (cloud computing,
searching encrypted e-mail)
Can perform “limited” number of hom. operations
W
h
a
t
w
e
h
a
v
e
:
“
S
o
m
e
w
h
a
t
H
o
m
o
m
o
r
p
h
i
c
”
E
n
c
r
y
p
t
i
o
n
Public-key
Homomorphic Encryption
S
e
c
r
e
t
k
e
y
:
a
n
n
2
-
b
i
t
o
d
d
n
u
m
b
e
r
p
T
o
D
e
c
r
y
p
t
a
c
i
p
h
e
r
t
e
x
t
c
:
–
c
(
m
o
d
p
)
=
2
·
r
+
b
(
m
o
d
p
)
=
2
·
r
+
b
–
read off the least significant bit
Eval (as before)
P
u
b
l
i
c
k
e
y
:
[
q
0
p
+
2
r
0
,
q
1
p
+
2
r
1
,
…
,
q
t
p
+
2
r
t
]
=
(
x
0
,
x
1
,
…
,
x
t
)
–
t+1 encryptions of 0
Δ
–
Wlog, assume that x
0
is the largest of them
c =
+ b (mod x
0
)
Public-key Homomorphic Encryption
S
e
c
r
e
t
k
e
y
:
a
n
n
2
-
b
i
t
o
d
d
n
u
m
b
e
r
p
T
o
D
e
c
r
y
p
t
a
c
i
p
h
e
r
t
e
x
t
c
:
–
c
(
m
o
d
p
)
=
2
·
r
+
b
(
m
o
d
p
)
=
2
·
r
+
b
–
read off the least significant bit
Eval (as before)
P
u
b
l
i
c
k
e
y
:
[
q
0
p
+
2
r
0
,
q
1
p
+
2
r
1
,
…
,
q
t
p
+
2
r
t
]
=
(
x
0
,
x
1
,
…
,
x
t
)
T
o
E
n
c
r
y
p
t
a
b
i
t
b
:
p
i
c
k
r
a
n
d
o
m
s
u
b
s
e
t
S
[
1
…
t
]
Δ
c =
+ b (mod x
0
)
Public-key Homomorphic Encryption
S
e
c
r
e
t
k
e
y
:
a
n
n
2
-
b
i
t
o
d
d
n
u
m
b
e
r
p
P
u
b
l
i
c
k
e
y
:
[
q
0
p
+
2
r
0
,
q
1
p
+
2
r
1
,
…
,
q
t
p
+
2
r
t
]
=
(
x
0
,
x
1
,
…
,
x
t
)
T
o
E
n
c
r
y
p
t
a
b
i
t
b
:
p
i
c
k
r
a
n
d
o
m
s
u
b
s
e
t
S
[
1
…
t
]
Δ
(
m
u
l
t
.
o
f
p
)
+
(
“
s
m
a
l
l
”
e
v
e
n
n
o
i
s
e
)
+
b
c =
+ b (mod x
0
)
Public-key Homomorphic Encryption
S
e
c
r
e
t
k
e
y
:
a
n
n
2
-
b
i
t
o
d
d
n
u
m
b
e
r
p
T
o
D
e
c
r
y
p
t
a
c
i
p
h
e
r
t
e
x
t
c
:
–
c
(
m
o
d
p
)
=
2
·
r
+
b
(
m
o
d
p
)
=
2
·
r
+
b
–
read off the least significant bit
E
v
a
l
:
R
e
d
u
c
e
m
o
d
x
0
a
f
t
e
r
e
a
c
h
o
p
e
r
a
t
i
o
n
T
o
E
n
c
r
y
p
t
a
b
i
t
b
:
p
i
c
k
r
a
n
d
o
m
s
u
b
s
e
t
S
[
1
…
t
]
Ciphertext Size Reduction
P
u
b
l
i
c
k
e
y
:
[
q
0
p
+
2
r
0
,
q
1
p
+
2
r
1
,
…
,
q
t
p
+
2
r
t
]
=
(
x
0
,
x
1
,
…
,
x
t
)
Δ
(*) additional tricks for mult
c =
+ b (mod x
0
)
Public-key Homomorphic Encryption
S
e
c
r
e
t
k
e
y
:
a
n
n
2
-
b
i
t
o
d
d
n
u
m
b
e
r
p
T
o
D
e
c
r
y
p
t
a
c
i
p
h
e
r
t
e
x
t
c
:
–
c
(
m
o
d
p
)
=
2
·
r
+
b
(
m
o
d
p
)
=
2
·
r
+
b
–
read off the least significant bit
E
v
a
l
:
R
e
d
u
c
e
m
o
d
x
0
a
f
t
e
r
e
a
c
h
o
p
e
r
a
t
i
o
n
T
o
E
n
c
r
y
p
t
a
b
i
t
b
:
p
i
c
k
r
a
n
d
o
m
s
u
b
s
e
t
S
[
1
…
t
]
Ciphertext Size Reduction
–
Resulting ciphertext < x
0
–
Underlying bit is the same (since x
0
has even noise)
–
Noise does not increase by much
(*)
P
u
b
l
i
c
k
e
y
:
[
q
0
p
+
2
r
0
,
q
1
p
+
2
r
1
,
…
,
q
t
p
+
2
r
t
]
=
(
x
0
,
x
1
,
…
,
x
t
)
Δ
(*) additional tricks for mult
A Roadmap
S
e
c
r
e
t
-
k
e
y
“
S
o
m
e
w
h
a
t
”
H
o
m
o
m
o
r
p
h
i
c
E
n
c
r
y
p
t
i
o
n
P
u
b
l
i
c
-
k
e
y
“
S
o
m
e
w
h
a
t
”
H
o
m
o
m
o
r
p
h
i
c
E
n
c
r
y
p
t
i
o
n
3
.
P
u
b
l
i
c
-
k
e
y
F
U
L
L
Y
H
o
m
o
m
o
r
p
h
i
c
E
n
c
r
y
p
t
i
o
n
How
“Somewhat”
Homomorphic is this?
Can evaluate (multi-variate) polynomials with m terms,
and maximum degree d if d << n.
f(x
1
, …, x
t
) = x
1
·x
2
·x
d
+ … + x
2
·x
5
·x
d-2
F
i
n
a
l
N
o
i
s
e
~
(
2
n
)
d
+
…
+
(
2
n
)
d
=
m
•
(
2
n
)
d
Say, noise in Enc(x
i
) < 2
n
or
m terms
Bootstrapping:
from “somewhat HE” to “fully HE”
Decrypt-then-NAND
circuit
“
S
o
m
e
w
h
a
t
”
H
E
“
B
o
o
t
s
t
r
a
p
p
a
b
l
e
”
Bootstrapping:
from “somewhat HE” to “fully HE”
F
H
E
=
C
a
n
e
v
a
l
a
l
l
c
i
r
c
u
i
t
s
T
h
e
o
r
e
m
[
G
e
n
t
r
y
’
0
9
]
:
C
o
n
v
e
r
t
“
b
o
o
t
s
t
r
a
p
p
a
b
l
e
”
→
F
H
E
.
Decrypt-then-NAND
circuit
Is our Scheme “Bootstrappable”?
What functions can the scheme evaluate?
Complexity of the Decrypt-then-NAND circuit
(?)
Can be made bootstrappable by “preprocessing”
some of the decryption outside the decryption
circuit
(Following [Gentry 09])
C
a
v
e
a
t
:
A
s
s
u
m
e
H
a
r
d
n
e
s
s
o
f
“
S
p
a
r
s
e
S
u
b
s
e
t
S
u
m
”
(polynomials of degree < n)
(degree ~ n
1.73
polynomial)
Security
(of the “somewhat” homomorphic scheme)
The Approximate GCD Assumption
q
1
p+r
1
p
?
q
1
←
[0…Q]
r
1
←
[-R…R]
odd p
←
[0…P]
(q
1
p+r
1
,…, q
t
p+r
t
)
A
s
s
u
m
p
t
i
o
n
:
n
o
P
P
T
a
d
v
e
r
s
a
r
y
c
a
n
g
u
e
s
s
t
h
e
n
u
m
b
e
r
p
P
a
r
a
m
e
t
e
r
s
o
f
t
h
e
P
r
o
b
l
e
m
:
T
h
r
e
e
n
u
m
b
e
r
s
P
,
Q
a
n
d
R
p
?
A
s
s
u
m
p
t
i
o
n
:
n
o
P
P
T
a
d
v
e
r
s
a
r
y
c
a
n
g
u
e
s
s
t
h
e
n
u
m
b
e
r
p
S
e
m
a
n
t
i
c
S
e
c
u
r
i
t
y
[
G
M
’
8
2
]
:
n
o
P
P
T
a
d
v
e
r
s
a
r
y
c
a
n
g
u
e
s
s
t
h
e
b
i
t
b
PK
=(q
0
p+2r
0
,{qi
p+2r
i
})
Enc(b)
=(qp+2r+b)
=
(proof of security)
(q
1
p+r
1
,…, q
t
p+r
t
)
P
r
o
g
r
e
s
s
i
n
F
H
E
►
“
G
a
l
a
c
t
i
c
”
→
“
E
f
f
i
c
i
e
n
t
”
Asymptotically: nearly
linear-time*
algorithms
►
S
t
r
a
n
g
e
a
s
s
u
m
p
t
i
o
n
s
→
M
i
l
d
a
s
s
u
m
p
t
i
o
n
s
*linear-time in the security parameter
–
B
e
s
t
K
n
o
w
n
[
B
G
V
1
1
]
:
(
l
e
v
e
l
e
d
)
F
H
E
f
r
o
m
w
o
r
s
t
-
c
a
s
e
h
a
r
d
n
e
s
s
o
f
n
O
(
l
o
g
n
)
-
a
p
p
r
o
x
s
h
o
r
t
v
e
c
t
o
r
s
o
n
l
a
t
t
i
c
e
s
30
M
u
l
t
i
-
k
e
y
F
H
E
Function
f
x
1
c
1
= Enc(pk
1
,
x
1
)
x
2
c
2
= Enc(pk
2
,
x
2
)
sk
1
, pk
1
sk
2
, pk
2
M
u
l
t
i
-
k
e
y
F
H
E
Function
f
x
1
y = Eval(f,c
1
,c
2
)
Dec(sk
1
,sk
2
y
)=
f
(
x
1
,x
2
)
Correctness:
x
2
sk
1
, pk
1
sk
2
, pk
2
Dec
Fully Homomorphic Encryption
Whiteboard discussion:
•
Properties
•
Performance
•
Contrast with obfuscation
•
Usefulness
Protecting memory using
Oblivious RAM
Motivation: memory/storage attacks
•
Physical attacks
–
Memory/storage is on a physical separate device (DRAM chip, SD
card, hard disk, …)
–
Communication between CPU and device is easy to tap
–
Memory/storage device may be under attack or stolen
•
Aggravated by data remanence problem
•
Software side channels
–
Leakage of accesses memory addresses across software
confinement boundaries (via data cache, instruction cache, page
table, …)
•
Network attacks
–
External storage (file server, Network Attached Storage, cloud
service, …)
–
Remote server/appliance/provider may be compromised
Protecting against memory attack
•
Computation model:
–
Random access memory
–
Small processor (logarithmic in memory size)
•
Leakage/tampering model:
–
All memory accesses (both data and address) leak or are
corrupted arbitrary (relaxation: by polytime adversary)
–
Processor assumed secure
•
Goal: a compiler that converts any program into one
that resists memory attacks
–
Functionality: input/output precisely preserved
–
Security: privacy against leakage
[MR04]
with suitable
(restricted) circuit classes and admissible functions
Protecting memory content from leakage
•
Encrypt the whole memory as a single
message
•
Encrypt every block separately
–
encrypt block data using AES
–
encrypt block number + data using AES
–
encrypt block using semantically-secure
(probabilistic encryption
•
Keep the decryption key inside the secure
processor
inefficient
Insecure
Insecure
OK
Protecting memory content from corruption
•
Sign every block, keep the signing key inside
the secure processor
•
Hash every block, keep digests inside the
secure processor
•
Using Merkle trees
–
Maintain a Merkle hash tree over the memory
–
Merkle nodes stored in the unstrusted memory
–
Merkle root stored in secure processor
–
At every read, processor verifies Merkle path
–
At every write, update Merkle path
OK
Insecure
inefficient
O
b
l
i
v
i
o
u
s
R
A
M
[
G
o
l
d
r
e
i
c
h
O
s
t
r
o
v
s
k
y
‘
9
6
]
…
P
r
o
t
e
c
t
i
n
g
a
g
a
i
n
s
t
m
e
m
o
r
y
a
c
c
e
s
s
l
e
a
k
a
g
e
“Simple ORAM” construction
[Chung Pass ‘13]
Simple ORAM” construction: reading
Simple “ORAM” construction: further details
Delve into the world of fully homomorphic encryption (FHE) with insights from Eran Tromer and Vinod Vaikuntanathan. Explore the implications of FHE on data confidentiality and delegation of computations without revealing sensitive information. Discover its applications in private search and cloud computing, alongside a historical perspective on its development and different encryption techniques.
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
Information Security Theory vs. Reality 0368-4474, Winter 2015-2016 Lecture 11: Fully homomorphic encryption Lecturer: Eran Tromer Including presentation material by Vinod Vaikuntanathan, MIT 1
Confidentiality of data inside computation: Fully Homomorphic Encryption 4 4
Fully Homomorphic Encryption Goal: delegate computation on data without revealing it A confidentiality goal 5 5
Example 1: Private search Delegate processing of data without revealing it You: (Google does not know the key, cannot see the query) Encrypt the query, send to Google Google: Encrypted query Encrypted results (You decrypt and recover the search results) 6 6
Example 2: Private Cloud Computing Delegate processing of data without revealing it Encrypt x (Enc(x), P) Enc(P(x)) (Input: x) (Program: P) 7 7
Fully Homomorphic Encryption Encrypted x, Program P Encrypted P(x) Definition: (KeyGen, Enc, Dec, Eval) (as in regular public/private-key encryption) Correctness of Eval: For every input x, program P If c = Enc(PK, x)and c = Eval (PK, c, P), then Dec (SK, c ) = P(x). Compactness: Length of c independent of size of P Security: semantic security / indistinguishability [GM82] 8 8
History of Fully Homomorphic Encryption First Defined: Privacy homomorphism [Rivest Adleman Dertouzos 78] motivation: searching encrypted data Limited homomorphism: RSA & El Gamal: multiplicatively homomorphic multiply ciphertexts multiply plaintext GM & Paillier: additively homomorphic plaintext in exponent multiply ciphertext add plaintext Quadratic formulas [BGN 05] [GHV 10] Non-compact homomorphic encryption: Based on Yao garbled circuits [SYY 99] [MGH 08]: c* grows exp with degree/depth [IP 07] branching programs Since Since 1978 1978 Eval: P, Enc(x) Enc(P(x)) ? ?1?2?3 ?1?2?3 (mod ?) ? ? ? ? ?3= ?3 ?1= ?1 ?2= ?2 9 9
Fully Homomorphic Encryption Since Since 1978 1978 Eval: P, Enc(x) Enc(P(x)) Big Breakthrough: [Gentry09] First Construction of Fully Homomorphic Encryption using algebraic number theory & ideal lattices Full-semester course Today: an alternative construction [DGHV 10] using just integer addition and multiplication easier to understand, implement and improve 10 10
Constructing fully-homomoprhic encryption assuming hardness of approximate GCD 11 11
A Roadmap 1. Secret-key Somewhat Homomorphic Encryption (under the approximate GCD assumption) (a simple transformation) 2. Public-key Somewhat Homomorphic Encryption (under the approximate GCD assumption) (borrows from Gentry s techniques) 3. Public-key FULLY Homomorphic Encryption (under approx GCD + sparse subset sum) 12 12 12
Secret-key Homomorphic Encryption Secret key: a large n2-bit odd number p (sec. param = n) To Encrypt a bit b: pick a random large multiple of p, say q p (q ~ n5 bits) (r ~ n bits) pick a random small even number 2 r Ciphertext c =q p+2 r+b noise To Decrypt a ciphertext c: c (mod p) = 2 r+b (mod p) = 2 r+b read off the least significant bit 13 13
Secret-key Homomorphic Encryption How to Add and Multiply Encrypted Bits: Add/Mult two near-multiples of p gives a near-multiple of p. c1 = q1 p + (2 r1 + b1), c2= q2 p + (2 r2 + b2) c1+c2 = p (q1 + q2) + 2 (r1+r2) + (b1+b2) p LSB = b1 XOR b2 c1c2 = p (c2 q1+c1 q2-q1 q2) + 2 (r1r2+r1b2+r2b1) + b1b2 p LSB = b1 AND b2 14 14
Problems Ciphertext grows with each operation Useless for many applications (cloud computing, searching encrypted e-mail) Noise grows with each operation Consider c = qp+2r+b Enc(b) c (mod p) = r 2r+b lsb(r ) b 2r+b r (q-1)p qp (q+1)p (q+2)p 15 15
Problems Ciphertext grows with each operation Useless for many applications (cloud computing, searching encrypted e-mail) Noise grows with each operation Can perform limited number of hom. operations What we have: Somewhat Homomorphic Encryption 16 16
Public-key Homomorphic Encryption Secret key: an n2-bit odd number p Public key: [q0p+2r0,q1p+2r1, ,qtp+2rt] = (x0,x1, ,xt) t+1 encryptions of 0 Wlog, assume that x0 is the largest of them To Decrypt a ciphertext c: c (mod p) = 2 r+b (mod p) = 2 r+b read off the least significant bit Eval (as before) 17 17
Public-key Homomorphic Encryption Secret key: an n2-bit odd number p Public key: [q0p+2r0,q1p+2r1, ,qtp+2rt]= (x0,x1, ,xt) To Encrypt a bit b: pick random subset S [1 t] + c = + b (mod x0) 2 x r i i S To Decrypt a ciphertext c: c (mod p) = 2 r+b (mod p) = 2 r+b read off the least significant bit Eval (as before) 18 18
Public-key Homomorphic Encryption Secret key: an n2-bit odd number p Public key: [q0p+2r0,q1p+2r1, ,qtp+2rt]= (x0,x1, ,xt) To Encrypt a bit b: pick random subset S [1 t] + c = + b (mod x0) 2 x r i i S c = p[ ]+ 2[ ] + b (mod x0) S i S i = p[ ]+ 2[ ] + b 0 kq q S i (mult. of p) +( small even noise) + b i i c = p[ ]+ 2[ ] + b kx0 (for a small k) + + iq r r ir iq ir S S r + i i r kr 0 i S 19 19
Public-key Homomorphic Encryption Ciphertext Size Reduction Secret key: an n2-bit odd number p Public key: [q0p+2r0,q1p+2r1, ,qtp+2rt]= (x0,x1, ,xt) To Encrypt a bit b: pick random subset S [1 t] + c = + b (mod x0) 2 x r i i S To Decrypt a ciphertext c: c (mod p) = 2 r+b (mod p) = 2 r+b read off the least significant bit Eval: Reduce mod x0 after each operation 20 20 (*) additional tricks for mult
Public-key Homomorphic Encryption Ciphertext Size Reduction Secret key: an n2-bit odd number p Public key: [q0p+2r0,q1p+2r1, ,qtp+2rt]= (x0,x1, ,xt) To Encrypt a bit b: pick random subset S [1 t] Resulting ciphertext < x0 + c = + b (mod x0) 2 x r i i S Underlying bit is the same (since x0 has even noise) To Decrypt a ciphertext c: Noise does not increase by much(*) c (mod p) = 2 r+b (mod p) = 2 r+b read off the least significant bit Eval: Reduce mod x0 after each operation 21 21 (*) additional tricks for mult
A Roadmap Secret-key Somewhat Homomorphic Encryption Public-key Somewhat Homomorphic Encryption 3. Public-key FULLY Homomorphic Encryption 22 22
How Somewhat Homomorphic is this? Can evaluate (multi-variate) polynomials with m terms, and maximum degree d if d << n. 2 / 2 2 / 2 p m = 2 nd n d ~ n or f(x1, , xt) = x1 x2 xd + + x2 x5 xd-2 m terms Say, noise in Enc(xi) < 2n Final Noise ~ (2n)d+ +(2n)d = m (2n)d 23 23
Bootstrapping: from somewhat HE to fully HE Decrypt-then-NAND circuit NAND Dec Dec c1 sk c2 sk 24 24
Bootstrapping: from somewhat HE to fully HE Theorem [Gentry 09]: Convert bootstrappable FHE. FHE = Can eval all circuits Decrypt-then-NAND circuit Somewhat HE Bootstrappable NAND Dec Dec c1 sk c2 sk 25 25
Is our Scheme Bootstrappable? What functions can the scheme evaluate? (polynomials of degree < n) (?) Complexity of the Decrypt-then-NAND circuit (degree ~ n1.73 polynomial) Can be made bootstrappable by preprocessing some of the decryption outside the decryption circuit (Following [Gentry 09]) Caveat: Assume Hardness of Sparse Subset Sum 26 26
Security (of the somewhat homomorphic scheme) 27 27
The Approximate GCD Assumption Parameters of the Problem: Three numbers P,Q and R p? (q1p+r1, , qtp+rt) q1p+r1 p q1 [0 Q] r1 [-R R] Assumption: no PPT adversary can guess the number p odd p [0 P] 28 28
(q1p+r1,, qtp+rt) p? p Assumption: no PPT adversary can guess the number p = (proof of security) Semantic Security [GM 82]: no PPT adversary can guess the bit b PK =(q0p+2r0,{qip+2ri}) Enc(b) =(qp+2r+b) 29 29
Progress in FHE Galactic Efficient Asymptotically: nearly linear-time* algorithms Practically: Implementations, including bootstrapping and packing github.com/shaih/HElib github.com/lducas/FHEW a few milliseconds for Enc, Dec [LNV 11,Gentry Halevi Smart 11] a few minutes (amortized) for evaluating an AES block [GHS 12] single bootstrapping < 1 second bootstrapping takes 5.5 minutes and allows a payload of depth 9 computation on ?? 216 1024 vectors [Ducas Micciancio '14] Strange assumptions Mild assumptions Best Known [BGV11]: (leveled) FHE from worst-case hardness of nO(log n)-approx short vectors on lattices *linear-time in the security parameter 30 30 30
Multi-key FHE sk1, pk1 x1 Function f sk2, pk2 x2 31 31
Multi-key FHE sk1, pk1 x1 Function f y = Eval(f,c1,c2) Dec sk2, pk2 x2 Correctness: Dec(sk1,sk2y)=f(x1,x2) 32 32
Fully Homomorphic Encryption Whiteboard discussion: Properties Performance Contrast with obfuscation Usefulness 33
Protecting memory using Oblivious RAM 34
Motivation: memory/storage attacks Physical attacks Memory/storage is on a physical separate device (DRAM chip, SD card, hard disk, ) Communication between CPU and device is easy to tap Memory/storage device may be under attack or stolen Aggravated by data remanence problem Software side channels Leakage of accesses memory addresses across software confinement boundaries (via data cache, instruction cache, page table, ) Network attacks External storage (file server, Network Attached Storage, cloud service, ) Remote server/appliance/provider may be compromised 35 35
Protecting against memory attack Computation model: Random access memory Small processor (logarithmic in memory size) Leakage/tampering model: All memory accesses (both data and address) leak or are corrupted arbitrary (relaxation: by polytime adversary) Processor assumed secure Goal: a compiler that converts any program into one that resists memory attacks Functionality: input/output precisely preserved Security: privacy against leakage [MR04] with suitable (restricted) circuit classes and admissible functions 36 36
Protecting memory content from leakage Encrypt the whole memory as a single message Encrypt every block separately encrypt block data using AES encrypt block number + data using AES encrypt block using semantically-secure (probabilistic encryption Keep the decryption key inside the secure processor 37 37
Protecting memory content from corruption Sign every block, keep the signing key inside the secure processor Hash every block, keep digests inside the secure processor Using Merkle trees Maintain a Merkle hash tree over the memory Merkle nodes stored in the unstrusted memory Merkle root stored in secure processor At every read, processor verifies Merkle path At every write, update Merkle path 38 38
Oblivious RAM Protecting against memory access leakage [Goldreich Ostrovsky 96] Compile any program ? and memory size ? into a new program ? , such that: (this definition follows [Chung Pass 2013]) For any ? with memory size ?, and input ?: Correctness: ? (?)=?(?)(up to some small failure probability) Efficiency: ? on ? runs ? ? times longer than ? on ?, where ?( ) is the computational overhead ? uses memory of size ? ? ?,where ?( ) is the memory overhead Extra registers in secure processor Obliviousness (security): For any ?1, ?2 with memory size ?, and inputs ?1, ?2, such that the number of memory accesses done by ?1 on ?1 is the same as ?2 on ?2, the (address,val) memory transcript of ?1 statistically close to that of ?2 on ?1 is on ?2. 39 39
Simple ORAM construction [Chung Pass 13] Given a progam ? and memory size ?, output ? : ? proceeds like ?, except: ????(?) ?????(?) write(?,???) Owrite(?,???) Memory divided into blocks of size ?. ? ? External memory holds a complete binary tree of depth ? = log ??? maps each memory blocks ? to a leaf ???. Invariant: the content of block ? is stored somewhere along path to ???. Each node contains a bucket: at most ? tuples (?,???,????) where ? is a block index and ? is the block s data. ( ? = polylog ? ) All registers and memory are initialized to . 40 40
Simple ORAM construction: reading ?????(?): ? is ? s block ??? ???[?] Fetch ? s block by traversing path from root to ??? looking for a tuple (?,???,?). (if not found, output ) Update map ??? ? ??? chosen at random. Put back ?,??? ,? into the root s bucket. (if overflow, output ) Flush tuples down a path to a random ??? , as far as they can go while consistent with invariant. (if overflow, output ) Obliviousness: each ????? operation traverses the tree along two paths that are chosen at random and independently of the history so far (doing a single read and single write at every node). 41 41
Simple ORAM construction: further details Writing: ??????(?,???): same as ????? ? except we put back the updated ?,??? ,? . Storing the position map Problem: the position map is too large. Solution ( full-fledged construction ): recursively stored the position map in a smaller oblivious RAM (same ? but smaller memory). Correctness: Obvious as long as overflows don t happen. Easy probabilistic analysis shows that overflows happen with negligible probability (for suitable parameters ? and ?). See [Chung Pass 13 A Simple ORAM ] for details. Overheads: all polylogarithmic. ?(1) registers suffice. Other ORAMs Lower bound: log(?) computational overhead. There are several variants of such path ORAM , and others. Implemented in software, FPGA hardware. 42 42
