gk15/gk15.go

/*
 * 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
}

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
	}
	fmt.Printf("n = %d\n", n);

	// We will keep the notation of the paper:
	// r, a, s, t, cl, ca, cb are 1-based,
	// c, rho, cd are 0-based.  The 1-based ones, we
	// just allocate an extra array element, and never
	// use element 0.
	var pub PubState
	var priv PrivState
	priv.r = make([]kyber.Scalar, n+1)
	priv.a = make([]kyber.Scalar, n+1)
	priv.s = make([]kyber.Scalar, n+1)
	priv.t = make([]kyber.Scalar, n+1)
	priv.rho = make([]kyber.Scalar, n)
	priv.ell = ell
	priv.privkey = privkey.Clone()
	pub.cl = make([]kyber.Point, n+1)
	pub.ca = make([]kyber.Point, n+1)
	pub.cb = make([]kyber.Point, n+1)
	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] = group.Scalar().Pick(rand)
		priv.a[j] = group.Scalar().Pick(rand)
		priv.s[j] = group.Scalar().Pick(rand)
		priv.t[j] = group.Scalar().Pick(rand)
		priv.rho[k] = group.Scalar().Pick(rand)

		pub.cl[j] = group.Point().Mul(priv.r[j], params.B)
		if (ell & mask) != 0 {
			pub.cl[j] = group.Point().Add(pub.cl[j], params.A)
		}
		pub.ca[j] = group.Point().Add(
				group.Point().Mul(priv.a[j], params.A),
				group.Point().Mul(priv.s[j], params.B))
		pub.cb[j] = group.Point().Mul(priv.t[j], params.B)
		if (ell & mask) != 0 {
			pub.cb[j] = group.Point().Add(pub.cb[j],
					group.Point().Mul(priv.a[j], params.A))
		}

		j++
		k++
		mask *= 2
	}

	k = 0
	for ; k < n ; {
		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()
			}

			// TODO: finish computation of p_i
			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]
						polymul_xplus(group, p_i, priv.a[j])
					} else {
						// Multiply p_i by a[j]
						polymul(group, p_i, priv.a[j])
					}
				} else {
					negaj := group.Scalar().Neg(priv.a[j])
					if (ell & jmask) != 0 {
						// Multiply p_i by -a[j]
						polymul(group, p_i, negaj)
					} else {
						// Multiply p_i by x - a[j]
						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")
			}
			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))
			}
		}

		k++
		mask *= 2
	}

	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+1)
	proof.za = make([]kyber.Scalar, n+1)
	proof.zb = make([]kyber.Scalar, n+1)

	var j, mask uint32
	// mask = 2^(j-1)
	j = 1
	mask = 1
	for  ; j <= n ; {
		if (priv.ell & mask) != 0 {
			proof.f[j] = group.Scalar().Add(x, priv.a[j])
		} else {
			proof.f[j] = priv.a[j].Clone()
		}
		proof.za[j] = group.Scalar().Add(
			group.Scalar().Mul(x, priv.r[j]), priv.s[j])
		proof.zb[j] = group.Scalar().Add(
			group.Scalar().Mul(
				group.Scalar().Sub(x, proof.f[j]),
				priv.r[j]),
			priv.t[j])

		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
}

func Verify(params GroupParams, pub PubState, x kyber.Scalar, proof Proof) bool {
	return false
}