-
Notifications
You must be signed in to change notification settings - Fork 169
/
dleq.go
172 lines (149 loc) · 4.27 KB
/
dleq.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
// Package dleq provides functionality to create and verify non-interactive
// zero-knowledge (NIZK) proofs for the equality (EQ) of discrete logarithms (DL).
// This means, for two values xG and xH one can check that
//
// log_{G}(xG) == log_{H}(xH)
//
// without revealing the secret value x.
package dleq
import (
"errors"
"fmt"
"go.dedis.ch/kyber/v4"
)
// Suite wraps the functionalities needed by the dleq package.
type Suite interface {
kyber.Group
kyber.HashFactory
kyber.XOFFactory
kyber.Random
}
var ErrDifferentLengths = errors.New("inputs of different lengths")
var ErrInvalidProof = errors.New("invalid proof")
// Proof represents a NIZK dlog-equality proof.
type Proof struct {
C kyber.Scalar // challenge
R kyber.Scalar // response
VG kyber.Point // public commitment with respect to base point G
VH kyber.Point // public commitment with respect to base point H
}
// NewDLEQProof computes a new NIZK dlog-equality proof for the scalar x with
// respect to base points G and H. It therefore randomly selects a commitment v
// and then computes the challenge c = H(xG,xH,vG,vH) and response r = v - cx.
// Besides the proof, this function also returns the encrypted base points xG
// and xH.
func NewDLEQProof(
suite Suite,
G kyber.Point,
H kyber.Point,
x kyber.Scalar,
) (proof *Proof, xG kyber.Point, xH kyber.Point, err error) {
// Encrypt base points with secret
xG = suite.Point().Mul(x, G)
xH = suite.Point().Mul(x, H)
// Commitment
v := suite.Scalar().Pick(suite.RandomStream())
vG := suite.Point().Mul(v, G)
vH := suite.Point().Mul(v, H)
// Challenge
hSuite := suite.Hash()
_, err = xG.MarshalTo(hSuite)
if err != nil {
return nil, nil, nil, err
}
_, err = xH.MarshalTo(hSuite)
if err != nil {
return nil, nil, nil, err
}
_, err = vG.MarshalTo(hSuite)
if err != nil {
return nil, nil, nil, err
}
_, err = vH.MarshalTo(hSuite)
if err != nil {
return nil, nil, nil, err
}
cb := hSuite.Sum(nil)
c := suite.Scalar().Pick(suite.XOF(cb))
// Response
r := suite.Scalar()
r.Mul(x, c).Sub(v, r)
return &Proof{c, r, vG, vH}, xG, xH, nil
}
// NewDLEQProofBatch computes lists of NIZK dlog-equality proofs and of
// encrypted base points xG and xH. Note that the challenge is computed over all
// input values.
func NewDLEQProofBatch(
suite Suite,
G []kyber.Point,
H []kyber.Point,
secrets []kyber.Scalar,
) (proof []*Proof, xG []kyber.Point, xH []kyber.Point, err error) {
if len(G) != len(H) || len(H) != len(secrets) {
return nil, nil, nil, fmt.Errorf("invalid: %w", ErrDifferentLengths)
}
n := len(secrets)
proofs := make([]*Proof, n)
v := make([]kyber.Scalar, n)
xG = make([]kyber.Point, n)
xH = make([]kyber.Point, n)
vG := make([]kyber.Point, n)
vH := make([]kyber.Point, n)
for i, x := range secrets {
// Encrypt base points with secrets
xG[i] = suite.Point().Mul(x, G[i])
xH[i] = suite.Point().Mul(x, H[i])
// Commitments
v[i] = suite.Scalar().Pick(suite.RandomStream())
vG[i] = suite.Point().Mul(v[i], G[i])
vH[i] = suite.Point().Mul(v[i], H[i])
}
// Collective challenge
hSuite := suite.Hash()
for _, x := range xG {
if _, err := x.MarshalTo(hSuite); err != nil {
return nil, nil, nil, err
}
}
for _, x := range xH {
if _, err := x.MarshalTo(hSuite); err != nil {
return nil, nil, nil, err
}
}
for _, x := range vG {
if _, err := x.MarshalTo(hSuite); err != nil {
return nil, nil, nil, err
}
}
for _, x := range vH {
if _, err := x.MarshalTo(hSuite); err != nil {
return nil, nil, nil, err
}
}
cb := hSuite.Sum(nil)
c := suite.Scalar().Pick(suite.XOF(cb))
// Responses
for i, x := range secrets {
r := suite.Scalar()
r.Mul(x, c).Sub(v[i], r)
proofs[i] = &Proof{c, r, vG[i], vH[i]}
}
return proofs, xG, xH, nil
}
// Verify examines the validity of the NIZK dlog-equality proof.
// The proof is valid if the following two conditions hold:
//
// vG == rG + c(xG)
// vH == rH + c(xH)
func (p *Proof) Verify(suite Suite, G kyber.Point, H kyber.Point, xG kyber.Point, xH kyber.Point) error {
rG := suite.Point().Mul(p.R, G)
rH := suite.Point().Mul(p.R, H)
cxG := suite.Point().Mul(p.C, xG)
cxH := suite.Point().Mul(p.C, xH)
a := suite.Point().Add(rG, cxG)
b := suite.Point().Add(rH, cxH)
if !(p.VG.Equal(a) && p.VH.Equal(b)) {
return fmt.Errorf("invalid. %w", ErrInvalidProof)
}
return nil
}