-
Notifications
You must be signed in to change notification settings - Fork 136
/
ss.go
159 lines (136 loc) · 5.12 KB
/
ss.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
// Package secretsharing provides methods to split secrets into shares.
//
// Let n be the number of parties, and t the number of corrupted parties such
// that 0 <= t < n. A (t,n) secret sharing allows to split a secret into n
// shares, such that the secret can be recovered from any subset of t+1 shares.
//
// The NewShamirSecretSharing function creates a Shamir secret sharing [1],
// which relies on Lagrange polynomial interpolation.
//
// The NewFeldmanSecretSharing function creates a Feldman secret sharing [2],
// which extends Shamir's by allowing to verify that a share is part of a
// committed secret.
//
// In this implementation, secret sharing is defined over the scalar field of
// a prime order group.
//
// References
//
// [1] https://dl.acm.org/doi/10.1145/359168.359176
// [2] https://ieeexplore.ieee.org/document/4568297
package secretsharing
import (
"fmt"
"io"
"github.com/cloudflare/circl/group"
"github.com/cloudflare/circl/math/polynomial"
)
// Share represents a share of a secret.
type Share struct {
// ID uniquely identifies a share in a secret sharing instance.
ID group.Scalar
// Value stores the share generated from a secret sharing instance.
Value group.Scalar
}
type SecretSharing struct {
t uint // t is the threshold.
}
// NewShamirSecretSharing implements a (t,n) Shamir's secret sharing.
// A (t,n) secret sharing allows to split a secret into n shares, such that the
// secret can be only recovered from any subset of t+1 shares.
func NewShamirSecretSharing(t uint) SecretSharing { return SecretSharing{t} }
func (s SecretSharing) polyFromSecret(rnd io.Reader, secret group.Scalar) polynomial.Polynomial {
c := make([]group.Scalar, s.t+1)
g := secret.Group()
c[0] = secret.Copy()
for i := 1; i < len(c); i++ {
c[i] = g.RandomScalar(rnd)
}
return polynomial.New(c)
}
// Shard splits the secret into n shares.
func (s SecretSharing) Shard(rnd io.Reader, secret group.Scalar, n uint) ([]Share, error) {
if n <= s.t {
return nil, errThreshold(s.t, n)
}
g := secret.Group()
poly := s.polyFromSecret(rnd, secret)
shares := make([]Share, n)
for i := range shares {
id := g.NewScalar().SetUint64(uint64(i + 1))
shares[i] = Share{ID: id, Value: poly.Evaluate(id)}
}
return shares, nil
}
// Recover returns the secret provided more than t shares are given. Returns an
// error if the number of shares is not above the threshold or goes beyond the
// maximum number of shares.
func (s SecretSharing) Recover(shares []Share) (group.Scalar, error) {
if l := len(shares); l <= int(s.t) {
return nil, errThreshold(s.t, uint(l))
}
x := make([]group.Scalar, s.t+1)
px := make([]group.Scalar, s.t+1)
for i := range shares[:s.t+1] {
x[i] = shares[i].ID
px[i] = shares[i].Value
}
l := polynomial.NewLagrangePolynomial(x, px)
zero := shares[0].ID.Group().NewScalar()
return l.Evaluate(zero), nil
}
type SharesCommitment = []group.Element
type VerifiableSecretSharing struct{ s SecretSharing }
// NewFeldmanSecretSharing implements a (t,n) Feldman's verifiable secret
// sharing. A (t,n) secret sharing allows to split a secret into n shares, such
// that the secret can be only recovered from any subset of t+1 shares. It's
// verifiable as it allows checking whether a share is part of a secret committed
// during sharding.
func NewFeldmanSecretSharing(t uint) (v VerifiableSecretSharing) { v.s.t = t; return }
// Shard splits the secret into n shares, and also returns a commitment to both
// the secret and the shares. The ShareCommitment must be sent to each party
// so each party can verify its share is correct. Sharding a secret more
// than once produces ShareCommitments with the same first entry.
func (v VerifiableSecretSharing) Shard(rnd io.Reader, secret group.Scalar, n uint) ([]Share, SharesCommitment, error) {
if n <= v.s.t {
return nil, nil, errThreshold(v.s.t, n)
}
g := secret.Group()
poly := v.s.polyFromSecret(rnd, secret)
shares := make([]Share, n)
for i := range shares {
id := g.NewScalar().SetUint64(uint64(i + 1))
shares[i] = Share{ID: id, Value: poly.Evaluate(id)}
}
shareComs := make(SharesCommitment, poly.Degree()+1)
for i := range shareComs {
shareComs[i] = g.NewElement().MulGen(poly.Coefficient(uint(i)))
}
return shares, shareComs, nil
}
// Verify returns true if a share was produced by sharding a secret. It uses
// the share commitments generated by the Shard function to verify this
// property.
func (v VerifiableSecretSharing) Verify(s Share, c SharesCommitment) bool {
if len(c) != int(v.s.t+1) {
return false
}
g := s.ID.Group()
lc := len(c) - 1
sum := g.NewElement().Set(c[lc])
for i := lc - 1; i >= 0; i-- {
sum.Mul(sum, s.ID)
sum.Add(sum, c[i])
}
polI := g.NewElement().MulGen(s.Value)
return polI.IsEqual(sum)
}
// Recover returns the secret provided more than t shares are given. Returns an
// error if the number of shares is not above the threshold (t) or is larger
// than the maximum number of shares (n).
func (v VerifiableSecretSharing) Recover(shares []Share) (group.Scalar, error) {
return v.s.Recover(shares)
}
var errThreshold = func(t, n uint) error {
return fmt.Errorf("secretsharing: number of shares (n=%v) must be above the threshold (t=%v)", n, t)
}