gk15.go 8.1 KB

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