"Secret" in the Cloud: Building Non-Interactive Zero-Knowledge Proofs — Exploring Zero-Knowledge Proofs Series (5)

Author: Yu Guo

Once exposed, a secret loses all its power. Ann Aguirre

This is the fifth article in this series, and this one goes deeper into non-interactive zero-knowledge proofs. This article is about 12,000 words.

Series 1: Getting to Know "Zero Knowledge" and "Proof"

Series 2: Understanding "Simulation"

• Perspectives | Re-analysis of Private Chain and Alliance Chain Concepts
• European Securities and Markets Authority to introduce digital currency legal framework to address growing cyber threats to retail customers
• People's Daily: Guangdong Financial High-tech Zone-Introducing "Blockchain" and Strengthening "Jinkechuang"

Series 3: Searching for "knowledge"

Series 4: Random "Challenge"

outline

1. CRS Past and Present
2. Hamiltonian loop problem
3. Secrets in the cloud: Hidden Bits
4. Upgrade randomness
5. FLS Transformation: From Hidden Bits to NIZK
6. Finding the Ideal Trapdoor Permutation
7. NIZK Proof vs. NIZK Argument
8. A world without secrets

Readers who come here must have a general understanding of zero-knowledge proofs. Have you ever thought about this question: Why is zero-knowledge proof feasible? Here, please think about it (such as the process of the map three coloring problem in series one ) … (Stay here for three minutes) The following two elements seem to be essential:

1. "Interaction": The verifier reduces the probability of cheating by the prover to a very small value through repeated challenges.
2. "Hidden Randomness": The verifier challenges the random number that the prover cannot predict

But for the non-interactive zero-knowledge proof, NIZK, how to achieve the above two points? In the fourth series, we introduced how to use the "random oracle" to play a virtual "third party" role, to realize the virtual "interaction" and "random challenge". This article will go deeper into another method, how to remove "interaction" and "hide randomness" through a shared string. This string must be randomly generated by a "third party" in advance. This is the legendary "Common Reference String" (CRS).

CRS Past and Present

If we do not resort to any other means and limit the prover Prover and the verifier to "zero-knowledge proof", then they can only prove the "trivial" problem, which is to calculate the complex class BPP ( Bounded- error Probabilistic Polynomial time ), and this complexity class is generally guessed that it may be equivalent to P (but it is still pending and has not been proven! BPP can be understood as P + Randomness).

Note: If Prover and Verifier only interact once, in such a NIZK system, we can easily construct a Decision Procedure-Verify (x, Sim (x)) to prove and falsify the theorem, so it can only prove trivial Question BPP.

Trivial problems can be proved with zero knowledge, but they have no meaning! How to understand it? Because the verifier can directly solve the "secret input" based on the "output" in polynomial time, although the verifier can solve it, the "proof" itself does not provide additional "knowledge" for the verifier. In other words, without the prover showing the proof, the verifier knows that the proposition is true, so the proof process is also zero-knowledge.

Therefore, when we discuss "zero-knowledge proofs," we need to consider NP-type problems with "knowledge." Everyone knows that the P problem is a complex class that can be solved in "deterministic Turing machine" polynomial time. Its execution path is a linear state transition for the input x. The NP problem is a type of problem that can be solved by "Uncertain Turing Machine" polynomial time. The so-called uncertainty Turing machine is that it is uncertain every time it takes a step forward. There are many options. As long as any execution path can reach the termination state, it means that it has solved the problem x. In other words, its execution trajectory is a tree. Then if we record the path selection of each step of the uncertainty Turing machine (this record of the execution path is called witness, which is the "knowledge" we repeatedly mentioned), then give (x, witness) to a deterministic graph Smart, then it can also solve the x problem in polynomial time.

Again, "knowledge" can improve Turing machines' ability to solve problems.

In the NP problem, there is a knowledge witness that does not want to "leak" to the verifier. At this time, in an interactive proof system, the prover and the verifier are not equal in the degree of "knowledge".

In order to guarantee the "zero knowledge" of the proof process, we need to ensure that the simulator is not equal to the verifier . However, there is no witness in the simulator. How can they make them not equal? In the previous article, we introduced the "random oracle". We created inequality by allowing simulators to abduct "random oracle sprites." This article will explain how to use CRS to create inequality.

The CRS is a random string that was published before the proof and shared between the prover and the verifier. How do we use CRS? Intuitively, a string of information that both parties "know" does not increase the "knowledge" inequality.

First of all, people will think, can you directly use CRS as a random challenge number? Can CRS be used instead of the role of the "random prophecy wizard"? The answer is no!

why? This is because the CRS was generated before the proof. If the prover Prover knows all the random challenge numbers in advance, then it is clear that the random challenge is meaningless.

Note: Please remember how the "random oracle" guarantees that the prover cannot predict the "random challenge number" in advance? If you don't want to understand, please reread the series (4).

The mission of CRS is to make "simulators" and "verifiers" unequal. How to do it? Hide some "secrets" into it.

If you ask further, what is the use of hiding the "secret"? Of course it is useful. In the "ideal world", simulators and extractors can play happily (get some super powers) …

In 1988, the paper "Non-Interactive Zero-Knowledge and Its Applications" ("Non-Interactive Zero-Knowledge and Its Applications" [BFM88]) by Manuel Blum, Paul Feldman and Silvio Micali pioneered "Hidden Randomness" is unnecessary. They presented a NIZK proof system for map three coloring problems, with the help of a shared randomly generated string (ie, CRS).

However,…, I will not tell you that this solution needs to share about n ^ 4 very long CRS, where n is the length of the "proposition" to be proved.

In 1990, Uriel Feige, Dror Lapidot and Adi Shamir proposed another NIZK scheme for constructing NP language [FLS90]. Unlike [BFM88], this NIZK scheme is no longer based on specific number theory assumptions, but based on a cryptographic tool, Trapdoor Permutation. In this scheme, FLS proposed the concept of "Hidden Bits" and then hid Hidden Bits into CRS. For the simulator, the effect of the simulation can be achieved by modifying the Hidden Bits in the CRS, thus reflecting the superiority of the verifier. However, this scheme needs to share a longer CRS, which exceeds k * n ^ 5, where k is a security parameter.

Since then, the idea of ​​Hidden Bits has been adopted by many people. It is worth mentioning that Kilian and Petrank have adopted a more clever method to use Hidden Bits [KP98] (the space is too small to write :), and successfully put CRS Is reduced to k * n ^ 2. Later, J. Groth continued to optimize, reducing the length of the CRS to about k * n [Groth10a].

In addition to Hidden Bits, J. Groth, R. Ostrovsky and A. Sahai [GOS06] used the homomorphic encryption scheme Boneh-Goh-Nissim [BGN05] or Boneh-Boyen-Shacham to implement NIZK. They used the "public key of the encryption scheme" As a CRS, Prover encryption is used as a proof, and then the homomorphic property is used to prove another NP-Complete problem-the satisfiability problem of Boolean circuits. The biggest advantage of this scheme is that the CRS length is fixed, because it is only a key, and the length is only k. For the simulator, it can get the trapdoor corresponding to this public key through super power, so it can seal any information, but get the same ciphertext; for the extractor, it can get The private key corresponding to the public key can decrypt the proof to obtain "knowledge".

In 2010, Jens Groth proposed a new NIZK Arguments scheme based on the KEA (Knowledge of Exponent Assumption) hypothesis and Pairing [Gorth10b], which is also the starting point for many subsequent zkSNARKs schemes. The CRS here is composed of a pair of (g ^ x ^ n, g ^ ⍺x ^ n), which is used to achieve the "knowledge commitment". Where x and ⍺ are two random numbers, they must be "forgotten" after generating the CRS. Some people call this to-be-forgotten random number "Toxic Wastes", which is easy to mislead the reader. Not only are they non-toxic and harmless, they are also very useful. They are the "secrets" hidden in the CRS, they are the weapons of the simulator. If the simulator gets x and ⍺, it can falsify the proof, thus guaranteeing zero knowledge of the proof. As for the extractor, he can extract knowledge directly through the built-in extraction function of KEA hypothesis.

The latest Sonic solution [MBK + 19] implements Updateable CRS on the basis of [Groth10b]. If anyone is worried that the secret in the CRS has been leaked, he can apply a patch to the original CRS and continue to hide a secret in it, so that the security of the CRS can be guaranteed. The CRS here is also "Universal", that is, the CRS only needs to be generated once to cope with all propositional proofs. This scheme was subsequently adopted by the latest Plonk [GWC19], Marlin [CHMMVW19] and other schemes.

Let's start with a simple example to understand how to construct NIZK based on CRS. Before that, we need to introduce an NP-Complete problem-the Hamiltonian loop problem.

Hamiltonian loop problem

Imagine there are several cities in a map, and there can be highways between cities.

If you have a map that allows you to find a path and walk through all the roads without repeating (assuming each road is a Parkway with beautiful scenery, maybe you want to eat all the roads without repeating it) McDonald's, out of a certain sentiment). I believe you will be excited immediately, isn't this the "stroke" you learned as a kid? To determine whether a map can be drawn in a single stroke, this is a math problem made by primary school students. We can calculate the number of highways connected to each city and divide them into "singular points" and "even points" according to the parity. If there are two singularity cities on a map, then you can only start from one singularity city, traverse all roads, and eventually reach another singularity city. This path is called the Euler's Path.

If all the cities in a map are even points, you can start from any city, easily find a path, traverse all roads without repeating, and return to the starting point. This loop is called the Euler's Circuit.

And if there are more than two singular points on the map, then there is no Euler circuit, such as the famous Gothenburg Seven Bridges problem.

The famous Gothenburg Seven Bridges problem is described as such, if you do not cross the seven bridges below repeatedly.

The Seven Bridges map of Gothenburg obviously has multiple singularities, and there is no Euler path. If any map is given, whether there is an Euler cycle, this is a P problem, that is, a computer can find it in poly (n) polynomial time.

Note: The finding algorithm of Euler's loop is called Fleury algorithm.

For such a P problem, if a prover Prover proves that he knows an Euler circuit, then he can send the plaintext of the circuit directly, and the verifier verifies that the circuit is correct. Please note that this process is still zero-knowledge. Because Verifier did not gain any additional knowledge through the information sent by Prover. In other words, Verifier did not enhance its computing power because it saw the loop, because Verifier could calculate the Euler loop by itself.

What we are talking about is the "Hamiltonian Loop Problem" which is an NP problem and is described as follows:

Is there a loop in a map that can cross every city without repeating it ?

For example, the following map:

We use a matrix of matrix V * V to represent this map. If two cities (A, B) are connected by road, then fill 1 in (A, B) and (B, A), or 0 otherwise. . This matrix is ​​called the "adjacent matrix". We can flatten this adjacency matrix into a 0/1 bit string.

Finding the "Hamiltonian loop" is an NP-Complete problem. In other words, there is no algorithm that allows a computer to find a loop in poly (n) polynomial time. However, a computer can test whether a path is a "Hamiltonian loop" in polynomial time. For example, there is a Hamilton Loop with directions in this map. We can verify at a glance that the loop actually passes through every city. If a map has a Hamilton cycle, its matrix must meet the following characteristics: each row must have a 1 and each column must also have a 1.

ZK-HAM protocol

We give a three-step interactive Sigma protocol below. Alice proves to Bob that she "knows" the Hamilton loop of map G above.

• Public input: G is a map with 6 vertices, expressed as a 6 * 6 adjacency matrix
• Secret input: Hamilton Circle C of G (the orange road in the picture)

• Step 1: Alice randomly selects a "permutation", Perm (.), And then uses this permutation to generate a new graph G '; then Alice encrypts each cell of the G' matrix and generates a new matrix to send to Bob .

[Nomenclature]: The so-called replacement, you can imagine that you can use the mouse to drag the points in the diagram, but the line between the points and points will be dragged along with the points. You get G ', such as the two pictures on the left side of the figure above. The permuted and transformed graphs are isomorphic before and after. In the figure below, the number in the angle brackets on each vertex is the number of the vertex in the figure before dragging. A formal point can be defined as follows: Perm () is an adjacency matrix of a new graph G 'of bijective functions {1, V} to {1, V}, [perm (i), perm (i + 1)] = 1 If and only if [i, i + 1] = 1, where i is the vertex number and V is the number of vertices.

• Step 2: Bob randomly selects b in {0, 1}} for the challenge.

• The third step (1): Alice sends the value according to Bob in the second step: if b = 0, then Alice sends the permutation function Perm () and reveals the complete graph G '. And Bob confirms whether G 'is the original image G and has been replaced without error.

• The third step (2): If Bob sends b = 1 in the second step, then Alice only reveals the Hamiltonian loop C 'in G'. And Bob needs to verify that C 'is a Hamiltonian loop

Recalling the three-step Sigma protocol, we understand the seemingly complex actions above:

• Step 1: It is called Commit. The prover Alice needs to perform homomorphic transformation on the answer in her hand to generate a new answer, and then lock each side and give it to Bob;
• Step 2: Bob challenges randomly;
• Step 3: Alice makes two different responses based on Bob's random challenge. If Bob challenges 0, then Alice opens the promise of the first step, indicating that she did not cheat in the first step; if Bob challenges 1, Alice only decrypts the edge (highway) that exposed the Hamiltonian loop, and the other edges do not need to be decrypted. Bob can easily check whether the exposed edges on the map form a loop that passes through all cities without repeating.

If this Sigma protocol only goes once, the probability of Alice cheating is 50%. If you repeat n times, the probability of Alice cheating will decrease exponentially. You can try to use the "simulator" and "extractor" methods to prove the "zero knowledge" and "reliability" of this protocol.

Deformation of ZK-HAM: ZK-HAM-2

Next change the above three-step protocol. Let us first consider the simple fact: if a subgraph C containing only loops is a subgraph of graph G, and C <= G, then G contains a Hamiltonian loop.

This fact is equivalent to another fact: the complement of a Hamiltonian graph G! G is the complement of the loop subgraph C!

[Nomenclature] The complement of a graph: The so-called complement is such a new map, the vertices remain unchanged, the edges on the old map do not exist in the new map, and the roads in the new map do not exist in the old map, but two When the graphs are superimposed, they become a complete graph (a complete graph is an edge between any two vertices).

Use the adjacency matrix to understand, that is, if a graph G contains a loop subgraph C, then all the set of elements in the G matrix with a value of 0 must be included in all the set of elements with a value of 0 in the C matrix. It can be expressed as! G <=! C.

Based on the second fact, we can define the following Sigma protocol:

• Public input: graph G, expressed as an adjacency matrix of 6 * 6
• Secret input: Hamilton Circle C of G (the orange road in the picture)

• first step:
  • Alice randomly selects a "permutation", Perm (.), And constructs a Hamilton cycle subgraph C '= Perm (C) by C;
  • Alice then encrypts each cell of C 'and sends the decrypted result to Bob.
• Step 2: Bob randomly selects b in {0, 1} for the challenge

• The third step (1): If b = 0, Alice reveals the complete C ', and Bob verifies whether this C' is indeed a Hamiltonian loop subgraph.

• The third step (2): If b = 1, Alice sends Perm (), and at the same time, reveals the corresponding unit in C 'according to the location of all units containing 0 in G' = Perm (G); Bob verifies C 'Whether all revealed units are all zeros.

Understand these three steps of the Sigma protocol:

• Step 1: The prover Alice needs to perform a transformation on the Hamilton subgraph C to generate a new Hamilton subgraph C ', which is encrypted and given to Bob;
• Step 2: Bob challenges randomly, 0 or 1;
• Step 3: If Bob challenges 0, then Alice opens the commitment in the first step and displays a graph with a unique loop; if Bob challenges 1, Alice opens the commitment according to the position of unit 0 in G 'and displays the commitment. The opened positions are all 0.

The point is here, let's take a closer look at the first step in this new version of the Sigma protocol. Did you find anything?

The first step Alice sends is irrelevant to map G!

Similarly, the challenge sent by Bob in the second step is also independent of the map. In this way, we can change the promise sent in the first step to a bit string prepared in advance , and we assume that this bit string is generated by a trusted third party, so that Bob does not need to send the branch b = 0, because The third party of the letter is honest, he must have prepared a correct loop sub-picture in advance. In this way, since Bob only needs to send 1 challenge branch, this step can also be removed.

As a result, the three-step protocol became a step. We successfully removed the interaction and hope to implement NIZK.

We next push the first and second steps of the ZK-HAM-2 protocol into a prepared string, and then only let Alice send the content of the third step to Bob. As shown below:

Please note that this is not yet a NIZK system, because this shared string cannot be made public to Bob, otherwise Bob can calculate the loop C. Next, we will explain a new concept: "Hidden Bits" [FLS90]. Hidden Bits are a series of random bits that are hidden from the verifier Bob but exposed to the prover Alice. Then during the proof process, Alice can selectively reveal a part of the bits to show to Bob. This is a good tool for constructing the NIZK certification system. We need to continue to deepen …

Secrets in the cloud: Hidden Bits

Let's open our brains again. Imagine a cloud in the sky. Behind the cloud is a string of randomly generated bit values, either 0 or 1. Then Alice (the prover) wears a "super eyeglasses" and can see the cloud All subsequent random bit strings are not visible to Bob (the verifier). At the same time, Alice also has a "super flashlight". She can turn on the flashlight and use the laser to penetrate the clouds, so that Bob can also see one or some of the bits. Of course, the choice of bits that Bob can see is entirely in Alice's hands.

The hidden bit strings in the clouds are called Hidden Bits .

Next, we need to complete a single-step interaction through Hidden Bits to complete the functions of the ZK-HAM-2 protocol. In the first step in ZK-HAM-2, Alice generates a random permutation Perm (), and then generates a transformed loop subgraph C '= Perm (C) through the Hamilton loop subgraph C in G. This is equivalent to generating a random Hamiltonian loop subgraph C 'by anyone beforehand, and then Alice calculates a corresponding Perm () from C and C'.

Suppose that a random third-party subgraph C 'is generated by a "third party", encoded into a "adjacent matrix" bit string, and placed behind the clouds. Suppose V is the number of vertices (city) and E is the number of edges (highway). The coding of this adjacency matrix requires a V * V bit string, which can be interpreted as a V * V matrix, where each row contains only one 1 and each column contains only one 1. The other elements of the matrix are all zero.

How does Alice construct the proof next? It's actually quite simple:

1. Alice uses the "super glasses" to get a random Hamiltonian loop subgraph C ', and then calculates a permutation Perm () such that Perm (C) = C'.
2. Alice calculates a transformed graph G '= Perm (G) based on Perm ()
3. Alice generates a proof, which consists of two parts: (1) Perm () replacement (2) The value of the C 'matrix corresponding to all the unit coordinates of 0 in the adjacency matrix of G', which is equivalent to Alice's need to use a "super flashlight" Hidden bits revealed to Bob.

So how does Bob verify this proof? Once Bob has the proof, he only needs to test two things:

1. Whether Perm () is a valid permutation V-> V, for example, two vertices cannot be mapped to the same vertex.
2. For each "non-edge" in G, after the replacement, Bob looks up at the corresponding "hidden bit" in the sky, the bit value must be 0

Let's take a closer look at this non-interactive protocol. Start with "completeness": If Alice didn't cheat, then obviously it can pass Bob's verification. Here, please check it yourself.

Next, we briefly prove the "reliability" in two steps: First, because Bob has verified that all non-edge sets after G replacement have been revealed, and all are 0, then we can conclude that! G < =! C, that is, the non-edge set of G is a subset of the non-edge set of the loop subgraph C. This is equivalent to C <= G, which means that G contains a Hamiltonian cycle. Note here that this reliability probability is 100%.

Then, imagine that in an "ideal world", Bob gains some kind of super power (such as Alice's "super glasses"), without the need for Alice's super flashlight, he can see through the clouds and get all the hidden bits C '. Then when Bob gets Perm (), he can calculate C by Perm (), so Bob is equivalent to transforming into an "Extractor". In an ideal world, it can use the knowledge that Alice wants to prove. Extract for success.

So how to prove "zero knowledge"? Alice needs to have a super ability, that is, in the "ideal world", you can secretly modify the hidden bits in the cloud. It's easy now, the simulator Zlice can trick Bob like this:

1. Zlice sets all hidden bits in the cloud to 0
2. Zlice randomly generates a valid Perm ()

Everyone found that the key is that the bit hidden in the sky must be a trusted string. The so-called "trusted" means that it should indeed be a Hamiltonian loop subgraph. Then the third party needs to be trusted.

But is such a third party unsatisfactory? Alice and Bob must absolutely trust him, and will not collude with their opponents. If he is conspiring with Alice, he can directly set the hidden bit string to all 0s; or he conspiring with Bob and directly showing this bit string to Bob. This agreement looks good, but it is difficult to practical. We will next upgrade this simple protocol.

Upgrade randomness

The first upgrade is to make the hidden bit string into a "consistently uniformly distributed" random hidden bit string, which is a bit string that looks rather random, rather than a deliberately placed Hamilton subgraph.

Completely random means that the number of zeros in the bit string is approximately close to the probability of the occurrence of one. Then the next problem is how to make a random Hamiltonian loop subgraph matrix appear in the random bit string. The method is very simple and rude: generate a random string long enough, and then scan from scratch until a random Hamiltonian loop is found.

But … Is this probability of success very, very small? Below we give a search method with a not so small probability.

1. We first slice the bit string according to the length of 5log (V), and then if all the bits in each slice are all 1, then we treat this segment as a unit of value 1 in the adjacency matrix, otherwise Treated as a unit with a value of 0. In this way, the probability of each matrix unit being 1 is 1 / (V ^ 5).
2. We take consecutive V ^ 6 fragments to form a large matrix of V ^ 3 * V ^ 3. If the large matrix contains a V * V Hamiltonian loop matrix and all other elements (V ^ 6-V ^ 2 in total) are 0. Then we call this large matrix "useful".
3. According to the probability calculation, the probability of a "useful" matrix is ​​1 / [V ^ (3/2)].

Note: Please refer to Fact 4.10.8, "Foundations of Cryptography, Vol I" by Oded Goldreich, P304 for the probability calculation process of the "useful" matrix.

OK, we need to upgrade the protocol in the next section. Because the "hidden bit string" is now split into several large matrices, some of these large matrices are "useful" and some are useless.

Next, Alice is going to construct the proof. She first puts on super glasses and scans the Hidden Bits in the clouds. There are two cases.

• Case 1: If Alice encounters a useless large matrix M, Alice exposes all the cells of M.
• Case 2: If Alice encounters a "useful" large matrix M, this means that Alice gets a random Hamiltonian loop C ', and then Alice can prove it by referring to the steps in the previous section.

So how does Bob verify this proof? We also have to discuss the situation,

• Case 1: If Alice exposes all M's, then Bob checks if this M is "useless". If M is useless, the proof is considered valid; otherwise, it is rejected.
• Case 2: If Alice sends a certificate of the form (Perm (), X), then Bob verifies according to the verification method in the previous section.

For this protocol, Bob no longer has to worry about whether a third party cheats, and deliberately generates an all-zero bit string, but Alice is still concerned that once the third party colludes with Bob, the knowledge is completely leaked.

Not only that, the current protocol has a very strong limitation. Alice cannot choose G that needs to be proven after seeing the hidden bits, otherwise Alice can cheat. If a "proposition" that a prover chooses to prove has nothing to do with CRS, then the prover is called Non-adaptive Adversary.

FLS Transformation: From Hidden Bits to NIZK

Next, we upgrade the protocol again to remove the hidden features from the "hidden bit string" and turn it into a "public reference string" CRS. Here we have to resort to a cryptographic tool-Trapdoor Permutation.

The so-called trapdoor permutation refers to a permutation function F (x), where x is an element in a set S, and then the function F (x) maps x to another element y in S. At the same time, F (x) satisfies one-way, that is, it is difficult to calculate x by y; but if anyone has trapdoor t, the backward calculation F ^ (-1) (t, y) = x can be realized. The trapdoor replacement can also match a Hardcore Predicate, h (x) = 0/1, which can generate a consistent distribution of 0/1 bits according to the elements in the S set. After the introduction, is everyone a little dizzy? It doesn't matter, dizziness will get used to it. In a word, the trapdoor replacement can convert the common reference string and Hidden Bits to each other.

Suppose we have such a cryptographic tool, and then we upgrade the protocol.

We see the public reference string as a list, y1, y2, y3, …, yn, where each item in the list is an element in the set S. Each bit in Hidden Bits is then generated by Hardcore Predicate. However, please note that you cannot directly generate Hidden Bits by h (y) = b, because then Bob can calculate all Hidden Bits by himself, which violates the agreement in the previous section. In order to guarantee the hiding of Bob, we need to use the original image of the public reference string, that is, x1, x2, x3, …, xn to generate Hidden Bits, h (x) = b. Although Bob cannot calculate b1, b2, b3, …, bn by himself, once he gets an x, he can check F (x)? = Y to determine whether x corresponds to the common reference string, and then calculate h ( x) = b gives the revealed Hidden Bits, b.

We can use a less accurate, but more intuitive way to understand that Alice is equivalent to generating a pair of public and private keys. Then Alice treats the public reference string as a piece of "ciphertext". Since Alice has a private key, she can decrypt the ciphertext to get the plaintext. These plaintexts are equivalent to Hidden Bits for Bob. When Alice wants to "reveal" Hidden Bits, she presents the corresponding plaintext fragment and brings the public key, so Bob can "encrypt" the plaintext again with the public key and compare it with the ciphertext of the public reference string to ensure that Alice does not have Cheating during the reveal process.

Here is the upgraded agreement:

For the prover Alice :

1. Alice randomly selects a Trapdoor Permutation, (F, h, t)
2. According to each yi in the common reference string, use the trapdoor to calculate xi = F ^ (-1) (t, yi)
3. Calculate Hidden Bits, bi = h (xi)
4. Generate a certificate according to the agreement in the previous section. Assume that the set of positions of Hidden bits to be revealed by Alice is r1, r2, …, rl, then Alice sends x of corresponding positions to Bob, which are x_r1, x_r2, x_r3, … x_rl, together with (F, h) , And send it to Bob along with the proof.

For the validator Bob :

1. Check if (F, h) is a valid Trapdoor Permutation.
2. For each element x_r in L, calculate the revealed Hidden Bits bi = h (F (x_r)), and then check the proof according to the agreement in the previous section.

Please check the "completeness" of this new agreement yourself.

For "zero-knowledge", we need to construct a "simulator" Zlice2 whose superpower is to modify the common reference string.

1. The simulator directly calls the simulator Zlice from the protocol in the previous section. Get a triple, (proof, {r}, {b})
2. For each common reference string position, if it corresponds to a certain r, the simulator randomly selects an x_r from the set S such that h (x_r) = b_r, where b_r is the corresponding r in {b}; then set y_r = F ( x_r) as part of the fake reference string.
3. For each common reference string position, if it has nothing to do with {r}, the simulator can choose a y
4. The simulator puts all y together to get a fake CRS.

With "reliability," things are not so simple. Because Alice now has the ability to pick (F, h, t), Alice can pick a (F, h, t) that is good for her or even cheat, so that she can control the results of Hidden Bits {b} once the protocol runs. For the new protocol upgraded in this section, it needs to be repeated many times, so that although Alice can control the Hidden Bits of one protocol operation, she cannot do anything about the Hidden Bits of other protocol operations. In other words, no matter how Alice chooses (F, h, t), she can't completely control the operation of the protocol multiple times.

This upgrade transformation can theoretically support non-interactive zero-knowledge proofs under any Hidden Bits model, which is called the FLS Protocol. The FLS transformation has many benefits: first, this randomly generated CRS can be used multiple times to achieve the so-called "Multi-Theorem NIZK"; second, it can implement "Adaptive Soundness", that is, Alice can see the CRS first, and then choose the The content of the proof. In the end, this protocol is still "Adaptive Zero-Knowledge", that is, Bob can also see the CRS first, and then choose what to prove to Alice.

Note: Adaptive Adversary is more in line with real-world security situations, such as Type II CCA security. Because CRS is public, an attacker can analyze the CRS before deciding how to launch the attack.

Finding the Ideal Trapdoor Permutation

Trapdoor Permutation first appeared in the paper "Theory and Application of Trapdoor Functions" [Yao82] by Yao Qizhi, and is an important foundation of public key cryptography. In the FLS transformation given in the previous section, an idealized Trapdoor Permutation is required. The so-called idealization means that each n-bit string can be uniquely turned into another n-bit string and will not appear. "Many to one" mapping relationship. Alice needs to randomly sample an Index and send it to Bob. Then Bob can check whether the F () corresponding to this Index is a "perfect" permutation. The question is, how can Bob check it out in polynomial time? If Bob can't check, then Alice can sample an imperfect Permutation (such as a "many-to-one" function), which may cheat and destroy the "Soundness" property. The 1996 paper by Bellare and Yung first noticed This, but it does not completely solve the problem [BY96].

How to find a bridge that can properly abstract Trapdoor Permutation and connect to the implementation of cryptographic tools is a very challenging task. Since then, various cryptographers (including Oded Goldreich) have studied this area for a long time and published many papers. Various types of Trapdoor Permutation have been defined and studied, but they are still not satisfactory. Until recently (2018) a job was that Ran Canetti and Amit Lichtenberg proposed a new type of Certifiable Injective Trapdoor Function [RL18] and proved that this Trapdoor Permutation can finally meet the FLS transformation requirements. But is this the end of the story? Theoretic cryptographers do not expect to stop exploring.

In addition to the FLS transformation based on Trapdoor Permutation, there are various solutions to upgrade the Hidden Bits Model, such as using Invariant Signature [BG90], or Verifiable Random Generator [DN00] to implement Hidden Bits transformation, or weakly verifiable random Function [BGRV09], there is another scheme called publicly-verifiable trapdoor predicates [CHK03].

In the past thirty years, there have been many NIZK schemes invented by cryptographers, but the Hidden Bits method is the only known method at present. (1) shared CRS based on "consistent distribution", and (2) implement NIZK Proofs of any NP language (Not Arguments!).

NIZK Proofs and NIZK Arguments

In this article, the reliability of the NIZK "proof" system we construct belongs to "Statistical Soundness", and zero knowledge belongs to "Computational Zero-Knowledge". What does this mean? This means that no matter how powerful the prover Alice is (even a super polynomial), Alice still cannot cheat. However, if the verifier Bob has super-computing power, then this possibility exists: Bob extracts valuable "knowledge" from the proof.

What does this mean?

This means that for NIZK Proofs, its length must be longer than "knowledge", which is the witness in the NP problem. As long as Bob is strong enough, he can decrypt the proof. For the "extractor", it also needs to extract the witness without interaction. The shortest proof of NIZK Proofs is the NIZK scheme constructed by Greg Gentry and others using "full homomorphic encryption" technology [GGI + 14], which proves that the length is only slightly longer than the length of witness.

Can you construct a NIZK that proves to be smaller than the witness? The answer is YES!

There is another type of NIZK system called NIZK Arguments: their reliability is "Computational Soundness", and zero knowledge belongs to "Perfect Zero-Knowledge" or "Statistical Zero-Knowledge". This shows that if Alice has super strong computing power, she has room for cheating, but because in the real world, we can greatly reduce the possibility of Alice cheating by increasing the Security Parameters, but it can achieve very extreme Zero-knowledge feature. Since the reliability is weakened, we can continue to compress the size of the proof.

Note: In this series, we do not intentionally distinguish the words "proof" and "argument". If Arguments need to be specified instead of Proofs, it will be specifically emphasized.

Suppose we want to publicize a NIZK certificate on Github. If a hundred years later, the Github website is still there, and the computing power of the computer has made a qualitative leap, at this time, a NIZK Proof may be broken by computing power , Leak knowledge, and NIZK Argument is likely to remain secure.

The popular buzzword-AR in zkSNARK is exactly Argument.

NIZK Argument can prove the length of O (1) constant level, which is independent of the length of witness. However, this requires hiding more secrets into the CRS.

A world without secrets

In 1956, Gödel mentioned a famous question in a letter to Von Neumann, "Is P equal to NP?" Later, this issue was listed by Clay Research as one of the seven millennial problems, with a reward of millions of dollars.

The zero-knowledge proof system is just to protect the witness from being leaked to realize the verification of the NP problem. So what does it mean if "P == NP" is proven? This means that witness no longer has much meaning, anyway, a Turing machine can also find witness in polynomial time. Zero knowledge proves that the witness trying to protect also becomes futile.

In fact, if "P == NP", the existing public key cryptography, symmetric encryption AES and SM4, and the difficult problems that the hash algorithm depends on may all collapse, and we may have a hard time keeping secrets. Not only that,

If P == NP, our world would be very different. "Creative Leaps" will no longer be of value, and the gap between solving problems and verifying problems no longer exists. Everyone who can appreciate the symphony will become Mozart, everyone who can reason will become Gauss, and everyone who can judge the good or bad investment will become Buffett. From the perspective of Darwinian evolution: If this is the universe in which we exist, why haven't we evolved to take full advantage of this benefit? -Scott Aaronson (2006)

The same is true for mathematics. The verification process of mathematical proofs is also of polynomial complexity. If "P == NP", then there is also a polynomial time finding algorithm (if the proof exists). This means that Goldbach's conjecture and Riemann's conjecture may be proved. No wonder Lance Fortnow said in his blog [For04]:

A person who proves P == NP would walk home from the Clay Institute not with one million-dollar check but with seven. If anyone could prove P = NP, then he would not go home with only a million dollar check, It's seven. -Lance Fortnow (2004)

A 2002 survey showed that 61% of computer scientists believe that "P! = NP", and ten years later, this proportion rose to 83% [Wil12]. I was convinced by Scott Aaronson's assertion:

Self-pointing argument: If P = NP is fact, then this proof will be easier to find; but if P! = NP, then this proof will be harder to find. So I believe that P! = NP seems to make the mathematical reality more consistent. -Scott Aaronson (2006)

Despite this reluctance, what would it look like if we really lived in a world without secrets? "Panopticon" is a thriller concept proposed by Jeremy Bentham, an English philosopher in the 18th century. The prisoners are monitored round-the-clock by the center, without any privacy at all, and they have no way of knowing whether they are being monitored. This extremely pessimistic statement is uncomfortable, but many people believe that it may be an accurate parable of the future digital age of the Internet more than 200 years ago.

From "Billy Budd", Kafka's "The Trial", Orwell's "1984", to the super-selling book "The Art of Invisibility" written by the famous hacker Kevin Mitnick (Teach you how to protect yourself in the era of big data Information), it seems that the crisis is pervading, the risks are constantly accumulating, and the imagination of the doomsday world has provided the authors with good materials …

Occasionally I accidentally saw an interesting comic "The Private Eye", which describes a postmodern scene of the rest of the world: in the future, all our information and data will be stored on the cloud, and then suddenly one day, this data cloud "Explosion", I don't know what the reason is (maybe someone accidentally opened Pandora's box and found the structural proof of P == NP), anyway, all the information, including everyone's darkest past, are not Become a secret again; all digital assets are erased and all online knowledge bases are permanently lost; everyone's words and deeds, bills, emails, chat messages, bank card passwords, middle school exam papers, GPS location information, and half of the diary , Deleted photos, Internet records, these information will be exposed to colleagues, neighbors, friends, loved ones, and even any curious person.

Everyone has no place for self-satisfaction, and they ca n’t stay there all day long. Then gradually, everyone chooses to hide themselves. People must wear masks when they go out to protect their identities carefully. Even one person can choose to use multiple identities. National law requires any voyeur All actions will be severely punished, access to information becomes an at least supreme power, cameras need to be strictly controlled, the Internet no longer exists, and people's communications are back in the phone booth era …

Is this the ultimate fate of humanity?

To be continued

As mentioned at the beginning of this article, "hidden randomness" is not necessary. Let's think about the Hidden Bits model. These Hidden Bits are not hidden from Prover, but open to let Prover know, but because Hidden Bits is a "consistent random distribution" string, even if Prover is known, he still cannot escape the firepower of random challenge. However, in the popular zkSNARK scheme, the CRS of "consistent random distribution" is not used, but a set of structured random numbers. Regardless, the secret to using CRS to build the "foundation of trust" is the "secret" hidden in it.

This is intuitive, and keeping a "secret" is also a form of trust. Because Alice does not know the secret backdoor hidden in the CRS, she cannot cheat. Similarly, Bob does not know the secrets in the CRS, and therefore cannot obtain "knowledge". Similarly, collaboration between people must be based on transparency and confidentiality.

All human beings have three lives: public, private, and secret. All human beings have three lives: public, private, and secret. ——Gabriel García Márqueel

Acknowledgements: Thanks to Chen Yu, Ding Shengchao, Zhang Yupeng, Hu Honggang, Liu Weiran, He Debiao, Wan Zhiguo and other teachers for their professional suggestions and corrections. Thanks to the friends of Abe Lab (p0n1, even, valuka, Vawheter, yghu, mr) for their suggestions . The content of this article does not represent their views.

Finally, I attached a link to the comic book: http://panelsyndicate.com/comics/tpeye The author even put out the mail and sketch of the creative process, everyone can experience the thrill of peeking at the production process.

references

• [Aar06] Aaronson, Scott. Reasons to believe , 2006. https://www.scottaaronson.com/blog/?p=122
• [BFM88] Blum, Manuel, Paul Feldman, and Silvio Micali. "Non-interactive zero-knowledge and its applications." STOC'88. 1988.
• [BG90] Bellare, Mihir, and Shafi Goldwasser. "New paradigms for digital signatures and message authentication based on non-interactive zero knowledge proofs." Conference on the Theory and Application of Cryptology . Springer, New York, NY, 1989.
• [BGN05] Boneh, Dan, Eu-Jin Goh, and Kobbi Nissim. "Evaluating 2-DNF formulas on ciphertexts." Theory of Cryptography Conference . Springer, Berlin, Heidelberg, 2005.
• [BGRV09] Brakerski, Zvika, Shafi Goldwasser, Guy N. Rothblum, and Vinod Vaikuntanathan. "Weak verifiable random functions." In Theory of Cryptography Conference , pp. 558-576. Springer, Berlin, Heidelberg, 2009.
• [BY96] Bellare, Mihir, and Moti Yung. "Certifying permutations: Noninteractive zero-knowledge based on any trapdoor permutation." Journal of Cryptology 9.3 (1996): 149-166.
• [CHK03] Canetti, Ran, Shai Halevi, and Jonathan Katz. "A forward-secure public-key encryption scheme." International Conference on the Theory and Applications of Cryptographic Techniques . Springer, Berlin, Heidelberg, 2003.
• [CHMMVW19] Chiesa, Alessandro, et al. Marlin: Preprocessing zksnarks with universal and updatable srs . Cryptology ePrint Archive, Report 2019/1047, 2019, https://eprint.iacr.org/2019/1047 , 2019.
• [DN00] Dwork, Cynthia, and Moni Naor. "Zaps and their applications." Proceedings 41st Annual Symposium on Foundations of Computer Science . IEEE, 2000.
• [FLS90] Feige, Uriel, Dror Lapidot, and Adi Shamir. "Multiple non-interactive zero knowledge proofs based on a single random string." Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science . IEEE, 1990.
• [For04] Fortnow, Lance. "What if P = NP?". 2004. https://blog.computationalcomplexity.org/2004/05/what-if-p-np.html
• [For09] Fortnow, Lance. "The status of the P versus NP problem." Communications of the ACM 52.9 (2009): 78-86.
• [Groth10a] Groth, Jens. "Short non-interactive zero-knowledge proofs." International Conference on the Theory and Application of Cryptology and Information Security . Springer, Berlin, Heidelberg, 2010.
• [Groth10b] Groth, Jens. "Short pairing-based non-interactive zero-knowledge arguments." International Conference on the Theory and Application of Cryptology and Information Security . Springer, Berlin, Heidelberg, 2010.
• [GOS06] Groth, Jens, Rafail Ostrovsky, and Amit Sahai. "Perfect non-interactive zero knowledge for NP." Annual International Conference on the Theory and Applications of Cryptographic Techniques . Springer, Berlin, Heidelberg, 2006.
• [GWC19] Gabizon, Ariel, Zachary J. Williamson, and Oana Ciobotaru. PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge . Cryptology ePrint Archive, Report 2019/953, 2019.
• [KP98] Kilian, Joe, and Erez Petrank. "An efficient noninteractive zero-knowledge proof system for NP with general assumptions." Journal of Cryptology 11.1 (1998): 1-27.
• [MBK + 19] Maller, Mary, et al. "Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updateable Structured Reference Strings." IACR Cryptology ePrint Archive 2019 (2019): 99.
• [RL18] Ran Canetti and Amit Lichtenberg. "Certifying trapdoor permutations, revisited." Theory of Cryptography Conference . Springer, Cham, 2018.
• [Wil12] Gasarch, William I. "Guest Column: The Third P =? NP Poll." ACM SIGACT News 50.1 (2019): 38-59.
• [Yao82] Yao, Andrew C. "Theory and application of trapdoor functions." 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982) . IEEE, 1982.

We will continue to update Blocking; if you have any questions or suggestions, please contact us!