nizk/stage1: Implementation of proof and verificaiton for stage1

The proof and verification of statements according to Stage1 (page 4) is
done.

5 files changed, 227 insertions, 44 deletions

diff --git a/nizk/commit/commit.go b/nizk/commit/commit.go
index d9d06b5..5238c15 100644
--- a/nizk/commit/commit.go
+++ b/nizk/commit/commit.go
@@ -1,9 +1,7 @@
 package commit
 
 import (
-	"crypto/sha512"
-
-	"kesim.org/seal/curve"
+	. "kesim.org/seal/nizk"
 )
 
 // This is a construction of a proof of a statement of the form
@@ -11,13 +9,6 @@ import (
 //		|| [(Φ = g^(αβ+1)) && (A = g^α) && (Β = g^β)]
 // for given Φ, A and B
 
-type Scalar = curve.Curve25519Scalar
-type Point = curve.Curve25519Point
-
-var Curve = curve.Curve25519
-var g = Curve.Generator()
-var one = Curve.ScalarOne()
-
 type Statement struct {
 	α    *Scalar
 	β    *Scalar
@@ -45,14 +36,14 @@ func commitment(α, β *Scalar, plus bool) *Commitment {
 	φ := α.Mul(β)
 
 	if plus {
-		Φ = g.Exp(φ.Add(one))
+		Φ = G.Exp(φ.Add(One))
 	} else {
-		Φ = g.Exp(φ)
+		Φ = G.Exp(φ)
 	}
 	return &Commitment{
 		Φ: Φ,
-		A: g.Exp(α),
-		B: g.Exp(β),
+		A: G.Exp(α),
+		B: G.Exp(β),
 	}
 }
 
@@ -72,25 +63,19 @@ func (s *Statement) Proof() *Proof {
 	r2 = Curve.RandomScalar()
 	ω = Curve.RandomScalar()
 
-	if s == nil {
-		panic("s is nil")
-	} else if ω == nil {
-		panic("ω is nil")
-	}
-
 	if s.plus {
-		ε[0][0] = g.Exp(r1)
-		ε[0][1] = s.B.Exp(r1).Mul(g.Exp(ω))
-		ε[1][0] = g.Exp(r2)
+		ε[0][0] = G.Exp(r1)
+		ε[0][1] = s.B.Exp(r1).Mul(G.Exp(ω))
+		ε[1][0] = G.Exp(r2)
 		ε[1][1] = s.B.Exp(r2)
 	} else {
-		ε[0][0] = g.Exp(r1)
+		ε[0][0] = G.Exp(r1)
 		ε[0][1] = s.B.Exp(r1)
-		ε[1][0] = g.Exp(r2).Mul(s.A.Exp(ω))
-		ε[1][1] = s.B.Exp(r2).Mul(s.Φ.Div(g).Exp(ω))
+		ε[1][0] = G.Exp(r2).Mul(s.A.Exp(ω))
+		ε[1][1] = s.B.Exp(r2).Mul(s.Φ.Div(G).Exp(ω))
 	}
 
-	ch := challenge(g, s.Φ, s.A, s.B, ε[0][0], ε[0][1], ε[1][0], ε[1][1])
+	ch := Challenge(G, s.Φ, s.A, s.B, ε[0][0], ε[0][1], ε[1][0], ε[1][1])
 	pr := &Proof{}
 
 	if s.plus {
@@ -108,24 +93,12 @@ func (s *Statement) Proof() *Proof {
 	return pr
 }
 
-func challenge(points ...*Point) *Scalar {
-	h512 := sha512.New()
-	for _, p := range points {
-		h512.Write(p.Bytes())
-	}
-	ch, e := Curve.ScalarFromBytes(h512.Sum(nil))
-	if e != nil {
-		panic(e)
-	}
-	return ch
-}
-
 func (c *Commitment) Verify(p *Proof) bool {
 	var ε [2][2]*Point
-	ε[0][0] = g.Exp(p.Rho[0]).Mul(c.A.Exp(p.Ch[0]))
+	ε[0][0] = G.Exp(p.Rho[0]).Mul(c.A.Exp(p.Ch[0]))
 	ε[0][1] = c.B.Exp(p.Rho[0]).Mul(c.Φ.Exp(p.Ch[0]))
-	ε[1][0] = g.Exp(p.Rho[1]).Mul(c.A.Exp(p.Ch[1]))
-	ε[1][1] = c.B.Exp(p.Rho[1]).Mul(c.Φ.Div(g).Exp(p.Ch[1]))
-	ch := challenge(g, c.Φ, c.A, c.B, ε[0][0], ε[0][1], ε[1][0], ε[1][1])
+	ε[1][0] = G.Exp(p.Rho[1]).Mul(c.A.Exp(p.Ch[1]))
+	ε[1][1] = c.B.Exp(p.Rho[1]).Mul(c.Φ.Div(G).Exp(p.Ch[1]))
+	ch := Challenge(G, c.Φ, c.A, c.B, ε[0][0], ε[0][1], ε[1][0], ε[1][1])
 	return p.Ch[0].Add(p.Ch[1]).Equal(ch)
 }
diff --git a/nizk/commit/commit_test.go b/nizk/commit/commit_test.go
index 09b8416..916ba0e 100644
--- a/nizk/commit/commit_test.go
+++ b/nizk/commit/commit_test.go
@@ -1,6 +1,10 @@
 package commit
 
-import "testing"
+import (
+	"testing"
+
+	. "kesim.org/seal/nizk"
+)
 
 func TestStatement(t *testing.T) {
 	var α, β = Curve.RandomScalar(), Curve.RandomScalar()
diff --git a/nizk/nizk.go b/nizk/nizk.go
new file mode 100644
index 0000000..7ea6d8a
--- /dev/null
+++ b/nizk/nizk.go
@@ -0,0 +1,28 @@
+package nizk
+
+import (
+	"crypto/sha512"
+
+	"kesim.org/seal/curve"
+)
+
+// Common functions for the various proof
+
+type Scalar = curve.Curve25519Scalar
+type Point = curve.Curve25519Point
+
+var Curve = curve.Curve25519
+var G = Curve.Generator()
+var One = Curve.ScalarOne()
+
+func Challenge(points ...*Point) *Scalar {
+	h512 := sha512.New()
+	for _, p := range points {
+		h512.Write(p.Bytes())
+	}
+	ch, e := Curve.ScalarFromBytes(h512.Sum(nil))
+	if e != nil {
+		panic(e)
+	}
+	return ch
+}
diff --git a/nizk/stage1/stage1.go b/nizk/stage1/stage1.go
new file mode 100644
index 0000000..691ea74
--- /dev/null
+++ b/nizk/stage1/stage1.go
@@ -0,0 +1,154 @@
+package stage1
+
+import (
+	. "kesim.org/seal/nizk"
+)
+
+// Implements the proof and verification of statements of the following form:
+// σ ==   [ Z=g^(xy) ∧ X=g^x ∧ Y=g^y ∧ C=g^(αβ)   ∧ A=g^α ∧ B=g^β ]
+//	∨ [ Z=g^(xr) ∧ X=g^x ∧ R=g^r ∧ C=g^(αβ+1) ∧ A=g^α ∧ B=g^β ]
+// for given Z, X, Y, R, C, A and B
+
+type Statement struct {
+	x    *Scalar
+	y    *Scalar
+	r    *Scalar
+	α    *Scalar
+	β    *Scalar
+	plus bool
+	*Commitment
+}
+
+type Commitment struct {
+	X *Point
+	Y *Point
+	Z *Point
+	R *Point
+	A *Point
+	B *Point
+	C *Point
+}
+
+func NewStatement(x, y, r, α, β *Scalar, plus bool) *Statement {
+	return &Statement{
+		x:          x,
+		y:          y,
+		r:          r,
+		α:          α,
+		β:          β,
+		plus:       plus,
+		Commitment: commitment(x, y, r, α, β, plus),
+	}
+}
+
+func commitment(x, y, r, α, β *Scalar, plus bool) *Commitment {
+	var Z *Point
+	φ := α.Mul(β)
+	if plus {
+		Z = G.Exp(x.Mul(r))
+		φ = φ.Add(One)
+	} else {
+		Z = G.Exp(x.Mul(y))
+	}
+
+	return &Commitment{
+		Z: Z,
+		X: G.Exp(x),
+		Y: G.Exp(y),
+		R: G.Exp(r),
+		A: G.Exp(α),
+		B: G.Exp(β),
+		C: G.Exp(φ),
+	}
+}
+
+func (s *Statement) Commit() *Commitment {
+	return s.Commitment
+}
+
+type Proof struct {
+	Ch  [2]*Scalar
+	Rho [2][2]*Scalar
+}
+
+func (s *Statement) Proof() *Proof {
+	var ε [2][4]*Point
+	var r1, r2, ρ1, ρ2, ω *Scalar
+	for _, s := range []**Scalar{&r1, &r2, &ρ1, &ρ2, &ω} {
+		*s = Curve.RandomScalar()
+	}
+
+	if s.plus {
+		ε[0][0] = G.Exp(r1).Mul(s.X.Exp(ω))
+		ε[0][1] = G.Exp(r2).Mul(s.A.Exp(ω))
+		ε[0][2] = s.Y.Exp(r1).Mul(s.Z.Exp(ω))
+		ε[0][3] = s.B.Exp(r2).Mul(s.C.Exp(ω))
+		ε[1][0] = G.Exp(ρ1)
+		ε[1][1] = G.Exp(ρ2)
+		ε[1][2] = s.R.Exp(ρ1)
+		ε[1][3] = s.B.Exp(ρ2)
+	} else {
+		ε[0][0] = G.Exp(r1)
+		ε[0][1] = G.Exp(r2)
+		ε[0][2] = s.Y.Exp(r1)
+		ε[0][3] = s.B.Exp(r2)
+		ε[1][0] = G.Exp(ρ1).Mul(s.X.Exp(ω))
+		ε[1][1] = G.Exp(ρ2).Mul(s.A.Exp(ω))
+		ε[1][2] = s.R.Exp(ρ1).Mul(s.Z.Exp(ω))
+		ε[1][3] = s.B.Exp(ρ2).Mul(s.C.Div(G).Exp(ω))
+	}
+
+	p := []*Point{G, s.A, s.B, s.C, s.R, s.X, s.Y, s.Z}
+	for _, e := range ε[0] {
+		p = append(p, e)
+	}
+	for _, e := range ε[1] {
+		p = append(p, e)
+	}
+
+	ch := Challenge(p...)
+	pr := &Proof{}
+
+	if s.plus {
+		pr.Ch[0] = ω
+		pr.Ch[1] = ch.Sub(ω)
+		pr.Rho[0][0] = r1
+		pr.Rho[0][1] = r2
+		pr.Rho[1][0] = ρ1.Sub(s.x.Mul(pr.Ch[1]))
+		pr.Rho[1][1] = ρ2.Sub(s.α.Mul(pr.Ch[1]))
+	} else {
+		pr.Ch[0] = ch.Sub(ω)
+		pr.Ch[1] = ω
+		pr.Rho[0][0] = r1.Sub(s.x.Mul(pr.Ch[0]))
+		pr.Rho[0][1] = r2.Sub(s.α.Mul(pr.Ch[0]))
+		pr.Rho[1][0] = ρ1
+		pr.Rho[1][1] = ρ2
+	}
+
+	return pr
+}
+
+func (c *Commitment) Verify(p *Proof) bool {
+	var ε [2][4]*Point
+
+	ε[0][0] = G.Exp(p.Rho[0][0]).Mul(c.X.Exp(p.Ch[0]))
+	ε[0][1] = G.Exp(p.Rho[0][1]).Mul(c.A.Exp(p.Ch[0]))
+	ε[0][2] = c.Y.Exp(p.Rho[0][0]).Mul(c.Z.Exp(p.Ch[0]))
+	ε[0][3] = c.B.Exp(p.Rho[0][1]).Mul(c.C.Exp(p.Ch[0]))
+	ε[1][0] = G.Exp(p.Rho[1][0]).Mul(c.X.Exp(p.Ch[1]))
+	ε[1][1] = G.Exp(p.Rho[1][1]).Mul(c.A.Exp(p.Ch[1]))
+	ε[1][2] = c.R.Exp(p.Rho[1][0]).Mul(c.Z.Exp(p.Ch[1]))
+	ε[1][3] = c.B.Exp(p.Rho[1][1]).Mul(c.C.Div(G).Exp(p.Ch[1]))
+
+	points := []*Point{G, c.A, c.B, c.C, c.R, c.X, c.Y, c.Z}
+	for _, e := range ε[0] {
+		points = append(points, e)
+	}
+	for _, e := range ε[1] {
+		points = append(points, e)
+	}
+
+	ch := Challenge(points...)
+
+	return p.Ch[0].Add(p.Ch[1]).Equal(ch)
+}
diff --git a/nizk/stage1/stage1_test.go b/nizk/stage1/stage1_test.go
new file mode 100644
index 0000000..828dd0a
--- /dev/null
+++ b/nizk/stage1/stage1_test.go
@@ -0,0 +1,24 @@
+package stage1
+
+import (
+	"testing"
+
+	. "kesim.org/seal/nizk"
+)
+
+func TestStatement(t *testing.T) {
+	var x, y, r, α, β *Scalar
+	for _, s := range []**Scalar{&x, &y, &r, &α, &β} {
+		*s = Curve.RandomScalar()
+	}
+
+	st1, st2 := NewStatement(x, y, r, α, β, true), NewStatement(x, y, r, α, β, false)
+	c1, c2 := st1.Commit(), st2.Commit()
+	pr1, pr2 := st1.Proof(), st2.Proof()
+	if !c1.Verify(pr1) {
+		t.Fatal("Could not verify st1 with c1 and pr1, plus=true case")
+	}
+	if !c2.Verify(pr2) {
+		t.Fatal("Could not verify st2 with c2 and pr2, plus=false case")
+	}
+}