Introduction to Privacy-Enhancing Cryptographic Techniques

Zero knowledge proof – Proving something without exchanging evidence

By: Betty Ann Bryanton, Canada Revenue Agency

Introduction

Enormous amounts of data are collected by government agencies, search engines, social networking systems, hospitals, financial institutions, and other organizations. This data, centrally stored, is at risk of security breaches. Additionally, individuals browse the internet, accept cookies, and share personally identifiable information (PII) in exchange for services, benefits, recommendations, etc. To facilitate e-commerce and access services, individuals need to authenticate, which means providing 'evidence' to prove they are who they say they are. This may mean providing a password, a driver's license, a passport number, or another personal identifier. These could potentially be stolen, and sharing this data may compromise related PII, such as age and home address. Zero knowledge proofs can assist in these scenarios.

What is Zero Knowledge Proof?

A Zero-Knowledge Proof (ZKP) is one of the cryptographic privacy-enhancing computational (PEC) techniques and may be used to implement granular, least access privacy controls and privacy-by-designFootnote1 principles.

Typically, a proof that some assertion X is true also reveals some information about why X is true. ZKPs, however, prove that a statement is true without revealing any additional knowledge. It's important to note that ZKPs do not guarantee 100% proof, but they do provide a very high degree of probability.

ZKPs use algorithms that take data as input and return either 'true' or 'false' as output. This allows two parties to verify the truth of information without exposing the information or how the truth was determined. For example, an individual can prove the statement "I am an adult at least 21 years old" without providing data for verification to a central server.

ZKP was introduced by researchers at MIT in 1985Footnote2 and is now being used in many real-world applications.

ZKP vs other concepts

ZKP is distinct from the following concepts:

Further, ZKP should not be confused with Advanced Encryption Standard (AES), where the parties share a secret number. In ZKP, the prover demonstrates their possession of a secret number without divulging that number. In both scenarios the parties arrive at a shared secret, but with ZKP, the goal is to make claims without revealing extraneous information.

How does ZKP work?

To understand how ZKP works, consider the scenario of a prover (Peggy) and a verifier (Victor). The goal of the ZKP is to prove a statement with very high probability without revealing any additional information.

Peggy (the prover) wants to prove to Victor (the verifier, who is colour-blind and does not trust her) that two balls are of different colours (e.g., green and red). Peggy asks Victor to reveal one of the balls, then put the two balls behind his back. Then Peggy asks Victor to switch them or not, then reveal one to her. She answers if it's the same colour or different than the previous one. Of course, she could be guessing or lying, or even colour-blind, herself. Thus, in order to convince him she's telling the truth, this process must be repeated many, many times. By doing so, eventually Peggy can convince Victor of her ability to correctly identify the different colours.

This scenario satisfies the three criteria of a ZKP:

  1. Soundness (the quality of being based on valid reason): If Peggy was not telling the truth, or was colour-blind, she could only guess correctly 50% of the time.
  2. Completeness: After repeating this process ('the proof') many, many times, the probability of Peggy correctly guessing would be very low, convincing Victor that the balls are of different colours.
  3. Zero-knowledge: Victor does not learn anything additional; he never even learns which ball is green and which is red.

What is explained above is interactive proving, requiring a back-and-forth communication between two parties. Today's ZKPs employ non-interactive proving, where two parties have a shared key to transmit and receive information. For example, a government-issued key as part of a passport could be used to demonstrate citizenship without revealing the passport number or the citizen's name.

Why is it important?

ZKPs assure a secure and invisible flow of data, protecting user information from potential leaks and identity theft. This enhances e-commerce, by allowing more private and secure transactions.

The use of ZKPs not only helps combat data security risk, but this minimum viable verification technique helps prevent the disclosure of more PII than necessary. This benefits both individuals and organizations. Individuals do not have to share their PII and organizations that are facing an increase in security breaches, and thus, dealing with significant costs, harm to reputations, and loss of trust, don't receive the PII to be breached.

Another benefit for both individuals and organizations is more efficient verification, reducing bottle-necked processes that rely on manual or inefficient burden of proof.

Having positive and efficient verification between parties (even untrusted ones) opens up a variety of avenues for collaboration and enquiry.

Applications and Use Cases

ZKPs can protect data privacy in a diverse set of applications and use cases, including:

  • Finance: A mortgage or leasing applicant can prove their income falls within a certain range without revealing their salary. (Financial institution ING is already using this technology, according to Dilmegani, 2022.)
  • Online voting: ZKP can enable anonymous and verifiable voting and help prevent voting fraud or manipulation.
  • Machine Learning: A machine learning algorithm owner can convince others about the model's results without revealing any information about the model.
  • Blockchain Security: Transactions can be verified without sharing information such as wallet addresses and amounts with third party systems.
  • Identity and credential management: Identity-free verification could apply to authentication, end-to-end encrypted messaging, digital signatures, or any application requiring passwords, passports, birth certificates, driving licences, or other forms of identity verification. Fraud prevention systems could validate user credentials and PII could be anonymized to comply with regulations or for decentralized identity.
  • International security: ZKPs enable the verification of the origin of a piece of information without revealing its source. This means cyber-attacks can be attributed to a specific entity or nation without revealing how the information was obtained. This is already being used by the United States' Department of Defense  (Zero-knowledge proof: how it works and why it's important, n.d.).
  • Nuclear disarmament: Countries could securely exchange proof of disarmament without requiring physical inspection of classified nuclear facilities.
  • COVID-19 vaccine passports and travel: As currently done in Denmark, individuals could prove their vaccination status without revealing their PII (Shilo, 2022).
  • Auditing or compliance applications: Any process that requires verification of compliance could use ZKP. This could include verifying that taxes are filed, an airplane was maintained, or data is retained by a record keeper.
  • Anonymous payments: Credit card payments could be made without being visible to multiple parties such as payments providers, banks, and government authorities.

Challenges

While there are many benefits, there are also challenges that need to be taken into consideration if an organization wants to use ZKPs.

  • Computation intensity: ZKP algorithms are computationally intense. For interactive ZKPs, many interactions between the verifier and the prover are required, and for non-interactive ZKPs, significant computational capabilities are required. This makes ZKPs unsuitable for slow or mobile devices and may cause scalability issues for large enterprises.
  • Hardware costs: Applications that want to use ZKPs must factor in hardware costs which may increase costs for end-users.
  • Trust assumptions: While, some ZKP public parameters are available for reuse, and participants in the trusted setup are assumed to be honest, recipients must rely on the honesty of the developers (What are zero-knowledge proofs?, 2023).
  • Quantum computing threats: While ZKP cryptographic algorithms are currently secure, the development of quantum computers could eventually break the security model.
  • Costs of using the technology: The costs of ZKPs can vary based on setup requirements, efficiency, interactive requirements, proof succinctness and the hardness assumptions required (Big Data UN Global Working Group, 2019).
  • Lack of standards: Despite ongoing initiatives to standardize zero knowledge techniques and constructions, there is still an absence of standards, systems, and homogeneous languages.Footnote3
  • No 100% guarantee: Though the probability of verification while the prover is lying can be significantly lowFootnote4, ZKPs do not guarantee the claim is 100% valid. 
  • Skills: ZKP developers should have expertise in ZKP cryptography and be aware of the subtleties and differences between the guarantees provided by ZKP algorithms.

What's next?

In recent years there has been a strong push for adopting zero knowledge in software applications. Several organizations have built applications using ZK capabilities, and ZKPs are widely used to safeguard blockchains. For example, the city of Zug in Switzerland has registered all its citizen IDs on a blockchain (Anwar, 2018).

Though there needs to be improvements in ZK education, standardization, and privacy certifications to improve trust in ZK products and services, ZKPs have great potential in saving organizational costs due to security breaches, as well as preserving users' privacy, and reducing PII as a product for sale. ZKPs help an organization move from reacting to security breaches to preventing them.

Meet the Data Scientist

Register for the Data Science Network's Meet the Data Scientist Presentation

If you have any questions about my article or would like to discuss this further, I invite you to Meet the Data Scientist, an event where authors meet the readers, present their topic and discuss their findings.

Thursday, June 15
1:00 to 4:00 p.m. ET
MS Teams – link will be provided to the registrants by email

Register for the Data Science Network's Meet the Data Scientist Presentation. We hope to see you there!

Subscribe to the Data Science Network for the Federal Public Service newsletter to keep up with the latest data science news.

Related Topics

Authentication, Blockchain, Web 3.0, Privacy-Enhancing Computation (PEC) techniques: Differential Privacy, Homomorphic Encryption, Secure Multiparty Computation, Trusted Execution Environment

References

Report a problem or mistake on this page
Date modified: