The Paillier cryptosystem supports homomorphic encryption, where two encrypted values can be added, subtracted and scalar multiplied and the decryption of the result gives the result. In this case we will use 1,024 bit prime numbers for \(p\) and \(q\) and thus produce a modulus with 2,048 bits (\(n=pq\)).
First Principles Paillier Add, Scalar Multiply and Subtraction |
Background
First we select two large prime numbers (\(p\) and \(q\)) and compute:
\(n=pq\)
\(\varphi=(p-1)(q-1)\)
\( \lambda =\operatorname {lcm} {\varphi} \)
and where lcm is the least common multiple. We then select random integer \(g\) for:
\( \displaystyle g \in \mathbb {Z} _{n^{2}}^{*} \)
We must make sure that \(n\) divides the order of \(g\) by checking the following:
\( \mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}\)
and where \(L\) is defined as \(L(x)=\frac {x-1}{n}\). The public key is \((n ,g)\) and the private key is \((\lambda ,\mu )\).
To encrypt a message (\(M\)), we select a random \(r\) value and compute the ciphertext of:
\(c=g^{m}\cdot r^{n} \pmod {n^{2}}\)
and then to decrypt:
\(m=L(c^{\lambda }{\bmod n}^{2})\cdot \mu {\pmod n} \)
Adding and scalar multiply
If we take two ciphers (\(C_1\) and \(C_2\)), we get:
\(C_1 = g^{m_1}\cdot r_1^{n} \pmod {n^{2}} \)
\(C_2 = g^{m_2}\cdot r_2^{n} \pmod {n^{2}} \)
If we now multiply them we get:
\(C_1 \cdot C_2 = g^{m_1}\cdot r_1^{n} \cdot g^{m_2}\cdot r_2^{n} \pmod {n^{2}}\)
\(C_1 \cdot C_2 = g^{m_1+m_2}\cdot r_1^{n} \cdot r_2^{n} \pmod {n^{2}}\)
And we adding two values requires a multiplication of the ciphers.
Subtract
If we take two ciphers (\(C_1\) and \(C_2\)), we get:
\(C_1 = g^{m_1}\cdot r_1^{n} \pmod {n^{2}} \)
\(C_2 = g^{m_2}\cdot r_2^{n} \pmod {n^{2}} \)
If we now divide them we get:
\(\frac{C_1} {C_2} = \frac{ g^{m_1}\cdot r_1^{n}}{g^{m_2}\cdot r_2^{n}} \pmod {n^{2}} \)
\(\frac{C_1} {C_2} = g^{m_1-m_2} \frac{r_1^{n}}{r_2^{n}} \pmod {n^{2}} \)
And thus a subtraction is equivalent to a divide operation. For this we perform a modular divide operation.
inv_cipher2, _ := crypto.Inv(cipher2, pub.N2)
and which is:
\(C_2^{-1} = \textrm{InverseMod}(C_2,n^2)\)
What we also need to do, is perform this operation when the result is greater than a given threshold:
\(m = m - n\)
Code
The basic data structures for the secret key, public key and ciphertext is:
type ( PublicKey struct { N *big.Int N2 *big.Int } SecretKey struct { PublicKey Lambda *big.Int Totient *big.Int U *big.Int } Ciphertext *big.Int )
The adding of ciphertext values is achieved through a multiplication of our big integer ciphertext values \(c=a \cdot b \pmod {n^2}\):
func add(pk PublicKey, a Ciphertext, b Ciphertext) Ciphertext { c := new(big.Int).Mul(a, b) return (new(big.Int).Mod(c, pk.N2)) }
When we multiply two Paillier ciphertext's, we actually use an exponenent function, and where \(Mult(a, c) -> c^a \mod n\)
func mul(a, c, m *big.Int) *big.Int { z := new(big.Int).Exp(c, a, m) return (z) }
When we need to multiply two big integers we do it using a mod operator:
func Mul(x, y, m *big.Int) *big.Int { z := new(big.Int).Mul(x, y) return z.Mod(z, m) }
The inverse mod is used in the subtraction operation, and is implemented as:
func Inv(x, m *big.Int) *big.Int { z := new(big.Int).ModInverse(x, m) return (z) }
To encrypt the values, we create a random nonce (\(r\)) and then compute:
\( \mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}\)
and where \(L\) is defined as \(L(x)=\frac {x-1}{n}\). The public key is \((n ,g)\) and the private key is \((\lambda ,\mu )\).
To encrypt a message (\(M\)), we select a random \(r\) value and compute the ciphertext of:
\(c=g^{m}\cdot r^{n} \pmod {n^{2}}\)
This is implemented as:
func encrypt(pk PublicKey, msg *big.Int) *big.Int { r, _ := core.Rand(pk.N) a := new(big.Int).Add(pk.N, core.One) a.Exp(a, msg, pk.N2) b := new(big.Int).Exp(r, pk.N, pk.N2) // b = r^N (mod N^2) // ciphertext = a*b = (N+1)^m * r^N (mod N^2) c := Mul(a, b, pk.N2) return c } func L(n, x *big.Int) *big.Int { // (x - 1) / n b := new(big.Int).Sub(x, big.NewInt(1)) return b.Div(b, n) }
To decrypt:
func decrypt(sk SecretKey, c *big.Int) *big.Int { // a ≡ c^{lambda(N)} mod N^2 a := new(big.Int).Exp(c, sk.Lambda, sk.N2) // l = L(ɑ, N) ell := L(sk.N, a) // m ≡ lu = L(ɑ)*u = L(c^{λ(N)})*u mod N m := Mul(ell, sk.U, sk.N) return m }
Coding
The outline coding using the library from the Kryptography library. We have manually added the public and secret key, but in real-life we would generate with:
pub, sec, _ := paillier.NewKeys()
The code is:
package main import ( "fmt" "math/big" "os" "github.com/coinbase/kryptology/pkg/core" ) type ( PublicKey struct { N *big.Int N2 *big.Int } SecretKey struct { PublicKey Lambda *big.Int Totient *big.Int U *big.Int } Ciphertext *big.Int ) func add(pk PublicKey, a Ciphertext, b Ciphertext) Ciphertext { c := new(big.Int).Mul(a, b) return (new(big.Int).Mod(c, pk.N2)) } func encrypt(pk PublicKey, msg *big.Int) *big.Int { r, _ := core.Rand(pk.N) a := new(big.Int).Add(pk.N, core.One) a.Exp(a, msg, pk.N2) b := new(big.Int).Exp(r, pk.N, pk.N2) // b = r^N (mod N^2) // ciphertext = a*b = (N+1)^m * r^N (mod N^2) c := Mul(a, b, pk.N2) return c } func L(n, x *big.Int) *big.Int { // (x - 1) / n b := new(big.Int).Sub(x, big.NewInt(1)) return b.Div(b, n) } func decrypt(sk SecretKey, c *big.Int) *big.Int { // a ≡ c^{lambda(N)} mod N^2 a := new(big.Int).Exp(c, sk.Lambda, sk.N2) // l = L(ɑ, N) ell := L(sk.N, a) // m ≡ lu = L(ɑ)*u = L(c^{λ(N)})*u mod N m := Mul(ell, sk.U, sk.N) return m } func Mul(x, y, m *big.Int) *big.Int { z := new(big.Int).Mul(x, y) return z.Mod(z, m) } func Inv(x, m *big.Int) *big.Int { z := new(big.Int).ModInverse(x, m) return (z) } func mul(a, c, m *big.Int) *big.Int { z := new(big.Int).Exp(c, a, m) return (z) } func setupKeys(sec *SecretKey, pub *PublicKey) { pub.N, _ = new(big.Int).SetString("22203902867524505059996239340306362808852805402888214954381553003002718752808306965243974655390219346481612755387890570991182385566928749760445875916800573782909761881261515602762049819293013811136510263722491329215251675663091154175860620927146517652389408089110716148633480085801107700968384078929774277970426932561081560231010426294975678729992804063220974701278229766883426991469078323539488917623430196595127834729964807458110080684240115196595760172158113810254192728271785178985307185853395355962836026777351498860874006114137632167254987479651229489157192247478252351962954320801263428208801271515398015887801", 10) pub.N2 = new(big.Int).Mul(pub.N, pub.N) sec.N = pub.N sec.N2 = pub.N2 sec.Lambda, _ = new(big.Int).SetString("11101951433762252529998119670153181404426402701444107477190776501501359376404153482621987327695109673240806377693945285495591192783464374880222937958400286891454880940630757801381024909646506905568255131861245664607625837831545577087930310463573258826194704044555358074316740042900553850484192039464887138985064438949068643503538028104882092520753872226183177268421975002892541203962036580811698912148170624870917841537346985483337432253649017635885024033744586145456966646545432316660152135614842196027111652507352356170725302821683928442675667004336523805058723372589095589316741830468728743532156406225121890756346", 10) sec.Totient, _ = new(big.Int).SetString("22203902867524505059996239340306362808852805402888214954381553003002718752808306965243974655390219346481612755387890570991182385566928749760445875916800573782909761881261515602762049819293013811136510263722491329215251675663091154175860620927146517652389408089110716148633480085801107700968384078929774277970128877898137287007076056209764185041507744452366354536843950005785082407924073161623397824296341249741835683074693970966674864507298035271770048067489172290913933293090864633320304271229684392054223305014704712341450605643367856885351334008673047610117446745178191178633483660937457487064312812450243781512692", 10) sec.U, _ = new(big.Int).SetString("11108720355657041776647490476262423100273444107890028034525926371450220865341816894255404548947647952186614924131107824022774134150177636593890919577479093776330856863330832621779073688637362125712752218152358601679371477743308049274665882845748928958872854339383876978533793119837835146167726752137945969833510158025058440018805812646143848801020667307117190186323497007267362203459968413761903710129427082211518450427328378521338965975284389455704146581178957343955351641425309976491396722227064973929033480821132777267246266490713852090985090755453080857556125803448778856380844874040092451545474091429770838805", 10) } func main() { var sec SecretKey var pub PublicKey // pub, sec, _ := paillier.NewKeys() setupKeys(&sec, &pub) v1 := "223" v2 := "224" argCount := len(os.Args[1:]) if argCount > 0 { v1 = os.Args[1] } if argCount > 1 { v2 = os.Args[2] } val1, _ := new(big.Int).SetString(v1, 10) val2, _ := new(big.Int).SetString(v2, 10) cipher1 := encrypt(pub, val1) cipher2 := encrypt(pub, val2) // Adding cipher3 := add(pub, cipher1, cipher2) decrypted1 := decrypt(sec, cipher3) // Subtraction inv_cipher2 := Inv(cipher2, pub.N2) cipher4 := add(pub, cipher1, inv_cipher2) decrypted2 := decrypt(sec, cipher4) // Multiply cipher5 := mul(val1, cipher2, pub.N2) decrypted3 := decrypt(sec, cipher5) fmt.Printf("\na=%s, b=%s\n", val1, val2) fmt.Printf("\nEnc(a)=%v, Enc(b)=%v\n", cipher1, cipher2) fmt.Printf("\n%s + %s = %s\n", val1, val2, decrypted1) fmt.Printf("\n%s * %s = %s\n", val1, val2, decrypted3) if decrypted2.Cmp(new(big.Int).Div(pub.N, big.NewInt(2))) > 0 { // m = m - n fmt.Printf("%s - %s = %s\n", val1, val2, new(big.Int).Sub(decrypted2, pub.N)) } else { fmt.Printf("%s - %s = %s\n", val1, val2, decrypted2) } }
A sample run is:
a=222, b=111 Enc(a)=480255181920800962319428195982635686810088385894694335732539232950598802361655578994299473947015823706085641632265918920177271050935899445772018657379409917340875585795573456622928011108763896998310685496049348635361148476665982292583742521662892246510134496910480985230953608457374596556061690681311372035369557473453948571498287540563940498719457037028423196712497593060402292462158152772365096268526544613966053669489002176306136618535389523393860906046429497082997574262450762786531668654114069457095304276136300381237935928488169886100022455673772985830484439920173220489954345908504730126607166660669616837735331132127595030555268828556190724381620586303349525363142824926041003132666363188063124075469384544768925327914082583686275806308821004655253016048332888033533857446684327464728753575758198032289396001937677420421304213675660776816637709884428865855227219223951888611467829806312828381700124791746116297756951418091223465584531827315766709832802225806892686198418948109322860207792492578901690557854559299736849385819889486069503912193322571436752435739403077721769655830857694261861731325926243758449255964430155072325622086559490250784450951299715352393589113643733050357885271539548238790965835016548892755681491217, Enc(b)=398205057005000805455412925833532994717615194020655376461633849479054914228469584412356182413073212222229225897995778310285802001620224215672510848280476816560246933598044438129822536195476471730535502177390452652250248208595245774868663210615963412562038409604119717517734532923327183494024965696228498538639558086901827119637452112502647978827481995866363495625837621647623546620410500086811780489366824575093690909960314240825269897595801111438023076383121529088191656996666295497574395828609506976835480393272407009883660101408839186236877371208967820363921744294119034984338166756418022949781351180172422781584254651807677632253283134440525408418041260953938375203226980802190306068235344987804712672397597944426532987481662630428128948672757884566423914969203583167323575075335034411157347418887682930435526342638719818198078786738032388166189020743344542420574023931557754426969505264962187883070184429059626960626546411313341199020568060067512561944206262699174908858448584688032887324374515251373912574173526824962194722293602736606882903604170107467326730803713106312324982828292317687693528819441737056014833346488071437353342607272253728630007825092500186949850603988095382717600780136544280866381494593592289423116839401 222 + 111 = 333 222 * 111 = 24642 222 - 111 = 111