Proving You Know A Polynomial — And Not Revealing It: Meet Kate
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:
Do you remember polynomials at school? I hope so because the world of privacy and security is built on these algebraic…medium.com
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.