Partial Homomorphic Encryption (PHE)

We are now moving into a world of Fully Homomorphic Encryption (FHE). This will typically use lattice-based methods. But, it can still be a little slow and also can suffer from too much noise when we multiply vectors which have a small error. Basically, we have the operation of:

and where we can replace the circle with any mathematical operation. But, if we do not need FHE, we can implement Partially Homomorphic Encryption (PHE). They include RSA, ElGamal, Exponential ElGamal, Elliptic Curve ElGamal, Paillier, Damgard-Jurik, Okamoto–Uchiyama, Benaloh, Naccache–Stern, and Goldwasser–Micali. A simple program to cipher each of these values is [here]:

from lightphe import LightPHE
import sys
import io
import pytest

algorithms = [
  "RSA",
  "ElGamal",
  "Exponential-ElGamal",
  "Paillier",
  "Damgard-Jurik",
  "Okamoto-Uchiyama",
  "Benaloh",
  "Naccache-Stern",
  "Goldwasser-Micali",
  "EllipticCurve-ElGamal"
]

hom_type="RSA"
a = 13
b = 17


if (len(sys.argv)>1):
        hom_type=str(sys.argv[1])

if (len(sys.argv)>2):
        a=int(sys.argv[2])

if (len(sys.argv)>3):
        b=int(sys.argv[3])

print(f"Method: {hom_type}")
print(f"a: {a}")
print(f"b: {b}\n")

cs = LightPHE(algorithm_name = hom_type)



a1 = cs.encrypt(a)
b1 = cs.encrypt(b)

print(f"\n== Try addition for {hom_type}==\n")
try:
 c=a1+b1
 dec=cs.decrypt(c)
 print(f"Cipher: {c}")
 print(f"{a}+{b} = {dec}")
except:
 print(f"\nAddition not possible for {hom_type}\n")

print(f"\n== Try multiplcation for {hom_type}==\n")
try:
 c=a1*b1
 dec=cs.decrypt(c)
 print(f"Cipher: {c}")
 print(f"{a}*{b} = {dec}")
except:
 print(f"\nMultiplication not possible for {hom_type}\n")



print(f"\n== Try scalar multiplcation for {hom_type}==\n")
try:
 c=2*b1
 dec=cs.decrypt(c)
 print(f"Cipher: {c}")
 print(f"{2}*{b} = {dec}")
except:
 print(f"\nScalar multiplication not possible for {hom_type}\n")

A sample run is [here]:

Method: EllipticCurve-ElGamal
a: 5
b: 13


== Try addition for EllipticCurve-ElGamal==

Cipher: Ciphertext(((55952729752529759656824484193420387481520062892712819725579428881191533136481, 113493774054689439846087415725028647275400557106250505973971943374042556078452), (111251437998238587273596541830311401483263919298304577970260073014526409982067, 74371937923904794129831676140803343647307791892463742574986706067345664515935)))
5+13 = 18

== Try multiplication for EllipticCurve-ElGamal==


Multiplication not possible for EllipticCurve-ElGamal


== Try scalar multiplication for EllipticCurve-ElGamal==

Cipher: Ciphertext(((73366040801266442295888005733383346059603169118545533084663384220879858183656, 84028693485220697726664588158423718046651625282333368396078336957009654651038), (22287525694643335135286298564517101605037850572501302235753732245582811431064, 8872335541977814693319613041070158131167065614958886140425081462573647127840)))
2*13 = 26

Overall, we see the RSA and ElGamal are additive homomorphic, while the others are multiplicative homomorphic:

RSA — Homomorphic Multiplying

In RSA, we can homomorphically multiply two ciphered values and gain the result of multiplication when we decipher them. So with RSA, we cipher with:

and where e is the encryption key, and N is the multiplication of two prime numbers (p and q). The difficulty in this is factorizing N to get two prime numbers. To decrypt, we find the decryption key (d) and then perform:

So if we take two values (a and b), then we can cipher them as:

If we multiply the ciphers, we get:

This is then:

When we can then decrypt and determine the value of a times b. A sample run is [here]:

Method: RSA
a: 5
b: 13


== Try addition for RSA==


Addition not possible for RSA


== Try multiplication for RSA==

Cipher: Ciphertext(53951754612684610825315821160503457565598077541198930446579105879694888348145639774246324879912519890879766085483137860677825170108979818971465959538906524793560240344613015199568044401969409134339934050754359608687981023597214109202970771119826864212369232674474525590264364497923183123392493615852726140)
5*13 = 65

== Try scalar multiplication for RSA==


Scalar multiplication not possible for RSA

ElGamal — Homomorphic Multiplying

ElGamal encryption can also be used to perform a multiplicative homomorphic encryption operation. Initially Bob creates his public key by selecting a g value and a prime number (p) and then selecting a private key (x). He then computes Y, which is:

His public key is (Y,g,p), and he will send this to Alice. Alice then creates a message (M) and selects a random value k). She then computes a and b:

Bob then receives these and decrypts with:

This works because:

The method is here:

Partial Homomorphic Encryption with ElGamal (Multiply)

A sample run is [here]:

Method: ElGamal
a: 5
b: 13


== Try addition for ElGamal==


Addition not possible for ElGamal


== Try multiplication for ElGamal==

Cipher: Ciphertext((3932762410421343372112085699521208820428297064179664722055084218555637810187992850298638002037471584321892371031784908498126435596066035214906495673853843
, 8366073110922317373262574978638906196461960312188579505189556871556324079340475511439348270826136520768351902727403940817507014733961776881633475870354161))
5*13 = 65

== Try scalar multiplication for ElGamal==


Scalar multiplication not possible for ElGamal

Paillier and Damgard-Jurik — Addition and Scalar Multiplication Homomorphic Encryption

With the Paillier method, we can perform additive and scalar multiply homomorphic encryptions. First, we select two large prime numbers (p and q) and compute:

and where lcm is the least common multiple. We then select random integer g for:

We must make sure that n divides the order of g by checking the following:

and where L is defined as L(x)=x−1N. The public key is (N,g) and the private key is (λ,μ). To encrypt a message (M), we select a random r value and compute the ciphertext of:

and then to decrypt:

If we take two ciphers (C1 and C2), we get:

If we now multiply them, we get:

And so adding two values requires a multiplication of the ciphers. The method is here:

Homomorphic Encryption with Damgard-Jurik

A sample run is [here]:

Method: Paillier
a: 5
b: 13


== Try addition for Paillier==

Cipher: Ciphertext(44299314268619135216244903790086236304456001754283729742488817837559462603918820282280845199413836012567670758792760970694917573470958896484571661176531668567941575811923809958146028499159373497817166004873575994514176110052921912005138047398106741058492475909657691860755570136995963480988140342588513576720486162805542278164787632202018543641661673247241043894145465481786765722410529061649839290345005665654060921934277381246012339197579139452012249902337216835511493641599589521488602125538659953464070921354286151036869150376150344511758521322796655582021471938075065369002386639842638816031324281246500555189)
5+13 = 18

== Try multiplication for Paillier==


Multiplication not possible for Paillier


== Try scalar multiplication for Paillier==

Cipher: Ciphertext(38810420202784837279776540293282153226134906683723551825985615646267576494312965865238279699549217266175527646897778235159301781917134653851938324635218060543052170221500121133976705674611505092766811969581256071266144057905834907630761054797961417023992444070019328190057292789740752162691000379688044096555371316459398089699581733120264811327840427596261546911979078432164751995330317967147961784865062065738774447577520402351142915831269582169456066722039549655707735005545320998430521776011923177677001837052982772170791375239718934086075376250164945293801533686352691681384683072203965943196070087287696627363)
2*13 = 26

Naccache–Stern — Addition and Scalar Multiplication Homomorphic Encryption

With the Naccache–Stern method, we can perform additive and scalar multiply homomorphic encryption. Initially, we select a large prime number (p). We then select a value (n) and for i from 0 to n, we select the first n prime numbers (p0…pn−1) of which p0 is 2. We must make sure that:

For our secret key (s) we make sure that:

To compute the public key (vi), we calculate:

To cipher, we take a message of m and then determine the message bits of mi. We can then cipher with the public key:

and then to decrypt:

We can multiply our ciphertext value, and thus perform a homomorphic addition. The method is here:

Naccache-Stern cryptosystem

A sample run is [here]:

Method: Naccache-Stern
a: 5
b: 13


== Try addition for Naccache-Stern==

Cipher: Ciphertext(32336420958064)
5+13 = 18

== Try multiplication for Naccache-Stern==


Multiplication not possible for Naccache-Stern


== Try scalar multiplication for Naccache-Stern==

Cipher: Ciphertext(49859254281974)
2*13 = 26

Okamoto-Uchiyama — Addition and Scalar Multiplication Homomorphic Encryption

With the Okamoto-Uchiyama method, we can perform additive and scalar multiply homomorphic encryption. A public/private key pair is generated as follows:

The public key is (n,g,h) and then the private key is (p,q). To encrypt a message m, where m is taken to be an element in 2^{k−1}.

Select

at random. The cipher is then:

Next, we define the function of:

We then decrypt with:

By multiplying the ciphers, we will perform a homomorphic addition.

The method is here:

Okamoto-Uchiyama

A sample run is [here]:

Method: Okamoto-Uchiyama
a: 5
b: 13


== Try addition for Okamoto-Uchiyama==

Cipher: Ciphertext(153301818025458387380007294904295970461358673174759811535473916468479853535627194789810184859006445248504355970307749458327412280698720876526198788482508786072381746404107181958259843203763249871982712757243809879448105291989870632779439055869572711796602191107035080315916903701756193584632189854613364071503025749228793134594555646964300196049447149960336662255398187077487551964701859721077009478419466845750381391321510277739791407261163817049622919707697456)
5+13 = 18

== Try multiplication for Okamoto-Uchiyama==


Multiplication not possible for Okamoto-Uchiyama


== Try scalar multiplication for Okamoto-Uchiyama==

Cipher: Ciphertext(77656925752253639587931039472221909185962823350859787704059717973372073303919980178238814171195389945126151447398984589476223355249075881355763557477344063282688170760113022874894532028252407481999863593238399253607622671336073865357650933895492925817202485526076283131253636574674716478105839211847503318604180103708430158910161465496809970305898423921420606966676599967038806526789857829388599307221618189665938863036289435139861625385705703904268598385259409)
2*13 = 26