El Gamal Homomorphic Encryption in Leo

This repository contains an implementation of the ElGamal encryption scheme in Leo. ElGamal is a public-key cryptosystem that provides secure encryption and supports homomorphic operations on ciphertexts.

Overview El Gamal

Key Generation

We have prime p (see docs about field elements) and generator g = 22 (see here).

• Sample a private key priv_key and compute public key pub_key.

Encryption

• Choose a random k (here, we provide it as input as we don't have a RNG)
• Compute C1 = g^k mod p and C2 = (m * pub_key^k) mod p.

Decryption

• Calculate s_a = (C1^priv_key)^(-1) mod p.
• Decrypt with m = (C2 * s_a) mod p.

Homomorphic Multiplication

• Multiply ciphertexts (C1_1, C2_1) and (C1_2, C2_2) like this (C1_1 * C1_2, C2_1 * C2_2). This multiplies the plaintexts, encrypted.

When you decrypt this resulting ciphertext, the outcome is the multiplication of input messages.

Testing

Test 1 - All random values

Using PARI/GP random(8444461749428370424248824938781546531375899335154063827935233455917409239041)

m1 = 3177328874216172998069933727674842583425142197792604746898916331347613098227field
k1 = 7788669533474620218943169245892310534571119762675803628366628629491833959872field

m2 = 7392385298686921874454720710640332676910208501264821737459763253801297566260field
k2 = 5134642952836080535142054789475428226920331649739086847970712717638629145195field

1. Test keypair. Priv key obtained from PARI/GP and public key calculated accordingly

• pub_key = 1202779357084265799172575109162116407510522098349359838939772755638433935334field
• priv_key = 8272198081443673477747743735279492263844137663249768316564672355525125340702field

leo run get_pub_key 8272198081443673477747743735279492263844137663249768316564672355525125340702field

2. Encrypt messages

leo run encrypt 3177328874216172998069933727674842583425142197792604746898916331347613098227field 1202779357084265799172575109162116407510522098349359838939772755638433935334field 7788669533474620218943169245892310534571119762675803628366628629491833959872field
# {
#   c1: 116575650185516315037706915534870957945861122734470769193284709558551905075field,
#   c2: 4471211774191713085171237206082550903057017645511837250896078589929639426138field
# }

leo run encrypt 7392385298686921874454720710640332676910208501264821737459763253801297566260field 1202779357084265799172575109162116407510522098349359838939772755638433935334field 5134642952836080535142054789475428226920331649739086847970712717638629145195field
# {
#   c1: 8356500384850355260863030215464266805952907230053491489345348145061329671073field,
#   c2: 6497783301369533769463154618080480544198785069776245714420412729566178306251field
# }

3. Multiply messages

leo run mult_ciphertexts "{
  c1: 116575650185516315037706915534870957945861122734470769193284709558551905075field,
  c2: 4471211774191713085171237206082550903057017645511837250896078589929639426138field
}" "{
  c1: 8356500384850355260863030215464266805952907230053491489345348145061329671073field,
  c2: 6497783301369533769463154618080480544198785069776245714420412729566178306251field
}"
#  {
#   c1: 4905016814170485075672822187469145847600627478371320601690326030471658137543field,
#   c2: 2262656180784385643118284026677859987588418961078216371132389931829390462001field
# }

4. Decrypt

leo run decrypt "{
  c1: 4905016814170485075672822187469145847600627478371320601690326030471658137543field,
  c2: 2262656180784385643118284026677859987588418961078216371132389931829390462001field
}" 8272198081443673477747743735279492263844137663249768316564672355525125340702field
# 5933534467186704308506600189314596155202034203178335985155887746469840603067field

Check result in PARI/GP

Mod(3177328874216172998069933727674842583425142197792604746898916331347613098227*7392385298686921874454720710640332676910208501264821737459763253801297566260, 8444461749428370424248824938781546531375899335154063827935233455917409239041)
#  5933534467186704308506600189314596155202034203178335985155887746469840603067
#  Correct!

Test 2 - Random values and small values

Using PARI/GP random(8444461749428370424248824938781546531375899335154063827935233455917409239041)

m1 = 45678field
k1 = 5203042127358649340904750314466367793094507691418755756208128707314580522552field

m2 = 888field
k2 = 7854063782064912777947283892113100481529492690563337484262592127033185220460field

Test keypair

• pub_key = 6400977530036418317775721924855138179897296576018842422808515401282150070936field
• priv_key = 753004072685881823636366456603650587050591895244751816960546428819898446772field

leo run get_pub_key 753004072685881823636366456603650587050591895244751816960546428819898446772field

1. Encrypt m1 under pub_key, using k1

leo run encrypt 45678field 6400977530036418317775721924855138179897296576018842422808515401282150070936field 5203042127358649340904750314466367793094507691418755756208128707314580522552field
# Result
# {
#   c1: 4545240134733908556125749800281845285389885560391618997728077370226461435670field,
#   c2: 4531182665311840178741949476500072442506888039781460179797884253108169739201field
# }

Encrypt m2 under pub_key, using k2
leo run encrypt 888field 6400977530036418317775721924855138179897296576018842422808515401282150070936field 7854063782064912777947283892113100481529492690563337484262592127033185220460field
# Result
# {
#   c1: 5271987784861258949073389714970410080411227307832527570448530128952551667122field,
#   c2: 2223377329472227322087938132587256302957818486055115575761851706179853533412field
# }

2. Multiply the ciphertexts

leo run mult_ciphertexts "{
  c1: 4545240134733908556125749800281845285389885560391618997728077370226461435670field,
  c2: 4531182665311840178741949476500072442506888039781460179797884253108169739201field
}" "{
  c1: 5271987784861258949073389714970410080411227307832527570448530128952551667122field,
  c2: 2223377329472227322087938132587256302957818486055115575761851706179853533412field
}"
# Result
# {
#   c1: 4365548365631094310119356159764511142009651057404730790402062883678859712742field,
#   c2: 7275958970451129681359730432297163208322898972993243649458571762652227260057field
# }

3. Decrypt

leo run decrypt "{
  c1: 4365548365631094310119356159764511142009651057404730790402062883678859712742field,
  c2: 7275958970451129681359730432297163208322898972993243649458571762652227260057field
}" 753004072685881823636366456603650587050591895244751816960546428819898446772field

# Result
# 40562064field = 45678 * 888
# Correct!

Test 3 - Small test values

Test keypair:

• pub_key = 5153632field
• priv_key = 5field

m1 = 2field
k1 = 123field

m2 = 3field
k2 = 456field

1. Encrypt both messages m1, m2:

leo run encrypt 2field 5153632field 123field
# {
#   c1: 4281024143617973432384462541056021194822242417477687245451443563273154242473field,
#   c2: 1572711479132772385188434990553282722904522729883541792384696766198878997498field
# }

leo run encrypt 3field 5153632field 456field
# {
#   c1: 8219006186278527715773371608839031405611473808626602570518694310896630839794field,
#   c2: 7905567122759533570302126001762943316506837083107534363619137121591430247813field
# }

2. Multiply the ciphertexts

leo run mult_ciphertexts "{
  c1: 4281024143617973432384462541056021194822242417477687245451443563273154242473field,
  c2: 1572711479132772385188434990553282722904522729883541792384696766198878997498field
}" "{
  c1: 8219006186278527715773371608839031405611473808626602570518694310896630839794field,
  c2: 7905567122759533570302126001762943316506837083107534363619137121591430247813field
}"

# Result
#  {
#   c1: 8382652612567042214492403753719299065156905393912387035871137815124637126753field,
#   c2: 7597951025613609547169088091808543498720626840350081699542403411289273624058field
# }

3. Decrypt to get result

leo run decrypt "{
  c1: 8382652612567042214492403753719299065156905393912387035871137815124637126753field,
  c2: 7597951025613609547169088091808543498720626840350081699542403411289273624058field
}" 5field

# Result
# 6field <- multiplying the ciphertexts multiplies the plaintexts

Build Guide

To compile this Aleo program, run:

snarkvm build

To execute this Aleo program, run:

snarkvm run hello

leo run get_pub_key 5field