-
Notifications
You must be signed in to change notification settings - Fork 172
/
threshold.go
178 lines (146 loc) · 6.35 KB
/
threshold.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
package drlwe
import (
"fmt"
"github.com/tuneinsight/lattigo/v4/ring"
"github.com/tuneinsight/lattigo/v4/rlwe"
"github.com/tuneinsight/lattigo/v4/rlwe/ringqp"
"github.com/tuneinsight/lattigo/v4/utils"
)
// Thresholdizer is a type for generating secret-shares of ringqp.Poly types such that
// the resulting sharing has a t-out-of-N-threshold access-structure. It implements the
// `Thresholdize` operation as presented in "An Efficient Threshold Access-Structure
// for RLWE-Based Multiparty Homomorphic Encryption" (2022) by Mouchet, C., Bertrand, E.,
// and Hubaux, J. P. (https://eprint.iacr.org/2022/780).
//
// See the `drlwe` package README.md.
type Thresholdizer struct {
params *rlwe.Parameters
ringQP *ringqp.Ring
usampler ringqp.UniformSampler
}
// Combiner is a type for generating t-out-of-t additive shares from local t-out-of-N
// shares. It implements the `Combine` operation as presented in "An Efficient Threshold
// Access-Structure for RLWE-Based Multiparty Homomorphic Encryption" (2022) by Mouchet, C.,
// Bertrand, E., and Hubaux, J. P. (https://eprint.iacr.org/2022/780).
type Combiner struct {
ringQP *ringqp.Ring
threshold int
tmp1, tmp2 []uint64
one ring.RNSScalar
lagrangeCoeffs map[ShamirPublicPoint]ring.RNSScalar
}
// ShamirPublicPoint is a type for Shamir public point associated with a party identity within
// the t-out-of-N-threshold scheme.
//
// See Thresholdizer and Combiner types.
type ShamirPublicPoint uint64
// ShamirPolynomial represents a polynomial with ringqp.Poly coefficients. It is used by the
// Thresholdizer type to produce t-out-of-N-threshold shares of an ringqp.Poly.
//
// See Thresholdizer type.
type ShamirPolynomial struct {
Coeffs []ringqp.Poly
}
// ShamirSecretShare represents a t-out-of-N-threshold secret-share.
//
// See Thresholdizer and Combiner types.
type ShamirSecretShare struct {
ringqp.Poly
}
// NewThresholdizer creates a new Thresholdizer instance from parameters.
func NewThresholdizer(params rlwe.Parameters) *Thresholdizer {
thr := new(Thresholdizer)
thr.params = ¶ms
thr.ringQP = params.RingQP()
prng, err := utils.NewPRNG()
if err != nil {
panic(fmt.Errorf("could not initialize PRNG: %s", err))
}
thr.usampler = ringqp.NewUniformSampler(prng, *params.RingQP())
return thr
}
// GenShamirPolynomial generates a new secret ShamirPolynomial to be used in the Thresholdizer.GenShamirSecretShare method.
// It does so by sampling a random polynomial of degree threshold - 1 and with its constant term equal to secret.
func (thr *Thresholdizer) GenShamirPolynomial(threshold int, secret *rlwe.SecretKey) (*ShamirPolynomial, error) {
if threshold < 1 {
return nil, fmt.Errorf("threshold should be >= 1")
}
gen := &ShamirPolynomial{Coeffs: make([]ringqp.Poly, int(threshold))}
gen.Coeffs[0] = secret.Value.CopyNew()
for i := 1; i < threshold; i++ {
gen.Coeffs[i] = thr.ringQP.NewPoly()
thr.usampler.Read(gen.Coeffs[i])
}
return gen, nil
}
// AllocateThresholdSecretShare allocates a ShamirSecretShare struct.
func (thr *Thresholdizer) AllocateThresholdSecretShare() *ShamirSecretShare {
return &ShamirSecretShare{thr.ringQP.NewPoly()}
}
// GenShamirSecretShare generates a secret share for the given recipient, identified by its ShamirPublicPoint.
// The result is stored in ShareOut and should be sent to this party.
func (thr *Thresholdizer) GenShamirSecretShare(recipient ShamirPublicPoint, secretPoly *ShamirPolynomial, shareOut *ShamirSecretShare) {
thr.ringQP.EvalPolyScalar(secretPoly.Coeffs, uint64(recipient), shareOut.Poly)
}
// AggregateShares aggregates two ShamirSecretShare and stores the result in outShare.
func (thr *Thresholdizer) AggregateShares(share1, share2, outShare *ShamirSecretShare) {
lvlQ, lvlP := thr.params.QCount()-1, thr.params.PCount()-1
thr.ringQP.AddLvl(lvlQ, lvlP, share1.Poly, share2.Poly, outShare.Poly)
}
// NewCombiner creates a new Combiner struct from the parameters and the set of ShamirPublicPoints. Note that the other
// parameter may contain the instantiator's own ShamirPublicPoint.
func NewCombiner(params rlwe.Parameters, own ShamirPublicPoint, others []ShamirPublicPoint, threshold int) *Combiner {
cmb := new(Combiner)
cmb.ringQP = params.RingQP()
cmb.threshold = threshold
cmb.tmp1, cmb.tmp2 = cmb.ringQP.NewRNSScalar(), cmb.ringQP.NewRNSScalar()
cmb.one = cmb.ringQP.NewRNSScalarFromUInt64(1)
qlen := len(cmb.ringQP.RingQ.Modulus)
for i, qi := range cmb.ringQP.RingQ.Modulus {
cmb.one[i] = ring.MForm(cmb.one[i], qi, cmb.ringQP.RingQ.BredParams[i])
}
if cmb.ringQP.RingP != nil {
for i, pi := range cmb.ringQP.RingP.Modulus {
cmb.one[i+qlen] = ring.MForm(cmb.one[i+qlen], pi, cmb.ringQP.RingP.BredParams[i])
}
}
// precomputes lagrange coefficient factors
cmb.lagrangeCoeffs = make(map[ShamirPublicPoint]ring.RNSScalar)
for _, spk := range others {
if spk != own {
cmb.lagrangeCoeffs[spk] = cmb.ringQP.NewRNSScalar()
cmb.lagrangeCoeff(own, spk, cmb.lagrangeCoeffs[spk])
}
}
return cmb
}
// GenAdditiveShare generates a t-out-of-t additive share of the secret from a local aggregated share ownSecret and the set of active identities, identified
// by their ShamirPublicPoint. It stores the resulting additive share in skOut.
func (cmb *Combiner) GenAdditiveShare(activesPoints []ShamirPublicPoint, ownPoint ShamirPublicPoint, ownShare *ShamirSecretShare, skOut *rlwe.SecretKey) {
if len(activesPoints) < cmb.threshold {
panic("cannot GenAdditiveShare: Not enough active players to combine threshold shares.")
}
prod := cmb.tmp2
copy(prod, cmb.one)
for _, active := range activesPoints[:cmb.threshold] {
//Lagrange Interpolation with the public threshold key of other active players
if active != ownPoint {
cmb.tmp1 = cmb.lagrangeCoeffs[active]
cmb.ringQP.MulRNSScalar(prod, cmb.tmp1, prod)
}
}
cmb.ringQP.MulRNSScalarMontgomery(ownShare.Poly, prod, skOut.Value)
}
func (cmb *Combiner) lagrangeCoeff(thisKey ShamirPublicPoint, thatKey ShamirPublicPoint, lagCoeff []uint64) {
this := cmb.ringQP.NewRNSScalarFromUInt64(uint64(thisKey))
that := cmb.ringQP.NewRNSScalarFromUInt64(uint64(thatKey))
cmb.ringQP.SubRNSScalar(that, this, lagCoeff)
cmb.ringQP.Inverse(lagCoeff)
cmb.ringQP.MulRNSScalar(lagCoeff, that, lagCoeff)
}
func (s *ShamirSecretShare) MarshalBinary() ([]byte, error) {
return s.Poly.MarshalBinary()
}
func (s *ShamirSecretShare) UnmarshalBinary(b []byte) error {
return s.Poly.UnmarshalBinary(b)
}