IHE-Columbia-Theory- diploma Seminar.pdf

IHE-Columbia-Theory-diploma Seminar.pdf

1. Fully Homomorphic
Encryption over the Integers
Marten van Dijk
1
, Craig Gentry
2
, 
Shai Halevi
2
, Vinod Vaikuntanathan
2
1 – MIT, 2 – IBM Research
Many slides borrowed 
from Craig

2. The Goal
I want to delegate processing
of my data, 
without giving away access
to it.

3. Application: Cloud Computing F
Storing my files on the cloud u
Encrypt them to protect my information
u
Later, I want to retrieve the files containing 
“cloud” within 5 words of “computing”.
l
Cloud should return only these (encrypted) files, 
without knowing the key
I want to delegate processing
of my 
data, without giving away access
to it.

4. Computing on Encrypted Data F
Separating processing from access via 
encryption:
u
I will encrypt my stuff before sending it to 
the cloud  u
They will apply their processing on the 
encrypted data, send me back the 
processed result
u
I will decrypt the result and get my answer

5. Application: Private Google Search F
Private Internet search u
Encrypt my query, send to Google l
Google cannot “see” my query, since it does not 
know my key
u
I still want to get the same results l
Results would be encrypted too
F
Privacy combo: 
Encrypted query on encrypted data
I want to delegate processing
of my 
data, without giving away access
to it.

6. An Analogy: Alice’s Jewelry Store F
Alice’s workers need to assemble raw 
materials into jewelry F
But Alice is worried about theft
How can the workers process the raw 
materials without having access to them?

7. An Analogy: Alice’s Jewelry Store F
Alice puts materials in locked glove box u
For which only she has the key
F
Workers assemble jewelry in the box
F
Alice unlocks box to get “results”

8. The Analogy F
Encrypt
: putting things inside the box
u
Anyone can do this (imagine a mail-drop)
u
c
i
y
Enc
(m
i)
F
Decrypt
: Taking things out of the box
u
Only Alice can do it, requires the key
u
m* y
Dec
(c*)
F
Process
: Assembling the jewelry
u
Anyone can do it, computing on ciphertext
u
c* y
Process
(c
1
,…,c
n
)
F
m* = Dec(c*) is “the ring”, made from 
“raw materials”m
i

9. Public-key Encryption F
Three procedures: 
KeyGen
, 
Enc
, 
Dec
u
(sk,pk) y
KeyGen
($)
l
Generate random public/secret key-pair
u
c y
Enc
pk
(m)
l
Encrypt a message with the public key
u
m y
Dec
sk
(c)
l
Decrypt a ciphertext with the secret key
F
E.g., RSA: cym
e
mod N, myc
d
mod N
u
(N,e) public key, d secret key

10. HomomorphicPublic-key Encryption F
Another procedure: 
Eval
(for Evaluate)
u
c
*
y
Eval
(pk, f, c
1
,…,c
t
)
u
No info about m
1
, …, m
t
, f(m
1
, …m
t
) is leaked
u
f(m
1
, …m
t
) is the “ring” made from raw 
materials m
1
, …, m
t
inside the encryption box
Encryptions of 
inputs m
1
,…,m
t
to f 
function
Encryption of f(m
1
,…,m
t
). 
I.e., Dec(sk, c) = f(m
1
, …m
t
) 

11. Can we do it? F
As described so far, sure.. u
(Π, c
1
,…,c
n
) = c* yEval
pk
(Π, c
1
,…,c
n
)
u
Dec
sk
(c*) decrypts individual c
i’s, apply Π
(the workers do nothing, Alice assembles
the jewelry by herself)
Of course, this is cheating:
F
We want c* to remain small u
independent of the size of Π
u
“Compact” homomorphic encryption
F
We may also want Πto remain secret
Can be done with 
“generic tools”
(Yao’s garbled 
circuits) This is the main 
challenge

12. Previous Schemes F
Only “somewhat homomorphic” u
Can only handle some functions f
F
RSA works for MULT function (mod N) c = c
1
x … x c
t
=(m
1
x … x m
t
)
e
(mod N)c y
Eval
(pk, f, c
1
,…,c
t
), 
Dec
(sk, c) = f(m
1
, …, m
t
)
c
1
= m
1
e
c
2
= m
2
e
c
t
= m
t
e
X

13. “Somewhat Homomorphic”Schemes
F
RSA, ElGamalwork for MULT mod N
F
GoMi, Paillierwork for XOR, ADD
F
BGN05 works for quadratic formulas

14. Schemes with large ciphertext F
SYY99 works for shallow fan-in-2 circuits u
c* grows exponentially with the depth of f
F
IsPe07 works for branching program u
c* grows with length of program
F
AMGH08 for low-degree polynomials u
c* grows exponentially with degree

15. Connection with 2-party computation F
Can get “homomorphicencryption”from 
certain protocols for 2-party secure 
function evaluation
u
E.g., Yao86
F
But size of c*, complexity of decryption, 
more than complexity of the function f
u
Think of Alice assembling the ring herself
F
These are solving a different problem

16. A Recent Breakthrough  F
Genrty09: A bootstrapping technique
F
Gentry also described a candidate 
“bootstrappable”scheme
u
Based on ideal lattices Scheme E can handle its 
own decryption function
Scheme E* can 
handle any function

17. The Current Work F
A second “bootstrappable”scheme u
Very simple: using only modular arithmetic
F
Security is based on the hardness of 
finding “approximate-GCD”

18. As much as 
we have time
1. Homomorphicsymmetric encryption
FVery simple
2. Turning it into public-key encryption
u
Result is “almost bootstrappable”
3. Making it bootstrappable
u
Similar to Gentry’09
4. Security
5. Gentry’s bootstrapping technique
Not today
Outline

19. A homomorphicsymmetric encryption  F
Shared secret key: odd number 
p
F
To encrypt a bit 
m
:
u
Choose at random small 
r
, large 
q
u
Output 
c = m + 2r + pq
l
Ciphertext is close to a multiple of p
l
m = LSB of distance to nearest multiple of p 
F
To decrypt 
c
:
u
Output 
m = (c mod p) mod 2
l
m  =   c – p •[c/p] mod 2
=   c – [c/p] mod 2 
=   LSB(c)  XOR  LSB([c/p])
Noise much 
smaller than p
The “noise”

20. HomomorphicPublic-Key Encryption F
Secret key is an odd p as before
F
Public key is many “encryptions of 0” u
x
i
= q
ip + 2r
i
F
Enc
pk
(m) = subset-sum(x
i’s)+m
F
Dec
sk
(c) = (c mod p) mod 2
[       ]
x0
for i=1,2,…,t
[                            ]
x0

21. Why is this homomorphic? F
Basically because: u
If you add or multiply two near-multiples 
of p, you get another near multiple of p…

22. Why is this homomorphic? F
c
1
=q
1
p+2r
1
+m
1
,   c
2
=q
2
p+2r
2
+m
2
F
c
1
+c
2
= (q
1
+q
2
)p + 2(r
1
+r
2
) + (m
1
+m
2
)
u
2(r
1
+r
2
)+(m
1
+m
2
) still much smaller than p
 c
1
+c
2
mod p = 2(r
1
+r
2
) + (m
1
+m
2
)
F
c
1
x c
2
= (c
1
q
2
+q
1
c
2
−
q
1
q
2
)p 
+ 2(2r
1
r
2
+r
1
m
2
+m
1
r
2
) + m
1
m
2
u
2(2r
1
r
2
+…) still much smaller than p
 c
1
xc
2
mod p = 2(2r
1
r
2
+…) + m
1
m
2
Distance to nearest multiple of p

23. Why is this homomorphic? F
c
1
=m
1
+2r
1
+q
1
p, …, c
t
=m
t
+2r
t
+q
t
p
F
Let f be a multivariate poly with integer 
coefficients (sequence of +’s and x’s) F
Let c = 
Eval
pk
(f, c
1
, …, c
t
) = f(c
1
, …, c
t
)
u
f(c
1
, …, c
t
) = f(m
1
+2r
1
, …, m
t
+2r
t
) + qp
= f(m
1
, …, m
t
) + 2r + qp
u
Then (c mod p) mod 2 = f(m
1
, …, m
t
) mod 2
Suppose this noise is much smaller than p
That’s what we want!

24. How homomorphicis this? F
Can keep adding and multiplying until the 
“noise term”grows larger than p/2
u
Noise doubles on addition, squares on 
multiplication u
Multiplying d ciphertexts noise of size ~2
dn
F
We choose r ~ 2
n
, p ~ 2
n   
(and q ~ 2
n 
)
u
Can compute polynomials of degree n before 
the noise grows too large
2 5

25. Keeping it small F
The ciphertext’sbit-length doubles with 
every multiplication
u
The original ciphertext already has n
6
bits
u
After ~log n multiplications we get ~n
7
bits
F
We can keep the bit-length at n
6
by 
adding more “encryption of zero”
u
|y
1
|=n
6
+1, |y
2
|=n
6
+2, …, |y
m
|=2n
6
u
Whenever the ciphertext length grows, 
set c’ = c mod y
m
mod y
m-1
… mod y
1

26. Bootstrappableyet? /
Almost, but not quite:
/
Decryption is m = LSB(c) /LSB([c/p]) ^
Computing [c/p] takes degree O(n)
^
But O() is more than one  (maybe 7??) p
Integer c has ~n
5
bits 
^
Our scheme only supports degree ≤n
/
To get a bootstrappablescheme, use 
Gentry09 technique to “squash the 
decryption circuit”
c/p, rounded to 
nearest integer

27. How do we “simplify”decryption? F
Idea: Add to public key another “hint”
about sk
u
Of course, hint should not break secrecy of encryption
F
With hint, anyone can post-process
the ciphertext, 
leaving less work for 
Dec
E*
to do
F
This idea is used in server-aided cryptography.
Old 
decryption 
algorithm
m
c sk
Dec
E

28. How do we “simplify”decryption?
Old 
decryption 
algorithm
m
c sk
Dec
E
c
f(sk, r)
Post-
Process
sk*
m
Dec
E*
c*
Processed 
ciphertext c*
New 
approach The hint 
about sk
in pub key
Hint in pub key lets anyone post-process
the ciphertext, 
leaving less work for 
Dec
E*
to do.

29. Squashing the decryption circuit F
Add to public key many real numbers u
d
1
,d
2
, …, d
t
∈[0,2]   
(with “sufficient precision”)
u
∃sparse set S for which Σ
i∈S
d
i
= 1/p mod 2
F
Enc
, 
Eval
output 
ψ
i
=c x d
i
mod 2, i=1,…,t
u
Together with c itself
F
New secret key is bit-vector 
σ
1
,…,
σ
t
u
σ
i=1 if i∈S, σ
i=0 otherwise
F
New 
Dec
(c) is c –[
Σ
i
σ
i
Ψ
i
] mod 2
u
Can be computed with a “low-degree circuit”
because S is sparse

30. A Different Way to Add Numbers F
Dec
E*
(s,c)= LSB(c) 
XOR
LSB([
Σ
i
σ
i
ψ
i
])
Our problem: t is large (e.g. n
6
)
a
1,0
a
1,-1
…
a
1,-log t
a
2,0
a
2,-1
…
a
2,-log t
a
3,0
a
3,-1
…
a
3,-log t
a
4,0
a
4,-1
…
a
4,-log t
a
5,0
a
5,-1
…
a
5,-log t
…
…
…
…
a
t,0
a
t,-1
…
a
t,-log t
a
i‘s in binary 
representation
a
i

31. A Different Way to Add Numbers
a
1,0
a
1,-1
…
a
1,-log t
a
2,0
a
2,-1
…
a
2,-log t
a
3,0
a
3,-1
…
a
3,-log t
a
4,0
a
4,-1
…
a
4,-log t
a
5,0
a
5,-1
…
a
5,-log t
…
…
…
…
a
t,0
a
t,-1
…
a
t,-log t
Let b
0
be 
the binary 
rep of 
Hamming 
weight
b
0,log t
…
b
0,1
b
0,0

32. A Different Way to Add Numbers
a
1,0
a
1,-1
…
a
1,-log t
a
2,0
a
2,-1
…
a
2,-log t
a
3,0
a
3,-1
…
a
3,-log t
a
4,0
a
4,-1
…
a
4,-log t
a
5,0
a
5,-1
…
a
5,-log t
…
…
…
…
a
t,0
a
t,-1
…
a
n,-log t
Let b
-1
be 
the binary 
rep of 
Hamming 
weight
b
0,log t
…
b
0,1
b
0,0
b
-1,log t
…
b
-1,1
b
-1,0

33. A Different Way to Add Numbers
a
1,0
a
1,-1
…
a
1,-log t
a
2,0
a
2,-1
…
a
2,-log t
a
3,0
a
3,-1
…
a
3,-log t
a
4,0
a
4,-1
…
a
4,-log t
a
5,0
a
5,-1
…
a
5,-log t
…
…
…
…
a
t,0
a
t,-1
…
a
t,-log t
Let b
-log t
be 
the binary 
rep of 
Hamming 
weight
b
0,log t
…
b
0,1
b
0,0
b
-1,log t
…
b
-1,1
b
-1,0
…
…
…
…
b
-log t,log t
…
b
-log t,1
b
-log t,0

34. A Different Way to Add Numbers
a
1,0
a
1,-1
…
a
1,-log t
a
2,0
a
2,-1
…
a
2,-log t
a
3,0
a
3,-1
…
a
3,-log t
a
4,0
a
4,-1
…
a
4,-log t
a
5,0
a
5,-1
…
a
5,-log t
…
…
…
…
a
t,0
a
t,-1
…
a
n,-log t
Only log t 
numbers with 
log t bits of 
precision.  Easy 
to handle.
b
0,log t
…
b
0,1
b
0,0
b
-1,log t
…
b
-1,1
b
-1,0
…
…
…
…
b
-log n,log t
…
b
-log t,1
b
-log t,0

35. Computing Sparse Hamming Wgt.
a
1,0
a
1,-1
…
a
1,-log n
a
2,0
a
2,-1
…
a
2,-log n
a
3,0
a
3,-1
…
a
3,-log n
a
4,0
a
4,-1
…
a
4,-log n
a
5,0
a
5,-1
…
a
5,-log n
…
…
…
…
a
t,0
a
t,-1
…
a
t,-log t

36. Computing Sparse Hamming Wgt.
a
1,0
a
1,-1
…
a
1,-log t
0
0
…
0
0
0
…
0
a
4,0
a
4,-1
…
a
4,-log t
0
0
…
0
…
…
…
…
a
t,0
a
t,-1
…
a
t,-log t

37. Computing Sparse Hamming Wgt. F
Binary representation of the Hamming 
weight of a= (a
1
, …, a
t
)
∈
{0,1}
t
u
The i’th bit of HW(a) is e
2
i(a) mod2
u
e
k
is elementary symmetric poly of degree k
l
Sum of all products of k bits
F
We know a priori that weight 
≤
|S|
u
 Only need upto e
2^[log |S|]
(a)
u
 Polynomials of degree upto |S|
F
Set |S| ~ n, then E* is bootstrappable.

38. Security /
The approximate-GCD problem: ^
Input: integers w
0
, w
1
,…, w
t, 
p
Chosen as w
i
= q
ip + r
i
for a secret odd p
p
p∈
$
[0,P], q
i∈
$
[0,Q], r
i∈
$
[0,R] (with R ^P ^Q)
^
Task: find p
/
Thm: If we can distinguish Enc(0)/Enc(1) 
for some p, then we can find that p
^
Roughly: the LSB of r
i
is a “hard core bit”
 Scheme is secure if approx-GCD is hard
/
Is approx-GCD really a hard problem?

39. Hard-core-bit theorem A.The approximate-GCD problem:
^
Input: w
i
= q
ip + r
i
(i=0,…,t)
p
p∈
$
[0,P], q
i∈
$
[0,Q], r
i∈
$
[0,R’] (with R’^P ^Q)
^
Task: find p
B.The cryptosystem
^
Input: x
i
= q
ip + 2r
i
(i=0,…,t),  c=qp+2r+m
p
p∈
$
[0,P], q
i∈
$
[0,Q], r
i∈
$
[0,R] (with R ^P ^Q)
^
Task: distinguish m=0 from m=1
/
Thm: Solution to B  solution to A ^
small caveat: R’ smaller than R

40. Proof outline F
Input: w
i
= q
ip+ r
i
(i=1,…,t)
F
Use the w
i’sto form a public key
u
This is where we need R’>R
F
Amplify the distinguishing advantage u
From any noticeable εto almost 1
F
Use reliable distinguisher to learn q
t
u
Using the binary GCD procedure
F
Finally p = round(w
t
/q
t
)

41. Use the w
i
’sto form a public key F
We have w
i=q
ip+r
i, need x
i=q
i’p+2r
i’
u
Setting x
i
= 2w
i
yields wrong distribution
F
Reorder w
i’s so w
0
is the largest one
u
Check that w
0
is odd, else abort
u
Also hope that q
0
is odd (else may fail to find p)
l
w
0
odd, q
0
odd Hr
0
is even
F
x
0
=w
0
+2ρ
0
,  x
i=(2w
i 
+2ρ
i) mod w
0
for i>0
u
The ρ
i’s are random < R 
F
Correctness: 1.
r
i+ρ
i
distributed almost identically to ρ
i
l
Since R>R’ by a super-polynomial factor
2.
2q
i
mod q
0
is random in [q
0
]

42. Amplify the distinguishing advantage
F
Given an integer z=qp+r, with r<R’: Set 
c = [z+ m+2ρ+ subset-sum(x
i’s)] mod x
0
u
For random ρ<R,  random bit m
F
c is a random ciphertext wrtthe x
i’s
u
ρ>r
i’s, so ρ+r
i’s distributed like ρ
u
(subset-sum(q
i)’s mod q
0
) random in [q
0
]
F
c mod p mod 2 = r+mmod 2 u
A guess for c mod p mod 2  vote for r mod 2
F
Choose many random c’s, take majority u
Noticeable advantage  Reliable r mod 2

43. z = (2s)p + r  z/2 = sp + r/2
 floor(z/2) = sp + floor(r/2)
Use reliable distinguisher to learn q
t’
/
From z=qp+r, can get r mod 2 ^
Note: z = q+r mod 2 (since p is odd)
^
So (q mod 2) = (r mod 2) /(z mod 2)
/
Given z
1
,z
2
, both near multiples of p
^
Get b
i
:= q
i
mod 2,  if z
1
<z
2
swap them
^
If b
1
=b
2
=1, set z
1
:=z
1
−z
2
, b
1
:=b
1
−b
2
p
At least one of the b
i’s must be zero now
^
For any b
i=0 set z
i
:= floor(z
i/2)
p
new-q
i
= old-q
i/2
^
Repeat until one z
i
is zero, output the other
Binary-GCD

44. The odd part 
of the GCD
Use reliable distinguisher to learn q
t
F
z
i=q
ip+r
i, i=1,2, z
’:=Binary-GCD(z
1
,z
2
)
u
Then z
’
= GCD
*
(q
1
,q
2
)·p + r
’
u
For random q
1
,q
2
, Pr[GCD(q
1
,q
2
)=1] ~ 0.6
F
Try (say) z
’:=Binary-GCD(w
t
,w
t-1
)
u
Hope that z
’=1·p+r 
l
Else try again with Binary-GCD(z
’,w
t-2
), etc.
F
Run Binary-GCD(w
t
,z
’)
u
The b
2
bits spell out the bits of q
t
F
Once you learn q
t
then
u
round(w
t
/q
t
) = p+round(r
t
/q
t
) = p

45. Hardness of Approximate-GCD /
Several lattice-based approaches for 
solving approximate-GCD
^
Related to Simultaneous Diophantine 
Approximation (SDA) ^
Studied in [Hawgrave-Graham01] p
We considered some extensions of his attacks
/
All run out of steam when |q
i|>|p|
2
^
In our case |p|~n
2
, |q
i|~n
5
p|p|
2

46. Relation to SDA /
x
i
= q
ip+ r
i
(r
i
^p ^q
i), i = 0,1,2,…
^
y
i
= x
i/x
0
= (q
ip + r
i)/(q
0
p + r
0
) 
= (q
i
+ (r
i/p))/(q
0
+ (r
0
/p))
p
= (q
i+s
i)/q
0
, with s
i
~ r
i/p^1
^
y1, y2, … is an instance of SDA p
q
0
is a denominator that approximates all y
i’s
/
Use Lagarias’esalgorithm to try and 
solve this SDA instance
^
Find q
0
, then p=round(x
0
/q
0
)

47. Lagarias’esSDA algorithm ª
Consider the rows of this matrix B: g
They span dim-(t+1) lattice
ª
<q
0
,q
1
,…,q
t
>
·
B is short
g
1
st
entry: q
0
R < Q·R
g
i
th
entry (i>1): q
0
(q
ip+r
i)-q
i(q
0
p+r
0
)=q
0
r
i-q
ir
0
l
Less than Q·R in absolute value
 Total size less than Q·R·ªt
l
vs. size ~Q·P (or more) for the basis vectors
ª
Hopefully we will find it with a lattice-
reduction algorithm (LLL or variants)
R x
1
x
2
… x
t
-x
0
-x
0
…
-x
0
B=

48. Minkowski
bound
Will this algorithm succeed?
ª
Is <q
0
,q
1
,…,q
t
>·B shortest in lattice?
g
Is it shorter than ªt·det(B)
1/t+1 
?
l
det(B) is small-ish (due to R in the corner)
g
Need ((QP)
t
R)
1/t+1
> QR
gt+1 > (log Q + log P – log R) / (log P – log R)
~ log Q/log P
ª
log Q = ω(log
2
P)  need t=ω(log P)
ª
Quality of LLL & co. degrades with t g
Only finds vectors of size ~ 2
t/2
·shortest
l
or 2
t/2
H2
ε
t
for any constant ε>0
g
t=ω(log P)  2
ε
t
·QR> det(B)
1/t+1
g
Contemporary lattice reduction is not strong enough
R x
1
x
2
…x
t
-x
0
-x
0…
-x
0

49. Why this algorithm fails
t
logQ/logP
size (log scale)
the solution we
are seeking 
auxiliary solutions
(Minkowski’s bound) converges to ~ logQ+logP
What LLL can find min(
blue
,
purple
)+
ε
t
blue line
remains above
purple line
log Q

50. Conclusions F
Fully HomomorphicEncryption is a very 
powerful tool F
Gentry09 gives first feasibility result u
Showing that it can be done “in principle”
F
We describe a “conceptually simpler”
scheme, using only modular arithmetic F
What about efficiency? u
Computation, ciphertext-expansion are 
polynomial, but a rather large one…
F
Improving efficiency is an open problem

51. Extra credit F
The hard-core-bit theorem
F
Connection between approximate-GCD 
and simultaneous Diophantine approx. F
Gentry’s technique for “squashing”the 
decryption circuit

52. Thank you