A zero-knowledge proof (ZKP) is a technique that enables one party (the prover) to demonstrate to another party (the verifier) the truth of a certain statement without revealing any additional information besides the fact that the statement is true.
Here is a simple example as to what a ZKP could be.
We are the prover, often denoted as P, and we are trying to prove that we know the colours of 2 balls (With distinct colours) to an honest verifier, often denoted as V. We must do this without revealing the colours of the balls.
ZKP Protocol:
This is a valid ZKP Protocol as P is always able to prove that they know which ball has which colour (Completeness), while a dishonest prover is only able to prove that they know which ball has which colour with a probability of \(\frac{1}{2^t}\), where \(t\) is the number of times this protocol is executed. This probability gets exponentially negligible as the number of rounds increase (Soundness). V also gains no knowledge about the colours of the balls (Zero-Knowledge).
A sigma protocol is a 3-message interactive zero-knowledge proof. It is as follows:
Sigma Protocols also satisfy 3 properties:
Schnorr’s Protocol is an example of a Sigma Protocol where P wants to prove to V that they know some \(w\), such that \(g^w \equiv y \pmod{p}\) where \(g\) generates a group \(\mathbb{F}_p^*\) with prime order \(q\) where computing Discrete Logarithm (DLP) is hard.
Schnorr’s Protocol:
Note that \(\overset{?}{=}\) denotes a binary output, where if both values are the same it will output 1, and if both values are different, it will output 0. V will accept if \(g^z \overset{?}{=} ay^e \pmod{p}\) means that V will output \(\top\) if \(g^z \overset{?}{=} ay^e \pmod{p}\) outputs 1, vice versa.
Completeness: If \(z = r + ew\), \(g^z = g^{r + ew}\), \(a = g^r\), \(y^e = (g^w)^e = g^{ew}\), \(\therefore g^z = ay^e \pmod{p}\)
Special Soundness is a property of a Sigma Protocol. A protocol is special sound if there exists a PPT extractor, \(\mathcal{E}\), that when given 2 accepting transcripts, \((a,\, e,\, z)\) and \((a,\, e^{'},\, z^{'})\) with \(e \neq e^{'}\) outputs a valid witness, \(w\). Note that in both transcripts, the commitment is the same.
Special Soundness also implies Soundness.
Let us define \(E_a = \{e \in \mathcal{C}: \exists z \text{ such that } (a,\, e,\, z) \text{ is accepted by the verifier}\}\). Special Soundness claims that if \(x \not\in \mathcal{L}_R\), where \(x\) is the statement and \(\mathcal{L}_R = \{x \in \mathcal{X}: \exists w \in \mathcal{W} \text{ s.t.} (x,\, w) \in R \}\), then \(\vert E_a \vert \leq 1\), \(\forall a\).
Assume that \(\vert E_a \vert \geq 2\), then there exists \(e_1 \neq e_2 \in E_a\) with accepting transcripts, \((a,\, e_1,\, z_1)\) and \((a,\, e_2,\, z_2)\). By special soundness, the extractor is able to compute a valid witnesss, \(w\), from these 2 accepting transcripts. However, that means that \(x \in \mathcal{L}_R\) but out initial assumption is that \(x \not\in \mathcal{L}_R\). This means that \(\vert E_a \vert \geq 2\) is impossible which implies \(\vert E_a \vert \leq 1 \, \square\)
This means that in order for a transcript to be accepted, the verifier must prick the only challenge (if it even exists at all) that allows for a valid response for the transcript to be accepted. As the prover must send a commitment, \(a\), before the verifier chooses challenge, \(e\), uniformly at random. Therefore:
\[\text{Pr}[\text{verifier accepts}] = \underset{e \leftarrow \mathcal{C}}{\text{Pr}} [e \in E_a] = \frac{\vert E_a \vert}{\vert \mathcal{C} \vert} \leq \frac{1}{\vert \mathcal{C} \vert}\]The probability that the prover is able to produce an accepting transcript is at most \(\frac{1}{\vert \mathcal{C} \vert}\). As \(\vert \mathcal{C} \vert\) is exponentially large in the security parameter, the probability of a prover without valid witness succeeding is negligible, therefore it implies soundness.
In order to receive the same 2 commitments, the extractor, \(\mathcal{E}\), must use rewinding. Rewinding is simply being able to replay probabilistic events with deterministic certainty. \(\mathcal{E}\) will first go through the first transcript as per normal, they will then rewind back to just after the commitment is given and give a distinct challenge from the first transcript.
HVZK, also known as Honest-Verifier-Zero-Knowledge, is a property that \(\sum\)-Protocols must fulfil.
Honest Verifier: This property means that the verifier will follow the protocol exactly. This specifically means that \(e\) is guaranteed to be a uniformly random \(t\)-bit string, independent of all other values in the protocol.
Zero-Knowledge: This property means that the verifier learns nothing about the witness. In order to prove this, we can show there exists a \(\text{PPT}\) simulator, \(\mathcal{S}\), who on input \(\mathcal{S}(x)\) can produce a satisfying transcript \((a,\, e,\, z)\) which is indistinguishable from a transcript of a real interaction between a Prover and a Verifier.
It is important that the simulated transcript and the actual transcript are indistinguishable. If they are indistinguishable, we can prove that a real transcript provides just as much information as a simulated transcript. As the simulated transcript was simulated without the knowledge of \(w\), and is indistinguishable from a real transcript, therefore a real transcript must provide no more information than a simulated transcript.
\[\mathcal{S}(x) \approx \{(a,\, e,\ z) \text{ honest prover with witness } w \text{, on challenge } e \in_R \mathcal{C}\}\]Note: \(\in_R\) also denotes selection uniformly at random.
If there exists such a simulator, then it follows that the verifier having access to an accepting transcript should given them no advantage in computing the witness, \(w\). This is true as the verifier is able to create an arbitrary amount of accepting transcripts by just running the simulator locally.
As the verifier is honest, we know that \(e\) is chosen uniformly at random. This means that it does not matter if \(a\) is chosen before or after \(e\) as the sampling for \(e\) is independent of the given \(a\).
This shows that for an Honest Verifier, if there exists such a simulator, then from completing the protocol with P, the verifier doesn’t learn anything extra that it couldn’t have computed locally other than P knows \(w\)
This property is only defined for \(x \in \mathcal{L}\)
SHVZK, also known as Special-Honest-Verifier-Zero-Knowledge, is a property that \(\sum\)-Protocols must fulfil.
The difference between SHVZK and HVZK is that the simulator is unable to select the challenge.
\[\forall e \in \mathcal{C}: \{(a,\, z):\mathcal{S}(x,\, e) \rightarrow (a,\, z)\} \approx_c \{(a,\,z): \text{Real Protocol with chosen } e\}\]In both scenarios, the challenge is uniformly selected, however, the simulator in SHVZK must be able to efficiently simulate an accepting transcript given any specific, \(e\), while having that transcript be indistinguishable from a real accepting transcript with the same \(e\).
The difference between HVZK and SHVZK is that HVZK’s simulator may not work for all challenges, however, SHVZK’s simulator must work for \(\forall e \in \mathcal{C}\).
Instead, HVZK’s simulator uniformly randomly picks a challenge from the space of challenges it is able to simulate.
NIZK, also known as Non-Interactive-Zero-Knowledge, does not require interactions between the Prover and the Verifier during the construction of the final transcript. This means that the proof can be completed locally (on the Prover’s side) and create an accepting transcript without ever interacting with a verifier.
From HVZK, we can see that the role of the verifier is to supply a uniformly random \(n\)-bit string, after the prover has committed an \(a\) value. Fiat and Shamir realised that we can replace the verifier with a hash function that takes in an input and returns a uniformly random value based on that input.
If the sigma protocol is HVZK, using this generic Fiat-Shamir transform makes this protocol Zero-Knowledge even against malicious adversaries.
Forgery is the Prover being able to prove that they possess knowledge of \(w\), however, \(x \not\in \mathcal{L}\). In NIZK, the Prover is able to re-sample as many \(e\) values by just bruteforcing \(a\) values locally. However, through Special Soundness and SHVZK, we know that for \(x \not\in \mathcal{L}\), the witness will only be able to answer at most one \(e\) with a valid \(z\). This means that each query to the hash function has at most \(\frac{1}{2^n}\) chance of leading to a valid transcript. This shows that the probability of forgery in NIZK is negligible.
A Random Oracle is an idealised hash functions, \(\text{RO}(a)\). It works by taking in an input, \(a\), it checks if \(a\) is inside its database. If not, it will uniformly random value, note down what it is for given input \(a\) and return the value. If it ism it will return its recorded down value for \(a\).
You may notice that with a Hash Function, extractors no longer work as \(e = \text{H}(a)\) is always the same. Hence, Fiat-Shamir NIZK’s are proved secure using Programmable Random Oracle.
A Programmable Random Oracle is used in order to give extractors the ability to see queries to the RO and control the initial output of the RO. This allows the extractor to make a call, receive \(e_1 = \text{H}(a)\), rewind the RO back before the query and make the RO return a different random value the second time such that \(e_2 = \text{H}(a)\) and \(e_1 \neq e_2\)
Girault’s Identification Protocol is used to prove DLOG Relation for a composite modulus.
Prover knows: \(x \leftarrow [S]\) such that \(h = g^{-x} \pmod{N}\)
Public knows: \(h,\, N\) and a high order generator \(g \in \mathbb{Z}_N^*\)
Security Parameters: \(k,\, k^{'},\, S\) and \(R = 2^{k + k^{'}} \times S\)
\(S\) -> Bit-length of secret (Usually 256 bits)
\(k\) -> Verifier’s challenge space, which also determines the soundness error (Usually 128 btis)
\(k^{'}\) -> Zero-knowledge masking parameter (Usually 128 bits)
Girault’s Identification Interactive Protocol is not safe against a malicious verifier. A malicious verifier can send \(e = R\) and recover \(x = z \div e\)
Through Fiat-Shamir’s Generic Transformation, we can obtain a non-interactive protocol.
An OR-Proof is a proof that combines 2 \(\Sigma\)-Protocol, \(\Sigma_1\) and \(\Sigma_2\), to form a new \(\Sigma\)-Protocol, \(\Sigma_3\) which is the OR of \(\Sigma_1\) and \(\Sigma_2\).
\(\Sigma_3\) is a protocol that allows the Verifier to only know that the Prover knows a witness to \((x_0,\, w) \in R\), without revealing what the witness was, and for which input it is for.
OR Proof for statements \((x_0,\, x_1)\) and \(\Sigma_0\) amd \(\Sigma_1\).
The Prover will simulate the half of the protocol that they do not have witness for. As the Prover is unable to change the \(a_i\) after sending it to the Verifier, they are unable to change the \(e_i\) such that \(e_j = e_i \oplus s\) is a desired challenge so that they can forget an accepting transcript. This implies that in order for the Verifier to accept both transcript, the Prover must at least have a witness for one half of the protocol. The \(\oplus\) also allows for the Verifier to choose a challenge for one half of the protocol.
We first denote \(G = \mathbb{Z}_q\), where \(q\) is a suitably large prime. \(\mathbb{Z}_p^*\) where \(q \vert p - 1\) and \(\vert \mathbb{Z}_p^* \vert = p - 1\), \(g\) and \(h\) are generators of \(G\).
Parameters of commitment scheme: \((G,\, q,\, g,\, h)\)
Generating Commitment, \(c \in G\):
\[c = C_{g,\, h}(s,\, t) = g^sh^t\]Alice sends Bob a commitment, \(c = C(s,\, t)\) to a value \(s\), where \(s\) represent the message that we want to send to Bob. Alice now wants to cheat by sending Bob the same commitment \(c = C(s^{'},\, t^{'})\) where \(s^{'} \neq s\).
Alice will have to find \(t^{'}\) such that \(g^{s^{'}}h^{t^{'}} = c\). This means that Alice will have to solve \(h^{t^{'}} = cg^{-s^{'}}\) or \(t^{'} = \text{log}_h(cg^{-s^{'}})\) (DLOG Problem)
If Alice looks for distinct pairs \((s,\, t)\), \((s^{'},\, t^{'})\) such that \(C(s,\, t) = C^(s^{'},\, t^{'})\) would be equivalent to solving discrete logarithm of \(h\) with respect to \(g\).
\[x = \text{log}_g(h) = \frac{s - s^{'}}{t^{'} - t} \pmod{q}\]Breaking the binding of Perdersen Commitments is equivalent to solving the discrete logarithm problem. (Computationally Binding)
Given 2 commitments, \(c_1 = C(s_1,\, t_1)\), \(c_2 = C(s_2,\, t_2)\). It is trivial that the product of any two Perdersen commitments is a commitment to the sum of the commited values.
\[c_1 \times c_2 = C(s_1 + s_2,\, t_1 + t_2) = g^{s_1 + s_2}h^{t_1 + t_2}\]We can perform exponentiation:
\[C(x,\, y)^n = C(nx,\, ny)\]For \(t \overset{R}{\leftarrow} \mathbb{Z}_q\), \(h^t\) is uniform on \(G\), so \(c = g^sh^t\) is uniform on \(G\) regardless of \(s\).
\(\therefore \{C(s,\, t)\}_t \equiv \{C(s^{'},\, t)\}_t\) -> Perfectly Hiding
If P were to know \(l = \text{log}_g(h)\) and has a commitment \(c = C(s,\,t) = g^sh^t\). P can let \(s^{'} = s + l\) and \(t^{'} = t - 1\). P can send the commitment \(c = C(s^{'},\, t^{'}) = g^{s^{'}}h^{t^{'}} = g^{s + tl} = C(s,\,t)\). This shows that if an insecure group is chosen or if \(\text{log}_g(h)\) is known to P, P is able to open \(c\) to any pair $$(s,\, t) that they want, removing the binding property.
Given a statement \(A = C_{g,\, h}(x,\, y) = g^xh^y\). P can prove that they know \(x\) and \(y\) to V without revealing either \(x\) or \(y\). This uses the additive property of Pedersen Commitments
Completeness: \(g^{s_1}h^{s_2} = g^{xk + t_1}h^{yk + t_2} = g^{xk}h^{yk}g^{t_1}h^{t_2} = (g^xh^y)^kT = A^kT\)
HVZK: Transcripts provide no additional information about the witness/Transcripts can be simulated by V
Okamoto’s Identification Protocol can be concerted into a non-interactive proof using the genertic Fiat-Shamir Transformation where \(k = \text{Hash}(g\vert\vert h\vert\vert A\vert\vert T)\) and \(k\) has then same bit-length as \(q\).
Given the statemetns, \(c_1 = C(s,\, t_1)\) and \(c_2 = C(s,\, t_2)\), where \(t_1 \neq t_2\). P proves to V that \(\exists(s,\, t_1,\, t_2):c_1 = C(s,\, t_1) \land c_2 = C(s,\, t_2)\)
Completeness: \(c_1c_2^{-1} = g^sh^t_1g^{-s}h^{-t_2} = h^{t_1 - t_2} = h^r\)
Given the statements, \(c_1 = C_{g_1,\, h}(s, t_1)\) and \(c_2 = C_{g_2,\, h}(s,\, t_2)\), possibly \(g_1 \neq g_2\). P proves to V that \(\exists (s,\, t_1,\, t_2): c_1 = g_1^{s}h^{t_1} \land c_2 = g_2^sh^{t_2}\).
PoEC w Different Binding Generators can be converted into a non-interactive proof using a generic Fiat-Shamir Transformation where \(k = \text{Hash}(g_1\vert\vert g_2\vert\vert h\vert\vert c_1\vert\vert c_2\vert\vert c_3\vert\vert c_4)\) and \(k\) has the same bit-length as \(q\).
Given the statements, \(c_1 = C_{g_h}(s,\, t_1)\), \(c_2 = C_{c_1,\, h}(s,\, t_2) = C_{g,\, h}(s^2,\, st_1 + t_2)\). P proves to V that \(\exists (s,\, t_1,\, t_2): c_1 = C_{g,\, h}(s,\, t_1) \land c_2 = C_{c_1,\, h}(s,\, t_2)\).
Note: This essentially the same proof of PoEC w Different Binding Generators as we can let the second generator be \(c_1\).
Hamiltonian Cycle is a closed loop in a graph that visits every vertex exactly once before returning to its original node.
Finding out if a graph has a Hamiltonian Cycle is NP-Complete
Blum’s Protocol is a sigma protocol for Hamiltonian Cycles
Bit commitmnets, like Perdersen Commitments, are used to commit the different entries of our adjacency matrix as they allow for us to send information to V without them learning what the information is. It also prevents us from editing the commitments once commiteed and it also allows us to selectively reveal certain information.
Correctness: By inspection of the protocol, if P knows \(w\), then an honest V should always accept
Special Soundness: Given 2 transcript, \((a,\, 0,\, z)\) and \((a,\, 1,\, z^{'})\), we can learn \(\text{perm}\) from the first transcript and reverse \(z^{'}\) from the second transcript in order to recover the original \(w\).
SHVZK: We receive the challenge first, if \(e = 0\), we will simply commit a random permutation of \(G\), if \(e = 1\), we will simply commit a graph with a known Hamiltonian Cycle. We will then respond accordingly.
Blum’s Protocol can be transformed into a non-interactive proof using a generic Fiat-Shamir Transformation.
UC, also known as Universal Composability, is a security definition that wroks by comparing the ability of an environment, \(\mathcal{Z}\), to differentiate between an ideal and the real world. If \(\mathcal{Z}\) is unable to distinguish between the 2 worlds, \(\pi\) is said to be UC-realise \(\mathcal{F}\). \(\text{UC} \implies \text{HVZK}\).
\(\mathcal{A}\): Corruptes Prover
\(\pi\): Protocol
\(\mathcal{S}\): Simulator
\(\mathcal{F}\): Ideal Functionality (Black Box)
\(\mathcal{Z}\): Environment (Distinguisher)
Formal Definition:
\[\forall \text{PPT } \mathcal{A} \,\, \exists \text{PPT } \mathcal{S} \,\, \forall \text{PPT } \mathcal{Z}: \text{EXEC}_{\pi,\, \mathcal{A},\, \mathcal{Z}} \approx_c \text{EXEC}_{\mathcal{F},\, \mathcal{S},\, \mathcal{Z}}\]In the real world, \(\mathcal{A}\) corrupts P, and sends arbitrary messages dictated by \(\mathcal{Z}\). Honest V runs \(\pi\) with \(\mathcal{Z}\)’s input and outputs \(\top\) or \(\bot\) which \(\mathcal{Z}\) reads.
In the ideal world, \(\mathcal{S}\) takes \(\mathcal{A}\)’s position interacts directly with \(\mathcal{Z}\), including acting as the RO. This allows \(\mathcal{S}\) to have a query list, \(Q\), from \(\mathcal{Z}\). \(\mathcal{S}\) will then verify the proof provided by \(\mathcal{Z}\). If it failts, \(\mathcal{S}\) will not do anything and dummy V will output \(\bot\). If it passes, \(\mathcal{S}\) will have to extract \(w\) from the proof provided by \(\mathcal{Z}\) and Q. \(\mathcal{S}\) then sends \((x,\, w)\) to \(\mathcal{F}\). If \((x,\,w) \in R\), then \(\mathcal{F}\) will tell honest V to output \(\top\), else \(\bot\).
UC requires straight-line extraction which means that the extractor does not have rewinding power over the prover. This is due to \(\mathcal{Z}\) being an external being, not located inside the ideal world, \(\mathcal{S}\) is unable to rewind \(\mathcal{Z}\), thus requiring straight-line extraction.
Fischlin Transformation, like the Fiat-Shamir Transformation, can turn any \(\Sigma\)-Protocol into a NIZK protocol. However, Fischlin Transformation allows for \(\pi\) to be UC-realised.
\(r\): Number of Repetitions
\(t\): Challenge-bit length
\(b\): Number of bits from output length of Hash
Prover:
Verifier:
Universal Composability: As \(\mathcal{Z}\) only gets to see V’s output bits, this means that for \(\mathcal{Z}\) to differentiate the 2 worlds, real and ideal, the output from the real and ideal world’s have to differ.
SHVZK: \(\mathcal{S}\) must work for all challenges, \(\therefore \text{SHVZK}\)
Special Soundness: A cheating P can only choosse the challenge, simulator will determine \((a,\, z)\), however, for each \(a\) chosen, \(\bar{a}\) changes, which changes the hash, not allowing progress to accumulate.
To be added
To be added
To be added