Homomorphic Encryption Schemes
Homomorphic encryption allows computation on encrypted data without decryption, enabling privacy-preserving computations.
Core Idea
Homomorphic Encryption (HE) enables operations on ciphertexts that correspond to operations on plaintexts:
$$\text{Decrypt}(E(m_1) \odot E(m_2)) = m_1 \circ m_2$$
where:
- $E(m)$ is the encryption of message $m$
- $\odot$ is an operation on ciphertexts
- $\circ$ is the corresponding operation on plaintexts
Types:
- Partially Homomorphic (PHE): Supports one operation (addition OR multiplication)
- Somewhat Homomorphic (SHE): Supports limited operations
- Fully Homomorphic (FHE): Supports arbitrary computations
Paillier Cryptosystem (Additive Homomorphic)
Core Idea: Supports addition of encrypted values and multiplication by plaintext constants.
Mathematical Foundation:
- Key Generation:
- Choose primes $p, q$, compute $n = pq$, $\lambda = \text{lcm}(p-1, q-1)$
- Public key: $(n, g)$ where $g \in \mathbb{Z}_{n^2}^*$
- Private key: $\lambda$
- Encryption: $E(m) = g^m \cdot r^n \bmod n^2$ where $r \in \mathbb{Z}_n^*$ is random
- Decryption: $m = \frac{L(c^\lambda \bmod n^2)}{L(g^\lambda \bmod n^2)} \bmod n$ where $L(x) = \frac{x-1}{n}$
- Homomorphic Addition: $E(m_1) \cdot E(m_2) = E(m_1 + m_2)$
- Homomorphic Scalar Multiplication: $E(m)^k = E(k \cdot m)$
Go Implementation
1package main
2
3import (
4 "crypto/rand"
5 "fmt"
6 "math/big"
7)
8
9type Paillier struct {
10 n, n2, g, lambda *big.Int
11}
12
13func NewPaillier(bits int) (*Paillier, error) {
14 // Generate primes
15 p, err := rand.Prime(rand.Reader, bits/2)
16 if err != nil {
17 return nil, err
18 }
19 q, err := rand.Prime(rand.Reader, bits/2)
20 if err != nil {
21 return nil, err
22 }
23
24 // Compute n = p * q
25 n := new(big.Int).Mul(p, q)
26 n2 := new(big.Int).Mul(n, n)
27
28 // Compute lambda = lcm(p-1, q-1)
29 p1 := new(big.Int).Sub(p, big.NewInt(1))
30 q1 := new(big.Int).Sub(q, big.NewInt(1))
31 lambda := new(big.Int).Div(
32 new(big.Int).Mul(p1, q1),
33 new(big.Int).GCD(nil, nil, p1, q1),
34 )
35
36 // Choose g = n + 1 (simplified)
37 g := new(big.Int).Add(n, big.NewInt(1))
38
39 return &Paillier{
40 n: n,
41 n2: n2,
42 g: g,
43 lambda: lambda,
44 }, nil
45}
46
47func (p *Paillier) Encrypt(m *big.Int) (*big.Int, error) {
48 // Generate random r
49 r, err := rand.Int(rand.Reader, p.n)
50 if err != nil {
51 return nil, err
52 }
53
54 // E(m) = g^m * r^n mod n^2
55 gm := new(big.Int).Exp(p.g, m, p.n2)
56 rn := new(big.Int).Exp(r, p.n, p.n2)
57
58 ciphertext := new(big.Int).Mod(
59 new(big.Int).Mul(gm, rn),
60 p.n2,
61 )
62
63 return ciphertext, nil
64}
65
66func (p *Paillier) Decrypt(c *big.Int) (*big.Int, error) {
67 // L(c^lambda mod n^2) / L(g^lambda mod n^2) mod n
68 clambda := new(big.Int).Exp(c, p.lambda, p.n2)
69 glambda := new(big.Int).Exp(p.g, p.lambda, p.n2)
70
71 Lc := new(big.Int).Div(
72 new(big.Int).Sub(clambda, big.NewInt(1)),
73 p.n,
74 )
75 Lg := new(big.Int).Div(
76 new(big.Int).Sub(glambda, big.NewInt(1)),
77 p.n,
78 )
79
80 // Compute modular inverse of Lg
81 LgInv := new(big.Int).ModInverse(Lg, p.n)
82
83 plaintext := new(big.Int).Mod(
84 new(big.Int).Mul(Lc, LgInv),
85 p.n,
86 )
87
88 return plaintext, nil
89}
90
91// Homomorphic addition: E(m1) * E(m2) = E(m1 + m2)
92func (p *Paillier) Add(c1, c2 *big.Int) *big.Int {
93 return new(big.Int).Mod(
94 new(big.Int).Mul(c1, c2),
95 p.n2,
96 )
97}
98
99// Homomorphic scalar multiplication: E(m)^k = E(k * m)
100func (p *Paillier) ScalarMult(c *big.Int, k *big.Int) *big.Int {
101 return new(big.Int).Exp(c, k, p.n2)
102}
103
104func main() {
105 paillier, err := NewPaillier(512)
106 if err != nil {
107 panic(err)
108 }
109
110 // Encrypt two values
111 m1 := big.NewInt(42)
112 m2 := big.NewInt(17)
113
114 c1, _ := paillier.Encrypt(m1)
115 c2, _ := paillier.Encrypt(m2)
116
117 // Homomorphic addition
118 cSum := paillier.Add(c1, c2)
119 sum, _ := paillier.Decrypt(cSum)
120 fmt.Printf("Encrypted: %d + %d = %d\n", m1.Int64(), m2.Int64(), sum.Int64())
121
122 // Homomorphic scalar multiplication
123 cMult := paillier.ScalarMult(c1, big.NewInt(3))
124 mult, _ := paillier.Decrypt(cMult)
125 fmt.Printf("Encrypted: %d * 3 = %d\n", m1.Int64(), mult.Int64())
126}
ElGamal Cryptosystem (Multiplicative Homomorphic)
Core Idea: Supports multiplication of encrypted values.
Mathematical Foundation:
- Key Generation:
- Choose cyclic group $G$ with generator $g$ and order $q$
- Private key: $x \in \mathbb{Z}_q$
- Public key: $h = g^x$
- Encryption: $E(m) = (g^r, m \cdot h^r)$ where $r \in \mathbb{Z}_q$ is random
- Decryption: $m = \frac{c_2}{c_1^x} = \frac{m \cdot h^r}{g^{rx}} = \frac{m \cdot g^{rx}}{g^{rx}} = m$
- Homomorphic Multiplication: $E(m_1) \cdot E(m_2) = (g^{r_1+r_2}, m_1 m_2 \cdot h^{r_1+r_2}) = E(m_1 \cdot m_2)$
Go Implementation
1package main
2
3import (
4 "crypto/rand"
5 "fmt"
6 "math/big"
7)
8
9type ElGamal struct {
10 p, g, q *big.Int // p is prime, g is generator, q is order
11 x, h *big.Int // x is private key, h = g^x is public key
12}
13
14func NewElGamal(bits int) (*ElGamal, error) {
15 // Generate safe prime p = 2q + 1
16 var p, q, g *big.Int
17 for {
18 q, _ = rand.Prime(rand.Reader, bits-1)
19 p = new(big.Int).Add(
20 new(big.Int).Mul(q, big.NewInt(2)),
21 big.NewInt(1),
22 )
23 if p.ProbablyPrime(20) {
24 break
25 }
26 }
27
28 // Find generator g
29 g = big.NewInt(2)
30 for {
31 if new(big.Int).Exp(g, q, p).Cmp(big.NewInt(1)) == 0 {
32 break
33 }
34 g.Add(g, big.NewInt(1))
35 }
36
37 // Generate private key
38 x, err := rand.Int(rand.Reader, q)
39 if err != nil {
40 return nil, err
41 }
42
43 // Compute public key
44 h := new(big.Int).Exp(g, x, p)
45
46 return &ElGamal{
47 p: p,
48 g: g,
49 q: q,
50 x: x,
51 h: h,
52 }, nil
53}
54
55type Ciphertext struct {
56 c1, c2 *big.Int
57}
58
59func (eg *ElGamal) Encrypt(m *big.Int) (*Ciphertext, error) {
60 // Generate random r
61 r, err := rand.Int(rand.Reader, eg.q)
62 if err != nil {
63 return nil, err
64 }
65
66 // E(m) = (g^r, m * h^r)
67 c1 := new(big.Int).Exp(eg.g, r, eg.p)
68 hr := new(big.Int).Exp(eg.h, r, eg.p)
69 c2 := new(big.Int).Mod(
70 new(big.Int).Mul(m, hr),
71 eg.p,
72 )
73
74 return &Ciphertext{c1: c1, c2: c2}, nil
75}
76
77func (eg *ElGamal) Decrypt(ct *Ciphertext) *big.Int {
78 // m = c2 / (c1^x)
79 c1x := new(big.Int).Exp(ct.c1, eg.x, eg.p)
80 c1xInv := new(big.Int).ModInverse(c1x, eg.p)
81
82 m := new(big.Int).Mod(
83 new(big.Int).Mul(ct.c2, c1xInv),
84 eg.p,
85 )
86
87 return m
88}
89
90// Homomorphic multiplication: E(m1) * E(m2) = E(m1 * m2)
91func (eg *ElGamal) Multiply(ct1, ct2 *Ciphertext) *Ciphertext {
92 c1 := new(big.Int).Mod(
93 new(big.Int).Mul(ct1.c1, ct2.c1),
94 eg.p,
95 )
96 c2 := new(big.Int).Mod(
97 new(big.Int).Mul(ct1.c2, ct2.c2),
98 eg.p,
99 )
100 return &Ciphertext{c1: c1, c2: c2}
101}
102
103func main() {
104 elgamal, err := NewElGamal(512)
105 if err != nil {
106 panic(err)
107 }
108
109 // Encrypt two values
110 m1 := big.NewInt(42)
111 m2 := big.NewInt(17)
112
113 ct1, _ := elgamal.Encrypt(m1)
114 ct2, _ := elgamal.Encrypt(m2)
115
116 // Homomorphic multiplication
117 ctMult := elgamal.Multiply(ct1, ct2)
118 mult := elgamal.Decrypt(ctMult)
119 fmt.Printf("Encrypted: %d * %d = %d\n", m1.Int64(), m2.Int64(), mult.Int64())
120}
BGV/BFV (Somewhat Homomorphic)
Core Idea: Ring Learning With Errors (RLWE) based scheme supporting addition and multiplication with noise management.
Mathematical Foundation:
- Operates on polynomials in ring $R_q = \mathbb{Z}_q /(X^n + 1)$
- Key Generation:
- Secret key: $s \in R_q$ (small coefficients)
- Public key: $(a, b = -a \cdot s + e)$ where $a$ is random, $e$ is small error
- Encryption: $E(m) = (u, v)$ where $u = a \cdot r + e_1$, $v = b \cdot r + e_2 + m$
- Decryption: $m = v + u \cdot s \bmod q$
- Homomorphic Operations:
- Addition: component-wise addition
- Multiplication: polynomial multiplication with relinearization
Go Implementation (Simplified)
1package main
2
3import (
4 "crypto/rand"
5 "fmt"
6 "math/big"
7)
8
9// Simplified BGV for demonstration
10type BGV struct {
11 n int // polynomial degree
12 q *big.Int // modulus
13 t *big.Int // plaintext modulus
14}
15
16type BGVKey struct {
17 sk []*big.Int // secret key (polynomial)
18 pk [][]*big.Int // public key
19}
20
21type BGVCiphertext struct {
22 c0, c1 []*big.Int // polynomial coefficients
23}
24
25func NewBGV(n int, qBits int) *BGV {
26 q, _ := rand.Prime(rand.Reader, qBits)
27 t := big.NewInt(2) // binary plaintext space
28
29 return &BGV{
30 n: n,
31 q: q,
32 t: t,
33 }
34}
35
36func (bgv *BGV) KeyGen() *BGVKey {
37 // Generate secret key (small coefficients)
38 sk := make([]*big.Int, bgv.n)
39 for i := range sk {
40 sk[i], _ = rand.Int(rand.Reader, big.NewInt(3))
41 sk[i].Sub(sk[i], big.NewInt(1)) // -1, 0, or 1
42 }
43
44 // Generate public key
45 pk := make([][]*big.Int, 2)
46 pk[0] = make([]*big.Int, bgv.n)
47 pk[1] = make([]*big.Int, bgv.n)
48
49 // a is random
50 for i := range pk[0] {
51 pk[0][i], _ = rand.Int(rand.Reader, bgv.q)
52 }
53
54 // b = -a * s + e (simplified, no error for demo)
55 pk[1] = bgv.polyMul(pk[0], sk)
56 bgv.polyNeg(pk[1])
57
58 return &BGVKey{sk: sk, pk: pk}
59}
60
61func (bgv *BGV) Encrypt(key *BGVKey, m *big.Int) *BGVCiphertext {
62 // Generate random r and errors
63 r := make([]*big.Int, bgv.n)
64 for i := range r {
65 r[i], _ = rand.Int(rand.Reader, big.NewInt(2))
66 }
67
68 // u = a * r
69 u := bgv.polyMul(key.pk[0], r)
70 bgv.polyMod(u, bgv.q)
71
72 // v = b * r + m
73 v := bgv.polyMul(key.pk[1], r)
74 bgv.polyMod(v, bgv.q)
75
76 // Add message (scalar)
77 if m.Int64() == 1 {
78 v[0].Add(v[0], big.NewInt(1))
79 }
80 bgv.polyMod(v, bgv.q)
81
82 return &BGVCiphertext{c0: u, c1: v}
83}
84
85func (bgv *BGV) Decrypt(key *BGVKey, ct *BGVCiphertext) *big.Int {
86 // m = v + u * s mod q mod t
87 us := bgv.polyMul(ct.c0, key.sk)
88 bgv.polyMod(us, bgv.q)
89
90 m := new(big.Int).Add(ct.c1[0], us[0])
91 m.Mod(m, bgv.q)
92 m.Mod(m, bgv.t)
93
94 return m
95}
96
97// Homomorphic addition
98func (bgv *BGV) Add(ct1, ct2 *BGVCiphertext) *BGVCiphertext {
99 c0 := make([]*big.Int, bgv.n)
100 c1 := make([]*big.Int, bgv.n)
101
102 for i := 0; i < bgv.n; i++ {
103 c0[i] = new(big.Int).Add(ct1.c0[i], ct2.c0[i])
104 c1[i] = new(big.Int).Add(ct1.c1[i], ct2.c1[i])
105 }
106
107 bgv.polyMod(c0, bgv.q)
108 bgv.polyMod(c1, bgv.q)
109
110 return &BGVCiphertext{c0: c0, c1: c1}
111}
112
113// Helper functions
114func (bgv *BGV) polyMul(a, b []*big.Int) []*big.Int {
115 result := make([]*big.Int, bgv.n)
116 for i := range result {
117 result[i] = big.NewInt(0)
118 }
119
120 for i := 0; i < bgv.n; i++ {
121 for j := 0; j < bgv.n; j++ {
122 idx := (i + j) % bgv.n
123 if i+j >= bgv.n {
124 // Handle X^n = -1
125 result[idx].Sub(result[idx], new(big.Int).Mul(a[i], b[j]))
126 } else {
127 result[idx].Add(result[idx], new(big.Int).Mul(a[i], b[j]))
128 }
129 }
130 }
131
132 return result
133}
134
135func (bgv *BGV) polyNeg(p []*big.Int) {
136 for i := range p {
137 p[i].Neg(p[i])
138 }
139}
140
141func (bgv *BGV) polyMod(p []*big.Int, mod *big.Int) {
142 for i := range p {
143 p[i].Mod(p[i], mod)
144 }
145}
146
147func main() {
148 bgv := NewBGV(8, 128) // Small parameters for demo
149 key := bgv.KeyGen()
150
151 // Encrypt two values
152 m1 := big.NewInt(1)
153 m2 := big.NewInt(1)
154
155 ct1 := bgv.Encrypt(key, m1)
156 ct2 := bgv.Encrypt(key, m2)
157
158 // Homomorphic addition
159 ctSum := bgv.Add(ct1, ct2)
160 sum := bgv.Decrypt(key, ctSum)
161 fmt.Printf("Encrypted: %d + %d = %d\n", m1.Int64(), m2.Int64(), sum.Int64())
162}
Use Cases
- Privacy-Preserving Machine Learning: Train models on encrypted data
- Secure Aggregation: Compute statistics on encrypted datasets
- Private Information Retrieval: Query databases without revealing queries
- Secure Voting: Tally votes without revealing individual votes
- Cloud Computing: Process encrypted data in untrusted environments
Performance Considerations
- PHE (Paillier/ElGamal): Fast, but limited operations
- SHE (BGV/BFV): Moderate performance, limited depth
- FHE: Slow, but supports arbitrary computations
Trade-offs:
- Security vs. Performance
- Ciphertext size vs. Computation depth
- Key size vs. Security level
Related Snippets
- Asymmetric Encryption & Key Exchange
Asymmetric (public-key) cryptography with mathematical foundations, including … - Cryptographic Hash Functions
Cryptographic hash functions with mathematical properties and practical … - Digital Signatures
Digital signature algorithms with mathematical foundations. Mathematical … - Encrypt/Decrypt with Key Pairs
Encrypt and decrypt data using public/private key pairs and derive symmetric … - Generate Public/Private Key Pairs
Generate public/private key pairs on Linux for various cryptographic purposes. … - Hash and Sign Text with Key Pairs
Hash and digitally sign text using public/private key pairs. Hash Text (OpenSSL) … - Key Derivation Functions
Key Derivation Functions (KDFs) for password hashing and key derivation. … - Key Sharding (Secret Sharing)
Key sharding splits a secret into multiple shares where a threshold of shares is … - Multi-Signature (Multisig) Schemes
Multi-signature schemes require multiple parties to sign a transaction or … - PGP Signature Operations
PGP/GPG signature operations for files, emails, and git commits. Generate GPG … - Setup PGP with Git (Auto-sign Commits)
Setup GPG/PGP to automatically sign Git commits and tags. Generate GPG Key for … - Symmetric Encryption
Symmetric encryption algorithms with mathematical foundations and practical … - Threshold Signatures
Threshold signatures enable a group to sign messages without ever reconstructing …