Proving Your Post Code in a Set of Post Codes, Without Revealing Your Post Code
Proving Your Post Code in a Set of Post Codes, Without Revealing Your Post Code
Let’s say that you have to pay a fine if you parked in a certain area of London. But, you have a permit that codes the areas of E1 1LJ, E1 1AA, E1 1AB, and E1 1AE, and where you parked your car in E1 1AE. How can you prove to the council that you have a valid parking permit for the place you parked without giving away where you parked?
For this, we can create a Zero Knowledge Proof (ZKP) for set membership. In this case, we have a set of valid parking places of “E11LJ E11AA E11AB E11AE”, and then create a ZKP for the location of “E11AE”. The proof will show that you have a postcode which is contained within the set without revealing it.
With this, Jan Camenisch et al created a method where we can prove that we have a value in a set of values, and without giving our value away [1]. The paper was produced in 2008, and is often referred to as CSS08. With this, we provide a zero-knowledge proof that σ is included in a discrete set Φ. This set is represented as 64-bit integers and could thus be hashed version of the string.
Initially, the verifier (Victor) sends the prover (Peggy) a signature of every element within Φ (which is the set of items to prove against). Peggy then receives a signature for the element (σ) and blinds it with a comment (C). This commitment is C = g^σ.h^r, where r is the blinding factor.
We can convert a string into a 64-bit integer by taking a SHA-256 hash and then using eight bytes to produce a signed 64-bit integer:
func StringToInt64(A string) int64 {
var ret int64
h := sha256.New()
h.Write([]byte(A))
bs := h.Sum(nil)[:8] // Just use 64 bits
buf := bytes.NewBuffer(bs)
binary.Read(buf, binary.BigEndian, &ret)
if ret < 0 {
ret = -ret
} // Make postive
return ret
}We can then take a string array for the postcodes and then parse these between spaces, and convert these into a 64-bit integer array to define our set:
func StringToIntInt64(A string) []int64 {
strs := strings.Split(A, " ")
ary := make([]int64, len(strs))
for i := range ary {
ary[i] = StringToInt64(strs[i])
}
return ary
}The code is then [link] [2]:
package main
import (
"bytes"
"crypto/rand"
"crypto/sha256"
"encoding/binary"
"fmt"
"os"
"strings"
"github.com/i0xdecaf/zkrp/ccs08"
"go.dedis.ch/kyber/v3/pairing/bn256"
)
func StringToInt64(A string) int64 {
var ret int64
h := sha256.New()
h.Write([]byte(A))
bs := h.Sum(nil)[:8] // Just use 64 bits
buf := bytes.NewBuffer(bs)
binary.Read(buf, binary.BigEndian, &ret)
if ret < 0 {
ret = -ret
} // Make postive
return ret
}
func StringToIntInt64(A string) []int64 {
strs := strings.Split(A, " ")
ary := make([]int64, len(strs))
for i := range ary {
ary[i] = StringToInt64(strs[i])
}
return ary
}
func main() {
tofind := "E11AE"
set := "E11LJ E11AA E11AB E11AE"
argCount := len(os.Args[1:])
if argCount > 0 {
tofind = os.Args[1]
}
if argCount > 1 {
set = os.Args[2]
}
s := StringToIntInt64(set)
p, _ := ccs08.SetupSet(s)
fmt.Printf("To prove: %s [%d]\n", tofind, StringToIntInt64(tofind))
fmt.Printf("Set: %v\n", s)
r, _ := rand.Int(rand.Reader, bn256.Order)
proof_out, err := ccs08.ProveSet(StringToInt64(tofind), r, p)
if err != nil {
fmt.Printf("Error %s", err.Error())
return
}
result, err2 := ccs08.VerifySet(&proof_out, &p)
if err2 != nil {
fmt.Printf("Error %s", err.Error())
return
}
if result == true {
fmt.Printf("\nProof that %s is in [%s]\n\n", tofind, set)
} else {
fmt.Printf("\nDid not find value in array\n")
}
fmt.Printf("Proof: C= %s\n", proof_out.C)
fmt.Printf("Proof: D= %s\n", proof_out.D)
fmt.Printf("Proof: V= %s\n", proof_out.V)
}Now, when we can try if E11AB is included in a set of [E11LJ E11AA E11AB E11AE] [link]:
To prove: E11AB [[4430824517528255324]]
Set: [1281183710520809036 5058162997375079209 4430824517528255324 2546757751935566498]
Proof that E11AB is in [E11LJ E11AA E11AB E11AE]
Proof: C= bn256.G2((7509873101214563597163683780190650039892638744018480009533152639528421573588,4475718032506726237139207880503469751673889912137360720800657351782230168130), (9188851371211643606407750017586881453211197241295535426263957389554181084227,18992014779931465783960663663280212683899890522293147279021309024382333571389), (6879391832489960392949975993929586748964605278079293556349212526397655394163,3844085117072733930522556927617194359937237558518477575268041663481016124684))
Proof: D= bn256.G2((19355457211851888432977175934410856791524853651139502739322367817795174382173,8806361547031016666199222727470212815571941949136321034587808231739030579132), (20336671890284777311594726186351805529212458788694915453274566302607164394586,5086717128969460245852049948120151339215585051883016476940954689933201622563), (0,1))
Proof: V= bn256.G2((15941655410179962564251634815483114091181494694542018383163679157355504337508,10641174239565692007167712294782899033411349507595365405311563271413378499800), (2517555212710176931884574117195971314655042724175768947683110308453733308529,8707140745037179280144535396889037601103996382682310712101145144167941001091), (8370535292913395075061781860418767351958837960139306760022823624996857342071,3095104344669839604671953292680082217798648219197010648729282314038918857078))Now, when we can try E11AD, we can see that we cannot create a valid proof [link]:
To prove: E11AD [[5797095357436850670]]
Set: [1281183710520809036 5058162997375079209 4430824517528255324 2546757751935566498]
Error Could not generate proof. Element does not belong to the interval.Conclusions
One day, soon, we will move to a world with most trusted computing, and where we can prove things without revealing sensitive information. If you are interested in range proofs for this, then try a few examples here:
https://asecuritysite.com/bulletproof
Reference
[1] Camenisch, J., Chaabouni, R., & Shelat, A. (2008, December). Efficient protocols for set membership and range proofs. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 234–252). Berlin, Heidelberg: Springer Berlin Heidelberg.