Maths & Logic for Zero-knowledge Proofs (simplified) — Part 3

A primer for understanding the mathematical insights used to build ZK.

• Part 1 (Proof systems & NP proofs)
• Part 2 (Computational complexity)

Questions answered in this part:

- What happens when even the verification process becomes inefficient or slow? (Read 1, 2 and 3)

- How can Interactive Proofs help us verify NP problems? (Read 4)

1. Super Polynomial Problems

In the last post, we saw examples of three membership problems and their computational complexity:

• (A,b) ∈ LIN : P → Polynomial-time(fast) prover & verifier
• x ∈ QR : NP → Super-polynomial (slow) prover & polynomial-time (fast) verifier
• ϕ ∈ SAT : NP-Complete → Can be used to solve other NP problems

BUT what happens when even the verification process becomes super-polynomial (slow)?

Here are a few examples of non-membership problems where the verification process also becomes difficult. Except LIN’, both SAT’ and QR’ have exponentially large naive proofs, i.e. their verification is slow. Verification for SAT’ and QR’ need new techniques to make it fast.

Examples of super-polynomial time problems (SAT’ and QR’). Source: [2] + Personal notes

2. Idea of Interactive Proofs

A paper published in 1985 by Goldwasser, Micali and Rackoff [3] solved the above problem by introducing a proof system that tolerates some error and utilizes rounds of interactions with the prover. This proof system is known as the Interactive Proof (IP) systems.

1. Tolerate error

In part 2, we had discussed probabilistic polynomial time (PPT) techniques which allows us to solve super-polynomial (hard) problems by using randomness and pseudo-guessing the answer. The solutions derived using these techniques include a margin of error (i.e. answer is right in most cases, but might be wrong in some).

In IP, verifiers utilise PPT techniques to verify the proof, and accepts valid proofs with “high” probability, whereas the probability that it will accept a false proof is “low” [1].

2. Interaction with prover

Insight: In maths, proofs are viewed as fixed objects (static). But we need to expand our idea of a proof. In particular, a proof is not a fixed object, but rather a process by which the validity of an assertion is established. For example, withstanding cross-examination in court can yield what can be considered a proof in law. [1]

Interaction between prover and verifier in an IP system. Source: [2] + Personal notes

Here is the formal definition of an interactive proof as given by the GMR’85 paper. IPs are able to verify super polynomial problems within (probabilistic) polynomial time by using interactions with a prover and tolerating some margin of error (less than 1/3).

Definition of Interactive Proof. Source: [2] + Personal notes

Let me emphasise few important points regarding IPs :

1. The completeness condition only refers to the prescribed prover P, but soundness condition refers to all potential malicious “provers” P*.
2. The verifier is required to be a probabilistic polynomial-time machine. But no resource bounds are placed on the computing power of the prover (i.e. prover has limitless amount of time and memory to solve the problem and convince the verifier of the completeness & soundness conditions).
3. The error probability given in the soundness condition can be made exponentially small by repeating the interaction (polynomially) many times (as we’ll see later).
4. The bounds on completeness (2/3) and soundness (1/3) are arbitrary. These bounds can be made stricter as per the requirements of the application. The general rule for these bounds are as follows:

Generalized Interactive Proof bounds. Source [2] + Personal notes

3. Use IP to verify Quadratic Non-residue (QR’)

Now let’s see how IP can be used to verify Quadratic Non-residue (QR’) within polynomial time.

IP for Quadratic Non-residue. Source: [2] + Personal notes

4. Why is NP ⊆ IP ?

We claim that NP is a subset of IP.

Before we dive into the reasoning, let’s review the definition of NP proof systems from part 1, BPP from part 2 and try to decipher the differences between the three.

Definition of NP. Source [2] + Personal notes

Differences between BPP (Bounded probabilistic polynonimal time), NP and IP. Source: [1], [2] + Personal notes

If a problem is defined as a membership problem (verify if x ∈ L):

1. BPP is a special case of IP where verifier can decide on the membership without any interaction.
2. NP is a special case of IP where prover condenses all possible statements required to convince the verifier into one message (proof), and verifier either, if true, accepts it (completeness = 1) and if false, rejects it (soundness = 0).

Note: It is not known whether or not BPP ⊆ NP [1].

BPP and NP are subsets of IP

Lastly, let’s see what type of problems can be verified using interactions, i.e. Which types of languages have interactive proof systems?

What does IP = PSPACE mean

Any problems in the PSPACE can be verified using interactions (IP). PSPACE is believed to be much larger than NP; in particular, coNP ⊆ PSPACE, whereas it is commonly believed that coNP ≠ NP [1].

In the next part, we will extend this idea of interactive proofs to zero-knowledge (finally!!!)

Sources :

[1] Goldreich, O. (2001, January 1). Foundations of Cryptography: Basic Tools.

[2] The 9th BIU Winter School on Cryptography | BIU Cyber Center. (2018, August 5). The 9th BIU Winter School on Cryptography | BIU Cyber Center. https://cyber.biu.ac.il/event/the-9th-biu-winter-school-on-cryptography/

[3] Goldwasser, S., Micali, S., & Rackoff, C. (1985). The knowledge complexity of interactive proof-systems. Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing — STOC ’85. https://doi.org/10.1145/22145.22178