With the Damgard-Fujisaki method [1], Peggy proves to Victor that she has a postive integer value, and using the secp256k1 curve.
Zero-knowledge proof (Damgard-Fujisaki method) for a positive value with ECC |
Method
In this case we will use the Damgard-Fujisaki method defined [here], and where Peggy has to prove to Victor that she has a postive value. First Victor and Peggy agree on two bases for their calculations (\(g\) and \(h\)) and a prime number (\(n\)). Victor then sends Peggy using a random number (\(r\)) as a challenge. As defined by Jacobi's four-square theorem, every positive value can be represented in the form:
\(x = x_0^2 + x_1^2 + x_2^2 + x_3^2\)
For example:
\(51 = 1^2 + 3^2 + 4^2 + 5^2\)
\(1451 = 1^2 +9^2 +12^2 +35^2\)
\(99999 = 1^2 +2^2 +313^2 +45^2\)
Peggy now creates four commitments from these four values, and takes four random numbers (\(r_0\), \(r_1\), \(r_2\) and \(r_3\)).
\(c_0=g^{x_0^2} h^{r_0} \pmod n\)
\(c_1=g^{x_1^2} h^{r_1} \pmod n\)
\(c_2=g^{x_2^2} h^{r_2} \pmod n\)
\(c_3=g^{x_3^2} h^{r_3} \pmod n\)
And:
\(r = r_0 + r_1 + r_2 + r_3\)
Victor then checks:
\(c = c_1 \times c_2 \times c_3 \times c_4\)
And this should be equal to:
\(g^x h^r \pmod n\)
Converting to ECC
We start with two points on the curve: \(G\) and \(H\). And then can compute:
\(c_0=({x_0}^2).G + (r_0).H\)
\(c_1=({x_1}^2).G + (r_1).H\)
\(c_2=({x_2}^2).G + (r_2).H\)
\(c_3=({x_3}^2).G + (r_3).H\)
and then:
\(r = r_0 + r_1 + r_2 + r_3\)
Victor then checks:
\(c = c_1 + c_2 + c_3 + c_4\)
and check than this equals:
\(x.G + r.H \)
Coding
The following is some simple coding to prove the method:
package main import ( "crypto/rand" "fmt" "math" "os" "strconv" "github.com/coinbase/kryptology/pkg/core/curves" ) func lipmaa(val int) (int, int, int, int) { for i := 0; i < 100000; i++ { for j := 0; j < 1000; j++ { for k := 0; k < 100; k++ { for l := 0; l < 10; l++ { if ((i * i) + (j * j) + (k * k) + (l * l)) == val { return i, j, k, l } } } } } return 0, 0, 0, 0 } func main() { nv := int(math.Pow(2, 19) - 1) argCount := len(os.Args[1:]) if argCount > 0 { nv, _ = strconv.Atoi(os.Args[1]) } if nv <= 0 { os.Exit(0) } curve := curves.K256() G := curve.Point.Generator() v := curve.Scalar.Random(rand.Reader) H := G.Mul(v) n := curve.Scalar.New(nv) x0v, x1v, x2v, x3v := lipmaa(nv) r0 := curve.Scalar.Random(rand.Reader) r1 := curve.Scalar.Random(rand.Reader) r2 := curve.Scalar.Random(rand.Reader) r3 := curve.Scalar.Random(rand.Reader) x0 := curve.Scalar.New(x0v) x1 := curve.Scalar.New(x1v) x2 := curve.Scalar.New(x2v) x3 := curve.Scalar.New(x3v) c0 := G.Mul(x0.Mul(x0)).Add(H.Mul(r0)) c1 := G.Mul(x1.Mul(x1)).Add(H.Mul(r1)) c2 := G.Mul(x2.Mul(x2)).Add(H.Mul(r2)) c3 := G.Mul(x3.Mul(x3)).Add(H.Mul(r3)) r := r0.Add(r1).Add(r2).Add(r3) c := c0.Add(c1).Add(c2).Add(c3) val := G.Mul(n).Add(H.Mul(r)) fmt.Printf("x=%d, x0= %d, x1=%d, x2=%d, x3=%d\n", nv, x0v, x1v, x2v, x3v) fmt.Printf("%d = %d^2+%d^2+%d^2+%d^2\n", nv, x0v, x1v, x2v, x3v) fmt.Printf("\nr0=%x\n", r0.Bytes()) fmt.Printf("r1=%x\n", r1.Bytes()) fmt.Printf("r2=%x\n", r2.Bytes()) fmt.Printf("r3=%x\n", r3.Bytes()) fmt.Printf("\nc0=%x\n", c0.ToAffineCompressed()) fmt.Printf("c1=%x\n", c1.ToAffineCompressed()) fmt.Printf("c2=%x\n", c2.ToAffineCompressed()) fmt.Printf("c3=%x\n", c3.ToAffineCompressed()) fmt.Printf("\nc=%x\n", c.ToAffineCompressed()) fmt.Printf("val=%x\n", val.ToAffineCompressed()) if c.Equal(val) { fmt.Printf("Peggy has proven that her value is positive") } else { fmt.Printf("Peggy has NOT proven that her value is positive") } }
A sample run is:
x=524287, x0= 1, x1=723, x2=39, x3=6 524287 = 1^2+723^2+39^2+6^2 r0=bc728e4e7b42d9f32b5e2b9e85880b7b6b38b1a829f6fcd633747e6c3e207d38 r1=44ed2c43b54ac2500bee1234a983adbb3fa5ff8da0e12c7cf5941495cf188574 r2=a40e6447ccbdb1a014b11887b9a097e72841d282ff2f508d88b78a5457b0831b r3=a6bf5571b08fafa85010de6fdaf44368ca4e8e8552b98e7610d991ec257bc0b3 c0=02aaf9df02e2c7021c986b4ad8ddfba1ed6be0dea13b097d3a0614be32812195d6 c1=023024f5e60598d1bf1bc33093c8012e8d80556f87df631a7980f293df8ef5b788 c2=032e986a414555b5ec0572da1fe5997632ec8be5b18c08765e7644e686eb2c3c99 c3=03ba3cf5c47fb9f186ad3406484cd6c3ca409e688678ca77f69cb871fc092598d8 c=02e340fbd0a03ece1722ce090ac5e90754a5f184cf6a621a3de030c4d7411db092 val=02e340fbd0a03ece1722ce090ac5e90754a5f184cf6a621a3de030c4d7411db092 Peggy has proven that her value is positive
Reference
[1] Damgård, I., & Fujisaki, E. (2002, December). A statistically-hiding integer commitment scheme based on groups with hidden order. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 125-142). Springer, Berlin, Heidelberg.