forked from henrycg/prio
/
prg.go
126 lines (101 loc) · 2.71 KB
/
prg.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
package share
import (
"math/big"
"github.com/KuraTheDog/prio/utils"
)
// Compressed representation of secret-shared data.
type PRGHints struct {
Key utils.PRGKey
Delta []*big.Int
}
// A server uses a ReplayPRG to recover the shared values
// that the client sent it (in the form of a PRGHints struct).
type ReplayPRG struct {
serverIdx int
leaderIdx int
rand *utils.BufPRGReader
hints *PRGHints
cur int
}
// A client uses a GenPRG to split values into shares
// (one share per server) using a PRG to compress the
// shares.
type GenPRG struct {
nServers int
leaderIdx int
rand []*utils.BufPRGReader
delta []*big.Int
}
// Produce a new ReplayPRG object for the given server/leader combo.
func NewReplayPRG(serverIdx int, leaderIdx int) *ReplayPRG {
out := new(ReplayPRG)
out.leaderIdx = leaderIdx
out.serverIdx = serverIdx
return out
}
// Import the compressed secret-shared values from hints.
func (p *ReplayPRG) Import(hints *PRGHints) {
p.hints = hints
p.rand = utils.NewBufPRG(utils.NewPRG(&p.hints.Key))
p.cur = 0
}
// Recover a secret-shared value that is shared in a field
// that uses modulus mod.
func (p *ReplayPRG) Get(mod *big.Int) *big.Int {
out := p.rand.RandInt(mod)
if p.IsLeader() {
out.Add(out, p.hints.Delta[p.cur])
out.Mod(out, mod)
}
p.cur++
return out
}
func (p *ReplayPRG) IsLeader() bool {
return p.serverIdx == p.leaderIdx
}
// Create a new GenPRG object for producing compressed secret-shared values.
func NewGenPRG(nServers int, leaderIdx int) *GenPRG {
out := new(GenPRG)
out.nServers = nServers
out.leaderIdx = leaderIdx
out.rand = make([]*utils.BufPRGReader, nServers)
for i := 0; i < nServers; i++ {
out.rand[i] = utils.NewBufPRG(utils.RandomPRG())
}
out.delta = make([]*big.Int, 0)
return out
}
// Split value into shares using modulus mod.
func (g *GenPRG) Share(mod *big.Int, value *big.Int) []*big.Int {
out := make([]*big.Int, g.nServers)
delta := new(big.Int)
for i := 0; i < g.nServers; i++ {
out[i] = g.rand[i].RandInt(mod)
delta.Add(delta, out[i])
}
delta.Sub(value, delta)
delta.Mod(delta, mod)
g.delta = append(g.delta, delta)
out[g.leaderIdx].Add(out[g.leaderIdx], delta)
out[g.leaderIdx].Mod(out[g.leaderIdx], mod)
return out
}
// Split a random value into shares using modulus mod.
func (g *GenPRG) ShareRand(mod *big.Int) *big.Int {
val := new(big.Int)
for i := 0; i < g.nServers; i++ {
val.Add(val, g.rand[i].RandInt(mod))
}
val.Mod(val, mod)
g.delta = append(g.delta, utils.Zero)
return val
}
// Generate the hints that serverIdx can use to recover the shares.
func (g *GenPRG) Hints(serverIdx int) *PRGHints {
out := new(PRGHints)
out.Key = g.rand[serverIdx].Key
if serverIdx == g.leaderIdx {
out.Delta = g.delta
}
return out
}