Commitment Schemes

Scenario: Coin Tossing Over the Phone

Imagine two people, Àdébísí and Bọ́lá, want to flip a coin to decide who should pay for drinks, but they are communicating over the phone and, thus, cannot physically toss a coin in the view of both of them. More concretely:

Àdébísí and Bọ́lá want to flip a coin.
Àdébísí secretly decides her guess for “heads” or “tails”.
Bọ́lá flips the coin and announces the result.
Àdébísí reveals her guess, proving she didn’t cheat by changing her guess after hearing the result.
Àdébísí wins the game if her guess matches the announced result.

In this scenario, Àdébísí and Bọ́lá can use a commitment scheme that allows one party to “commit” to a chosen value while keeping it hidden to the other party until an appropriate time. [1]

This ensures neither party can cheat:

Àdébísí cannot change her guess after Bọ́lá announces the result (binding).
Bọ́lá cannot deduce Àdébísí’s guess before she reveals it (hiding).

A commitment scheme is a cryptographic primitive that allows one party (the sender) to commit to a chosen value while keeping it hidden from another party (the receiver), with the ability to reveal the committed value later. Commitment schemes are essential building blocks in various cryptographic protocols, such as zero-knowledge proofs and secure multi-party computations.

Properties of Commitment Schemes

A commitment scheme must satisfy two fundamental properties:

Binding Property
- Once the sender has committed to a value, they cannot change it.
- This ensures that the commitment is “binding,” preventing the sender from lying about the value during the reveal phase.
Hiding Property
- The commitment does not reveal any information about the value to the receiver until the sender decides to reveal it.
- This ensures that the value is “hidden” until the sender discloses it.

Phases of a Commitment Scheme

A commitment scheme typically involves two phases:

Commit Phase
- The sender chooses a value $m$ and generates a commitment $C$ using a commitment function, often involving random coins $r$ .
- $C = \text{Commit}(m, r)$
- The commitment $C$ is sent to the receiver.
Reveal Phase
- The sender reveals $m$ and $r$ to the receiver.
- The receiver verifies the commitment $C$ by checking if $C = \text{Commit}(m, r)$ .

Hiding

The hiding property of a commitment scheme ensures that the commitment does not reveal any information about the committed value $m$ to the receiver until the sender decides to reveal it. In other words, the commitment conceals the value $m$ while still binding the sender to that value.

Types of Hiding

Perfect/Statistical Hiding: The commitment $C$ provides no information about $m$ at all, even with infinite computational power. This is achieved if the distribution of $C$ is independent of $m$ .
Computational Hiding: It is computationally infeasible for the receiver to deduce $m$ from $C$ (in polynomial time in relevant parameters).

Binding

The binding property in a commitment scheme ensures that once a sender commits to a value, they cannot change it later. This property prevents the sender from “cheating” by revealing a different value during the reveal phase.

Types of Binding

Perfect/Statistical Binding: It is mathematically impossible to find two different values $m_1$ and $m_2$ that produce the same commitment $C$ .
Computational Binding: Finding such a pair $(m_1, r_1)$ and $(m_2, r_2)$ , that produces the same commitment $C$ , is computationally infeasible for any adversary with limited computational resources.

Exercise

Prove that a commitment scheme cannot be both perfectly hiding and perfectly binding at the same time.

References

[1] Gilles Brassard, David Chaum, and Claude Crépeau, Minimum Disclosure Proofs of Knowledge, Journal of Computer and System Sciences, vol. 37, pp. 156–189, 1988.

[2] Manuel Blum, Coin Flipping by Telephone, Proceedings of CRYPTO 1981.

[3] Oded Goldreich, Silvio Micali, and Avi Wigderson, Proofs that yield nothing but their validity, or all languages in NP have zero-knowledge proof systems, Journal of the ACM, 38: 3, pp. 690–728, 1991

🎉 Happy New Year! 🎉

Here’s to a year filled with joy, success, and unforgettable memories. 🥂🎆

With love,
Daniel Alabi

Statistical Zero-Knowledge Proofs

How would you prove you’ve solved a Sudoku puzzle without revealing the solution? You can construct a zero-knowledge proof showing the grid satisfies Sudoku rules (unique numbers per row, column, and box).

This semester, one of my projects involves zero-knowledge proofs. I’ll try to explain what I’ve learned about this amazing concept and its variants (with particular attention to statistical zero-knowledge). Shout out to Boaz’s cryptography class. Zero-knowledge proofs have found profound use in blockchain technology, authentication, privacy, and so on.

Definition

Intuition: Imagine someone wants to prove they know the solution to a complex problem (e.g., a puzzle or how Trump was going to win the election) without revealing the solution. They use a process that convinces the verifier they have the solution without showing it.

A zero-knowledge proof (ZKP) is a method by which one party (the prover) can demonstrate to another party (the verifier) that a specific statement is true without revealing any additional information about the statement itself.

Key Properties of Zero-Knowledge Proofs

There are a few variants of zero-knowledge. Here is one:

Completeness:
If the statement is true, a honest prover can convince the verifier of its truth:
- If $x \in L$ and the prover $P$ knows a valid witness $w$ , then for all $\epsilon > 0$ , the honest verifier $V$ will accept the proof with probability at least $1 - \epsilon$ : $\Pr[V(x) = \text{accept} \mid x \in L, w \text{ valid}] \geq 1 - \epsilon.$
Soundness:
If the statement is false, no dishonest prover can convince the verifier that it is true (except with an extremely small probability).
- If $x \not\in L$ , then no cheating prover $P^*$ can convince the honest verifier $V$ to accept, except with negligible probability: $\Pr[V(x) = \text{accept} \mid x \not\in L] \leq \epsilon$ where $\epsilon$ is a negligible function.,
Zero-Knowledge:
The verifier learns nothing other than the fact that the statement is true. No information about how or why the statement is true is revealed.
- For every polynomial-time verifier $V^*$ , there exists a polynomial-time simulator $S$ such that the output of $S(x)$ is computationally indistinguishable from the interaction between $P$ and $V^*$ on input $x$ : ${S(x)}_{x \in L} \approx {\text{Transcript}(P \leftrightarrow V^*, x)}_{x \in L}.$

Type	Definition	Guarantee
Perfect Zero-Knowledge	Real and simulated distributions are identical.	Holds even against computationally unbounded verifiers.
Statistical Zero-Knowledge	Real and simulated distributions are statistically close (negligible difference).	Holds against computationally unbounded verifiers.
Computational Zero-Knowledge	Real and simulated distributions are computationally indistinguishable for polynomial-time verifiers.	Holds only against computationally bounded verifiers.

Interactive Zero-Knowledge Proofs

These involve a back-and-forth interaction between the prover and the verifier.

Graph Isomorphism:
Prove that two graphs are isomorphic (structurally identical) without revealing the isomorphism itself. Alice proves to Bob that she knows a way to relabel the nodes of graph $A$ to match graph $B$ .
Hamiltonian Cycle Problem:
Prove that a graph contains a Hamiltonian cycle (a path visiting every vertex exactly once) without revealing the actual cycle.

Non-Interactive Zero-Knowledge Proofs (NIZKs)

These eliminate the need for interaction, enabling the prover to generate a single proof that can be verified multiple times.

zk-SNARKs (Succinct Non-Interactive Arguments of Knowledge):
Widely used in blockchain systems like Zcash to validate transactions while keeping them private. Example: Prove that a transaction is valid (inputs equal outputs) without disclosing amounts or participants.
zk-STARKs (Scalable Transparent Arguments of Knowledge):
A transparent alternative to zk-SNARKs that avoids the need for trusted setups and is more scalable. Example: Used in Ethereum Layer-2 solutions like StarkNet to bundle transaction proofs.

The Fiat-Shamir Heuristic technique to convert interactive proofs into non-interactive ones using cryptographic hash functions.

Schnorr Protocol:
A proof that you know a discrete logarithm of a number without revealing the logarithm itself. Example: Prove ownership of a private key without exposing it (used in Schnorr signatures).

Example Use Cases

Zero-knowledge proofs (ZKPs) come in different forms, with specific examples being applied across theoretical and practical scenarios. Below are some notable examples:

1. Commit-and-Prove Protocols

Combine commitments (binding and hiding data) with zero-knowledge proofs (for example Pedersen Commitments). Prove that you committed to a number $x$ without revealing $x$ but can later open the commitment to verify $x$ .

2. Bulletproofs

Efficient range proofs that demonstrate a value lies within a specific range without revealing the value. Example: Used in Monero to ensure transaction amounts are positive without disclosing the actual amounts.

3. Proofs in Cloud Computing

Proof of Retrievability:
Prove a cloud provider stores your data without downloading it. Example: Used in decentralized storage systems like Filecoin.
Proof of Computation:
Demonstrate the correctness of outsourced computation without revealing inputs or outputs.

4. Secure Voting Protocols

Homomorphic Encryption-Based Proofs:
Prove a vote is valid (e.g., within a candidate set) without revealing the voter’s choice.

5. Knowledge of a Password

Example: Authenticate to a server by proving knowledge of a password without transmitting it. SRP Protocol (Secure Remote Password): Verifies a user knows a password without sending the password itself.

Perfect Zero-Knowledge

Perfect Zero-Knowledge is a stronger version of zero-knowledge where the verifier cannot distinguish between the interaction with the actual prover and the simulated interaction, even with unlimited computational power. In other words, the simulator’s output is statistically identical to the real interaction transcript, not just computationally indistinguishable.

Formal Definition

Let $(P, V)$ be a proof system for a language $L$ . The proof system is perfect zero-knowledge if for every polynomial-time verifier $V^*$ , there exists a probabilistic polynomial-time simulator $S$ such that for every $x\in L$ : $\Pr[\text{Transcript}(P\leftrightarrow V^*,x)=t]= \Pr[S(x)=t]\forall t,$

where:

$\text{Transcript}(P\leftrightarrow V^*,x)$ is the transcript of the interaction between $P$ and $V^*$ on input $x$ ,
$S(x)$ is the simulated transcript generated by $S$ for the same input $x$ .

This implies that the probability distributions of the transcripts from the real interaction and the simulated interaction are exactly the same.

Key Features of Perfect Zero-Knowledge

Statistical Indistinguishability:
The output of the simulator is statistically indistinguishable from the real transcript, meaning the difference between the two distributions is exactly zero.
Stronger Privacy Guarantees:
Since the guarantee holds even against verifiers with infinite computational power, it is stronger than computational zero-knowledge, where the indistinguishability only holds for polynomial-time adversaries.

Example of Perfect Zero-Knowledge

The classic Graph Isomorphism Zero-Knowledge Protocol is a perfect zero-knowledge protocol:

A prover shows two graphs are isomorphic without revealing the actual isomorphism.
The verifier cannot distinguish between a genuine interaction and a simulated one, even with infinite computational power, making it perfect zero-knowledge.

Computational Zero-Knowledge

Computational Zero-Knowledge is a type of zero-knowledge proof where the verifier cannot distinguish between the actual interaction with the prover and the output of a simulator, provided the verifier has limited (polynomial-time) computational power.

This means that the zero-knowledge property relies on the computational infeasibility of distinguishing between the two scenarios, often based on cryptographic hardness assumptions (e.g., the difficulty of factoring large numbers or solving discrete logarithms).

Formal Definition

Let $(P,V)$ be a proof system for a language $L$ . The system is computational zero-knowledge if for every probabilistic polynomial-time (PPT) verifier $V^*$ , there exists a PPT simulator $S$ such that for every $x \in L$ , the distributions: $\text{Transcript}(P \leftrightarrow V^*, x)\}_{x \in L}$ and $\{S(x)\}_{x \in L}$ are computationally indistinguishable. That is, no polynomial-time distinguisher can tell apart the real interaction and the simulated interaction with non-negligible probability.

Key Features of Computational Zero-Knowledge

Computational Indistinguishability:
The zero-knowledge property holds against adversaries with limited computational power (polynomial-time distinguishers). If the verifier were computationally unbounded, they might be able to differentiate the two distributions.
Cryptographic Assumptions:
Computational zero-knowledge often relies on assumptions like:
- The infeasibility of factoring large integers.
- The hardness of the discrete logarithm problem.
- Other complexity-theoretic assumptions.
Relaxed Privacy Guarantees:
Unlike perfect zero-knowledge, where the simulated and real distributions are statistically identical, computational zero-knowledge only guarantees privacy against computationally bounded adversaries.

Examples of Computational Zero-Knowledge

zk-SNARKs:
Used in blockchain protocols like Zcash to ensure transaction validity without revealing sensitive details. The zero-knowledge property here relies on computational assumptions.
Interactive Proofs with Commitment Schemes:
Many zero-knowledge protocols use cryptographic commitments (e.g., Pedersen commitments) to hide information during the proof, ensuring the verifier cannot extract more data computationally.

Real-World Importance

Computational zero-knowledge is widely used in practical applications, such as:

Cryptocurrencies (e.g., Zcash, zkRollups).
Authentication protocols.
Privacy-preserving identity verification.

It strikes a balance between strong privacy guarantees and computational efficiency, making it suitable for real-world cryptographic systems.

Statistical Zero-Knowledge

Statistical Zero-Knowledge (SZK) is a type of zero-knowledge proof where the verifier cannot distinguish between the real interaction with the prover and the output of a simulator, even with unlimited computational power. The key difference from perfect zero-knowledge is that the two distributions (real and simulated) are not identical but are statistically close, meaning the difference between them is negligible.

Formal Definition

Let $(P,V)$ be a proof system for a language $L$ . The system is statistical zero-knowledge if for every probabilistic polynomial-time (PPT) verifier $V^*$ , there exists a PPT simulator $S$ such that for every $x \in L$ , the output distributions: $\text{Transcript}(P \leftrightarrow V^*, x)\}_{x \in L}$ and $\{S(x)\}_{x \in L}$ are statistically indistinguishable. This means the statistical distance (or total variation distance) between the two distributions is negligible:

$\Delta(\text{Transcript}(P \leftrightarrow V^*, x), S(x)) = \frac{1}{2} \sum_t \left| \Pr[\text{Transcript} = t] - \Pr[S(x) = t] \right| \leq \epsilon,$

where $\epsilon$ is a negligible function of the input size.

Key Features of Statistical Zero-Knowledge

Statistical Indistinguishability:
The difference between the real and simulated transcripts is negligibly small, even for verifiers with unlimited computational power.
Weaker than Perfect Zero-Knowledge:
Perfect zero-knowledge requires the distributions to be exactly identical, while statistical zero-knowledge allows for a negligible difference.
Stronger than Computational Zero-Knowledge:
Computational zero-knowledge only guarantees indistinguishability for polynomial-time adversaries, whereas statistical zero-knowledge holds against adversaries with unlimited computational power.
No Dependence on Cryptographic Assumptions:
SZK is typically not reliant on computational hardness assumptions, unlike computational zero-knowledge.

Examples of Statistical Zero-Knowledge

Quadratic Residuosity Problem:
Prove that a number $x$ is a quadratic residue modulo $N$ (a composite number) without revealing the factorization of $N$ . The simulator can generate transcripts statistically indistinguishable from those produced during the real interaction.
Graph Isomorphism Problem:
Prove that two graphs $G_1$ and $G_2$ are isomorphic without revealing the isomorphism. The verifier’s view of the interaction can be statistically simulated.

Real-World Applications

While SZK is less common in practical applications compared to computational zero-knowledge, it has theoretical importance in cryptographic protocol design and scenarios where absolute guarantees against powerful adversaries are required.

Some References

[1] Goldreich, Oded (2001). Foundations of Cryptography Volume I. Cambridge University Press.

[2] Murtagh, Jack. https://www.scientificamerican.com/article/wheres-waldo-how-to-prove-you-found-him-without-revealing-where-he-is/

[3] Goldwasser, S.; Micali, S.; Rackoff, C. (1989), “The knowledge complexity of interactive proof systems” (PDF), SIAM Journal on Computing, 18 (1): 186–208, doi:10.1137/0218012, ISSN 1095-7111

Electrical Engineering, Computer Engineering, Computer Science

tl;dr Computer Engineering $\approx$ Electrical Engineering with Computer Science

Recently, I accepted an offer to join the department of Electrical and Computer Engineering (ECE) at the University of Illinois, Urbana-Champaign. While I am already an affiliate of the ECE department, I do not plan on teaching a course until Fall 2025. Tentatively, I am planning on teaching a topics course related to privacy/cryptography. (Will share more details on the planned topics course in a later post.)

I have gotten a few questions (especially from NaijaCoder students) concerning the differences between electrical engineering, computer science, and computer engineering. Let me try to explain what I think the key differences are.

Electrical Engineering (EE)

I see electrical engineering as the parent discipline of electronic and computing devices just as the parent discipline of EE is (probably) physics. EE includes the study of analog and digital devices used for various forms of computation and communication.

Computer Engineering (CE) and Computer Science (CS)

Computer Engineering, to me, is about computing aspects of electrical engineering. In fact, at Illinois, the major was called Electrical Engineering and Computer Science. This page states that in 1969, an electrical engineering/computer science curriculum was unveiled and that that year “An electrical engineering/computer science curriculum [was] established within the department. It will be replaced in 1973 by the computer engineering curriculum.”

So, Computer Engineering (CE) and Computer Science (CS) are closely related fields.

1. Focus of Study

Computer Engineering (CE):
- Combines electrical engineering with computer science.
- Focuses on hardware and software: how computers and devices are physically constructed and how software interacts with hardware.
- Includes designing and analyzing microprocessors, circuit boards, and networks, as well as embedded systems like IoT (Internet of Things).
Computer Science (CS):
- Primarily focused on software.
- Emphasizes programming languages, software development, artificial intelligence, machine learning.

2. Core Curriculum

Computer Engineering:
- Electrical circuits, digital design, microcontrollers, VLSI design (Very Large Scale Integration), robotics, signal processing, and computer architecture.
- Emphasis on low-level programming that interacts with hardware.
Computer Science:
- Software engineering, computer graphics, artificial intelligence, and machine learning.
- Emphasis on high-level programming and the development of complex software systems.

3. Skills Developed

Computer Engineering:
- Understanding of both hardware and software systems.
- Skills in circuit design, chip fabrication, computer architecture, and low-level programming (like C, assembly).
Computer Science:
- Problem-solving and analytical skills for software development.
- Proficiency in programming languages (e.g., Python, Java, C++), software development life cycle, and working with large-scale systems.

Both fields share knowledge of programming and computer systems, and professionals in both disciplines work in industries like tech, telecommunications, healthcare, and aerospace. However, computer engineers have deeper knowledge of hardware, while computer scientists are more specialized in software development.