The Paillier cryptosystem supports homomorphic encryption, where two encrypted values can be added or one value can be 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\)).
Paillier Adding and Scalar Multiplying with Kryptology |
Background
First we select two large prime numbers (\(p\) and \(q\)) and compute:
\(n=pq\)
\(PHI=(p-1)(q-1)\)
\( \lambda =\operatorname {lcm} {(p-1,q-1)} \)
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.
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/paillier" ) func main() { var sec paillier.SecretKey var pub paillier.PublicKey // pub, sec, _ := paillier.NewKeys() 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) // fmt.Printf("Pub N: %v\n", pub.N) // fmt.Printf("Pub N2: %v\n", pub.N2) // fmt.Printf("Sec: Lambda: %v\n", sec.Lambda) // fmt.Printf("Sec: Totient: %v\n", sec.Totient) // fmt.Printf("U: %v\n", sec.U) v1 := "111" v2 := "123" 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, c1, _ := pub.Encrypt(val1) cipher2, c2, _ := pub.Encrypt(val2) cipher3, _ := pub.Add(cipher1, cipher2) cipher4, _ := pub.Mul(val1, cipher2) decrypted1, _ := sec.Decrypt(cipher3) decrypted2, _ := sec.Decrypt(cipher4) fmt.Printf("\na=%s, b=%s\n", val1, val2) fmt.Printf("\nEnc(a)=%v, Enc(b)=%v\n", c1, c2) fmt.Printf("%s + %s = %s\n", val1, val2, decrypted1) fmt.Printf("%s * %s = %s\n", val1, val2, decrypted2) }
A sample run is:
a=99, b=101 Enc(a)=3194871588628358748966290700084048039504351559895566068649699226686196823202719691848442538154334259086870718517154309238960535353238124681826437650609974756182111331187136550288888243913621355453394195988893907331662212619099956597214048344379155251813838360379613014234504733115070813852665958338054399570730908960729062476752496268730534679455242536966348295264398620170743424134258798655234402342376007577814664497900979829030250365742441838215291615628708192832598514895136556284052555200143916946043349922329083954234944551751946938497382693177826236713968527218819113690486875483513214352456619925368986523829, Enc(b)=13589527499232325752634778817851281121651040055415530301574438693923234689704613260352777781803577016195096649735936270615387802707921560074089079322940073435224175548073476004757540792879509712875530692314042199000397816797600039616264877447516437328780537103533071545942061490755982844224226236302168781174648600938374827556758739664948513788576346004713439291103166197919603791687898854044026637077370502518171971262488604799791153729247987748432317839412374043015668538315916284242023004655533679040068212527422566840965831377168708156964822692509744524741001528815590877128498757010895632375885634162380520158219 99 + 101 = 200 99 * 101 = 9999