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…