gk15.go 8.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337
  1. /*
  2. * An implementation of Groth and Kohlweiss, "One-out-of-Many Proofs: Or
  3. * How to Leak a Secret and Spend a Coin", Eurocrypt 2015
  4. * https://eprint.iacr.org/2014/764.pdf
  5. */
  6. package main
  7. import (
  8. "fmt"
  9. "go.dedis.ch/kyber"
  10. "go.dedis.ch/kyber/util/random"
  11. )
  12. type GroupParams struct {
  13. /* A group of prime order */
  14. group kyber.Group
  15. /* Three generators of the group; the relative discrete logs
  16. * must be unknown. Commitments to a value x with randomness r
  17. * are x*A + r*B. Y is used to pad the list of commitments to a
  18. * power of 2. */
  19. A, B, Y kyber.Point
  20. }
  21. // In the paper, some arrays are 0-based, and some are 1-based. We
  22. // want to keep all arrays 0-based, so the following arrays (1-based in
  23. // the paper) have 1 subtracted from their indices whenever they are
  24. // used: cl, ca, cb, r, a, s, t, f, za, zb
  25. // Each array in the three structs below is of length n, where
  26. // n = ceil(log_2(N)), and N is the number of commitments.
  27. // The total proof size (PubState plus Proof) is then
  28. // 4*n points, plus (3*n+1) scalars.
  29. type PubState struct {
  30. cl, ca, cb, cd []kyber.Point
  31. }
  32. type PrivState struct {
  33. r, a, s, t, rho []kyber.Scalar
  34. ell uint32
  35. privkey kyber.Scalar
  36. }
  37. type Proof struct {
  38. f, za, zb []kyber.Scalar
  39. zd kyber.Scalar
  40. }
  41. // Multiply a polynomial expressed as a slice of coefficients by the
  42. // scalar a
  43. func polymul(group kyber.Group, poly []kyber.Scalar, a kyber.Scalar) {
  44. numcoeffs := len(poly)
  45. for i := 0 ; i < numcoeffs ; i++ {
  46. poly[i] = group.Scalar().Mul(poly[i], a)
  47. }
  48. }
  49. // Multiply a polynomial expressed as a slice of coefficients by
  50. // the linear polynomial x+a
  51. func polymul_xplus(group kyber.Group, poly []kyber.Scalar, a kyber.Scalar) {
  52. numcoeffs := len(poly)
  53. if !poly[numcoeffs-1].Equal(group.Scalar().Zero()) {
  54. panic("Degree too large in multiplication")
  55. }
  56. for i := numcoeffs-1 ; i > 0 ; i-- {
  57. poly[i] = group.Scalar().Add(
  58. group.Scalar().Mul(poly[i], a), poly[i-1])
  59. }
  60. poly[0] = group.Scalar().Mul(poly[0], a)
  61. }
  62. /* Sigma protocol for one out of N commitments containing 0
  63. * Section 3 of https://eprint.iacr.org/2014/764.pdf
  64. */
  65. func ProofStep1(params GroupParams, c []kyber.Point, ell uint32, privkey kyber.Scalar) (PubState, PrivState) {
  66. N := uint32(len(c))
  67. rand := random.New()
  68. group := params.group
  69. // Find n := ceil(log_2(N))
  70. n := uint32(1)
  71. two_n := uint32(2) // 2^n
  72. for ; two_n < N ; {
  73. n += 1
  74. two_n *= 2
  75. }
  76. var pub PubState
  77. var priv PrivState
  78. priv.r = make([]kyber.Scalar, n)
  79. priv.a = make([]kyber.Scalar, n)
  80. priv.s = make([]kyber.Scalar, n)
  81. priv.t = make([]kyber.Scalar, n)
  82. priv.rho = make([]kyber.Scalar, n)
  83. priv.ell = ell
  84. priv.privkey = privkey.Clone()
  85. pub.cl = make([]kyber.Point, n)
  86. pub.ca = make([]kyber.Point, n)
  87. pub.cb = make([]kyber.Point, n)
  88. pub.cd = make([]kyber.Point, n)
  89. var j, k, mask uint32
  90. // mask = 2^k
  91. j = 1
  92. k = 0
  93. mask = 1
  94. for ; k < n ; {
  95. priv.r[j-1] = group.Scalar().Pick(rand)
  96. priv.a[j-1] = group.Scalar().Pick(rand)
  97. priv.s[j-1] = group.Scalar().Pick(rand)
  98. priv.t[j-1] = group.Scalar().Pick(rand)
  99. priv.rho[k] = group.Scalar().Pick(rand)
  100. pub.cl[j-1] = group.Point().Mul(priv.r[j-1], params.B)
  101. if (ell & mask) != 0 {
  102. pub.cl[j-1] = group.Point().Add(pub.cl[j-1], params.A)
  103. }
  104. pub.ca[j-1] = group.Point().Add(
  105. group.Point().Mul(priv.a[j-1], params.A),
  106. group.Point().Mul(priv.s[j-1], params.B))
  107. pub.cb[j-1] = group.Point().Mul(priv.t[j-1], params.B)
  108. if (ell & mask) != 0 {
  109. pub.cb[j-1] = group.Point().Add(pub.cb[j-1],
  110. group.Point().Mul(priv.a[j-1], params.A))
  111. }
  112. j++
  113. k++
  114. mask *= 2
  115. }
  116. for k = 0 ; k < n ; k++ {
  117. pub.cd[k] = group.Point().Mul(priv.rho[k], params.B)
  118. }
  119. for i := uint32(0); i < two_n; i++ {
  120. // Compute the coefficients of p_i
  121. p_i := make([]kyber.Scalar, n+1)
  122. p_i[0] = group.Scalar().One()
  123. for t := uint32(1); t <= n; t++ {
  124. p_i[t] = group.Scalar().Zero()
  125. }
  126. j = 1
  127. // jmask = 2^(j-1)
  128. jmask := uint32(1)
  129. for ; j <= n ; {
  130. if (i & jmask) != 0 {
  131. if (ell & jmask) != 0 {
  132. // Multiply p_i by x + a[j-1]
  133. polymul_xplus(group, p_i, priv.a[j-1])
  134. } else {
  135. // Multiply p_i by a[j-1]
  136. polymul(group, p_i, priv.a[j-1])
  137. }
  138. } else {
  139. negaj := group.Scalar().Neg(priv.a[j-1])
  140. if (ell & jmask) != 0 {
  141. // Multiply p_i by -a[j-1]
  142. polymul(group, p_i, negaj)
  143. } else {
  144. // Multiply p_i by x - a[j-1]
  145. polymul_xplus(group, p_i, negaj)
  146. }
  147. }
  148. j++
  149. jmask *= 2
  150. }
  151. if i == ell && !p_i[n].Equal(group.Scalar().One()) {
  152. panic("Leading coeff should be 1 but was not")
  153. }
  154. if i != ell && !p_i[n].Equal(group.Scalar().Zero()) {
  155. panic("Leading coeff should be 0 but was not")
  156. }
  157. for k = 0 ; k < n ; k++ {
  158. if i < N {
  159. pub.cd[k] = group.Point().Add(pub.cd[k],
  160. group.Point().Mul(p_i[k], c[i]))
  161. } else {
  162. pub.cd[k] = group.Point().Add(pub.cd[k],
  163. group.Point().Mul(p_i[k], params.Y))
  164. }
  165. }
  166. }
  167. return pub, priv
  168. }
  169. func GenChallenge(params GroupParams, pub PubState) kyber.Scalar {
  170. // In the interactive version, just pick a random challenge.
  171. // In the noninteractive version, this would be a hash of pub
  172. // and a message.
  173. rand := random.New()
  174. return params.group.Scalar().Pick(rand)
  175. }
  176. func ProofStep2(params GroupParams, priv PrivState, x kyber.Scalar) Proof {
  177. var proof Proof
  178. n := uint32(len(priv.rho))
  179. group := params.group
  180. proof.f = make([]kyber.Scalar, n)
  181. proof.za = make([]kyber.Scalar, n)
  182. proof.zb = make([]kyber.Scalar, n)
  183. var j, mask uint32
  184. // mask = 2^(j-1)
  185. j = 1
  186. mask = 1
  187. for ; j <= n ; {
  188. if (priv.ell & mask) != 0 {
  189. proof.f[j-1] = group.Scalar().Add(x, priv.a[j-1])
  190. } else {
  191. proof.f[j-1] = priv.a[j-1].Clone()
  192. }
  193. proof.za[j-1] = group.Scalar().Add(
  194. group.Scalar().Mul(x, priv.r[j-1]), priv.s[j-1])
  195. proof.zb[j-1] = group.Scalar().Add(
  196. group.Scalar().Mul(
  197. group.Scalar().Sub(x, proof.f[j-1]),
  198. priv.r[j-1]),
  199. priv.t[j-1])
  200. j++
  201. mask *= 2
  202. }
  203. proof.zd = group.Scalar().Zero()
  204. k := uint32(0)
  205. xk := group.Scalar().One() // x^k
  206. for ; k < n ; {
  207. proof.zd = group.Scalar().Sub(proof.zd,
  208. group.Scalar().Mul(priv.rho[k], xk))
  209. k++
  210. xk = group.Scalar().Mul(xk, x)
  211. }
  212. // At this point, xk = x^n
  213. proof.zd = group.Scalar().Add(proof.zd,
  214. group.Scalar().Mul(priv.privkey, xk))
  215. return proof
  216. }
  217. // We assume that the checks that the Points are in fact in the right
  218. // group and the Scalars are in the right range were done at the time
  219. // the PubState and Proof structures were populated from data received
  220. // over the network. This function checks the relations between the
  221. // elements.
  222. func Verify(params GroupParams, c []kyber.Point, pub PubState, x kyber.Scalar, proof Proof) bool {
  223. N := uint32(len(c))
  224. group := params.group
  225. // Find n := ceil(log_2(N))
  226. n := uint32(1)
  227. two_n := uint32(2) // 2^n
  228. for ; two_n < N ; {
  229. n += 1
  230. two_n *= 2
  231. }
  232. // Check that the lengths of the arrays are correct
  233. intn := int(n)
  234. if len(pub.cl) != intn || len(pub.ca) != intn ||
  235. len(pub.cb) != intn ||
  236. len(pub.cd) != intn ||
  237. len(proof.f) != intn ||
  238. len(proof.za) != intn ||
  239. len(proof.zb) != intn {
  240. fmt.Printf("Inputs not of the correct length\n")
  241. return false
  242. }
  243. for j := uint32(1) ; j <= n ; j++ {
  244. lhs1 := group.Point().Add(group.Point().Mul(x, pub.cl[j-1]),
  245. pub.ca[j-1])
  246. rhs1 := group.Point().Add(
  247. group.Point().Mul(proof.f[j-1], params.A),
  248. group.Point().Mul(proof.za[j-1], params.B))
  249. if !lhs1.Equal(rhs1) {
  250. fmt.Printf("Failed equality check 1\n")
  251. return false
  252. }
  253. lhs2 := group.Point().Add(
  254. group.Point().Mul(
  255. group.Scalar().Sub(x, proof.f[j-1]),
  256. pub.cl[j-1]),
  257. pub.cb[j-1])
  258. rhs2 := group.Point().Mul(proof.zb[j-1], params.B)
  259. if !lhs2.Equal(rhs2) {
  260. fmt.Printf("Failed equality check 2\n")
  261. return false
  262. }
  263. }
  264. lhs := group.Point().Null()
  265. for i := uint32(0) ; i < two_n ; i++ {
  266. fprod := group.Scalar().One()
  267. j := uint32(1)
  268. mask := uint32(1) // mask = 2^(j-1)
  269. for ; j <= n ; {
  270. if (i & mask) != 0 {
  271. fprod = group.Scalar().Mul(fprod,
  272. proof.f[j-1])
  273. } else {
  274. fprod = group.Scalar().Mul(fprod,
  275. group.Scalar().Sub(x,
  276. proof.f[j-1]))
  277. }
  278. j++
  279. mask *= 2
  280. }
  281. if i < N {
  282. lhs = group.Point().Add(lhs,
  283. group.Point().Mul(fprod, c[i]))
  284. } else {
  285. lhs = group.Point().Add(lhs,
  286. group.Point().Mul(fprod, params.Y))
  287. }
  288. }
  289. rhs := group.Point().Mul(proof.zd, params.B)
  290. k := uint32(0)
  291. xk := group.Scalar().One() // xk = x^k
  292. for ; k < n ; {
  293. rhs = group.Point().Add(rhs,
  294. group.Point().Mul(xk, pub.cd[k]))
  295. k++
  296. xk = group.Scalar().Mul(xk, x)
  297. }
  298. if !lhs.Equal(rhs) {
  299. fmt.Printf("Failed equality check\n")
  300. return false
  301. }
  302. return true
  303. }