Where’s Wally?

Zero Knowledge Proof (ZKP) Protocols — Finding “Wally” Is Just Part Of The Task

Provability without exposing any knowledge or data, is ideal in Digital Identity verification. This is because of how information can easily be copied and stored by computers. Exchanging data poses several risks. It not only exposes additional details of a personally identifiable information (PII), but there is also the possibility it can end up in a bad actor’s hands. People should have the right to prove attributes about themselves without having to expose the actual details. This allows the “blind” approach to sharing data. One technique that can be used is Zero Knowledge Proof (ZKP) like the zk-SNARKS method. ZKP allows data to be verified without revealing that data.

Now you might be wondering who “Wally” is and what this has to do with ZKP or cybersecurity in general. That is an abstract I would like to share to better understand ZKP. In a real world application, you have to take the abstractions from theory and code it into reality. By taking an example like “Wally” we can come up with solutions for implementing a ZKP system. “Wally” is actually a children’s puzzle book that can relate to the theoretical concepts of ZKP by using a fictitious story.

The inspiration for “Where’s Wally” as an example in ZKP is from a children’s puzzle book.

Finding “Wally”

Let us say that you are one of the world’s finding “Wally” experts. You have gained that position by winning “Where’s Wally” competitions all over the world. Now you have been hired by a company with the task of finding “Wally” in a photo among a crowd of hundreds of people on a Southern California beach. You only need to identify “Wally” from the crowd and present it to the company to prove you know where “Wally” is.

You want to get paid in return for offering this as a service. The company agrees, but they need to be sure that you will correctly identify “Wally” for them. The issue now becomes one about trust, since the company and yourself are not familiar with each other. The question that arises for you is “how do I know the company will pay me when I identify Wally for them”. The company is also not so sure they can trust you because you might just want to collect the money by identifying a random “Wally” on the beach.

The idea here is to just reveal to the company where “Wally” is exactly in the photo. The terms are that the company representatives must meet with you in person, so there is no opportunity to cheat for both party. You are handed a genuine photo, and now you turn around and take a large piece of cardboard. You cut a hole in the cardboard to the position in the photo where “Wally” is located. You then turn around to show the company the piece of cardboard with the cutout that identifies “Wally”.

By covering the photo up with a large piece of cardboard, you can hide the actual position of where “Wally” is located in the frame. All you need to show the other party is a cutout to where “Wally” is.
The cutout will reveal “Wally”, but (unless the other party has a super sharp intuition) does not reveal where exactly he is in the photo just by the cutout alone. In fact, the photo can be placed anywhere under the cardboard with a different cutout relative to “Wally”.

You then remove the cardboard from the photo without revealing exactly where in the photo “Wally” is. The cardboard is large enough to cover over the entire photo without revealing the actual position of where “Wally” is. Let us say that you had a large 8" x 11" sheet of paper covering a smaller 2" x 4" photo. The analogy is that you cover the smaller photo with the larger size sheet of paper. You are obscuring the complete details or hiding it from the viewer, yet you are showing proof with the cutout to where “Wally” is in the photo.

The company will now know that you do have the knowledge, based also on your record as an expert in finding “Wally”. Since it is important to them, they decide to pay you if you reveal the proof and full details. Now that you gained their trust, you can reveal where “Wally” is and they should then pay you the money.

Proving Your Identity

By definition ZKP must meet 3 properties:

  1. Completeness: if the statement is true, the honest verifier will be convinced of this fact by an honest prover.
  2. Soundness: if the statement is false, no cheating prover can convince the honest verifier that it is true, except with some small probability.
  3. Zero-knowledge: if the statement is true, no verifier learns anything other than the fact that the statement is true. In other words, just knowing the statement (not the secret) is sufficient to imagine a scenario showing that the prover knows the secret. This is formalized by showing that every verifier has some simulator that, given only the statement to be proved (and no access to the prover), can produce a transcript that “looks like” an interaction between the honest prover and the verifier in question. (Source Wikipedia)

To meet all three properties, the prover must be able to provide the following to the verifier when sharing their personal data:

  • Allow verification of data to another party without revealing its contents. For example, if customer Bob needs to prove he is over 21 years old to rent a car online, he must provide proof using his date of birth (DOB). The verifier needs proof that Bob is indeed over the age or the age of 21. Typically, if Bob were in front of the verifier, he can just take out his driver’s license which shows date of birth. However, there are other personal information contained on the license card that the verifier does not need to see. This can be even more at risk for the prover when it comes to submitting their entire copy of their license online. This copy could get stolen and put the customer at risk for identity theft and other crimes. There is no need to do this when you use ZKP.
  • Prevent the disclosure of non-required personal data.
  • Allow the customer to provide attestation of their personal attributes.

The Turing Machine Model

We can base ZKP on the Turing Machine model, where the value of P, V and S can be represented as machines. The P is the prover and the V is the verifier. This can be represented in Probabilistic Polynomial Time (PPT) with the following equation:

This formula is a theoretical representation of perfect zero knowledge, which does not exist in the real world. L is the zero knowledge given an interactive proof system between P and V.

The elements for all interactions within this proof system must produce a proof beyond a reasonable doubt (in theory) that P is telling the truth for V without revealing any data. This can often be accomplished using a cryptographic hash function.

Identity Theft Is A Serious Issue

There is no way of knowing for sure that when we provide our personal information that it is safe. The least secure would be filling out forms when applying for services, which is quite common in less developed economies. The security risk there is the forms that contain your information can be copied illegally or stolen. The information can then be used by bad actors to impersonate your identity and use it to their benefit. It is all the way fraudulent, and it could have been prevented.

Electronic form applications offer some level of security. The problem there is if the company that stores the information is somehow hacked. It has happened before with Equifax being a big example. According to statistics from the US Bureau Of Justice:

  • The majority of identity theft victims (86%) experienced the fraudulent use of existing account information, such as credit card or bank account information.
  • About 15% of people have experienced identity fraud. (2014 data)

The numbers are likely to decrease with more sophisticated software and due diligence by online companies. The fact remains that they still have your personal data, and anyone who has access to it can view it. What if a malicious software was able to breach the company database and steal your information? That is why the next level of security must come in a form that provides even more protection to user data in the event of a breach. The most common method is by cryptographic means, and ZKP can be one of those implementations.

Synopsis

As a cybersecurity measure, ZKP provides a blind approach to sharing data. This is useful when it comes to proving data without actually revealing it. Real world applications can be used in digital identity verification systems. In this case you would need a backend platform that is neutral to both parties to facilitate identity verification using ZKP.

ZKP makes use of cryptographic algorithms to present data from a prover to a verifier. The prover presents a hash of their personal data which a verifier compares to the hash of the information they have obtained about the prover. If the hashes match, then it proves the information that the verifier needs. For example, instead of revealing a user’s actual birth date to a verifier, it can be presented in the form of hash that can be compared to a backend platform that stores that data. The verifier for example could be a cashier at the liquor store. Do they need to actually know when your birth date is? Instead an identity verification system will prove the person’s legal age using a hash that can be represented by a QR code.

We can take the “Wally” example to show how verification can build trust among parties who do not trust or know each other. Once the “Wally” expert can show that they have information (data) that another party needs, it can lead to a transaction. In this case it was the cardboard with a cutout to show that they know where “Wally” is in the photo. Building a software that takes this abstraction into account is foundational for the development of ZKP applications for real world cybersecurity use.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store