So, let's say there's a number of winning tickets in a lottery of [654, 703, 991, 1011], can I prove I have a value which is in this set, and without giving away the number on my ticket? Well, one of my favouriate researchers - Jan Camenisch - 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 CCS08 (after its authors). 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 string.
Set Membership and Range Proofs in Golang (CCS08) |
Method
So, let's say there's a number of winning tickets in a lottery of [654, 703, 991, 1011], can I prove I have a value which is in this set? For 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 string.
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 string. The code used is [2]:
package main import ( "crypto/rand" "fmt" "os" "strconv" "strings" "github.com/0xdecaf/zkrp/ccs08" "go.dedis.ch/kyber/v3/pairing/bn256" ) func StringToIntArray(A string) []int64 { strs := strings.Split(A, " ") ary := make([]int64, len(strs)) for i := range ary { v, _ := strconv.Atoi(strs[i]) ary[i] = int64(v) } return ary } func main() { tofind := 6 set := "1 2 3 4 5" argCount := len(os.Args[1:]) if argCount > 0 { tofind, _ = strconv.Atoi(os.Args[1]) } if argCount > 1 { set = os.Args[2] } s := StringToIntArray(set) p, _ := ccs08.SetupSet(s) fmt.Printf("To find: %d\n", tofind) fmt.Printf("Set: %v\n", s) r, _ := rand.Int(rand.Reader, bn256.Order) proof_out, err := ccs08.ProveSet(int64(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 %d is in [%v]\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 3 is included in a set of [1, 2, 3, 4, 5, 6]:
To find: 3 Set: [1 2 3 4 5 6] Proof that 3 is in 1 2 3 4 5 6 Proof: C= bn256.G2((19027679596361727465830466691714590027150250928743100188329248607389451375082,16949628276016363601794894538213922177395443826498276657422770803261495066169), (5699393798569477841978040021820316268277614436097958436753449789474039110118,8806612708159320381692367829880243948618090450626214010787274656678555437726), (5236041996946827246272430617707245970400478318225497342948916690172135694053,9938720226749779124332076293433564025582280697351896039484171140878978368112)) Proof: D= bn256.G2((3055385285225682457170931824984084710557591129970555220631679154490160538007,16741863869001983303859601610226823943417933471155831914781932489026213480048), (8851887114736475637449165663341713980374824686853280533381963095602317456359,529833433432526140282887716252910899691512855350147520271943056326737960188), (0,1)) Proof: V= bn256.G2((5389494577184098706147450878418556221050036083334693733955352021661432953834,6692919577824347552839485052008328374223293481178835104263907115847795868964), (1914193116904688737702450702033754563518223052612828372842693950285070367730,14918588892877446422261524405322282796423663255426519483236776812327905525652), (16911356167497400501411690244093098585964473813732663002213275613039696596134,5188262128010807626583488468074248822613977405555581853697113883066450076566))
Now, when we can try if 7is included in a set of [1, 2, 3, 4, 5, 6]:
To find: 7 Set: [1 2 3 4 5 6] Error Could not generate proof. Element does not belong to the interval.
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.
[2] https://github.com/0xdecaf/zkrp