In A World Of Privacy: The Time Has Come For Paillier Encryption To Step Forward

In A World Of Privacy: The Time Has Come For Paillier Encryption To Step Forward

The number of single-author papers is very low these days, but there is one paper from the past that is really making an impact in the world of cybersecurity [here]:

Overall, it has been a slow burner:

The reason that Paillier has not had a massive impact on public-key systems is that RSA and ECC have cornered the market for public-key encryption. But, we now see the rise of homomorphic encryption, and where we can operate on encrypted values in an arithmetic way. Unfortunately, RSA and ECC are not really set up for these types of operations, and the current full homomorphic encryption (FHE) methods are just so slow. So, in steps the Paillier method with its partial homomorphic encryption (PHE) methods. While it only does add/subtract and scalar multiply, it fits into many privacy-preserving use cases. For example, we could implement a COVID-19 tracking application by taking encrypted time stamps, and then determining the difference between them, without revealing each timestamp.

Key generation

For key generation, we create a public key (g,N) and a private key (λ,μ). The method is [here]:

The code for this is [here]:

package main

import (
 "crypto/rand"
 "fmt"
 "math/big"
 "os"
 "strconv"
)

type PalPublicKey struct {
 N  *big.Int
 g  *big.Int
 N2 *big.Int
}

var oneBig = new(big.Int).SetInt64(1)

func Phi(x, y *big.Int) *big.Int {
 p := new(big.Int).Sub(x, oneBig)
 q := new(big.Int).Sub(y, oneBig)
 return new(big.Int).Mul(p, q)
}

type PalPrivateKey struct {
 mu     *big.Int
 lambda *big.Int
 pk     *PalPublicKey
}

func getPrime(no_bits int) *big.Int {
 p, _ := rand.Prime(rand.Reader, no_bits)
 return p
}
func NewKeys(bitlen int) (*PalPublicKey, *PalPrivateKey, error) {

p := getPrime(bitlen / 2)
 q := getPrime(bitlen / 2)

n := new(big.Int).Mul(p, q)
 nn := new(big.Int).Mul(n, n)

lambda := Phi(p, q)
 mu := new(big.Int).ModInverse(lambda, n)
 g := new(big.Int).Add(n, oneBig)

pk := &PalPublicKey{
  N:  n,
  g:  g,
  N2: nn,
 }

sk := &PalPrivateKey{
  mu:     mu,
  lambda: lambda,
  pk:     pk,
 }

return pk, sk, nil
}

func main() {

argCount := len(os.Args[1:])

no_bits := int(1024)

if argCount > 0 {
  no_bits, _ = strconv.Atoi(os.Args[1])
 }

pk, sk, _ := NewKeys(no_bits)

fmt.Printf("Paillier Key Size: %d\n",no_bits)
 fmt.Printf("\n==== Generating private key ===\n")
 fmt.Printf("Lambda=%s\n\nMu=%s\n\n", sk.lambda, sk.mu)

fmt.Printf("==== Generating public key ===\n")
 fmt.Printf("g=%s\n\nN=%s\n\nN^2=%s", pk.N, pk.g, pk.N2)

}

and a sample run [here]:

Paillier Key Size: 1024

==== Generating private key ===
Lambda=117962190498172878925511010040842443358789874904899704498556492799778947530352960647607934645953430416491868244722104948311762669996035551198440895420764308007743533891361941828036014206149022330025209841714944592980600785324488954945674235644515832039956106858907941973125400787706086687207661972619905325000

Mu=85543750197004163717221835565775322801690176679453655074628570323830350797386395038329367992789888238342862148064220511513823781001549918800950971406265247068042083881386133410308322469303627573484526297590139804912344365845354289301717338242620236620518139641704593316286721893330274019259475547143467362906

==== Generating public key ===
g=117962190498172878925511010040842443358789874904899704498556492799778947530352960647607934645953430416491868244722104948311762669996035551198440895420764329738563327763993701792816736110947376638958050928535269054420030230394401527390718250825163476022956120295048997265219711884499563885911539998653927949671

N=117962190498172878925511010040842443358789874904899704498556492799778947530352960647607934645953430416491868244722104948311762669996035551198440895420764329738563327763993701792816736110947376638958050928535269054420030230394401527390718250825163476022956120295048997265219711884499563885911539998653927949672

N^2=13915078387127227841492468523991379969145003599237060912663799823083900137067659455999290015916082170041712643124458262756105225210323842258380845803575767947654976729584597398368714425403134875561050311112351663919199268612081960003053920228476978934198777743216097019574274011870952175825819836677967661105994926549761087196219797028667631283811211889649609270074787513283969988075940839915211710361361607859238517192312402444737019247638131663231471569935992340106065801615600411303409653447850115311162521236746621908327655763866090749654565744153473650918190744970135399226752383569461431968116644676917909008241

Encryption and Decryption

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). To encrypt and decrypt [here]:

And to add and scalar multiply [here]:

and to subtract [here]:

You can try these methods out here:

https://asecuritysite.com/paillier/pail03

Conclusions

And there you go. A method that is fit for a world of privacy. If you want to learn more about the Paillier method, try here:

https://asecuritysite.com/paillier

Overall, the method is used within the Coinbase Krytology library, and you can find out more about this here:

https://asecuritysite.com/kryptology/