Proving You Know A Polynomial — And Not Revealing It: Meet Kate

In a previous post, I showed how you can create a simple method in commiting to a polynomial value:

Knowledge Commitments With Polynomials

Please excuse the poor layout of the maths in Medium. The full layout is here.

Meet Kate

The KZG polynomial commitment scheme [1] is also known as the Kate method. It allows a committer (Peggy) to commit to a polynomial with a short string. Victor can send Peggy a challenge, and of which she creates a proof against the committed polynomial. It has applications for Credentials and Selective Disclosure of Signed Data. ZKS (zero-knowledge sets), and Veriable Secret Sharing (VSS).

Trusted Setup

Overall, xG∈𝔾1 defines a point (x.G) on one curve (𝔾1) and xH∈𝔾2 defines a point (x.H) on the other curve (𝔾2). The notation we will use is:

[x]1=xG∈𝔾1

[x]2=xH∈𝔾2

and 𝔾1=⟨G⟩ and 𝔾2=⟨H⟩. G is the generator of 𝔾1, and H is the generator of 𝔾2.

In the first part, we use a Trusted Setup, and should be computed with a Multi-Party Computation (MPC). The parameters are generated from random τ∈𝔽p, and from this parameter, we can compute [τi]1 and [τi]2 for i=0,…,n−1:

[τi]1=([τ0]1,[τ1]1,[τ2]1,…,[τn−1]1)

[τi]2=([τ0]2,[τ1]2,[τ2]2,…,[τn−1]2)

Which in additive representation is:

(G,τG,τ2G,…,τn−1G)∈𝔾1

(H,τH,τ2H,…,τn−1H)∈𝔾2

Commitment

With this we have a polynomial of p(x)=∑ni=0pixi

and then can create a commitment with:

c=[p(τ)]1

and where c=∑deg(p(x))i=0[τi]⋅pi

Peggy (‘the prover’) would then send this commitment c to Victor (the verifier) as a proof against the polynomial. Victor would then choose a value z∈𝔽p, and where 𝔽p is the finite field defined by the polynomial.

Evaluating the proof

Peggy then computes p(z)=y, and a quotient polynomial is derived as: q(x)=p(x)−yx−z. This polynomial proves that p(z)=y, and where p(x)−y is divisible by x−z. This means it has a root at z — as p(z)−y=0. The evaluation proof is then:

π=[q(τ)]1

and which is determine from π=∑deg(q(x))i=0[τi]⋅qi Peggy can then send this evaluation proof π to Victor.

Verifying the proof

Victor has the commitment of c=[p(τ)]1, the evaluation of y=p(z), and the proof of π=[q(τ)]1. He can now check the pairing of:

ê (π,[τ]2−[z]2)==ê (c−[y]1,H)

The prover provides π and c are given by Peggy, and where [τ]2 is derived in the trusted setup, [z]2 defines the point at which the polynomial has been evaluated with, and [y]1 defines the claimed value of p(z).

This works because:

ê (π,[τ]2−[z]2)==ê (c−[y]1,H)

⇒ê ([q(τ)]1,[τ−z]2)==ê ([p(τ)]1−[y]1,H)

⇒[q(τ)⋅(τ−z)]T==[p(τ)−y]T

For this we see that we have q(x)(x−z)=p(x)−y, and which can be rearranged as q(x)=p(x)−yx−z. This is evaluated at τ for the trusted setup and not known for q(τ)=p(τ)−yτ−z.

Coding

Here is the coding for a commitment to the polynomial of x³+x+5 and where we have a challenge of z=3, and where p(3)=3³+3+5=35 [here]:

package main
import (
 "fmt"
 "math/big"
 zzz "github.com/arnaucube/kzg-commitments-study"
)
func main() {
 p := []*big.Int{
  big.NewInt(5),
  big.NewInt(1), // x^1
  big.NewInt(0), // x^2
  big.NewInt(1), // x^3
 }
 // TrustedSetup
 ts, _ := zzz.NewTrustedSetup(len(p))
 // Commit
 c := zzz.Commit(ts, p)
 // p(z)=y --> p(3)=35
 z := big.NewInt(3)
 y := big.NewInt(35)
 // z & y: to prove an evaluation p(z)=y
 proof, _ := zzz.EvaluationProof(ts, p, z, y)
 // verification
 v := zzz.Verify(ts, c, proof, z, y)
 fmt.Printf("Polynomial: %s\n\n", zzz.PolynomialToString(p))
 fmt.Printf("Ts=%v\n\nz=%v\n\ny=%v\n\n", ts, z, y)
 fmt.Printf("Proof: %s\n\n", proof)
 fmt.Printf("Verified: %v", v)
}

and a sample run:

Polynomial: x³ + x¹ + 5
Ts=&{[bn256.G1(0000000000000000000000000000000000000000000000000000000000000001, 0000000000000000000000000000000000000000000000000000000000000002) bn256.G1(2e16fb2d6441058fd96668f7011657672bcd4590dd0a27a26bcb3ce4339d435b, 2b1496f37a27b0c0874ba265341b915f6e075cca2bf4524c62de45325d8d89ec) bn256.G1(195cea9981977bb1be1e954e1037e8394875cb13a4ba27ffe4b0410a7d828294, 1f3766199b55276e127cb578483b148b0fd848477b29523d6da9a7105a3ea193) bn256.G1(130b08bd79890c11f9c02ae0d0a73d507e7a0b1d2a6a3d4bdfb9dae383a6e8fb, 1b7ada10ecba4a4c105235ca859f562d4e90ffdae5e8030d6862f3c2cfd1078f)] [bn256.G2((198e9393920d483a7260bfb731fb5d25f1aa493335a9e71297e485b7aef312c2, 1800deef121f1e76426a00665e5c4479674322d4f75edadd46debd5cd992f6ed), (090689d0585ff075ec9e99ad690c3395bc4b313370b38ef355acdadcd122975b, 12c85ea5db8c6deb4aab71808dcb408fe3d1e7690c43d37b4ce6cc0166fa7daa)) bn256.G2((27649cf8bc9235496a95a0eed267ab0575fc0e5ee617030000ed32b7ddefdc2b, 26825048b9c228e19b608c7b5decd53a5933382a2f939450c0e762b28df9d91e), (121a56dd25b40d35fdc66b29ebcb931e38a46d7c35f4ff886bc47cb0931b09f4, 061e6c2d84c94995ad887e089a16bacd786d21b69554e40d061d2872dfad75f7)) bn256.G2((019845d01267e61f923d30c0e6e6d4cf93731a4821c008d87d037e1c9cba446f, 2d88a13dc9ecfc314ed03cb94c3919658e99c52bdda0e18403e1c036f2dea796), (1de3b8cff466dcfe069844a225654a35f573971a855ab1d2771083fe0d9f1c41, 14b34109ba5ac99b67139e44adce4c395f260ec7ce0b8d97ed1d4a8db0ca16ea)) bn256.G2((290c20c370ffd4bf2d928265eef38f85934b9e7c75511f4e4a7a068278ee5298, 17596d2ed876e2198fecc136ea3bf189d6a97b25da28be2218693aa93bc761ed), (2363ba96a818adbf3e6f95d8b5c19daf3a0fbd789ba22be82de387ef79399314, 17e9091710f525baa7f8fad9ba636a193abf138f75fe3117280b99e468c66785))]}
z=3
y=35
Proof: bn256.G1(0a0d867417b725296c5f749cb0dcc5c39b6b07572c9c7f95a831672acd242abe, 0d1c632b099402acc37d35f03d69c4d07ffa399a28c4f4ad0a2f6f210fb3075f)
Verified: true

Conclusions

As we move towards lattice cryptography, we will increasingly use polynomials. The Kate protocol is one method we can use to show the Peggy still has knowledge of a defined polynomial.

References

[1] Kate, A., Zaverucha, G. M., & Goldberg, I. (2010). Constant-size commitments to polynomials and their applications. In Advances in Cryptology-ASIACRYPT 2010: 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5–9, 2010. Proceedings 16 (pp. 177–194). Springer Berlin Heidelberg.