1 // Homomorphic evaluation on Ring-LWE ciphertexts (BGV scheme, plaintext mod 2).
2 package ring
3
4 import (
5 "crypto/rand"
6 "io"
7
8 "crypto/sha3"
9 )
10
11 type HEParams struct {
12 KEM KEMParams
13 RelinKey *RelinearizationKey
14 }
15
16 type HECiphertext struct {
17 U *Poly
18 V *Poly
19 NoiseEstimate float64
20 params KEMParams
21 }
22
23 type RelinearizationKey struct {
24 A []*Poly
25 B []*Poly
26 L int32
27 }
28
29 func DefaultHEParams() (kp KEMParams) {
30 return KEMParams{
31 Ring: HE64(),
32 Eta1: 1,
33 Eta2: 1,
34 SharedKeyLen: 32,
35 }
36 }
37
38 func HEKeyGen(kp KEMParams) (pk *KEMPublicKey, sk *KEMSecretKey, rlk *RelinearizationKey) {
39 return HEKeyGenFrom(kp, rand.Reader)
40 }
41
42 func HEKeyGenFrom(kp KEMParams, rng io.Reader) (pk *KEMPublicKey, sk *KEMSecretKey, rlk *RelinearizationKey) {
43 p := kp.Ring
44
45 a := UniformPolyFrom(p, rng)
46 NTT(a)
47
48 s := TernaryPolyFrom(p, rng)
49 NTT(s)
50
51 e := CBDPolyFrom(p, kp.Eta1, rng)
52 e = ScalarMul(e, 2)
53 NTT(e)
54
55 b := MulPointwise(a, s)
56 b = Add(b, e)
57
58 z := []byte{:kp.SharedKeyLen}
59 io.ReadFull(rng, z)
60
61 pk = &KEMPublicKey{A: a, B: b, P: kp}
62 sk = &KEMSecretKey{S: s, PK: pk, Z: z}
63 rlk = genRelinKey(sk, rng)
64 return pk, sk, rlk
65 }
66
67 func genRelinKey(sk *KEMSecretKey, rng io.Reader) (rlk *RelinearizationKey) {
68 p := sk.PK.P.Ring
69 q := p.Q
70
71 base := uint32(256)
72 levels := int32(0)
73 for v := q; v > 0; v /= base {
74 levels++
75 }
76
77 s2 := MulPointwise(sk.S, sk.S)
78
79 rlkA := []*Poly{:levels}
80 rlkB := []*Poly{:levels}
81
82 power := uint32(1)
83 for i := int32(0); i < levels; i++ {
84 ai := UniformPolyFrom(p, rng)
85 NTT(ai)
86
87 ei := CBDPolyFrom(p, sk.PK.P.Eta1, rng)
88 ei = ScalarMul(ei, 2)
89 NTT(ei)
90
91 bi := MulPointwise(ai, sk.S)
92 bi = Add(bi, ei)
93
94 s2Scaled := ScalarMul(s2, power)
95 bi = Add(bi, s2Scaled)
96
97 rlkA[i] = ai
98 rlkB[i] = bi
99
100 power = mulMod(power, base, q)
101 }
102
103 return &RelinearizationKey{A: rlkA, B: rlkB, L: levels}
104 }
105
106 func HEEncrypt(pk *KEMPublicKey, bit int32) (ct *HECiphertext) {
107 return HEEncryptFrom(pk, bit, rand.Reader)
108 }
109
110 func HEEncryptFrom(pk *KEMPublicKey, bit int32, rng io.Reader) (ct *HECiphertext) {
111 p := pk.P.Ring
112 q := p.Q
113
114 coins := []byte{:32}
115 io.ReadFull(rng, coins)
116
117 noiseRng := sha3.NewSHAKE256()
118 noiseRng.Write(coins)
119
120 r := TernaryPolyFrom(p, noiseRng)
121 NTT(r)
122
123 e1 := CBDPolyFrom(p, pk.P.Eta1, noiseRng)
124 e2 := CBDPolyFrom(p, pk.P.Eta2, noiseRng)
125 e1 = ScalarMul(e1, 2)
126 e2 = ScalarMul(e2, 2)
127
128 u := MulPointwise(pk.A, r)
129 INTT(u)
130 u = Add(u, e1)
131
132 v := MulPointwise(pk.B, r)
133 INTT(v)
134 v = Add(v, e2)
135
136 if bit != 0 {
137 v.Coeffs[0] = addMod(v.Coeffs[0], 1, q)
138 }
139
140 return &HECiphertext{
141 U: u,
142 V: v,
143 NoiseEstimate: float64(pk.P.Eta1+pk.P.Eta2) * 4,
144 params: pk.P,
145 }
146 }
147
148 func HEDecrypt(sk *KEMSecretKey, ct *HECiphertext) (result int32) {
149 uNTT := ct.U.Clone()
150 NTT(uNTT)
151 su := MulPointwise(sk.S, uNTT)
152 INTT(su)
153
154 noisy := Sub(ct.V, su)
155
156 q := ct.params.Ring.Q
157 c := noisy.Coeffs[0]
158
159 if c > q/2 {
160 c = q - c
161 }
162 return int32(c % 2)
163 }
164
165 func HEAdd(a, b *HECiphertext) (c *HECiphertext) {
166 return &HECiphertext{
167 U: Add(a.U, b.U),
168 V: Add(a.V, b.V),
169 NoiseEstimate: a.NoiseEstimate + b.NoiseEstimate,
170 params: a.params,
171 }
172 }
173
174 func HESub(a, b *HECiphertext) (c *HECiphertext) {
175 return &HECiphertext{
176 U: Sub(a.U, b.U),
177 V: Sub(a.V, b.V),
178 NoiseEstimate: a.NoiseEstimate + b.NoiseEstimate,
179 params: a.params,
180 }
181 }
182
183 func HEMul(a, b *HECiphertext, rlk *RelinearizationKey) (result *HECiphertext) {
184 p := a.params.Ring
185
186 c0 := Mul(a.V, b.V)
187 c1a := Mul(a.V, b.U)
188 c1b := Mul(a.U, b.V)
189 c1 := Add(c1a, c1b)
190 c2 := Mul(a.U, b.U)
191
192 base := uint32(256)
193 relinU := New(p)
194 relinV := New(p)
195
196 if c2.isNTT {
197 INTT(c2)
198 }
199
200 for level := int32(0); level < rlk.L; level++ {
201 digit := New(p)
202 for j := int32(0); j < int32(len(digit.Coeffs)); j++ {
203 d := c2.Coeffs[j]
204 for k := int32(0); k < level; k++ {
205 d /= base
206 }
207 digit.Coeffs[j] = d % base
208 }
209
210 NTT(digit)
211
212 uPart := MulPointwise(digit, rlk.A[level])
213 vPart := MulPointwise(digit, rlk.B[level])
214 INTT(uPart)
215 INTT(vPart)
216
217 relinU = Add(relinU, uPart)
218 relinV = Add(relinV, vPart)
219 }
220
221 return &HECiphertext{
222 U: Add(c1, relinU),
223 V: Add(c0, relinV),
224 NoiseEstimate: a.NoiseEstimate * b.NoiseEstimate * 4,
225 params: a.params,
226 }
227 }
228
229 func HENot(a *HECiphertext) (result *HECiphertext) {
230 p := a.params.Ring
231
232 newV := a.V.Clone()
233 newV.Coeffs[0] = addMod(newV.Coeffs[0], 1, p.Q)
234
235 return &HECiphertext{
236 U: a.U.Clone(),
237 V: newV,
238 NoiseEstimate: a.NoiseEstimate,
239 params: a.params,
240 }
241 }
242
243 func HEXOR(a, b *HECiphertext) (c *HECiphertext) {
244 return HEAdd(a, b)
245 }
246
247 func HEAND(a, b *HECiphertext, rlk *RelinearizationKey) (c *HECiphertext) {
248 return HEMul(a, b, rlk)
249 }
250
251 func Rerandomize(pk *KEMPublicKey, ct *HECiphertext) (result *HECiphertext) {
252 return RerandomizeFrom(pk, ct, rand.Reader)
253 }
254
255 func RerandomizeFrom(pk *KEMPublicKey, ct *HECiphertext, rng io.Reader) (result *HECiphertext) {
256 zero := HEEncryptFrom(pk, 0, rng)
257 return HEAdd(ct, zero)
258 }
259