Chapter 5: Introduction to Zero-Knowledge Protocols

As we have already seen with the digital signature, the authentication problem is one of the most important, complicated, and intriguing challenges that cryptography is going to face in the near future. Imagine that you want to identify yourself to someone who doesn't know you online. First, you will be asked to provide your name, surname, and address; going deeper, you will be asked for your social security number and other sensitive data that identifies you. Of course, you know that exposing such data via the internet can be very dangerous because someone might steal your private information and use it for nefarious purposes.

Some time ago, I watched a video that impressed me. I have even decided to insert it into my presentations about privacy and security, and I presented it during an event related to Smart Cities in Silicon Valley where I had been invited to talk. The video starts with an alleged magician who invites people to enter a tent set up in the middle of the city. The magician reads, one by one, each person's past and something about their future. The unbelievable thing was that the magician (who had never met any of the people interviewed before) knew particulars about the astonished participants' lives only they were supposed to know.

How was it possible? Was it really magic or was it just a trick? At the end of the video, the trick was revealed. The magician knew everything about the participants' lives – finances, assets owned, and even credit card numbers – thanks to a staff of techno-hackers who sat behind a curtain, working hard to discover all the digital secrets they could about the participants. If a hacker knows your identity, they can easily find out about most of your digital life.

In another case, you might have read a news story where a gang of thieves planted a fake ATM in a commercial center. Each time a person inserted a card and entered their PIN, a computer recorded this information and the ATM refused the operation. Once the information had been collected from the cards and the PINs stolen, the hackers could then clone the cards, reproducing them along with their PINs, and subsequently be able to withdraw money at an actual ATM.

How is it possible to block this kind of scam? There are many situations in which sensitive information, such as passwords and other private information, is required. If a hacker obtains this information linked to a person or a machine, they can easily steal identities and wreak havoc for their victims.

One way to solve these kinds of problems is by not revealing any sensitive information, but this is not always possible. Another way is to avoid exposing private information by giving proof of knowledge. These cryptographic protocols are called Zero-Knowledge Protocols (ZKPs), which we are going to study in this chapter.

In this chapter, we are going to cover the following topics:

• Non-interactive and interactive ZKPs (the Schnorr protocol) with examples and possible attacks on them
• SNARK protocols and Zcash
• One-round ZKPs
• ZK13 and the zero-authentication protocol

Now that you have been introduced to the world of ZKPs and know what they are used for, it's time to go deeper to analyze the main scenarios and protocols used in cryptography.

The main scenario of a ZKP – the digital cave

Imagine this fantastic scenario: Peggy has to demonstrate to Victor that she is able to open a locked door in the middle of Ali Baba’s cave, an annular cave with only one entrance/exit that can be reached from two directions, as you can see in the following figure. I suppose you have noticed that I have changed the names of the two actors, Peggy and Victor, from the usual Alice and Bob, just because here a verification is due, and the names Peggy and Victor match better with the first letters of prover (P) and verifier (V).

Figure 5.1 – Ali Baba's cave

This example involves Ali Baba's cave revisited in modern times, in which the door in the middle of the cave is locked through a secret electronic combination that's strong enough to prevent the entry of anyone who doesn't know the secret combination.

Now, suppose that Peggy must prove to Victor that she knows the combination to unlock the door without revealing the numbers to him.

So then, the challenge for Peggy is not to reveal the combination of the door to Victor, because Peggy is not sure whether Victor knows it and she doesn't want to give Victor any information about the combination. She just needs to demonstrate to Victor that she can exit from the opposite side of the cave.

Expressed differently, ZKP is a challenge where the answer is not revealing the exact information required, but simply proving to be able to solve the underlying problem. Indeed, the natural way to demonstrate knowing something is to reveal it, and the verification just comes naturally. However, by taking this approach of just demonstrating what you know so directly, you could reveal more information than required. With a ZKP, Peggy can avoid the issue of revealing the digital door's combination and, at the same time, Victor can be sure (even if he doesn't know the combination) that Peggy knows the combination if he sees Peggy coming out of the cave from the opposite side.

There are many ways to implement a ZKP because, as you can imagine, there are many scenarios in which such verification could be required.

For example, you can think of Peggy as a human and Victor as a machine (an ATM or server). Peggy has to identify herself to the machine, but she doesn't want to reveal any sensitive data, such as her name or surname. She just has to prove to the machine that she is really who she is supposed to be. The aim, in this case, is to avoid revealing Peggy's identity. ZKPs can be applied here. Another use case where ZKPs can be applied is the authentication of virtual machines in a computer network. We will cover this use case in Chapter 9, Crypto Search Engine, where we will use ZKPs to protect against man-in-the-middle attacks.

ZKPs can be applied to other kinds of challenges than authentication, such as the fields of nuclear disarmament and blockchain.

Now, we will delve deeper into the applications of ZKPs, starting with analyzing non-interactive protocols used to prove statements.

Non-interactive ZKPs

The protocol we are going to analyze in this section is a non-interactive ZKP. This means that the prover has to demonstrate the statement, assuming that the verifier does not know the solution (the content of the statement) and that the verification is made without any exchange of information from the verifier.

The scheme could be summed up as follows:

Prover (statement) ————-> [Proof of knowledge] —————> Verifier (verification)

Let's take this problem into consideration: Peggy states to know that a document [m] is encrypted with RSA, as follows:

m^e ≡ c (mod N)

Here, (N, c, e) are public parameters, and [m] is secret.

Important Note

Remember, I always denote the secret elements of the functions with the [] symbols.

In order to demonstrate the statement to Victor, the following protocol is executed:

1. Peggy chooses a random integer, [r1] (she keeps it secret), and calculates the inverse of r1 (represented as INV[r1]) multiplied by [m] (modulo N):

   r2 ≡ [m] * r1^-1 (mod N)

2. Peggy calculates (x1) and (x2), as follows:

   x1 ≡ r1^e (mod N)

   x2 ≡ r2^e (mod N)

   Peggy sends x1 and x2 to Victor.

3. Finally, Victor verifies the following:

   x1*x2 ≡ c (mod N)

It is supposed here that if Victor can verify step 3, x1*x2 ≡ c (mod N), then Peggy really should know [m].

As you can imagine, Peggy wants to demonstrate to Victor that she effectively knows the message [m] without revealing it. Remember that in this case, Peggy ignores whether Victor knows [m] or not.

So, the underlying challenge implicit to this statement is for Peggy to be able to solve the RSA problem without revealing [m].

Indeed, it's supposed that if Peggy knows [m] (hidden in the cryptogram (c)), she can also calculate the function x1*x2 ≡ c (mod N); otherwise, she will not be able to do that.

Another important consideration is the following: if (c) is a big number, it is supposed (I hope you will agree with me, but don't take this as gospel) that it should be hard to know x1 and x2 (the two factors of (c)) without knowing [m]. It could be considered the same degree of computational difficulty to factoring (N).

As you can see in the preceding function, (r2) is calculated using [m] in the following equation:

r2 ≡ [m] * r1^-1 (mod N)

So, the final effect of the multiplication between x1*x2 (as you can see in the following demonstration) will be to eliminate (r1) and leave m^e (mod N), which is equal to (c).

Even if Victor doesn't know [m], he can believe what Peggy states (to know [m]) because she has demonstrated she can factorize (c).

RSA is supported by the factorization problem (as we saw in Chapter 3, Asymmetric Encryption); here, the function is as follows:

x1*x2 ≡ c (mod N)

This states that it is computationally hard to find two numbers (x1, x2) that factorize (c).

Important Note

I will prove that an attack on this protocol exists that avoids the factorization problem in order to trick Victor, which we will experiment with later in this chapter.

Numerical example:

Let's see with a numerical example how this protocol works before going deeper to analyze it:

m = 88

N = 2430101

e = 9007

m^e ≡ c (mod N)

88^9007 ≡ 160613 (mod 2430101)

Now, let's start the protocol of verification.

Peggy chooses a random number:

r1 = 67

• Step 1: Peggy calculates r2:

  r2 ≡ [m] * r1^-1 (mod N)

  First, we calculate the [Inv(r1)] function (the inverse value of r1 (mod N)), and then we multiplicate it for [m]:

  67 * x ≡ 1 (mod 2430101)

  x = 217621

  [m]* x ≡ r2 (mod N)

  88 * 217621 ≡ 2139941 (mod 2430101)

  So, we have found r2:

  r2 = 2139941

• Step 2: Peggy calculates x1 and x2:

  x1 ≡ r1^e (mod N)

  x2 ≡ r2^e (mod N)

  67^9007 = 1587671 (mod 2430101)

  x1 = 1587671

  2139941^9007 ≡ 374578 (mod 2430101)

  x2 = 374578

  Peggy sends x1, x2 (1587671, 374578) to Victor.

• Step 3: Finally, Victor can verify the following:

  x1 * x2 ≡ c (mod N)

  1587671 * 374578 ≡ 160613 (mod 2430101)

  160613 = c (OK)

Let's see why this protocol is mathematically correct.

Demonstration of a non-interactive ZKP

We have to demonstrate the following:

x1 * x2 ≡ c (mod N)

Where c ≡ [m]^e (mod N), we can substitute in the previous function (x1 = r1^e) and (x2 = r2^e) so that we get the following:

x1 * x2 ≡ r1^e * r2^e ≡ c (mod N)

Substituting r2 into the equation, we have the following:

x1 * x2 ≡ (r1)^e *(m * ((r1^-1)^e) ≡ (r1)^e * m^e * (Inv(r1)^e) ≡ c (mod N)

Going by the modular power's properties (collecting together the two factors I have highlighted), we have the following:

r1^e * (Inv(r1))^e ≡ 1 (mod N)

So, eliminating r1^e and (Inv(r1))^e from the final equation will leave only the m^e remaining in the second stage of the equation, and the result will be as follows:

x1 * x2 ≡ m^e ≡ c (mod N)

As you know, since the beginning of this demonstration, (m^e) is just the RSA encryption of the secret message [m], which is equal to the cryptogram (c); that is why x1*x2 = c. That's just what we wanted to demonstrate.

The next section will show how we can attack an RSA ZKP.

Demonstrating an attack on an RSA ZKP

If you have stayed with me until this point, I'm hoping you will follow me further on this journey, so I can give you a demonstration of using a protocol to trick the verifier.

Note that I created this attack at the end of 2018. This is one of the possible attacks on a ZKP that I have demonstrated.

The goal of this attack is to demonstrate that Eve (the attacker) can calculate two fake numbers (x1, x2) which prove to factorize (N) even if Eve effectively doesn't know [m].

Let's explore how this attack works and what effects are produced:

1. Eve (the attacker) picks up a random number, [r], and calculates the following:

   [r] * (v1) ≡ e (mod N)

   [r] and (e) are public, so that is known by everyone. By means of this function, Eve can extract (v1).

2. In parallel, Eve calculates the following:

   e * x ≡ c (mod N)

   The parameters (e, c) are also known. This, just like in step 1, is an inverse multiplication (modulo N). The scope of this operation is to obtain [x]. Then, using [x], Eve multiplies [x] by [r], yielding (v2):

   x * r ≡ v2 (mod N)

   Eve sends (v1, v2) to Victor, who can verify the following:

   v1 * v2 ≡ c (mod N)

Eve can impersonate Peggy, and she can claim to know [m] even if she doesn't know it!

Numerical example:

r = 39 is the secret number chosen by Eve.

(N, c, e) are the same public parameters of the previous example (N = 2430101, c = 160613, e = 9007).

• Step 1: Eve calculates v1:

  e * r^-1 ≡ v1 (mod N)

  9007 * 436172 = 1557988 (mod 2430101)

  v1 = 1557988

• Step 2: Eve performs v2.

  The next operation is to obtain the inverse of (e) with respect to (c).

  e * x ≡ c (mod N), obtaining (x) in inverse modular multiplication:

  9007 * x = 160613 (mod 2430101)

  x = 2031892

  Then, using x, Eve obtains v2, performing the following operation:

  x * r ≡ v2 (mod N), obtaining v2:

  v2 = 1480556

  After having gained v2, Eve sends (v1 = 1557988; v2 = 1480556) to Victor.

• Step 3: Verification stage.

  Finally, Victor can verify the following:

  v1 * v2 = c

  1557988 * 1480556 = 160613 (mod 2430101)

The attack was successful!

Important Note

Peggy herself could be the primary actor of this trick if she doesn't know [m], but she wishes to convince Victor of it.

This attack works because (c) contains [m], and I don't need to demonstrate showing the value of [m]. This protocol isn't required to show [m] or its hash, [H(m)], because Peggy doesn't want to reveal any information about [m] to Victor. Remember this is not an authentication protocol, but it's a proof of statement (or knowledge) that Peggy knows [m].

To use a hypothetical example, you can think of a scenario where there are two countries: (A) has to demonstrate to (B) that it holds the formula for an atomic bomb. Using this ZKP, (A) could claim to know [m] (the formula of the atomic bomb) without really knowing it.

This attack could be avoided under one condition:

If Victor already knows [m], then he can require Peggy to send him a hash of the message, H[m]. Victor can then verify whether (x1 and x2) are the correct values, and he will accept or deny the verification based on the correspondence of the hash value with [m].

In this case, the problem is that the aim of this protocol was not to prove something that was already known but to prove something independently, regardless of whether or not it was known.

This last point is very important because if Victor knows [m], then this protocol works; if Victor doesn't know [m], this protocol fails.

To avoid this problem, we have to switch to an interactive protocol, as we will see in the next section.

Schnorr's interactive ZKP

The protocol that we saw in the previous section is a non-interactive protocol, where Peggy and Victor don't interact with each other but there is simply a commitment between them. The commitment is that Peggy has to show that she knew the message [m] without revealing anything about it. Thus, she tries to demonstrate to Victor that she can overcome the RSA problem (or another hard mathematical problem) as proof of her honesty. However, we have also seen that this protocol can be bypassed using a mathematical trick.

Let's see whether the following interactive ZKP is more robust and can prevent possibly devastating attacks.

We always have Peggy and Victor as our main actors. So, let's assume the following:

• p is a big prime number.
• g is the generator of (Zp).
• B ≡ g^a (mod p) is the public parameter of Peggy.
• (p, g, B) are public parameters.
• [a] is the secret number object of the commitment.

Peggy claims that she knows [a]. In order to demonstrate the claim, Peggy and Victor apply the following protocol:

• Step 1: Peggy chooses a random integer, [k], where 1 ≤ k < p-1.

  She performs the following calculation:

  V ≡ g^k (mod p)

  Peggy sends (V) to Victor.

• Step 2: Victor chooses a random integer, (r), where 1 ≤ r < p-1.

  Victor sends (r) to Peggy.

• Step 3: Peggy calculates as follows:

  w ≡ (k - a*r) (mod p-1)

  Peggy sends (w) to Victor.

• Step 4: Finally, Victor verifies as follows:

  V ≡ g^w * B^r (mod p)

  If that is true, Victor should be convinced that Peggy knows [a].

Let's see why the protocol should work and the reason why the last function (V) states that Peggy really knows [a] (the commitment).

First of all, I will show why the protocol is mathematically true, and then I will give a numerical example of this protocol.

A demonstration of an interactive ZKP

Recall the following instructions:

V ≡ g^k (mod p)

B ≡ g^a (mod p)

w ≡ k - a*r (mod p-1)

Now, we substitute all the past equations inside the last verification of step 3:

V ≡ g^w * B^r (mod p)

V ≡ g^k (mod p)

Substituting the functions in (V), the equation becomes the following:

V ≡ (g^ (k - a*r (mod p-1))) * ((g^a)^r) (mod p)

For the properties of exponential factors, we have the following:

g^k ≡ g^ (k -[ar]) * g^[ar] (mod p)

V ≡ g^k ≡ g ^(k -ar +ar)

Simplifying [-ar] with [+ar], we get back the following:

g^k ≡ g^k (mod p)

That's what we wanted to demonstrate.

Let's do a numerical example to better visualize how this interactive ZKP works.

Numerical example:

p = 1987

a = 17

g = 3

(p = 1987 and g = 3) are public parameters.

[a] = 17 is the secret number that Peggy claims to know:

B ≡ g^a (mod p)

(B) is the public key of Peggy, given by the following:

3^17 ≡ 1059 (mod 1987)

Peggy picks up a random number, [k] = 67, and she calculates (V):

V = 3^67 = 1753 (mod 1987)

Peggy sends (V) to Victor.

Victor picks up a random number (r = 37) and sends it to Peggy, who can calculate was following:

k – a * r ≡ w (mod p-1)

67 – 17 * 37 ≡ 1424 (mod 1987-1)

w = 1424

Peggy sends (w = 1424).

Finally, Victor now verifies whether (V) = 1753 corresponds to the following:

g^w * B^r ≡ V (mod p)

3^1424 * 1059^37 ≡ 1753 (mod 1984)

V = 1753

In fact, it does correspond.

Now, we analyze the reason why this protocol states that by knowing [a] automatically, Peggy can convince Victor. Let's use an example to better understand the problem.

This protocol can be used as an authentication scheme in which, for example, Victor is a bank that holds the public parameter (B) of Peggy (a client of the bank). The secret number [a] could be Peggy's secret code (PIN). In order to gain access to her online account, Peggy has to demonstrate that she knows [a].

In another use case, we could have Victor as a central unit computational power (server) and Peggy as a user who wants to connect to the server using an insecure line, or again (as we will see later), Peggy could be another server, too.

The point of using a ZKP is to avoid Peggy revealing her sensitive data to the public. So, the underlying problem she has to demonstrate to Victor consists of solving a challenge in which she can demonstrate that she knows the discrete logarithm of (B).

As we have seen in Chapter 3, Asymmetric Encryption, knowing (B) and (g) is not enough to compute [a] in this function:

B ≡ g^[a] (mod p)

This is because we are operating in modular functions.

Of course, Peggy needs to know [a] if she wants to compute the verification function, (w):

w ≡ k - a*r (mod p-1)

There is no way to trick Victor, who moreover sent (r) to Peggy, which is used in the last verification function together with (v) and (B), along with (r), to be sure that Peggy cannot bluff:

V ≡ g^w * B^r (mod p)

So, I hope to have convinced you that there is no way for Peggy to trick Victor in this case.

Demonstrating an attack on an interactive ZKP

Now that we have seen that Peggy can't trick Victor, I have an attack against this protocol that I created in late 2018; let's see whether it works or not.

Here, the scope for an attacker (Eve) is to provide a final proof of verification without knowing the secret number, [a].

Step 1: Peggy chooses a random integer [k] where 1 ≤ k < p-1.

Then she calculates the following:

V ≡ g^[k] (mod p)

It's when Peggy sends (V) to Victor that Eve can try to shoot a man-in-the-middle attack.

Peggy sends (V) to Victor.

Step 2: Victor chooses a random integer, (r), where 1 ≤ r < p-1.

Eve injects V1 ≡ g^k1 (mod p), where [k1] is a number invented by Eve that substitutes [k].

Eve sends (V1) to Victor, substituting her value for Peggy's result. After receiving (r) from Victor, Eve calculates (v1) as follows:

V1 ≡ g^(v1) * B^r (mod p)

This is the path to the attack:

• If you can exclude (r) from the final verification function, (V1), then you have reached the goal.
• Essentially, the attacker should find a value for (v1), as follows:

  v1 = [x] —————-> V1 = g^k1

Here are some notes:

• Remember that you don't have to implement (v1) in the same way the preceding function (v) did, but you are free to give (v1) any value.
• Remember that the earliest point of attack is substituting (V) with (V1), but that is not mandatory. In this case, the warning is that as you don't know (r) when you have delivered (V1) to Victor, this parameter can no longer be changed.
• Good luck! If you are able to find a way to trick the Schnorr interactive protocol, please let me know when you have arrived at a conclusion, and you will get a cryptographer researcher position.

The preceding analyzed interactive protocol suffers from another problem. Let's imagine that two people live in different time zones, such as Europe and Australia. If one is ON, the other one is probably OFF because they're sleeping. So, what happens if they have to wait for many hours to make or receive an economic transaction?

This protocol doesn't fit well with this kind of purpose, such as cryptocurrency transactions. Most cryptocurrency protocols use zero-knowledge algorithms to anonymize data inside their architecture structures. Now that we know how to implement such a protocol, we can explore zk-SNARKs.

An introduction to zk-SNARKs – spooky moon math

If you think ZKPs are pretty difficult to understand, that is because you haven't yet faced off with zk-SNARKs – a kind of ZKP, also known as spooky moon math. Here, the situation gets a little bit more complicated, but don't worry – it's not impossible. In the next section, you will see interesting new attack possibilities.

Non-interactive zero-knowledge proofs, also known as zk-SNARKs or zk-STARKs, are kinds of ZKPs that require no interaction between the prover and verifier, like the first protocol we saw in this chapter. In this section, we are going to focus on zk-SNARKs.

The name zk-SNARK stands for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge. So, we are facing off with schemes that need only one interaction between the prover and the verifier.

Indeed, zk-SNARKs are very much appreciated for their ability to anonymize transactions and to identify users in cryptocurrency schemes, as we will see in this section.

The first cryptocurrency that adopted this new system to create consensus was Zcash.

The use of zk-SNARKs in a blockchain is important, as we will see later, for the use of smart contracts. As you may know, a smart contract is an escrow of cryptocurrency activated following the completion of an agreed execution.

Since smart contracts and blockchains are not a part of this book, I will show just a limited example of how zk-SNARKs work in a cryptocurrency environment, as it will be useful to understand.

For example, suppose Peggy makes a payment in Ethereum to execute a smart contract with Victor. In that case, both Peggy and Victor want to be sure that the execution of the smart contract (for Peggy) and the payment received (for Victor) are completed successfully. However, many details inherent to the smart contract will not be revealed. So, the role that zk-SNARKs play is fundamental to covering these secrets and executing smart contracts. In order to work, the protocol has to be fast, secure, and easy to implement.

As we have already seen, you will notice that this is just what the purpose of a ZKP is – to ease the navigation of an untrustworthy environment. Here, we are talking about blockchains and virtual payments, but essentially the process is similar.

So, in this environment, zk-SNARKs keep secrets by protecting the steps involved in a smart contract and, at the same time, proving that all these steps have been executed. This way, they protect the privacy of people and companies.

Remember that – not because you have to be super-skeptical, but because you should be realistic – this statement is true under determinate conditions, which I will try to explain as follows:

• The proof given by the prover holds the same computational degree of difficulty as the underlying algorithm chosen as a proof of knowledge.
• There is no mathematical way to trick the verifier with a shortcut or fake proof (such as substituting fake parameters into the V1 ≡ g^(v1) * B^r (mod p) equation in order to avoid knowing [a] ).

So, let's see how a zk-SNARK works.

Understanding how a zk-SNARK works

In this section, first of all, I will try to synthesize how zk-SNARKs generally work, and then we will return with a zk-SNARK protocol related to a proof of knowledge based on a discrete logarithm.

As we already have seen for the other ZKPs, a zk-SNARK is composed of three parts or items – (G), (P), and (V):

• G: This is a generator of keys, made by a private parameter (the statement or another random key) that generates public parameters given by private keys.
• P: This is a proof algorithm that states what the prover wants to demonstrate.
• V: This is a verification algorithm that returns a TRUE or FALSE Boolean variable from the verifier. I will demonstrate now that using ZKPs (and, in particular, zk-SNARK protocols) is not enough to keep [w] secret, but it is possible to arrive at proving the statement as TRUE if it is also FALSE.

Let's look at how a similar protocol example explained in the Interactive ZKP section (Schnorr) would work in a non-interactive way (zk-SNARK mode).

In this protocol, we have Anna as the prover and Carl as the verifier.

Here, Anna has to prove that [a] is known to her.

Anna calculates her private key, (y), given by the following:

y ≡ g^a (mod p)

(g) is a generator (as in D-H or other private-public algorithms we have already seen in this book).

Then, Anna picks up a random value, [v], inside p-1, which she keeps secret, and consequently, she can calculate the following:

t ≡ g^v (mod p)

Anna calculates (c) as a hash function of the three parameters, (g, y, t), and she can compute (r) as follows:

r ≡ v – c*a (mod p-1)

The verifier, Carl, can check the following:

t ≡ g^r * y^c (mod p)

Finally, if the verification validates the two terms of the function, then Carl accepts that the statement [a] proposed by Anna is TRUE.

Now that we have analyzed how this ZKP works in a zk-SNARK environment, let's see an attack on this protocol before we cover a numerical example.

Demonstrating an attack on a zk-SNARK protocol

This attack was performed by me in June 2019 and just goes to show that nothing is completely secure.

Let's say that Eve is an Artificial Intelligence (AI) server. We suppose that Eve (AI) intercepts the H(g, y, t) public hash function and performs a MiM attack.

While Peggy sends (V) to Victor, Eve substitutes (c) = H(g, y, t) with (c1) = H1(g, y, t1), remembering that (H) is the hash function and that (t1) is given by the following:

t1 ≡ g^v1 (mod p)

As you have probably noticed, substituting (v) with (v1) is the same trick that substituted (k) with (k1) in the previous attack.

Simply, Eve can put (r1) as follows:

r1 = v1

Now, Eve orders the AI (the intelligent third server connected to the internet) to send to Carl (r1, v1, c1), who can verify the following:

t1 ≡ g^r1 * y^c1 (mod p)

It's simple to demonstrate that t1 = g^v1 because of the following:

y^(p-1) ≡ 1 (mod p)

Finally, as we have assigned c1 = p-1 and r1 = v1, the final effect will be as follows:

t1 ≡ g^v1 ≡ g^v1 * 1 (mod p)

Numerical example:

p = 3571

g = 7

x = 23

Anna's public key is as follows:

y ≡ g^x (mod p)

7^ 23 = 907 (mod 3571)

y = 907

Now, I will show you how Anna can demonstrate to Carl to get the secret number, [x].

She chooses v = 67, as follows:

t ≡ g^v (mod p)

7^ 67 = 584 (mod 3571)

t = 584

Let's suppose that hash (g, y, t) as follows:

c = 37

She computes r as follows:

r ≡ v - c*x (mod p-1)

(67 - 37*23) ≡ 2786 (mod 3570-1)

r = 2786

Anna sends (r, t, c) = (2786, 584, 37) to Carl.

Carl can verify the following:

g^r * y^ c ≡ t (mod p-1)

7^2786 * 907^37 = 584 (mod 3571)

However, the AI intercepts the public parameters (y), (t), and (r). Eve leaves the (y) invariant, but she changes (t) with (t1) and (r) with (r1), performing a man-in-the-middle attack:

v1 = 57

Eve calculates the following:

t1 ≡ 7^57 (mod 3571)

t1 = 712

v1 = r1 = 57

c1 = p-1 = 3570

Eve sends (r1, t1, c1) = (57, 712, 3570) to Carl.

Carl verifies the following:

t1 ≡ g^r1 * y^c1 (mod p)

I highlighted the parameter that Eve substitutes, (t1, r1, c1); she left the (y, g, p) invariant.

Substituting the new parameters into the equation of verification, we have the following:

7^57 * 907^3570 ≡ 712 (mod 3571)

Indeed, Carl is able to verify that t1 = 712 corresponds with the parameters received from Eve.

Essentially, if Carl is not able to recognize that r1 = v1 and/or he doesn't accept c = p-1, then the trick is done, and Eve can replace Anna.

So, what are the protections to adopt against this attack?

If this attack is implemented in a more sophisticated mode, it will probably be very difficult to avoid it.

Note that the parameter (y), the public key of Anna that "envelopes" the private key [a] object of the statement, hasn't been modified during the attack.

Anyway, zk-SNARKs can be implemented using other methods and protocols to prove statements; we will see what these algorithms and protocols are in the next section. Blockchains and cryptocurrency are evolving quickly to find new methods to authenticate users anonymously. However, with this topic being relatively new, it is better to make the effort to find all the possible attacks and the repair methods for them.

Zk-SNARKs in Zcash cryptocurrency

In this section, we will analyze the zk-SNARK behind Zcash, a new cryptocurrency that aims to preserve the security and privacy of transactions, as discussed in a scientific paper released on November 12, 2020 (Demystifying the Role of zk-SNARKs in Zcash):

"The underlying principle of the Zcash algorithm is such that it delivers a full-fledged, ledger-based digital currency with strong privacy guarantees and the root of ensuring privacy lies fully on the construction of a proper zk-SNARK."

A blog about Zcash stated the following regarding zero-knowledge proofs: allow one party (the prover) to prove to another (the verifier) that a statement is true, without revealing any information beyond the validity of the statement itself. In a version of zero-knowledge called "proof of knowledge," the prover can demonstrate a statement without revealing any sensitive information about the content.

But, as we have seen until now, these protocols are based on problems that are difficult to solve, such as factorization and discrete logarithms, and we have seen in the previous sections how some of them could be vulnerable to various kinds of attacks.

A reason why you should adopt a ZKP is to authenticate yourself without revealing too much information about your sensitive data or your server's identity.

Another reason for using a ZKP is to prove that you know something that you want to keep secret.

Here, we have two main different cases:

• In the first case, it is supposed that the verifier doesn't know the content of the statement.
• In the second case, it is supposed that the verifier already knows the content of the statement, and only has to verify its correctness.

All that becomes much more complicated if you decide to adopt a non-interactive protocol instead of an interactive protocol because, in the first case, the verifier does not need to give any further input. Indeed, as you can see, if a parameter is exchanged between the prover and the verifier, that could increase the security of the algorithm. On the other hand, we know that interactive protocols need many steps to reach the goal, hence they are not used as much as non-interactive protocols.

As we have seen in the previous sections, I have shown some attacks that are capable of deceiving the verifier, making them believe something that isn't true; moreover, if the verifier doesn't know the content of the statement, it is even easier to send fake mathematical parameters to trick them.

Now, the situation is changing fast in cryptography, for two reasons:

• The need for cryptography to address privacy and anonymize data for an increasing number of transactions over the internet and in e-commerce
• The rise in the use of digital payments and cryptocurrency

To anonymize exchanges of digital money and to ensure the privacy of users in cryptocurrency transactions, zk-SNARKs are adopted in several cases. The verifications used for the two main problems we have seen (RSA and the discrete logarithm) are almost obsolete. They are leaving room for new and more sophisticated, hard-to-solve problems; in Zcash, we see one such use case.

To get perfect zero-knowledge privacy, Zcash implemented a complex system of functions to determine the validity of a transaction.

In Zcash's consensus system, using zk-SNARKs, the objective is to return a response on the validity of a transaction without knowing anything about the content and terms of the transaction itself.

Zcash adopts a complex scheme to anonymize transactions and obtain a final answer as to whether transactions are valid. Here, I have tried to schematize the circuit:

Computation → Arithmetic circuit → R1CS → QAP → zk-SNARK

Figure 5.2 – Circuit flow

Let's analyze what these functions represent one by one.

The first step is turning transaction validity into a mathematical function, which finally has to be gathered into a logical expression. This step is taken by creating an arithmetic circuit similar to a Boolean circuit (we saw this in Chapter 2, Introduction to Symmetric Encryption, and Chapter 3, Asymmetric Encryption) made by mathematical base operations (+, -, *, and /) and computed by Boolean operators (AND, OR, NOT, and XOR), so that the program converges into only one gate, which is the result of all the operations chained together, as we can see in the following example of computing the expression (a+b)*b*c:

Figure 5.3 – An example of an arithmetic circuit. Inputs: a, b, and c. Output: (a+b)*b*c

As you can see, the arithmetic (or algebraic) circuit converges in only a single gate all the operations performed on the inputs: a, b, and c. Looking at this circuit, from left to right, we have the single terms (a, b, and c); first, (a) is added to (b), then (b) is multiplied by (c), and finally, the result is multiplied by the result of the previous sum. All that is mathematically expressed in only one final gate. We can represent layers and layers of these operations, reducing them all to one arithmetic circuit.

The second step is a Rank 1 Constraint System (R1CS) representation.

In R1CS, we have a group of three vectors (A, B, and C), as you can see in the following figure. The solution to satisfy the system is a new vector (S) given by an operation of a (.) dot product between the vectors, of which the final result has to be zero. So, R1CS has this scheme of operations and must satisfy the following equation with a result of zero:

(S ● A) * (S ● B) - (S ● C) = 0

For example, this is a satisfied R1CS system:

Figure 5.4 – An example of a satisfied R1CS system

As you can see in Figure 5.4, the value of the vector [S] is [1, 3, 35, 9, 27, 30], which ensures a satisfied R1CS system.

Indeed, if you look at column [A], the result of the operations (.) at the end of the column is as follows:

[1.5 + 3.0 + 35.0 + 9.0 + 27.0 + 30.1] = [5 + 0 + 0 + 0 + 0 + 30] = [35]

The result of the operations in column [B] is as follows:

[1.1 + 3.0 + 35.0 + 9.0 + 27.0 + 30.0] = [1 + 0 + 0 + 0 + 0 + 0] = [1]

Finally, the result of the operations in column [C] is as follows:

[1.0 + 3.0 + 35.1 + 9.0 + 27.0 + 30.0] = [0 + 0 + 35 + 0 + 0 + 0] = [35]

Therefore, R1CS checks whether the values are traveling correctly. It's a verification of the values. In our example in Figure 5.4 for instance, R1CS will confirm that the value coming out of the multiplication gate where (b) and (c) went in is (b*c).

In the third step, Zcash converts R1CS flat code to a Quadratic Arithmetic Program (QAP), which operates on polynomials in (mod x).

So, the next step is taking R1CS and converting it into QAP form, which implements the same logic as before, except using polynomials instead of dot (.) products between vectors.

As I told you before, I will limit myself to explaining the Zcash process at a high level, so I will not go any deeper in analyzing the third step of the QAP.

At this point, can you guess why the inventors of Zcash put so much effort into this system?

It is probably because the inventors aspired to create the perfect ZKP. Indeed, in the paper entitled Aurora: Transparent Succinct Arguments for R1CS, the authors stated that their goal is to obtain transparent zk-SNARKs that satisfy the following conditions:

• Post-quantum security: This is motivated by the desire to ensure the long-term security of deployed systems and protocols.
• Concrete efficiency: We seek argument systems that not only exhibit good asymptotics (in argument size and prover/verifier time), but also demonstrably offer good efficiency via a prototype.

Given the high expectations predicted by the authors for this protocol, let's go on to explore the final steps of the sequence.

This protocol offers a probabilistic solution by performing a multiplication of polynomials. If the two polynomials match at a random point, we can be confident that the chosen point verifies the proof correctly. The reason for this transformation is that instead of checking the constraints individually, as in R1CS, we can now check all the constraints at the same time. Here, you can see an example of how the vector verification looks in a QAP:

Figure 5.5 – An example of the vector verification in a QAP

Can you recognize the differences between this representation and the checksum in R1CS?

In both cases, if the logic gate is equal to zero, the result given by the dot (.) product of the checks passes; if at least one of the (x) coordinates gives a non-zero result, this means that the values going into and out of that logic gate are inconsistent.

But at this point, there could be a problem: if someone knows in advance which point the verifier chooses to check the validity, they can generate an invalid polynomial, but it could still satisfy that point.

Essentially, this is a dangerous step and could be vulnerable to attacks. To overcome this problem, Zcash applied sophisticated techniques to zk-SNARKs in order to evaluate the polynomials blindly. These mathematical techniques used in Zcash, such as homomorphic encryption and pairings of elliptic curves, help to blind the operations but increase complexity. We will look at these issues in the next section, but now we will finish discussing the entire process of zk-SNARKs in Zcash.

As I said at the beginning of the Zcash explanation, the goal of the protocol is to determine whether a statement (in this case, a transaction) is true or false, thereby preventing the double-spending problem.

Conclusions and the weaknesses of zk-SNARKs in Zcash

As we saw in the previous section, one of the weak points of this protocol can be found in QAP. As I have explained, Zcash has tried to overcome this problem using homomorphic evaluation, in other words, keeping the polynomials in blind. The issue is that homomorphic encryption usually causes bit-overflow; moreover, the protocols and schemes required to achieve fully homomorphic encryption are very complex. As you already know, my theory is that in cryptography, complexity is the enemy of security. I won't enter this debate now because it's not within the scope of the book to analyze the entire protocol of Zcash.

Imagine the scenario discussed in the Non-interactive ZKPs section based on the RSA problem. If I have to demonstrate to an expert that I hold the formula for an atomic bomb, then the experts will probably ask me to show something more than a hash function of the document, [m], that states the proof. The verifier will be convinced only when they get substantial proof. In other words, ZKPs are limited in the amount of evidence of knowledge they are able to provide.

One-round ZKP

In this section, we'll explore a little-known ZKP composed of only one round of encryption that was presented by two researchers, Sultan Almuhammadi and Clifford Neuman, of the University of Southern California, which purports to give proof of knowledge for a challenge in just one round. The paper states the following: “The proposed approach creates new protocols that allow the prover to prove knowledge of a secret without revealing it.”

The researchers also proved that a non-interactive ZKP is more efficient in terms of computational and communications costs because it saves execution time and reduces latency in communication.

ZKPs are used in many fields of information technology, such as e-commerce applications, smart cards, digital cash, anonymous communication, and electronic voting. Almuhammadi and Neuman sought to satisfy the requirements of ZKPs but in just one round, eliminating any iterative mathematical scheme that would entail high computation and communication costs.

So, let's dive deep to analyze this one-round ZKP and see how it works.

Let's say that Peggy wants to demonstrate to Victor that she knows a discrete logarithm (we'll be focusing on a discrete logarithm, but the protocol can work for other problems); in order to do this, Peggy has to demonstrate that she knows [x], as follows:

g^[x] ≡ b (mod p)

Victor launches a challenge (c) to verify whether Peggy really knows [x]. He picks up a random [y] and calculates the preceding function:

c ≡ g^[y] (mod p)

Victor sends (c) to Peggy. She inserts the parameter [x] on (c), computing (r) as follows:

c^[x] ≡ r (mod p)

Peggy sends (r) to Victor, who can verify the following:

r ≡ b^[y] (mod p)

Finally, Victor accepts the verification if (r) corresponds to V = b^[y] (mod p).

This protocol looks very simple and straightforward. It is based on the computational difficulty to calculate the discrete logarithm, as you have seen in previous cases. But to help you better understand the operations, I will show how it works mathematically and demonstrate a numerical example in the next section.

How it works mathematically

The first question is: why are the parameters (r and V) mathematically identical?

Here, you can find the answer:

r ≡ c^[x] ≡ g^[y]^[x] ≡ g^[y*x] (mod p)

V ≡ b^[y] ≡ g^[x]^[y] ≡ g^[x*y] (mod p)

As you can see, r ≡ V ≡ b^y (mod p).

Numerical example

Let's look at a numerical example:

p = 2741

g = 7

x = 88 is the secret number that Peggy has to demonstrate that she knows.

The statement is as follows:

g^x ≡ b (mod p)

7^88 ≡ 1095 (mod 2741)

b = 1095

Victor chooses a random number:

y = 67

Victor calculates the following:

g^y ≡ c (mod p)]

7^67 ≡ 1298 (mod 2741)

c = 1298

Peggy, after having received (c), calculates the following:

c^x ≡ r (mod p)

1298^88 ≡ 361 (mod 2741)

r = 361

Peggy sends (r) to Victor, who can verify the following:

b^y ≡ V (mod p)

1095^67 ≡ 361 (mod 2741)

V = 361 = r

Finally, it is verified!

As you can see, we have proved the one-round ZKP with the help of a numerical example. In the next section, I will demonstrate the strong similarity of this protocol with a protocol we have analyzed before in this book: Diffie-Hellmann (D-H).

Notes on the one-round protocol

Having analyzed this protocol, you may have noticed that it is similar to the D-H exchange. Undoubtedly, the authors of the one-round ZKP were well aware of that. Still, even though the aim of the one-round ZKP is different from that of D-H, I will compare the two algorithms so that you can see what similarities there are.

In the second part of the analysis, we will see how efficient this protocol is. Indeed, with only two steps, Peggy can demonstrate to Victor that the statement [x] is valid.

Now, we can reassemble the one-round protocol using the following method:

Step 1: Peggy

g^x ≡ b (mod p)

That is the same in D-H as the following:

g^a ≡ A (mod p)

Step 2: Victor

g^y ≡ c (mod p)

That is the same in D-H as the following:

g^b ≡ B (mod p)

Step 3: Peggy

c^x ≡ r (mod p)

In D-H, this becomes the shared key H:

B^a ≡ H (mod p)

Step 4: Victor

b^y ≡ r (mod p)

In D-H, this again becomes the shared key H:

A^b ≡ H (mod p)   

So, [H] is the shared private key that "Alice and Bob" (here, Peggy and Victor) use to compute in D-H. Here, it is just [r = H] that gives the proof to Victor.

So, we can certainly say that Sultan and Clifford's protocol is identical to D-H, as discussed in Chapter 3, Asymmetric Encryption.

This protocol undoubtedly verifies that Peggy knows [x]. She can demonstrate it to Victor even if Victor doesn't know [x]. That is the exciting point, and the innovation of this protocol: even if Victor doesn't know [x], by using this protocol, he can be confident that Peggy knows it. In other words, what the authors of this protocol did was apply the D-H protocol to the ZKP use case.

If you look at the simplified version of the protocol shown below, you will get an even better understanding of the steps required. There are only two, essentially:

• Initialization of the parameters for Peggy is g, b, p, and x.
• Victor generates a random y.

Step 1: Victor sends the following to Peggy:

c ≡ g^y (mod p)

Step 2: Peggy sends the following to Victor:

r ≡ c^x (mod p)

Instantly, Victor can verify the following:

r ≡ b^y (mod p)

As you can see, there are only two steps required to perform this protocol and verify the statement [x] through Victor's validation of the parameter (r).

This protocol gave me the inspiration to build a new protocol, which we will explore in the next section. My research has allowed me to reduce the number of steps to one.

ZK13 – a ZKP for authentication and key exchange

The ZK13 protocol was invented and patented by me in 2013. It's a non-interactive protocol that solves an issue that was very important to my Crypto Search Engine (CSE) project: authentication without a public key.

In this section, we will analyze this ZKP that's used for authentication. It doesn't matter whether it's humans or computers; we could call this protocol a ZK-proof of authentication. To better understand the problem, imagine Alice and Bob want to share a common secret, something that only they know. Let's say that the secret is the answer to the following question: how many birds were counted at the lake shoreline today? The answer is known only to Alice and Bob, unless they have revealed it to someone, but this is a problem we will take into consideration later. For now, nobody else can know the answer except Alice and Bob. We can consider the number of birds counted as a shared secret, a key that doesn't need to be exchanged. It is shared by Alice and Bob, a key that is implicitly formed by a common experience. So, besides the authentication problem, there is also the problem of verifying a private Pre-Shared Key (PSK). Indeed, under ZK13, Alice tells Bob to use the secret shared key (the number of birds counted) as a secret password, [private key]. What's even more interesting here (and this is where it really differs from the D-H key exchange algorithm we saw before) is that the secret key is not really exchanged at all, but instead is simply something that is known to both parties and is only verified.

So, the problems that this ZKP can solve are several. Here, we will just consider the authentication problem. Later in the book, we will analyze how to use a ZKP to exchange a shared private key.

In 2013, I was drawing up the architecture of the CSE, a project that has absorbed a large part of my professional life. We will talk in detail about the CSE in Chapter 9, Crypto Search Engine. At the time, one of the toughest problems to solve with the CSE's architecture was finding a cryptographic method to identify the Virtual Machines (VMs) network. Since the algorithm chosen was symmetric, the problem was to find a method of authentication that would work with the symmetric algorithm. As you already know from Chapter 2, Introduction to Symmetric Encryption, it's common to think that symmetric algorithms don't have a digital signature method of authentication because they do not have public keys. At first glance, it doesn't seem easy to find such a method of authentication, but it can be possible if the process starts with a shared secret. The goal was to prevent a man-in-the-middle attack by an external hostile VM against a network.

To overcome all these issues, I considered implementing a new ZKP. Taking a look at the most popular ZKPs, I did consider Schnorr (presented earlier in this chapter) as a candidate. But an interactive protocol didn't fit well. This scheme needs more steps between the prover and verifier, generating latency in the communication. So, I decided to implement a new personal zero-knowledge non-interactive protocol.

After many studies and a pinch of inventiveness, I designed ZK13. Before analyzing it, I will explain what constraints I worked under:

• The secret shared key (the challenge) has to be embedded inside the VM database. Therefore, engineers could inject the secret parameter [s] into both of the VMs without exchanging any keys through an asymmetric algorithm.
• The goal of ZK13 is to enable parties to identify each other by sharing a small amount of sensitive information. This means exchanging only the minimum amount of sensitive information (that is, the hash of [m]: H(m) instead of [m] itself) that needs to be shared. Indeed, the greater the amount of information exchanged, the greater the vulnerability to attack becomes.
• ZK13 had to be a simple and, as I have already said, non-interactive protocol. Therefore, only one piece of information should be required by the prover. The reasons for this are twofold: first, to avoid an excess of information being exchanged (see the previous point) because that could compromise security. The second reason is related to the goal of the application: the CSE is a platform on which encrypted data is searched and retrieved using the cloud or external servers. Because a search engine has to be fast, queries should be fielded and answers given in the least amount of time possible. So, it is crucial to avoid latency during the authentication phase.
• Another constraint of ZK13 was for it to use the best and most secure authentication methods. At the time that it was conceived (2011–2013), the quantum computing era was not yet seen as dangerous for cryptography. So, the underlying problem on which the system relied was the discrete logarithm, which is still considered a hard problem.

ZK13 explained

The ZK13 protocol, with only one transmission and a shared secret, is presented as follows:

Figure 5.6 – The scheme of the shared hash[s] secret

Let's dive deeper into ZK13 and see how it works.

Bob (VM-1) has to prove that he knows the secret, [s], to Alice (VM-2) in order to send Alice a set of encrypted files using the CSE system. Remember that [s] is stored inside the brains of both Alice and Bob, the two VMs, as an innate native injected secret.

Bob picks a random number [k] (the (G) element of a zk-SNARK or the random key generator). This random number, [k], is generated and destroyed in each session:

Public parameters:

p: This is a prime number.

g: This is the generator.

Key initialization:

[k]: This is Bob's random key.

Secret parameters:

[s]: This is the common shared secret.

H[s]: This is the hash of the secret, [s].

Step 1a: Bob calculates (r) as follows:

r ≡ gk (mod p)

Let's say that the secret shared is [s], but effectively, the VM operates with H[s], the hash functions of [s].

Step 1b: Bob calculates [F], a secret parameter, which is changed in each session (just because [k] changes):

H[s]*k ≡ F (mod p-1)

Now, with (g) raised to [F], Bob proves (P), which is the second element of the zk-SNARK:

gF ≡ P (mod p)

Bob sends the pair (P, r) to Alice.

Step 2: The verification step (V) validates the prove, (P), based on the function:

[s] ——> H[s]

r[Hs] ≡ gF (mod p)

If:

V ≡ r[Hs] = P (mod p)

Alice proceeds to make a hash of [s]: H[s], and then she accepts the authentication if V = P; if ((V) is not equal to (P)), she doesn't accept the validation.

In this case, as we have supposed in the initial conditions, [s] is supposed to be known by Alice.

As you can see, ZK13 works in only two steps, but the verifier (in this case, Alice) must know the secret, [s]; otherwise, it is impossible to verify the proof.

Numerical example:

Now, let's see a numerical example of the ZK13 protocol:

Public parameters:

p = 2741

g = 7

Secret parameters:

H[s] = 88

k = 23

g^k ≡ r (mod p)

7^23 ≡ 2379 (mod 2741)

r = 2379

Now, Bob calculates [F] and then (P):

[Hs] * k ≡ F (mod p-1)

88 * 23 ≡ 2024 (mod 2741-1)

F = 2024

g^F ≡ P (mod 2741)

7^2024 ≡ 132 (mod 2741)

P = 132

Alice verifies the following:

r^[Hs] ≡ P (mod p)

2379^88 ≡ 132 (mod 2741)

Alice double-checks whether [Hs] = [s]; if it's TRUE, then it means that Bob does know the secret, [s]. Now that we have proven that ZK13 works with a numerical example, I want to demonstrate how it works mathematically.

Demonstrating the ZK13 protocol

Since P ≡ g^F (mod p), what we want to demonstrate is the following:

P ≡ gF ≡ rs (mod p)

(Here, I use [s] for the demonstration instead of H[s].)

As r ≡ g^k (mod p), substituting (r) in the preceding equation, we have the following:

P ≡ gF ≡ (g^k)^s (mod p)

We also know that F is the following:

F ≡ s*k (mod p-1)

Finally, for the properties of the modular powers substituting both [F] and (r), we get the following:

P ≡ gs*k ≡ (g^k)^s ≡ g^k*s (mod p)

Basically, I have substituted the parameter (P), the proof created by Bob, with the elements of the parameter itself, demonstrating that the secret, [s], is contained inside (P). So, (P) has to match with the ephemeral parameter (r)^[s] generated by Bob and sent to Alice together with the proof, (P). If Alice knows [s], then she can be sure that Bob also knows [s] because (P) contains [s]. That's what we wanted to demonstrate.

Notes and possible attacks on the ZK13 protocol

You will agree with me that using this protocol, it is possible to determine proof of knowledge of the secret, [s], in only one transmission.

During the explanation of the algorithm, I have divided it into three steps, but actually, there are only two steps (with only one transmission), because the operations of (G) key generation are offline. So, steps 1a and 1b can be combined into effectively only one step.

Possible attacks on ZK13

Let's say Eve (an attacker) wants to substitute herself for Alice or Bob, creating a man-in-the-middle attack.

This could be done as follows.

Eve replaces (r) with (r1), generating a fake (k1), by calculating the following:

r1 ≡ g^k1 (mod p)

But when Eve computes [F], she doesn't know H[s] (because it's assumed that [s] will remain secret). So, this attack fails.

Instead, she can collect (r, P) and replay these parameters in the next session, activating a so-called replay attack.

This attack could be avoided here, because (r) is generated by a random [k], so it is possible to avoid accepting an (r) already presented in a previous selection.

So, that was one attack that could be faced, and we saw how to avoid it.

Summary

Now you have a clear understanding of what ZKPs are and what they are used for.

In this chapter, we have analyzed in detail the different kinds of ZKPs, both interactive and non-interactive. Among these protocols, we saw a ZKP that used RSA as an underlying problem, and I proposed an original way to trick it.

Then, we saw the Schnorr protocol implemented in an interactive way for authentication, on which I have proposed an attempt to attack.

Moving on, we explored the zk-SNARKs protocols and spooky moon math, just to look at the complexity of some other problems. Among them, we saw an interesting way to attack a discrete logarithm-based zk-SNARK. We dived deep into Zcash and its protocols to see how to anonymize the transactions of this cryptocurrency.

Later in the chapter, we encountered and analyzed a non-interactive protocol based on the D-H algorithm. Finally, we explored ZK13, a non-interactive protocol, and its use of shared secrets to enable the authentication of VMs.

You became familiar with some schemes of attacks, such as man-in-the-middle, and used some mathematical tricks to experiment with ZKPs.

The topics covered in this chapter should have helped you understand ZKPs in greater depth, and you should now be more familiar with their functions. We will see in later chapters many links back to what we explored here. Now that you have learned the fundamentals of ZKPs, in the next chapter, we will analyze some private/public key algorithms that I have invented.