Homomorphic Encryption

Applied Cryptography

These slides are from a lecture I designed and repeatedly gave in the course on Applied Cryptography at TU Eindhoven.

Unlike the previous lecture on OCB2, this was always towards the end of the course with the goal of giving the students an idea of how much is possible with cryptography. These slides specifically are from the first half of the first half of the lecture, with further topics including Multi-Party Computation (MPC), and a discussion of requirements for security notions.

One issue this lecture always had is that there is so much to talk about with regards to those topics that it was always too long, to the point where this could fit most of two full lectures; because of this, and to give me more time to prepare the other parts separately, I’ve decided to split this part of, but note that I haven’t changed much otherwise.

Encryption Can Create Problems

“All the Things” meme: Encrypt all the things.

For Confidentiality in E-Voting:
Encrypt all the votes!
- But how do we then count them?

For Research on Confidential Data (say DNA databases):
Encrypt all the data!
- But how can we then do the research?

For Confidentiality in cloud-computing:
Encrypt all your data!
- But how would we then run computations in the cloud?

Homowhat?

Homomorphism = Structure Preserving Map

Let $φ: A → B$
Let $∘: A × A → A$
Let $∙: B × B → B$

If $\forall a,b ∊ A$ : $φ(a)∙φ(b) = φ(a∘ b)$ , then $φ$ is “homomorphic” with regards to “ $∘$ ” and called a Homomorphism.

Today: $φ = \mathsf{Enc}$
For ElGamal: $∘ = ⋅$ in $𝔾$

Textbook RSA

Just for completeness: Yes, strictly speaking textbook-RSA is homomorphic.

For reasonable definitions of those words, it is however not an encryption- or signature-scheme, but rather a trapdoor one-way permutation. Using it as encryption- or signature-scheme is catastrophically insecure!

A vomiting person. — Typical Cryptographers reaction to inadequate use of textbook RSA.

ElGamal

Let ⟨g⟩=:𝔾⟨ g⟩ =: 𝔾 be a group of prime order qq with hard DDH-problem.
- That is for random $x,y,z ∈ ℤ_{q}$ : $(g^x,g^y,g^z)$ is indistinguishable from $(g^x,g^y,g^{x⋅y})$
Key-Generation: Sample $a ← ℤ_q$ , then $sk = a$ and $pk = g^a$ .
Encryption: Sample $r ← ℤ_q$ , then $c = (g^r, [g^a]^r⋅m)$
Decryption: $m = c[0]^{−a} ⋅ c[1] = \left(g^r\right)^{-a} ⋅ g^{ra} ⋅ m = g^{-ra + ra} ⋅ m = g^0 ⋅ m = 1 ⋅ m = m$

Let $c₀ := \left(g^{r₀}, g^{r₀y}⋅ m₀\right)$ and $c₁ := \left(g^{r₁}, g^{r₁y}⋅ m₁\right)$ be ElGamal ciphertexts encrypted for the public key $g^y$

Componentwise multiplication gives $\left(g^{r₀}⋅ g^{r₁},\ g^{r₀y}⋅ m₀ ⋅ g^{r₁y}⋅ m₁\right) = \left(g^{r₀ +r₁},\ g^{(r₀+r₁)y}⋅ m₀⋅ m₁\right)$

Let $r := r₀ + r₁$
$\left(g^{r},\ g^{ry}⋅ (m₀⋅ m₁)\right)$ $⇒$ regular ciphertext containing $m₀⋅ m₁$

How useful is this?

Over prime-order subgroups of $ℤ_p^×$ : Very limited, 0 not in the group
Over elliptic curves: Even worse.
Still demonstrates the viability of the concept.

The “useless machine”, an art piece with a switch that is turned off by the machine if someone turns it on.

What about Security?

IND-CCA2 security is unachievable for any homomorphic encryption scheme!
- Proof left as a simple exercise for you.

ElGamal is famously IND-CPA secure under standard assumptions.
- Semantic Security is achievable and thou shalt not compromise on it.

ElGamal is also IND-CCA1 secure under reasonable assumptions.
- If you can easily get IND-CCA1 security, go for it.

All sensible homomorphic encryption-schemes known today are also rerandomizable.
- Encrypt neutral element and use homomorphism with it.

Exponential ElGamal

Let $m₀', m₁' ∊ ℤ ≪ q$
Let $m₀ := g^{m₀'},\ m₁ := g^{m₁'}$ .
Use ElGamal Encryption and apply the homomorphism as before
Decryption yields $m = m₀⋅ m₁ = g^{m₀'}⋅ g^{m₁'} = g^{m₀' + m₁'}$ .
Compute $m' := \mathsf{dlog}(m) = \mathsf{dlog}\left(g^{m₀' + m₁'}\right) = m₀' + m₁'$

Computing the discrete logarithm is possible if $m'$ is small.

$⇒$ Homomorphic over (small) subsets of $ℤ^+$

How useful is this?

Votes are added
Money is often added and subtracted
…

Paillier

Computing the discrete logarithm is still annoying though.

Key-Generation:

$p,q \leftarrow$ Primes
$n := p⋅ q$
$φ(n) = (p-1)(q-1)$
return $n$ (pk), $φ(n))$ (sk)

Encrypt( $m$ ; $r$ )

$r \leftarrow ℤ_{n²}$
return $(mn+1)\ ⋅\ r^n \mod n²$
Equivalent: $(n+1)^m\ ⋅\ r^n \mod n²$

Decryption( $c$ )

$L(x ∊ \mathbb{N}, n ∊ \mathbb{N}) := \frac{x-1}{n}$
$m := \frac{L\left(c^{φ(n)} \mod n²\right)}{φ(n)} \mod n$
Works because: $(r^n)^{φ(n)} = r^{n⋅φ(n)} = r^{φ(n²)} \equiv r^0 = 1 \mod n²$

Homomorphic Property

$\mathsf{Enc}(m₀; r₀)⋅\mathsf{Enc}(m₁; r₁)$

$= (n+1)^{m₀} ⋅ r₀^n ⋅ (n+1)^{m₁} ⋅ r₁^n$

$=(n+1)^{m₀+m₁} ⋅ (r₀⋅ r₁)^n$

$=\mathsf{Enc}\left(m₀ + m₁; \left(r₀ ⋅ r₁ \mod n²\right)\right)$

Correctness

Let $λ = φ(n)$
$\left((n+1)^m ⋅ r^n\right)^λ\mod n²$

$=(n+1)^{m⋅λ} ⋅ r^{n⋅ λ}\mod n²$

$=(m⋅λ⋅ n+1) ⋅ r^0 \mod n²$

$=m⋅λ⋅ n+1$
$L(m⋅λ⋅ n+1)$

$= \frac{m⋅λ⋅ n + 1 -1}{n} = \frac{m⋅λ⋅ n}{n} = m⋅λ$
$\frac{m⋅λ}{λ} = m$

Soundness

IND-CPA follows from the “Decisional Composite Residuosity Assumption”:

Let $n$ be an RSA-modulus, $x$ , $y$ random in $ℤ_{n^2}^\times$ , then $x^n$ and $y$ are computationally indistinguishable.
Stronger (“more daring”) assumption than the RSA-assumption.
Random-self-reducible problem ⇒ Average case hardness = Worst case hardness

The CGS Voting Scheme

Ronald Cramer, Rosario Gennaro and Berry Schoenmakers

Assume (for now!) a trusted authority $𝒜$ and voters $𝒱_i$ .

Basic idea:
- $𝒜$ generates keypar $\mathsf{pk}_{𝒜},\ \mathsf{sk}_{𝒜}$
- Users $𝒱_i$ encrypt their vote $v_i$ : $c_i := \mathsf{Enc}(\mathsf{pk}_{𝒜}, v_i)$
- Everyone publishes their encrypted vote $c_i$ with a signature to proof that it is theirs.
- $C := ∑ c_i$
- $𝒜$ computes $M := \mathsf{Dec}(\mathsf{sk}_{𝒜}, C)$
- $M$ is the sum of all votes

This works if all involved parties are honest!

Add signatures and proof honest execution of all algorithms.
- Reasonably efficient zero-knowledge-proofs exist for this.

Assuming many assumptions this provides a verifiably correct result!
Trusted authority can learn all individual votes!

Voting with Trusted Authorities

Distributing the Authority

Assume a set of Parties 𝒜₀,…,𝒜n𝒜₀,…,𝒜_n that are unlikely to collude (e.g. Nazis, Social Democrats and Tankies)
- No need to trust any of them individually!
Each generates a DH-keypair $(g^{x_i}, x_i)$ and publishes the public key $g^{x_i}$
Compute ∏gxi=g∑xi≕𝗉𝗄𝒜∏ g^{x_i} = g^{∑x_i} ≕ \mathsf{pk}_𝒜
- $\mathsf{sk}_𝒜$ is distributed amongst (by assumption) non-colluding parties.
To decrypt (gr,gr⋅∑xi+v)(g^r, g^{r⋅∑x_i+ v}) each party 𝒜i𝒜_i publishes grxig^{rx_i} with a proof of correctness.
- $g^v = g^{r⋅∑x_i+ v} ⋅ \left(∏g^{rx_i}\right)^{-1}$

Fairness

Problem: Last party to publish grxig^{rx_i} can use the already published values to compute the result.
- If the result is not what they like, they can just not publish their share.
  - Can be resolved with an honest majority
- Can always simply refuse to publish as an act of obstruction.
Possible Solution: Require kk out of nn parties to participate in encryption.
- So called Treshold Encryption
- Possible with Shamir’s Secret Sharing (next slide)

Every degree- $k$ polynomial $p$ is uniquely defined by any $k+1$ points on it.
Let $p$ be a large enough prime so that every possible secret key can be encoded into $ℤ_p$ .
Sample any degree- $k+1$ polynomial over $ℤ_p$ , such that $p(0) = \mathsf{sk}$ .
Party $𝒜_i$ receives $p(i+1)$ as share.
Any subset of at least $k$ parties can now recover $\mathsf{sk}$ and use it to decrypt.
Use Multi-Party Computation (→Second half) to do so without revealing shares.

Voting with Exponential ElGamal

Number of votes is small enough for brute-force search
Distributing decryption is quite easy
Somewhat practical NIZK proofs.

Attacking Weak Groups

But what if $\left|⟨g⟩\right|$ is not prime?

Let $⟨ g⟩ = 𝔾 = ℤ_p^×$ for $p = 2q + 1$ with $p$ and $q$ prime. Then $|𝔾| = 2q$

$𝔾$ has four subgroups: $\{1\}$ , $𝔾$ , $\{1,\ -1\}$ ) and $\left\{h² |h ∊ 𝔾\right\}$ (the “squares”).
All elements can be mapped into the order-2 subgroup ({−1,1}\{−1,1\}) by raising them to p−12\frac{p-1}{2} (Legendre-symbol)
- For non-squares $h$ : $h^{\frac{p-1}{2}} = h^q = -1$
- For squares $h$ : $h^{\frac{p-1}{2}} = h^q = 1$
$⇒$ $g^x$ is a square if and only if $x$ is even; there are exactly $q = \frac{p-1}{2}$ squares

Let $g^x$ be a public key and $(g^r, g^{rx+v})$ an exponential ElGamal Ciphertext.
Using the Legendre-Symbol extract $x$ , $r$ and $rx + v$ modulo 2.
Compute $v ≡ (rx + v) − x⋅r \mod 2$

$⇒$ From provably secure to broken in one plaintext-bit.

Nothing magic about 2, except that it always factors $p-1$ ; attack reveals even more with bigger factors of $p-1$ if there are any. (Second part of the CTF.)

Extracing a Yes/No-vote

Let $p$ ≔ ffdhe3072, as defined in rfc 7919, but set $g ≔ 5$ .

Let $g^x$ be the authority’s public key, and $\left(g^r, g^{r⋅x + v}\right)$ be the vote;

ffdhe3072

5809605995369958062758586654274580047791722104970656507438869740087793294939022179753100900150316602414836960597893531254315756065700170507943025794723871619068282822579148207659984331724286057133800207014820356957933334364535176201393094406964280368146360322417397201921556656310696298417414318434929392806928868314831784332237038568260988712237196665742900353512788403877776568945491183287529096888884348887176901995757588549340219807606149955056871781046117195453427070254533858964729101754281121787330325506574928503501334937579191349178901801866451262831560570379780282604068262795024384318599710948857446185134652829941527736472860172354516733867877780829051346167153594329592339252295871976889069885964128038593002336846153522149026229984394781638501125312676451837144945451331832522946684620954184360294871798125320434686136230055213248587935623124338652624786221871129902570119964134282018641257113252046271726747647

g^x

1178422411924486958310518240424821423040957188687825057555659830550378263510073306107826979544796575581092864474013859848411683110722461050524985535903633267933181649449521492140619218190781017834141057813996864031540673127077260750562976883056933265299524235879517573522680152812762038788571588762969840540459358973658480304807631153501906537924864957165401501433029412118442995605830313482463502502611043476703721906336742557389097631604837824007057894990710151627388543409148631930102190218822566302711720142222891200239944222450611688678907361499075375542224708939911163827928094457401814485596390766702817007700506763687293635562017790104498759031039920234675912623036025508035266193042054655551018340474532335243964280335581101768295546418789778720097444072051193680655163299476318431723372529905023123598295034508594560332985609322215259523161622741652739241422734569926920887821903929220695977470881014091083161936497

g^r

4391994992610190319761449423767558518287000603245015644061861968679879933337395995429756128961352401863780868474236878652870242607882799062369358925651987215239410611308619408087876420713598003194048378754945497590284890820077288736035873337993256978522181661688946519984569922761353732835113526226029750825838812660117533998736797535557556410205726216629493883843853203085360508003871567520804422137558521937428953984073787478727608587818371443939806961148299427728514263951625957282663618146244114379853035041193337725332563682083900915059496335423262906532905696023570562596603494105746473558018253933459521477116630109743166505878873669721663774512137675064450410776198632736987001294081430110777572089316530344511484242018477683933728607336968422554102152043942737684665009459102328694144745524015741187437105408651421671925483097972699414030058069235142954282491047924744808340833880546775727942983678131147663439447709

g^{r⋅x + v}

5395416124159647852232053526888393879470035232885404715821474458723296253865500209247073839556053288575953298332048662616216656063245701775482656576939598611157858792608541167492306188208191737104682763662891236061367927020485765715282045810686491717965013085514719091288047370378638177850483310244998761743341955636446177708689672802618220061539470560431452184170627175614843771618345320897499929749589681937943153125034657123338945309361175952082354149816407275782478032361990297631827451164722092243937473539235664730836409837283440318166725738525759585833190163728094416505668926031712944518562785349495799335306706887922893135632101334647955977364415120025138102280729172829522688508535240963566716776803003424540328548627396245236166759995547053443637697617303536790324197962909441609724344467008965246110304923044935561966769054021248304317000428404682799132820685369364288090193400890270137366516610436388585339230955

Extracing a lot more

Let’s look at another case with a modulus that is merely a strong prime, but not a safe prime. (We say that a prime $p$ is strong if $p - 1$ has a large prime-factor).

In our case $p - 1$ is divisible by 2, 3, 19, 29, and one more very large prime-factor; we set $g ≔ 3$ .

p

39427225484355975102122600527167302777805510048781168392636183693013851243149270836739456524825801432201096199599098837095124524178989165662152572613751755039167267056414754728944498770643037152808863262177629669439832711280387073579264571863375293058926284173351179703389057202165646232990957198441854659340513518404920247358713319869533563202860005285693572620182090544469728768558369196539592053834936634362896039654693258365850287567082105126090534698108468407005216489068184924395507401289092087150151804123009972300008624145519860441350665518426857193464224049197310434176217485695053226283892054946252281144445763

g^r

36981052468204015342814738886535889262303816373942871782354072965419111977428988029591751718593750303549486532165596737396639074163765723792999775542824594983641080378960918791705467496105793562432494134172049602654797267947073315992738363352297441290445038812540973419812886087905175206734035088338782951307817177031996038671276499176546378702002550363471057798900060392802512722265250574768121113861555344142836128806956289892118658119853137096658853880215859575012370051967344193602399685489342306558859327433334550192742467618712050597491566408592255067448165452574459357391258520026968084348560186898996649757308090

g^x

10795413919299506427910466223527337935363002929252676398876302508914409257071944905678346360861475901850033320533149685589748011158474408784139478481429894796234833051864312509042526078156253354562165666142023950977152193014586642217821653627539196186628753880916943903639574952034303131136200946250409944309207038682275431290465184032752904723996966822707995758294205800296398056896937621111736251437580020809350620943102808896919589693593540652151149724735965648542177534454301093886394663729124484185167537965968550285629874212870411593675629916011609742678132687506145645337617959446411096354221785455353316440864701

g^{r⋅x+v}

33330859593184613696230395939031978408958334719631475004006216203461834696669154109969917408468331667777451411924184668888812972058260019937437412653703592015018635183892166957401945680089327654695532867266658656727546030404543158736654804738955611390461390401929507979512798110723528678746579365902727283615390104670367729787555345614021454181564723496934578804290920348904864533192734294938083789040237018298087291666348051784970318609853771343985719715621814596725541349201296285190582915066558517067680055317813080518519870242506507387177985994926804123608504149321685825212437457708928295386859542357104381968254250

To make things more interesting, we allow more than just voting 0 or 1, but allow all options from 0 to 9 inclusive.

Fully Homomorphic Encryption (FHE)

Addition is nice, but insufficient for cloud-computing.
We need the ability to run arbitrary circuits!

Craig Gentry. CC-BY(?) John D. and Catherine T. MacArthur Foundation

Situation before 2009

Lattice based schemes support both addition and multiplication
They are noisy however; every operation will increase that noise
- Ciphertexts grew exponentially in size.
- Decryption becoming unreliable.
Additions add a little, multiplications a lot of noise.

$⇒$ Only practical for circuits with limited depth, existence of a “proper” scheme dubious.

2009: Craig Gentry publishes his PhD-thesis

“A Fully Homomorphic Encryption Scheme”
First plausible scheme
Foundation of everything we have seen since then

Gentrys idea: Bootstrapping

Encrypt the secret key with its public key, giving 𝖾𝗌𝗄≔𝖤𝗇𝖼(𝗌𝗄)\mathsf{esk} ≔ \mathsf{Enc}(\mathsf{sk})).
- Not guaranteed to be secure by IND-CPA! (Adversary doesn’t know it.)
  
  ⇒ Requires extra analysis!
Encrypt the ciphertext $c = \mathsf{Enc}(m)$ a second time, giving $c' ≔ \mathsf{Enc}(\mathsf{Enc}(m))$ .
Run $\mathsf{Dec}$ homomorphically on $\mathsf{esk}$ and $c'$ .
The resulting $c''$ now contains $m$ with less noise.
Perform at least one more operation towards the actual goal.
Rinse and Repeat.

As long as the capacity is enough for one arbitrary computation, bootstrapping will eventually arrive at the goal.

Performance

Homomorphic decrypting needs many operations
Huge parameters necessary
Combined $⇒$ SLOW and HUGE!

Initial scheme roughly a hundred trillion times slower compared to operations on the plaintext! (one hundred trillion = 100000000000000)

FHE: State of the Art

Wonkyung Jung, Sangpyo Kim1, Jung Ho Ahn, Jung Hee Cheon and Younho Lee in “Over 100x Faster Bootstrapping in Fully Homomorphic Encryption through Memory-centric Optimization with GPUs”, April 2021:

The wall-clock time for bootstrapping is reduced to 526.96ms in a 173-bit security parameter set with 65,536 slots and 19-bit precision bit, which translates into 0.423us in terms of amortized time per bit.

[…]

The amortized FHE-mult time of our implementation is 24.35 ms, through which we believe that practical privacy-preserving applications can be developed.

$⇒$ This is clearly going somewhere.

Conclusions about FHE

Theoretical

Existence is an amazing result!
Super-useful for cloud-computing.
Potential building-block for MPC.

Practical

Performance still unusable for cloud-computing.
Getting better.
Current research topic.
Already usable for specific applications.

Main Problems

Bootstrapping very expensive
Multiplications require frequent bootstrapping
Large size terrible for communication

$⇒$ If somebody wants to sell it to you as a solution to an actual problem, stay sceptical but don’t dismiss it right away!

References

Papers

Taher Elgamal: A public key cryptosystem and a signature scheme based on discrete logarithms, 1985
Pascal Paillier: Public-Key Cryptosystems Based on Composite Degree Residuosity Classes, 1999
Ronald Cramer, Rosario Gennaro, Berry Schoenmakers: A Secure and Optimally Efficient Multi-Authority Election Scheme, 1997
Adi Shamir: How to share a secret, 1979
Craig Gentry: A fully homomorphic encryption scheme. Stanford university, 2009

Images

“All the Things”: “Allie” (original post)
Vomiting Man: Public Domain, CDC (via)
Useless Box: CC-BY-SA, “Drpixie” (via)
Ballot Box: CC-BY-SA, “DALIBRI” (via)
Pile of Coins: CC-BY-SA, Michael Sander (via)
Voting in North Korea: CC-BY-SA, “Mannen av börd” (via)
Jolly Roger: CC-BY-SA, “fdecomite” (via)
Craig Gentry: CC-BY, “John D. and Catherine T. MacArthur Foundation” (via)
Snail: CC-BY-SA, “H. Zell”

Settings

Homomorphic Encryption

Encryption Can Create Problems

Homowhat?

Textbook RSA

ElGamal

How useful is this?

What about Security?

Exponential ElGamal

How useful is this?

Paillier

Key-Generation:

Encrypt( $m$ ; $r$ )

Decryption( $c$ )

Homomorphic Property

Correctness

Soundness

The CGS Voting Scheme

Voting with Trusted Authorities

Distributing the Authority

Fairness

Voting with Exponential ElGamal

Attacking Weak Groups

Extracing a Yes/No-vote

What is the value of 𝑣?

Extracing a lot more

What is the value of 𝑣?

Fully Homomorphic Encryption (FHE)

Situation before 2009

2009: Craig Gentry publishes his PhD-thesis

Gentrys idea: Bootstrapping

Performance

FHE: State of the Art

Conclusions about FHE

Theoretical

Practical

Main Problems

References

Papers

Images

Settings

Encryption Can Create Problems

Homowhat?

Textbook RSA

ElGamal

How useful is this?

What about Security?

Exponential ElGamal

How useful is this?

Paillier

Key-Generation:

Encrypt(mm; rr)

Decryption(cc)

Homomorphic Property

Correctness

Soundness

The CGS Voting Scheme

Voting with Trusted Authorities

Distributing the Authority

Fairness

Shamir’s Secret Sharing

Voting with Exponential ElGamal

Attacking Weak Groups

Extracing a Yes/No-vote

What is the value of 𝑣?

Extracing a lot more

What is the value of 𝑣?

Fully Homomorphic Encryption (FHE)

Situation before 2009

2009: Craig Gentry publishes his PhD-thesis

Gentrys idea: Bootstrapping

Performance

FHE: State of the Art

Conclusions about FHE

Theoretical

Practical

Main Problems

References

Papers

Images

Encrypt( $m$ ; $r$ )

Decryption( $c$ )