An Overview of Homomorphic Encryption

Alexander Lange

Department of Computer Science

Rochester Institute of Technology
Rochester, NY 14623

May 9, 2011

Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 1 / 22

Outline
1 Algebraic Homomorphisms
Group & Ring Homomorphism
2 Application to Cryptography
Example: RSA
3 History
Data Banks
Blind Signatures
4 Additive Homomorphisms
ElGamal
Paillier
5 Applications
E-Voting
Private Information Retrieval
6 Fully Homorphic Encryption
Overview
Craig Gentry
Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 2 / 22
 Algebraic Homomorphisms Group & Ring Homomorphism

Algebraic Homomorphisms

Definition (Group Homomorphism)

Let (G, ?) and (H, ) be groups. The map ϕ : G → H is a homomorphism if

ϕ(x ? y ) = ϕ(x)  ϕ(y) ∀ x, y ∈ G

Definition (Ring Homomorphism)

Let R and S be rings with addition and multiplication. The map ϕ : R → S is a
homomorphism if
1 ϕ is a group homomorphism on the additive groups (R, +) and (S, +)
2 ϕ(xy) = ϕ(x)ϕ(y) ∀ x, y ∈ R

Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 3 / 22

 Application to Cryptography

Application to Cryptography
A homomorphic encryption function allows for the manipulation of encrypted
data with out the seemingly inherent loss of the encryption.
Applications
• E-Cash
• E-Voting
• Private information retrieval
• Cloud computing
A fully homomorphic encryption function (two operations) has been an open
problem in cryptography for 30+ years. The first ever system was proposed by
Craig Gentry in 2009.
However, encryption systems that respect one operation have been utilized
for decades.

Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 4 / 22

 Application to Cryptography Example: RSA

Example: The RSA Cryptosystem

Definition (RSA)
Let n = pq where p and q are primes. Pick a and b such that ab ≡ 1
(mod φ(n)). n and b are public while p, q and a are private.

eK (x) = x b mod n

dK (y ) = y a mod n

The Homomorphism: Suppose x1 and x2 are plaintexts. Then,

eK (x1 )eK (x2 ) = x1b x2b mod n = (x1 x2 )b mod n = eK (x1 x2 )

Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 5 / 22

 History Data Banks

History
On Data Banks and Privacy Homomorphisms
• Rivest, Adleman and Dertouzos, 1978
• Introduced idea of “Privacy Homomorphisms”
• “...it appears likely that there exist encryption functions which permit
encrypted data to be operated on without preliminary decryption.”
• Encrypted data of loan company
• What is the size of the average loan?
• How many loans over $5,000?

• Introduced four possible encryption functions (RSA was one of them)

Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 6 / 22

 History Blind Signatures

History
Blind signatures for untraceable payments
• David Chaum, 1982
• Calls for payment system with:
• Anonymity of payment
• Proof of payment

• Analogy to secure voting

• Place vote in a carbon envelope
• The signer can then sign the envelope, consequently signing the vote with
out ever knowing what the vote is
• Although no mention of a private homomorphism, the paper helps
introduce the need for secure voting as well as the relationship between
e-cash and e-voting

Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 7 / 22

 Additive Homomorphisms ElGamal

ElGamal Cryptosystem
Definition (ElGamal)
Let p be a prime and pick α ∈ Z∗p such that α is a generator of Z∗p . Pick a and
β such that β ≡ αa (mod p). p, α and β are public; a is private. Let r ∈ Zp−1
be a secret random number. Then,

eK (x, r ) = (αr mod p, xβ r mod p)

The Homomorphism: Let x1 and x2 be plaintexts. Then,

eK (x1 , r1 )eK (x2 , r2 ) = αr1 mod p, x1 β r1 mod p αr2 mod p, x2 β r2 mod p

= αr1 αr2 mod p, x1 β r1 x2 β r2 mod p

= αr1 +r2 mod p, (x1 x2 )β r1 +r2 mod p

= eK (x1 x2 , r1 + r2 )

Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 8 / 22

 Additive Homomorphisms ElGamal

ElGamal
The Problem: This homomorphism is multiplicative
• E-cash and e-voting would benefit from an additive homomorphism
One solution: Modify ElGamal
• Put the plaintext in the exponent
If we modify ElGamal so that

eK (x, r ) = (αr mod p, αx β r mod p)

Then the homomorphism is

eK (x1 , r1 )eK (x2 , r2 ) = αr1 mod p, αx1 β r1 mod p αr2 mod p, αx2 β r2 mod p

= αr1 +r2 mod p, αx1 +x2 β r1 +r2 mod p

= eK (x1 + x2 , r1 + r2 )

Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 9 / 22

 Additive Homomorphisms ElGamal

The problem with this modification is that dK = αx , introducing the discrete

logarithm problem into the decryption. For large enough texts, this becomes
impractical.

We would like another cryptosystem which takes advantage of this additive

property of exponentiation, but does so with out extra decryption time.

Solution: the Paillier Cryptosystem

Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 10 / 22

 Additive Homomorphisms Paillier

Paillier Cryptosystem
• Introduced by Pascal Paillier in Public-Key Cryptosystems Based on
Composite Degree Residuosity Classes, 1999
• Probabilistic, asymmetric algorithm
• Decisional composite residuosity assumption
• Given composite n and integer z, it is hard to determine if y exists such that

z ≡ yn (mod n2 )

• Homomorphic and self-blinding

• Extended by Damgård and Jurik in 2001
• modulo n2 =⇒ modulo ns+1

Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 11 / 22

 Additive Homomorphisms Paillier

Paillier Cryptosystem

Definition
Pick two large primes p and q and let n = pq. Let λ denote the Carmichael
function, that is, λ(n) = lcm(p − 1, q − 1). Pick random g ∈ Z∗n2 such that L(g λ
mod n2 ) is invertible modulo n (where L(u) = u−1 n ). n and g are public; p and
q (or λ) are private. For plaintext x and resulting ciphertext y , select a random
r ∈ Z∗n . Then,
eK (x, r ) = g m r n mod n2
L(y λ mod n2 )
dK (y ) = mod n
L(g λ mod n2 )

Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 12 / 22

 Applications E-Voting

Paillier Example: E-Voting

Suppose Alice, Bob and Oscar are running in an election. Only 6 people
voted in the election, and the results are tabulated below.

Vote Oscar Bob Alice

1 ! −→ 00 00 01 = 1
2 ! −→ 00 01 00 = 4
3 ! −→ 00 01 00 = 4
4 ! −→ 00 00 01 = 1
5 ! −→ 01 00 00 = 16
6 ! −→ 00 00 01 = 1

Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 13 / 22

 Applications E-Voting

Paillier Example: E-Voting

Let p = 5 and q = 7. Then n = 35, n2 = 1225 and λ = 12. g is chosen to be
141. For the first vote x1 = 1, r is randomly chosen as 4. Then,

eK (x1 , r1 ) = eK (1, 4) = 1411 · 435 = 141 · 324 = 359 mod 1225

All votes, r values and resulting encryptions are shown below

x r eK (x, r )
1 4 359
4 17 173
4 26 486
1 12 1088
16 11 541
1 32 163

Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 14 / 22

 Applications E-Voting

Paillier Example: E-Voting

In order to sum the votes, we multiply the encrypted data modulo n2 :
359 · 173 · 486 · 1088 · 541 · 163 mod 1225 = 983
We then decrypt:

36 − 1
L(y λ mod n2 ) = L(98312 mod 1225) = =1
35
456 − 1
L(g λ mod n2 ) = L(14112 mod 1225) = = 13
35
−1
dK (y) = L(y λ mod n2 ) L(g λ mod n2 )



mod n
= 1 · 13−1 mod 35
= 27

We convert 27 to (01 02 03) for the final results.

Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 15 / 22

 Applications Private Information Retrieval

Another Application: Private Information Retrieval

• Idea first introduced by Chor, Goldreich, Kushilevitz and Sudan in 1997
• The problem:
• How can the user access an item from a database with out the database
knowing which item it is? (Private Information Retrieval)
• How can the user do this with out knowing about any other item of the
database? (Symmetric Private Information Retrieval)
• The additive homomorphic properties of Paillier allow for the indexing and
filtering of an encrypted database

Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 16 / 22

 Applications Private Information Retrieval

Some PIR Protocols

• Stern Protocol - Uses a simple homomorphic scheme and a linear
indexing technique
• Chang Protocol - Expands on Stern by allowing the indexing to take place
on a hyper cube. Uses the Paillier Cryptosystem
• Lipmaa Protocol - Expands on Chang by using Damgård-Jurik system -
removes the limit set on the plaintext due to Paillier

Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 17 / 22

 Fully Homorphic Encryption Overview

Fully Homomorphic Encryption

• Up until now, the homomorphic systems described have been partially
homomorphic
• They preserve the structures of multiplication or division, but cannot do both

• If a fully homomorphic encryption was implemented, then any arbitrary

computation could be performed on a ciphertext, preserving the
encryption as if the computation was performed on the plaintext
• The additive and multiplicative preservation of a Ring Homomorphism
modulo 2 directly correspond to the XOR and AND operations of a circuit
• Applications:
• Private queries on search engines - The search engine would be able to
return encrypted data with out every decrypting the query
• Cloud Computing - Storing encrypted data on the cloud is seemingly
useless; no manipulation of the data can be obtained with out allowing the
cloud access and/or decrypting the data off the cloud

Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 18 / 22

 Fully Homorphic Encryption Craig Gentry

Craig Gentry
• In 2009, Craig Gentry proposed the first fully homomorphic encryption
scheme in his PhD thesis A Fully Homomorphic Encryption Scheme
• Centers around a function which introduces a certain level of noise into
the encryption
• Each operation on the ciphertext results in compounding noise
• Resolved with the bootstrapability of the encryption
• Each re-encryption cuts down the noise
• Analogy to Alice’s jewelry shop

• Involves operations on Ideal Lattices

• Allows for less complex circuit implementation
• Correspond to the structure of Rings

Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 19 / 22

 Fully Homorphic Encryption Craig Gentry

A Simple Example Over the Integers

A Somewhat Homomorphic Scheme
• K EY G EN : Output a random odd integer p
• For bit m ∈ {0, 1}, let a random m0 = m mod 2 (ie. m0 is even if m = 0,
odd if m = 1). Pick a random q. Then E NCRYPT (m, p) = c = m0 + pq.
m0 is the noise associated with the plaintext.
• Let c 0 = c mod p where c 0 ∈ (−p/2, p/2). Then
D ECRYPT (p, c) = c 0 mod 2. c 0 is considered to be the noise associated
with the ciphertext (ie. the shortest distance to a multiple of p)
The Homomorphism: (Multiplication) Let m1 , m2 ∈ {0, 1}. Then

e(m1 , p)e(m2 , p) = (m10 + pq1 )(m20 + pq2 )

=⇒ d(c) = (m10 + pq1 )(m20 + pq2 ) mod p mod 2 = m10 · m20 mod 2 = m1 · m2

Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 20 / 22

 Fully Homorphic Encryption Craig Gentry

The Problem
• The compounding noise (m10 · m20 in the example) results in loss of
homomorphic property after a certain number of operations
• The bootstrapping of the algorithm allows for this noise to be reduced,
allowing for no limit in operations
• However, the combination of the noise production followed by the noise
reduction makes the scheme completely impractical
• Complexity grows as more and more operations are performed (inherent
limitation of the algorithm)
• Gentry has stated that in order to perform one search on Google using this
encryption, the amount of computations needed would increase by a trillion
• More schemes have been introduced to try and decrease this complexity, but
all rely on the same
• Despite this impracticality, Gentry’s discovery is an amazing
breakthrough in cryptography and proves that (at least theoretical) fully
homomorphic encryption schemes exist

Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 21 / 22

 Fully Homorphic Encryption Craig Gentry

Questions?
Sources
• R. L. Rivest, L. Adleman, and M. L. Dertouzos. ”On data banks and
privacy homomorphisms.” Foundations of Secure Computation, 1978.
• Craig Gentry. ”Computing Arbitrary Functions of Encrypted Data.”
Association for Computing Machinery, 2010.
• Pascal Paillier. ”Public-Key Cryptosystems Based on Composite Degree
Residuosity Classes.” EUROCRYPT 1999.
• Laura Lincoln. ”Symmetric Private Information Retrieval via Additive
Homomorphic Probabilistic Encryption”. RIT, Department of Computer
Science, 2006.
• David Chaum. ”Blind signatures for untraceable payments.” Advances in
Cryptology - Crypto ’82, Springer-Verlag 1983
• Paillier Cryptosystem Interactive Simulator. Andreas Steffen. HSR
Hochschule fur Technik Rapperswil. 2009.
• Steve Weis. ”Verifying Elections with Cryptography”. Google Tech Talks:
Theory and Practive of Cyptography. December 2007. Youtube.
Alexander Lange (RIT) Homomorphic Encryption May 9, 2011 22 / 22