-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathprotocol.txt
175 lines (133 loc) · 6.97 KB
/
protocol.txt
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
####################
# Signature #
####################
- Let G be a group of unknown order with no known low-order elements.
- Let g,h in G be two generators with an unknown discrete log relation.
* SendTokens(pk): to send tokens to an RSA public key pk=(n,e) do:
step 1: generate a random 256-bit s' and set s = H(s').
Here H is a hash function that outputs a 2048-bit integer.
step 2: output (C0, C1) where
C0 = RSAencrypt(pk, s') in Z_n
C1 = g^n * h^s in G
note: as described, the magnitude of C0 leaks information about n.
Instead of simply reducing mod n, the algorithm must do the following:
repeat:
- choose a random r in {0,1,...,2^4104//n}
- compute C0 = (s^e mod n) + r*n in Z
until (C0 < 2^4104)
output C0 in Z
this process ensures that C0 is uniform in {0,1,...,2^4104-1}
and is independent of n, as long as n is at most 4096 bits.
another note: while C1 is on the blockchain, C0 can be off chain.
There is a public association between C0 and pk (e.g., via a hash
table), so that the owner of pk can easily find C0. One can
include H(C1) in the plaintext encrypted in C0 to help the owner
of pk quickly find C1.
* Sign(sk, (C0,C1), m): to withdraw the funds associated with (C0,C1)
by signing a message m using the RSA secret key sk do:
step 1: Use sk to decrypt C0 and obtain s'. Compute s = H(s').
Then C1 = g^n * h^s in G.
step 2: choose a random prime 2 <= t <= 1000 s.t. t is a quadratic residue mod n.
step 3: find integers (w,a) such that w^2 = t + a*n
(i.e. w is sqrt(t) mod n)
step 4: choose a random 2048-bit integer s1 and compute
C2 = g^w * h^(s1) in G
step 5: choose a random 2048-bit integer s2 and compute
C3 = g^a * h^(s2) in G
With (C2, C3, t) public, the computed signature is a
signature of knowledge of integers (n, w, a, s, s1, s2) where
(1) C1 = g^n h^s in G,
(2) C2 = g^w h^(s1) in G,
(3) C3 = g^a h^(s2) in G,
(4) w^2 = t + a*n.
The ZKPK works by proving knowledge of eight integers
w, w2, s1, a, an, s1w, sa, s2
satisfying:
C2 = g^w h^(s1)
C3 = g^a h^(s2)
g^(w2) h^(s1w) = C2^w
g^(an) h^(sa) = C1^a
w2 = t + an
Concretely:
(i) choose eight random 2048-bit integers
r_w, r_w2, r_s1, r_a, r_an, r_s1w, r_sa, r_s2
(ii) compute
A = g^(r_w) h^(r_s1)
B = g^(r_a) h^(r_s2)
C = g^(r_w2) h^(r_s1w) / C2^(r_w)
D = g^(r_an) h^(r_sa) / C1^(r_a)
E = r_w2 - r_an in the integers
(iii) computes
PRNG_Key = Hash(G, g, h, C1, C2, C3, t, A, B, C, D, E, m)
(iv) Use a PRNG seeded with PRNG_Key to generate a random 128-bit chal
and a random 264-bit prime ell.
note: need to check if a Miller-Rabin pseudoprime is sufficient.
note: ell is a 264-bit prime because there are about 2^256 primes less than 2^264
(v) compute the integer vector
z = chal*(w, w2, s1, a, an, s1w, sa, s2) +
(r_w, r_w2, r_s1, r_a, r_an, r_s1w, r_sa, r_s2) in Z^8
let (z_w, z_w2, z_s1, z_a, z_an, z_s1w, z_sa, z_s2) = z
and z' = (z mod ell) = (z_w mod ell, z_w2 mod ell, ..., z_s2 mod ell) in Z^8
(vi) compute (here x // y is the integer quotient of x divided by y)
Aq = g^(z_w // ell) h^(z_s1 // ell) in G
Bq = g^(z_a // ell) h^(z_s2 // ell) in G
Cq = g^(z_w2 // ell) h^(z_s1w // ell) / C2^(z_w // ell) in G
Dq = g^(z_an // ell) h^(z_sa // ell) / C1^(z_a // ell) in G
Eq = (z_w2 - z_an) // \ell in the integers
(vii) output the signature sig = (C2, C3, t, chal, ell, Aq, Bq, Cq, Dq, Eq, z')
* Verify(C1, m, sig):
verify that sig is a valid Schnorr signature using
public key C1 on the message (m, C1, C2, C3).
(1) Compute
A = Aq^ell g^(z'_w) h^(z'_s1) / C2^(chal)
B = Bq^ell g^(z'_a) h^(z'_s2) / C3^(chal)
C = Cq^ell g^(z'_w2) h^(z'_s1w) / C2^(z'_w)
D = Dq^ell g^(z'_an) h^(z'_sa) / C1^(z'_a)
E = Eq * ell + ((z'_w2 - z'_an) mod ell) - t * chal
PRNG_Key = Hash(G, g, h, C1, C2, C3, t, A, B, C, D, E, m)
(2) Use a PRNG seeded with PRNG_Key to generate chal' and ell'
as described in step (iii) and (iv) of sign.
note: since ell is included in the signature, the verifier
does not need to search for a prime, but can instead
verify that the given ell is prime and is not too far
from the base starting point of the prime search.
(3) Accept iff chal' == chal and ell' == ell.
### Comments ###
1. There is a seemingly simpler method to prove that one knows the
factorization of n, namely, prove that one knows p such that p
divides n. That is, instead of committing to "w" we would commit
to "p" and then prove that the committed value divides n. But we
would also need to prove that the committed factor is not one of
{1, -1, n, -n}, and that will result in a longer proof.
2. RSAGroupOps implements the quotient group (Z/n)/{1,-1},
representing elements as |x| = min(x, n - x). This is because the
proof method requires that no one knows an element of low order
other than the identity in the group of unknown order. But for
Z/n, -1 is such an element. By quotienting out {1,-1}, -1 becomes
the identity (since min(n - 1, (n + 1) mod n) == 1).
3. This document was updated January 6, 2019 (commit c5c91e8),
adding step 5 in the signing process (C3, a commitment to 'a'),
plus extra elements in the signature, etc. Corresponding code
updates are marked with a short explanatory comment starting
with 'UPDATE 2019 Jan 06'.
Note that a verifier for the prior version of the protocol can
check a signature for the new version by ignoring the two new
group elements in the signature (informally, this is complete
but not sound). A new signer can help backward compatibility
by serializing the signature such that the new group elements
fall at the end. Schematically, write:
sig_new = (C2, t, chal, ell, Aq, Cq, Dq, Eq, z', C3, Bq)
Now, if a verifier for the prior version of the protocol ignores
the last two elements during deserialization and applies the old
verification procedure, it will accept valid signatures made
using the new protocol.
4. This repository was updated January 7, 2020 (commit 364180f),
changing the length of the prime challenge ell from 136 bits
(i.e., 2^128 possible primes) to 264 bits (i.e., 2^256 possible
primes). This addresses security loss that occurs as a result of
the Fiat-Shamir transform. For more information on the security
loss, see Section 3.3 of
Boneh, Buenz, Fisch. "A Survey of Two Verifiable Delay Functions."
ePrint # 2018/712, https://eprint.iacr.org/2018/712
Corresponding code updates are marked with a short explanatory
comment starting with "UPDATE 2020 Jan 07".