/* * An implementation of Groth and Kohlweiss, "One-out-of-Many Proofs: Or * How to Leak a Secret and Spend a Coin", Eurocrypt 2015 * https://eprint.iacr.org/2014/764.pdf */ package main import ( "fmt" "go.dedis.ch/kyber" "go.dedis.ch/kyber/util/random" ) type GroupParams struct { /* A group of prime order */ group kyber.Group /* Three generators of the group; the relative discrete logs * must be unknown. Commitments to a value x with randomness r * are x*A + r*B. Y is used to pad the list of commitments to a * power of 2. */ A, B, Y kyber.Point } // In the paper, some arrays are 0-based, and some are 1-based. We // want to keep all arrays 0-based, so the following arrays (1-based in // the paper) have 1 subtracted from their indices whenever they are // used: cl, ca, cb, r, a, s, t, f, za, zb // Each array in the three structs below is of length n, where // n = ceil(log_2(N)), and N is the number of commitments. // The total proof size (PubState plus Proof) is then // 4*n points, plus (3*n+1) scalars. type PubState struct { cl, ca, cb, cd []kyber.Point } type PrivState struct { r, a, s, t, rho []kyber.Scalar ell uint32 privkey kyber.Scalar } type Proof struct { f, za, zb []kyber.Scalar zd kyber.Scalar } // Multiply a polynomial expressed as a slice of coefficients by the // scalar a func polymul(group kyber.Group, poly []kyber.Scalar, a kyber.Scalar) { numcoeffs := len(poly) for i := 0 ; i < numcoeffs ; i++ { poly[i] = group.Scalar().Mul(poly[i], a) } } // Multiply a polynomial expressed as a slice of coefficients by // the linear polynomial x+a func polymul_xplus(group kyber.Group, poly []kyber.Scalar, a kyber.Scalar) { numcoeffs := len(poly) if !poly[numcoeffs-1].Equal(group.Scalar().Zero()) { panic("Degree too large in multiplication") } for i := numcoeffs-1 ; i > 0 ; i-- { poly[i] = group.Scalar().Add( group.Scalar().Mul(poly[i], a), poly[i-1]) } poly[0] = group.Scalar().Mul(poly[0], a) } /* Sigma protocol for one out of N commitments containing 0 * Section 3 of https://eprint.iacr.org/2014/764.pdf */ func ProofStep1(params GroupParams, c []kyber.Point, ell uint32, privkey kyber.Scalar) (PubState, PrivState) { N := uint32(len(c)) rand := random.New() group := params.group // Find n := ceil(log_2(N)) n := uint32(1) two_n := uint32(2) // 2^n for ; two_n < N ; { n += 1 two_n *= 2 } var pub PubState var priv PrivState priv.r = make([]kyber.Scalar, n) priv.a = make([]kyber.Scalar, n) priv.s = make([]kyber.Scalar, n) priv.t = make([]kyber.Scalar, n) priv.rho = make([]kyber.Scalar, n) priv.ell = ell priv.privkey = privkey.Clone() pub.cl = make([]kyber.Point, n) pub.ca = make([]kyber.Point, n) pub.cb = make([]kyber.Point, n) pub.cd = make([]kyber.Point, n) var j, k, mask uint32 // mask = 2^k j = 1 k = 0 mask = 1 for ; k < n ; { priv.r[j-1] = group.Scalar().Pick(rand) priv.a[j-1] = group.Scalar().Pick(rand) priv.s[j-1] = group.Scalar().Pick(rand) priv.t[j-1] = group.Scalar().Pick(rand) priv.rho[k] = group.Scalar().Pick(rand) pub.cl[j-1] = group.Point().Mul(priv.r[j-1], params.B) if (ell & mask) != 0 { pub.cl[j-1] = group.Point().Add(pub.cl[j-1], params.A) } pub.ca[j-1] = group.Point().Add( group.Point().Mul(priv.a[j-1], params.A), group.Point().Mul(priv.s[j-1], params.B)) pub.cb[j-1] = group.Point().Mul(priv.t[j-1], params.B) if (ell & mask) != 0 { pub.cb[j-1] = group.Point().Add(pub.cb[j-1], group.Point().Mul(priv.a[j-1], params.A)) } j++ k++ mask *= 2 } for k = 0 ; k < n ; k++ { pub.cd[k] = group.Point().Mul(priv.rho[k], params.B) } for i := uint32(0); i < two_n; i++ { // Compute the coefficients of p_i p_i := make([]kyber.Scalar, n+1) p_i[0] = group.Scalar().One() for t := uint32(1); t <= n; t++ { p_i[t] = group.Scalar().Zero() } j = 1 // jmask = 2^(j-1) jmask := uint32(1) for ; j <= n ; { if (i & jmask) != 0 { if (ell & jmask) != 0 { // Multiply p_i by x + a[j-1] polymul_xplus(group, p_i, priv.a[j-1]) } else { // Multiply p_i by a[j-1] polymul(group, p_i, priv.a[j-1]) } } else { negaj := group.Scalar().Neg(priv.a[j-1]) if (ell & jmask) != 0 { // Multiply p_i by -a[j-1] polymul(group, p_i, negaj) } else { // Multiply p_i by x - a[j-1] polymul_xplus(group, p_i, negaj) } } j++ jmask *= 2 } if i == ell && !p_i[n].Equal(group.Scalar().One()) { panic("Leading coeff should be 1 but was not") } if i != ell && !p_i[n].Equal(group.Scalar().Zero()) { panic("Leading coeff should be 0 but was not") } for k = 0 ; k < n ; k++ { if i < N { pub.cd[k] = group.Point().Add(pub.cd[k], group.Point().Mul(p_i[k], c[i])) } else { pub.cd[k] = group.Point().Add(pub.cd[k], group.Point().Mul(p_i[k], params.Y)) } } } return pub, priv } func GenChallenge(params GroupParams, pub PubState) kyber.Scalar { // In the interactive version, just pick a random challenge. // In the noninteractive version, this would be a hash of pub // and a message. rand := random.New() return params.group.Scalar().Pick(rand) } func ProofStep2(params GroupParams, priv PrivState, x kyber.Scalar) Proof { var proof Proof n := uint32(len(priv.rho)) group := params.group proof.f = make([]kyber.Scalar, n) proof.za = make([]kyber.Scalar, n) proof.zb = make([]kyber.Scalar, n) var j, mask uint32 // mask = 2^(j-1) j = 1 mask = 1 for ; j <= n ; { if (priv.ell & mask) != 0 { proof.f[j-1] = group.Scalar().Add(x, priv.a[j-1]) } else { proof.f[j-1] = priv.a[j-1].Clone() } proof.za[j-1] = group.Scalar().Add( group.Scalar().Mul(x, priv.r[j-1]), priv.s[j-1]) proof.zb[j-1] = group.Scalar().Add( group.Scalar().Mul( group.Scalar().Sub(x, proof.f[j-1]), priv.r[j-1]), priv.t[j-1]) j++ mask *= 2 } proof.zd = group.Scalar().Zero() k := uint32(0) xk := group.Scalar().One() // x^k for ; k < n ; { proof.zd = group.Scalar().Sub(proof.zd, group.Scalar().Mul(priv.rho[k], xk)) k++ xk = group.Scalar().Mul(xk, x) } // At this point, xk = x^n proof.zd = group.Scalar().Add(proof.zd, group.Scalar().Mul(priv.privkey, xk)) return proof } // We assume that the checks that the Points are in fact in the right // group and the Scalars are in the right range were done at the time // the PubState and Proof structures were populated from data received // over the network. This function checks the relations between the // elements. func Verify(params GroupParams, c []kyber.Point, pub PubState, x kyber.Scalar, proof Proof) bool { N := uint32(len(c)) group := params.group // Find n := ceil(log_2(N)) n := uint32(1) two_n := uint32(2) // 2^n for ; two_n < N ; { n += 1 two_n *= 2 } // Check that the lengths of the arrays are correct intn := int(n) if len(pub.cl) != intn || len(pub.ca) != intn || len(pub.cb) != intn || len(pub.cd) != intn || len(proof.f) != intn || len(proof.za) != intn || len(proof.zb) != intn { fmt.Printf("Inputs not of the correct length\n") return false } for j := uint32(1) ; j <= n ; j++ { lhs1 := group.Point().Add(group.Point().Mul(x, pub.cl[j-1]), pub.ca[j-1]) rhs1 := group.Point().Add( group.Point().Mul(proof.f[j-1], params.A), group.Point().Mul(proof.za[j-1], params.B)) if !lhs1.Equal(rhs1) { fmt.Printf("Failed equality check 1\n") return false } lhs2 := group.Point().Add( group.Point().Mul( group.Scalar().Sub(x, proof.f[j-1]), pub.cl[j-1]), pub.cb[j-1]) rhs2 := group.Point().Mul(proof.zb[j-1], params.B) if !lhs2.Equal(rhs2) { fmt.Printf("Failed equality check 2\n") return false } } lhs := group.Point().Null() for i := uint32(0) ; i < two_n ; i++ { fprod := group.Scalar().One() j := uint32(1) mask := uint32(1) // mask = 2^(j-1) for ; j <= n ; { if (i & mask) != 0 { fprod = group.Scalar().Mul(fprod, proof.f[j-1]) } else { fprod = group.Scalar().Mul(fprod, group.Scalar().Sub(x, proof.f[j-1])) } j++ mask *= 2 } if i < N { lhs = group.Point().Add(lhs, group.Point().Mul(fprod, c[i])) } else { lhs = group.Point().Add(lhs, group.Point().Mul(fprod, params.Y)) } } rhs := group.Point().Mul(proof.zd, params.B) k := uint32(0) xk := group.Scalar().One() // xk = x^k for ; k < n ; { rhs = group.Point().Add(rhs, group.Point().Mul(xk, pub.cd[k])) k++ xk = group.Scalar().Mul(xk, x) } if !lhs.Equal(rhs) { fmt.Printf("Failed equality check\n") return false } return true }