forked from tuneinsight/lattigo
/
evaluator_keyswitch.go
189 lines (144 loc) · 6.43 KB
/
evaluator_keyswitch.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
package rlwe
import (
"github.com/fedejinich/lattigo/v6/ring"
"github.com/fedejinich/lattigo/v6/rlwe/ringqp"
"github.com/fedejinich/lattigo/v6/utils"
)
// SwitchKeys re-encrypts ctIn under a different key and returns the result in ctOut.
// It requires a SwitchingKey, which is computed from the key under which the Ciphertext is currently encrypted
// and the key under which the Ciphertext will be re-encrypted.
// The method will panic if either ctIn or ctOut degree isn't 1.
func (eval *Evaluator) SwitchKeys(ctIn *Ciphertext, switchingKey *SwitchingKey, ctOut *Ciphertext) {
if ctIn.Degree() != 1 || ctOut.Degree() != 1 {
panic("cannot SwitchKeys: input and output Ciphertext must be of degree 1")
}
level := utils.MinInt(ctIn.Level(), ctOut.Level())
ringQ := eval.params.RingQ().AtLevel(level)
ctTmp := &Ciphertext{}
ctTmp.Value = []*ring.Poly{eval.BuffQP[1].Q, eval.BuffQP[2].Q}
ctTmp.IsNTT = ctIn.IsNTT
eval.GadgetProduct(level, ctIn.Value[1], switchingKey.GadgetCiphertext, ctTmp)
ringQ.Add(ctIn.Value[0], ctTmp.Value[0], ctOut.Value[0])
ring.CopyLvl(level, ctTmp.Value[1], ctOut.Value[1])
ctOut.MetaData = ctIn.MetaData
}
// Relinearize applies the relinearization procedure on ct0 and returns the result in ctOut.
// The method will panic if the corresponding relinearization key to the ciphertext degree
// is missing.
func (eval *Evaluator) Relinearize(ctIn *Ciphertext, ctOut *Ciphertext) {
if eval.Rlk == nil || ctIn.Degree()-1 > len(eval.Rlk.Keys) {
panic("cannot Relinearize: relinearization key missing (or ciphertext degree is too large)")
}
level := utils.MinInt(ctIn.Level(), ctOut.Level())
ringQ := eval.params.RingQ().AtLevel(level)
ctTmp := &Ciphertext{}
ctTmp.Value = []*ring.Poly{eval.BuffQP[1].Q, eval.BuffQP[2].Q}
ctTmp.IsNTT = ctIn.IsNTT
eval.GadgetProduct(level, ctIn.Value[2], eval.Rlk.Keys[0].GadgetCiphertext, ctTmp)
ringQ.Add(ctIn.Value[0], ctTmp.Value[0], ctOut.Value[0])
ringQ.Add(ctIn.Value[1], ctTmp.Value[1], ctOut.Value[1])
for deg := ctIn.Degree() - 1; deg > 1; deg-- {
eval.GadgetProduct(level, ctIn.Value[deg], eval.Rlk.Keys[deg-2].GadgetCiphertext, ctTmp)
ringQ.Add(ctOut.Value[0], ctTmp.Value[0], ctOut.Value[0])
ringQ.Add(ctOut.Value[1], ctTmp.Value[1], ctOut.Value[1])
}
ctOut.Resize(1, level)
ctOut.MetaData = ctIn.MetaData
}
// DecomposeNTT applies the full RNS basis decomposition on c2.
// Expects the IsNTT flag of c2 to correctly reflect the domain of c2.
// BuffQPDecompQ and BuffQPDecompQ are vectors of polynomials (mod Q and mod P) that store the
// special RNS decomposition of c2 (in the NTT domain)
func (eval *Evaluator) DecomposeNTT(levelQ, levelP, nbPi int, c2 *ring.Poly, c2IsNTT bool, BuffDecompQP []ringqp.Poly) {
ringQ := eval.params.RingQ().AtLevel(levelQ)
var polyNTT, polyInvNTT *ring.Poly
if c2IsNTT {
polyNTT = c2
polyInvNTT = eval.BuffInvNTT
ringQ.INTT(polyNTT, polyInvNTT)
} else {
polyNTT = eval.BuffInvNTT
polyInvNTT = c2
ringQ.NTT(polyInvNTT, polyNTT)
}
decompRNS := eval.params.DecompRNS(levelQ, levelP)
for i := 0; i < decompRNS; i++ {
eval.DecomposeSingleNTT(levelQ, levelP, nbPi, i, polyNTT, polyInvNTT, BuffDecompQP[i].Q, BuffDecompQP[i].P)
}
}
// DecomposeSingleNTT takes the input polynomial c2 (c2NTT and c2InvNTT, respectively in the NTT and out of the NTT domain)
// modulo the RNS basis, and returns the result on c2QiQ and c2QiP, the receiver polynomials respectively mod Q and mod P (in the NTT domain)
func (eval *Evaluator) DecomposeSingleNTT(levelQ, levelP, nbPi, decompRNS int, c2NTT, c2InvNTT, c2QiQ, c2QiP *ring.Poly) {
ringQ := eval.params.RingQ().AtLevel(levelQ)
ringP := eval.params.RingP().AtLevel(levelP)
eval.Decomposer.DecomposeAndSplit(levelQ, levelP, nbPi, decompRNS, c2InvNTT, c2QiQ, c2QiP)
p0idxst := decompRNS * nbPi
p0idxed := p0idxst + nbPi
// c2_qi = cx mod qi mod qi
for x := 0; x < levelQ+1; x++ {
if p0idxst <= x && x < p0idxed {
copy(c2QiQ.Coeffs[x], c2NTT.Coeffs[x])
} else {
ringQ.SubRings[x].NTT(c2QiQ.Coeffs[x], c2QiQ.Coeffs[x])
}
}
if ringP != nil {
// c2QiP = c2 mod qi mod pj
ringP.NTT(c2QiP, c2QiP)
}
}
// KeyswitchHoisted applies the key-switch to the decomposed polynomial c2 mod QP (BuffQPDecompQ and BuffQPDecompP)
// and divides the result by P, reducing the basis from QP to Q.
//
// BuffQP2 = dot(BuffQPDecompQ||BuffQPDecompP * evakey[0]) mod Q
// BuffQP3 = dot(BuffQPDecompQ||BuffQPDecompP * evakey[1]) mod Q
func (eval *Evaluator) KeyswitchHoisted(levelQ int, BuffQPDecompQP []ringqp.Poly, evakey *SwitchingKey, c0Q, c1Q, c0P, c1P *ring.Poly) {
eval.KeyswitchHoistedLazy(levelQ, BuffQPDecompQP, evakey, c0Q, c1Q, c0P, c1P)
levelP := evakey.Value[0][0].Value[0].P.Level()
// Computes c0Q = c0Q/c0P and c1Q = c1Q/c1P
eval.BasisExtender.ModDownQPtoQNTT(levelQ, levelP, c0Q, c0P, c0Q)
eval.BasisExtender.ModDownQPtoQNTT(levelQ, levelP, c1Q, c1P, c1Q)
}
// KeyswitchHoistedLazy applies the key-switch to the decomposed polynomial c2 mod QP (BuffQPDecompQ and BuffQPDecompP)
//
// BuffQP2 = dot(BuffQPDecompQ||BuffQPDecompP * evakey[0]) mod QP
// BuffQP3 = dot(BuffQPDecompQ||BuffQPDecompP * evakey[1]) mod QP
func (eval *Evaluator) KeyswitchHoistedLazy(levelQ int, BuffQPDecompQP []ringqp.Poly, evakey *SwitchingKey, c0Q, c1Q, c0P, c1P *ring.Poly) {
levelP := evakey.LevelP()
ringQP := eval.params.RingQP().AtLevel(levelQ, levelP)
ringQ := ringQP.RingQ
ringP := ringQP.RingP
c0QP := ringqp.Poly{Q: c0Q, P: c0P}
c1QP := ringqp.Poly{Q: c1Q, P: c1P}
decompRNS := (levelQ + 1 + levelP) / (levelP + 1)
QiOverF := eval.params.QiOverflowMargin(levelQ) >> 1
PiOverF := eval.params.PiOverflowMargin(levelP) >> 1
// Key switching with CRT decomposition for the Qi
var reduce int
for i := 0; i < decompRNS; i++ {
if i == 0 {
ringQP.MulCoeffsMontgomeryLazy(evakey.Value[i][0].Value[0], BuffQPDecompQP[i], c0QP)
ringQP.MulCoeffsMontgomeryLazy(evakey.Value[i][0].Value[1], BuffQPDecompQP[i], c1QP)
} else {
ringQP.MulCoeffsMontgomeryLazyThenAddLazy(evakey.Value[i][0].Value[0], BuffQPDecompQP[i], c0QP)
ringQP.MulCoeffsMontgomeryLazyThenAddLazy(evakey.Value[i][0].Value[1], BuffQPDecompQP[i], c1QP)
}
if reduce%QiOverF == QiOverF-1 {
ringQ.Reduce(c0QP.Q, c0QP.Q)
ringQ.Reduce(c1QP.Q, c1QP.Q)
}
if reduce%PiOverF == PiOverF-1 {
ringP.Reduce(c0QP.P, c0QP.P)
ringP.Reduce(c1QP.P, c1QP.P)
}
reduce++
}
if reduce%QiOverF != 0 {
ringQ.Reduce(c0QP.Q, c0QP.Q)
ringQ.Reduce(c1QP.Q, c1QP.Q)
}
if reduce%PiOverF != 0 {
ringP.Reduce(c0QP.P, c0QP.P)
ringP.Reduce(c1QP.P, c1QP.P)
}
}