Set-Membership Zero-Knowledge Proofs

Set-Membership Zero-Knowledge Proofs

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][here]:

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 [here]:

package main

import (
 "crypto/rand"
 "fmt"
 "os"

 "strconv"
 "strings"

 "github.com/ing-bank/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] [here]:

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 7 is included in a set of [1, 2, 3, 4, 5, 6] [here]:

To find: 7
Set: [1 2 3 4 5 6]
Error Could not generate proof. Element does not belong to the interval.

Conclusions

As we save the values as a 64-bit integer, we could easy apply the method as 64-bit hashes of strings. This could be achieved by taking the first 64 bits of a SHA-256 hash of strings. While collisions are possible, the set is likely to be limited in its range. Another application is within privacy-aware cryptocurrency coins, and where we can determine if a coin has been issued as spent.

If you are interested in range proofs, try 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.