-
Notifications
You must be signed in to change notification settings - Fork 2
/
polynomial.go
188 lines (149 loc) · 4.7 KB
/
polynomial.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
// SPDX-License-Identifier: MIT
//
// Copyright (C) 2024 Daniel Bourdrez. All Rights Reserved.
//
// This source code is licensed under the MIT license found in the
// LICENSE file in the root directory of this source tree or at
// https://spdx.org/licenses/MIT.html
package secretsharing
import (
"errors"
group "github.com/bytemare/crypto"
)
var (
errPolyXIsZero = errors.New("identifier for interpolation is nil or zero")
errPolyHasZeroCoeff = errors.New("one of the polynomial's coefficients is zero")
errPolyHasDuplicates = errors.New("the polynomial has duplicate coefficients")
errPolyHasNilCoeff = errors.New("the polynomial has a nil coefficient")
errPolyCoeffInexistant = errors.New("the identifier does not exist in the polynomial")
)
// Polynomial over scalars, represented as a list of t+1 coefficients, where t is the threshold.
// The constant term is in the first position and the highest degree coefficient is in the last position.
// All operations on the polynomial's coefficient are done modulo the scalar's group order.
type Polynomial []*group.Scalar
// NewPolynomial returns a slice of Scalars with the capacity to hold the desired coefficients.
func NewPolynomial(coefficients uint16) Polynomial {
return make(Polynomial, coefficients)
}
// NewPolynomialFromIntegers returns a Polynomial from a slice of uint16.
func NewPolynomialFromIntegers(g group.Group, ints []uint16) Polynomial {
polynomial := make(Polynomial, len(ints))
for i, v := range ints {
polynomial[i] = g.NewScalar().SetUInt64(uint64(v))
}
return polynomial
}
// NewPolynomialFromListFunc returns a Polynomial from the group.Scalar returned by f applied on each element
// of the slice.
func NewPolynomialFromListFunc[S ~[]E, E any](g group.Group, s S, f func(E) *group.Scalar) Polynomial {
polynomial := make(Polynomial, len(s))
for i, v := range s {
polynomial[i] = g.NewScalar().Set(f(v))
}
return polynomial
}
// the only call to copyPolynomial ensure that both polynomials are of the same length.
func copyPolynomial(dst, src Polynomial) error {
for index, coeff := range src {
if coeff == nil {
return errPolyHasNilCoeff
}
if coeff.IsZero() {
return errPolyHasZeroCoeff
}
dst[index] = coeff.Copy()
}
return nil
}
// Verify returns an appropriate error if the polynomial has a nil or 0 coefficient, or duplicates.
func (p Polynomial) Verify() error {
if p.hasNil() {
return errPolyHasNilCoeff
}
if p.hasZero() {
return errPolyHasZeroCoeff
}
if p.hasDuplicates() {
return errPolyHasDuplicates
}
return nil
}
// VerifyInterpolatingInput checks compatibility of the input id with the polynomial. If not, an error is returned.
func (p Polynomial) VerifyInterpolatingInput(id *group.Scalar) error {
if id == nil || id.IsZero() {
return errPolyXIsZero
}
if err := p.Verify(); err != nil {
return err
}
if !p.has(id) {
return errPolyCoeffInexistant
}
return nil
}
// has returns whether s is a coefficient of the polynomial.
func (p Polynomial) has(s *group.Scalar) bool {
for _, si := range p {
if si.Equal(s) == 1 {
return true
}
}
return false
}
// has returns whether s is a coefficient of the polynomial.
func (p Polynomial) hasNil() bool {
for _, si := range p {
if si == nil {
return true
}
}
return false
}
// hasZero returns whether one of the polynomials coefficients is 0.
func (p Polynomial) hasZero() bool {
for _, xj := range p {
if xj.IsZero() {
return true
}
}
return false
}
// hasDuplicates returns whether the polynomial has at least one coefficient that appears more than once.
func (p Polynomial) hasDuplicates() bool {
visited := make(map[string]bool, len(p))
for _, pi := range p {
enc := string(pi.Encode())
if visited[enc] {
return true
}
visited[enc] = true
}
return false
}
// Evaluate evaluates the polynomial p at point x using Horner's method.
func (p Polynomial) Evaluate(x *group.Scalar) *group.Scalar {
// since value is an accumulator and starts with 0, we can skip multiplying by x, and start from the end
value := p[len(p)-1].Copy()
for i := len(p) - 2; i >= 0; i-- {
value.Multiply(x)
value.Add(p[i])
}
return value
}
// DeriveInterpolatingValue derives a value used for polynomial interpolation.
// id and all the coefficients must be non-zero scalars.
func (p Polynomial) DeriveInterpolatingValue(g group.Group, id *group.Scalar) (*group.Scalar, error) {
if err := p.VerifyInterpolatingInput(id); err != nil {
return nil, err
}
numerator := g.NewScalar().One()
denominator := g.NewScalar().One()
for _, coeff := range p {
if coeff.Equal(id) == 1 {
continue
}
numerator.Multiply(coeff)
denominator.Multiply(coeff.Copy().Subtract(id))
}
return numerator.Multiply(denominator.Invert()), nil
}