This article comes fromThis article comes fromAmbi Laboratory (ID: SECBIT)
, author Guo Yu, reproduced by Odaily with authorization.
https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/4/zkp-rom.md
This article has been updated to Github
"Challenges are at times an indication of Lord's trust in you." Challenges are sometimes an indication of God's trust in you. ― D. Todd Christofferson
Series 1: Getting to Know "Zero Knowledge" and "Proof"
Series 2: Understanding "Simulation"
Series Three: Searching for "Knowledge"
Interaction and Challenge
The zero-knowledge proof systems we introduced before are all "interactive", requiring the verifier Bob to provide one or several "random numbers" to challenge during the interaction, such as the "map three-coloring problem" (see "Series 2") , the verifier Bob needs to "constantly" randomly select a side to challenge Alice's answer until Bob is satisfied, and Alice's cheating probability will decay "exponentially". And the "basis" for Bob to believe in the proof depends on whether the random number chosen by Bob is random enough. If Alice can predict Bob's random number in advance, disaster will happen, the real world will degenerate into an "ideal world", and Alice can immediately upgrade to a "simulator" to fool Bob through superpowers.
In "Series 3", we analyzed the Schnorr protocol. In the protocol, although the verifier Bob only needs to pick a random number c to challenge Alice and ask her to calculate a value z, Bob must not let Alice have the ability to predict the value of c. Any knowledge, otherwise, Alice will also transform into a simulator.
The importance of random numbers is self-evident:
Random number challenges are the "root of trust" for interactive zero-knowledge proofs.
However, the "interaction process" will limit the application scenarios. What if interactive zero-knowledge proofs could be turned into "non-interactive"? It's going to be very, very exciting. The so-called non-interactive can be regarded as a "one-round" proof process, that is, Alice directly sends a proof to Bob for verification.
Non-interactive zero-knowledge proof, English is Non-Interactive Zero Knowledge, NIZK for short. It means that the entire proof is encoded into a "string", which can be written on a piece of paper and sent to any verifier at will through various methods such as emails and chat tools. The string can even be placed on Github for everyone to download at any time verify.
In the blockchain world, "NIZK" can be used as part of the consensus protocol. Because a transaction requires multiple miners to verify. Imagine, if the sender of the transaction and each miner have to interact and let the miners challenge, then the consensus process will be extremely slow. Non-interactive zero-knowledge proofs can be directly broadcast to all miner nodes, allowing them to verify themselves.
Some friends may ask: Isn’t it enough for only one miner to challenge? Encode the interaction script between the miner and the transaction sender into a proof, and then broadcast it to other miners, and then other miners will directly believe that the challenge process is credible, isn’t it possible? However, it is clear that the first interactive miner needs to be trusted as a trusted third party, third party? Doesn't seem like a good idea...
Rather than an interactive zero-knowledge proof, we will directly say "NIZK" below, which seems ideal, and there is no third party to make the difference.
The confusion caused by "non-interactive"
Non-interactive zero-knowledge proofs, NIZK, if they exist, are much more powerful than interactive proofs.
Interactive proof can only be trusted by one verifier; while NIZK can be trusted by multiple verifiers, even everyone.
Interactive proof can only be valid at the moment of interaction; while NIZK will always be valid.
NIZK can not only span space, but also time
Sounds beautiful, doesn't it? But,……
Repeat a conclusion from the previous section:
Random number challenges are the "root of trust" for interactive zero-knowledge proofs.
But if NIZK loses the challenge process, what are the consequences?
We have already recalled the "zero-knowledge" proof (refer to "Series 2"). The proof process needs to construct a simulator (algorithm), which also interacts with the verifier (Bob) in an ideal world, and the verifier Bob does not Ability to distinguish whether the other party is real Alice or a simulator.
If you now consider the non-interactive in NIZK, if "I" shows "you" a piece of paper with a "true" proof X written on it, and if "you" really believes me after reading this paper ; and because the protocol is "zero-knowledge", then if "I" is replaced by a simulator, the simulator can also "forge" a false proof Y, which can also convince "you".
Ok, here comes the problem:
How do you distinguish between X and Y, which is true and which is false? Of course you can't tell the difference, since the protocol is zero-knowledge, you must not be able to tell the difference
I can show you Y in the same way. Doesn't that mean "I" can deceive you?
Is it discordant? Please think for two minutes here.
(two minutes later...)
Because NIZK has no interaction, there is no challenge process. All the proof processes have Alice to calculate and write. In theory, Alice can write whatever she wants, and no one can stop her. For example, Alice wrote "ideal world" false proof of Y.
Presumably, friends who have a deep understanding of the simulator will find a key point here: the simulator must only construct Y in the "ideal world", that is to say, something as evil as Y can only exist in the "ideal world" and cannot reach The "real world" is a disaster for the world.
keep thinking...
There is also a deeper problem. Please recall the "map three-coloring problem". The core reason why the simulator cannot do evil in the "real world" is that he has the superpower of "rewinding time" in the ideal world. And in the "real world" there is no such black magic. The "non-existence" of the real world is the key.
Moreover, there is no interaction in NIZK, which leads to a serious consequence. The simulator has no way to use the superpower of "rewinding time", and of course it seems that it cannot distinguish the behavior of the prover in the two worlds.
In other words, if we face any NIZK system, it seems that the "simulator" is difficult to stand above the ground, it seems that it can only fall into the world and become an ordinary mortal. If, I said if, according to this inference, assuming that the simulator no longer has superpowers, it means that Alice and the simulator are no different, Alice can also become a simulator, and then continue to deduce, Alice can be in the "real world" If Bob is arbitrarily deceived in the process, then this proof system is no longer valuable, because it loses its "reliability". Conclusion: Any NIZK is not reliable.
There must be something wrong here...
In the process of analysis above, we mentioned the lack of interactive challenges. Indeed, if Bob does not participate in Alice's process of generating the proof, every bit contained in the proof is provided by Alice, and it seems that the "proof" itself does not have any "root" for Bob to trust. This doesn't seem to make sense "intuitively".
Does that mean that without Bob's participation, there is "completely" no way to establish a "root of trust"? Where else can the foundation of trust come from?
The answer is "third party"!
Wait..., isn't there only two parties in the protocol interaction? Alice and Bob, where is the third party?
A third party needs to be introduced in a special way, and there are more than one method. Let's study the first one first.
(Tears: Didn't you say it well, don't we introduce a third party?)
Review of the Schnorr protocol
Let’s take a look at our old friend—the Schnorr protocol, which is a three-step protocol: in the first step, Alice sends a promise, then in the second step Bob sends a random number challenge, and in the third step, Alice responds to the challenge.
Let's see how to turn a three-step Schnorr protocol into one step.
c = Hash(PK, R)
Look at the second step of the Schnorr protocol. Bob needs to give a random challenge number c. Here we can let Alice use the following formula to calculate the challenge number, so as to achieve the purpose of eliminating the second step of the protocol.
Where R is the elliptic curve point Alice sent to Bob, and PK is the public key. You can take a good look at this formula for calculating c using the Hash algorithm. This formula serves two purposes:
Before Alice generates commitment R, there is no way to predict c, even if c is finally chosen by Alice in disguise
c Calculated by the Hash function, it will be evenly distributed in an integer field, and can be used as a random number (Note: Please understand this for now, we will discuss it in depth later)
Please note: Alice can never predict c before generating R, otherwise, Alice has the superpower of "reverse time" in disguise, so that she can fool Bob arbitrarily.
And a cryptographically secure Hash function is "one-way", such as SHA256, SHA3, blake2 and so on. In this way, although c is calculated by Alice, Alice has no ability to cheat by picking c. Because as soon as Alice generates R, c is equivalent to being fixed. We assume that Alice, a mortal, does not have the ability to reverse calculate Hash in the "real world".
Looking at the picture above, we use the Hash function to combine the three-step Schnorr protocol into one step. Alice can send directly: (R, c, z). And because Bob has PK, Bob can calculate c by himself, so Alice can just send (R, z).
We slightly deformed the above scheme and obtained the "digital signature" scheme. The so-called digital signature means that "I" presents a string to "you", such as "The sun is at the end of the mountain, the Yellow River flows into the sea", and then in order to prove that this poem was presented by me, I need to sign something. This thing can prove that my identity is connected with this poem.
Digital Signature from NIZK's Perspective
Loosely speaking, a digital signature scheme is equivalent to proving (1) that I have the private key, and (2) that the private key and the message have been associated with the calculation.
I first have to prove my identity, so this is simple, this is the function of the Schnorr protocol, which can prove the statement "I have the private key" to the other party. And this proof process is zero-knowledge: no knowledge about the "private key" is revealed.
m = "So how does it relate to this Tang poem? We modify the process of calculating c:"
c = Hash(m, R)
The sun is at the end of the mountain, the Yellow River flows into the sea
Here, in order to ensure that the attacker cannot forge the signature at will, it is the assumption that the discrete logarithm problem (DLP) and the Hash function satisfy the secondary preimage resistance (Secondary Preimage Resistance).
Note: Strictly speaking, in order to ensure the unforgeability of digital signatures, it is necessary to prove that the Schnorr protocol satisfies the stronger property of "Simulation Soundness". For this, please refer to [2]
The above picture is the well-known digital signature scheme - Schnorr signature scheme [1]. There is another optimization here. What Alice sends to Bob is not (R, z) but (c, z), because R can be calculated through c, z.
Note: Why is this an "optimization"? Currently, there are Shanks algorithm, Lambda algorithm, and Pollard's rho algorithm for attacking elliptic curves. Please remember that their algorithm complexity is about [3], and n is the number of digits in the size of the finite field. Suppose we use a finite field that is very close to 2^256, that is to say, z is 256bit, then the size of the elliptic curve group is almost close to 256bit, so that the square root of 2^256 is 2^128, so The security of 256bit elliptic curve group is only 128bit. Then, only 128bit is enough for the challenge number c. In this way, it is more space-saving for Alice to send c than to send R, and the latter requires at least 256 bits. The two values of c and z add up to a total of 384 bits. Compared with the popular ECDSA signature scheme, it can save 1/4 of the precious space. Now the Bitcoin development team is ready to change the ECDSA signature scheme to a Schnorr-like signature scheme—muSig[4], which can support multi-signature and aggregation more flexibly.
The method of using the Hash function to change an interactive proof system into a non-interactive method is called Fiat-Shamir transformation [5], which was proposed in 1986 by Amos Fiat and Adi Shamir, the veterans of cryptography.
Rebuilding Trust - Random Prophecy Wizard
As mentioned earlier, without the challenge, it seems that the "trust foundation" of the proof has been lost. In the Schnorr signature scheme, the Hash function takes on the role of "challenger". This role has a very academic name: "Random Oracle" (Random Oracle) [6].
But why use Hash here? In fact, when Alice wants to generate public random numbers, she needs something called a "random oracle". What is it?
It's brainstorming time!
We imagine that in the "real world", there is an "elf" in the sky. He is holding a two-column form, the left column is a string, and the right column is a number. Anyone, including you and me, including Alice and Bob, can send strings to the "elf".
After the elf gets the string, it will check the left column of the table to see if there is such a string in the table. There are two situations as follows:
Situation 1: If the string cannot be found in the left column, the elf will generate a "true random number", then write the string and random number into the table, and then return the random number to the mortal on the ground.
Case 2: If there is this string record in the left column, the elf will directly return the number in the right column to the ground.
You will find that this sprite acts like a random number generator, but it is very different. The difference is that when we send the same string, it will return the same number. This elf is the legendary "random oracle".
In the process of merging the Schnorr protocol, what we actually need is such a random oracle wizard, not a Hash function. What's the difference between the two? The difference is:
The random oracle returns a "true" random number with a consistent distribution every time for a new string
The result calculated by the Hash function is not a truly random number with consistent distribution
So why is the Hash function used earlier? This is because in the real world, true random oracles don't exist! why? In fact, it is impossible for a Hash function to generate truly random numbers, because the Hash function is a "deterministic" algorithm, and no other random quantities are introduced except parameters.
And a Hash function with cryptographic security strength "seems" can act as a "pseudo" random oracle. Then the combined security protocol needs to add an additional strong security assumption, which is:
Hypothesis: A cryptographically secure Hash function can approximate the legendary "random oracle"
Because this assumption cannot be proven, we can only trust this assumption, or use it as an axiom. As an aside, the generalized anti-collision properties of the Hash function determine that its output can simulate random numbers. At the same time, in many cases (not all), it is very difficult to attack the Hash function, so many cryptographers are boldly using it.
A security model that does not use this assumption is called a "standard model", and a security model that uses this assumption cannot of course be called a "non-standard model". It has a nice term called "random oracle model".
There are two different types of people in the world, those who like sweet bean curd and those who don’t. Similarly, there are two types of cryptographers in the world, those who like the random oracle model, and those who don't like the random oracle model [6].
Structural Foundation - Kidnapped Elves
After the Schnorr protocol undergoes Fiat-Shamir transformation, it has the NIZK property. This is different from the SHVZK we have proved. SHVZK requires the verifier to be honest, while NIZK no longer has any unrealistic requirements on the verifier, because the verifier does not participate in the interaction, and the so-called problem of requiring an honest verifier no longer exists.
Note: What happens if the verifier Bob is dishonest? Then it is possible for Bob to extract Alice's knowledge. But for the three-step Schnorr protocol, whether it satisfies "zero knowledge" is still unknown. We only proved that it satisfies a relatively weak property in Series 3: SHVZK.
However, when the Schnorr protocol is transformed into a non-interactive zero-knowledge proof system, it becomes truly "zero-knowledge".
However, your question may also come. This assertion sounds reasonable. Can you prove it?
The time is up, "Cuihua, get on the simulator"
How to use the simulator method to construct an "ideal world"? You can think about it, we have used "back in time" before, and modified the superpower of "random number conveyor belt" to let the "simulator" cheat. But there is no interaction, which means: the super power of "back in time" cannot be used; Bob's random number conveyor belt does not exist, and the super power of "tampering the conveyor belt" cannot be used either!
But the simulator must always have some kind of "super power", so that it can build the "root" of trust
(If the simulator has the ability to cheat without superpowers, it is equivalent to proving the unreliability of the protocol).
Maybe everyone has guessed it by now, the simulator has to do something on the "random oracle".First consider constructing an "ideal world" to prove "zero knowledge". In an ideal world, the simulator "kidnapped" the "elf" responsible for providing the prophecy. When Bob asked the elf for a random number, the elf did not give a real random number, but gave it to Zlice (the simulator pretends to be Alice) A number prepared in advance (which also conforms to the consistent distribution and guarantees indistinguishability), the "genie" has no choice but to return Bob a number that looks random but actually has a backdoor.
The so-called back door means that this number is chosen by Zlice himself in advance.
Step 1: Zlice randomly selects z, randomly selects c, and calculates R'=z*G - c*PK.
Step 2: Zlice writes c and (m, R') into the sprite's table.
Step 3: Zlice sends the signature (c, z) to Bob.
Step 4: Bob calculates R=z*G - c*PK, and sends (m, R) to the elf, and the elf returns c'. Note that here Bob's calculated R and Zlice's calculated R' are equal.
Step 5: Bob verifies that c ?= c', to see if the random number returned by the elf is equal to the random number sent by the other party. If they are equal, the verification signature passes; otherwise, the verification fails.
By kidnapping the "elf", Zlice can also predict the random number in advance, which can achieve the same effect as going back in time.
We have proved the "existence" of the simulator Zlice, so we have proved NIZK above.
sk = (z1 - z2)/(c1 - c2)
Next, we prove the "reliability" of this protocol. Imagine that in another "ideal world", a thing called "extractor" also kidnapped elves. When innocent Alice asked the "elf" for a random number, the "elf" returned a c1, and the "extractor" peeked at c1 from the elf's table. After Alice calculated z1, then the "extractor" still You can activate the super power of "reverse time", let Alice go back to the second step, and ask the "elf" for a random number again, the string sent by Alice is obviously the same as the string sent for the first time, (R, m) . Logically, since (R, m) is already written in the "left column" of the sprite sheet, an honest "sprite" should return c1. However, the "extractor" kidnapped the sprite, and he changed the "right column" corresponding to the row (R, m) in the table to a different number c2. After Alice calculates another z2, the extractor completes the task and calculates Alice's private key sk through the following equation:
Fiat-Shamir transformation - from Public-Coin to NIZK
Not only for the Schnorr protocol, but for any "Public-Coin protocol", the Fiat-Shamir transformation can be used to "compress" the entire protocol into a one-step interaction, that is, a non-interactive proof system. This transformation technique first came from The paper "How to Prove Yourself: Practical Solutions to Identification and Signature Problems." by Amos Fiat and Adi Shamir was published at the Crypto Conference in 1986 [5]. It is also said that this technique comes from Manuel Blum[6].
To repeat, in the Public-coin protocol, the validator Bob only does one type of thing, which is to generate a random number and challenge Alice. Through the Fiat-Shamir transformation, each "challenging behavior" of Bob can be replaced by a "random prophecy".
In the specific implementation, the random oracle needs to use a hash function with cryptographic security strength (you cannot choose it randomly, you must use a cryptographically secure hash), and the parameters of the hash function should be all previous context inputs. The following is an example diagram, you can quickly understand the practice of this Fiat-Shamir transformation.
As mentioned earlier, in a non-interactive proof system, a third party needs to be introduced to build the "root" of trust, so that Bob can fully trust the proof constructed by Alice. Here, the third party is the "elf", which in academic slang is "Random Oracle". This elf is not a real third party, but a virtual third party, which exists in both the "real world" and the "ideal world". In the "real world", the elf is a responsible and quiet handsome man, but in the "ideal world", it will be kidnapped by the "simulator".
The Public-Coin protocol also has a nice name, "Arthur-Merlin Game"...
Look at the picture above, the "white robe" on the left is Merlin (the magician Merlin), and the handsome guy with the sword in the middle is King Arthur (King Arthur). The two characters come from the medieval European legend - King Arthur's Knights of the Round Table.
Arthur is an impatient king who carries a coin with him, and Merlin is a magical magician with unlimited computing power. To the dialogue, but because the king is lazy, he will only flip a coin at a time, and then "challenge" the magician, and the magician needs to respond in time, and needs to make the king believe in his own judgment after k rounds. Since Merlin has magic, every coin thrown by King Arthur can be seen by Merlin[7].this is with us in"Series One"
The Interactive Proof System (IP for short) mentioned in is somewhat similar, but different. IP was formally proposed by Goldwasser, Micali and Rackoff (GMR for short) in 1985, and its proving ability covers a large class of computational complexity problems. The difference is that in the definition of IP, both Prover and Verifier are Turing machines that can toss coins, and Verifier can secretly toss coins and hide them from Prover; while in the Arthur-Merlin game, the king can only A coin toss, not only that, but Merlin would always know the outcome of the coin toss.
However, the Fiat-Shamir transformation can only prove security under the "random oracle model", and whether the process of using the Hash function to realize the random oracle is safe is lack of security proof. Not only that, the secure protocol under the "random oracle model" may be insecure, and some counterexamples have been found [8]; more unfortunately, S. Goldwasser and Y. Tauman proved in 2003 that the Fiat-Shamir transformation There are security counterexamples in itself [9]. But this does not mean that the Fiat-Shamir transformation cannot be used, but it must be very careful during use and cannot be applied blindly.
Still, one cannot resist the temptation of the Fiat-Shamir transformation, which is extremely widely used. It is worth mentioning that Fiat-Shamir transformations abound in various schemes of the hottest general-purpose non-interactive zero-knowledge proof zkSNARK. For example, you may be familiar with Bulletproofs (bullet proof), and there are some general-purpose zero-knowledge proof schemes that are not so well-known for the time being, such as Hyrax, Ligero, Supersonic, Libra, etc. (we will follow up and explain them one by one).
Caution: Security Implications in Fiat-Shamir Transformations
In the Fiat-Shamir transformation, pay special attention to the parameters fed to the Hash function. In the actual code implementation, there are such cases where some parameters of the Hash function are omitted:
For example, in A, Hash(A), B, Hash(B), the second Hash function misses the parameter A, and the correct way should be A, Hash(A), B, Hash(A,B). This type of approach will introduce serious security loopholes. For example, in the Swiss electronic voting system SwissPost-Scytl, the implementation code of the Fiat-Shamir transformation has repeatedly missed the parameters that should exist, causing the attacker not only Ballots can be invalidated at will, and ballots can be forged at will to achieve the purpose of fraud [10]. Therefore, in engineering implementation, please pay attention.
Careful readers may look back at the Schnorr signature, and you will find that the Hash algorithm in the Schnorr signature seems to have missed a parameter PK, which is not a strict Fiat-Shamir transformation, which is called Weak Fiat-Shamir transformation [11]. However, there is no security problem in this special case [3], please do not imitate minors at will.
Recently, some scholars have begun to study how to strictly prove the security of Fiat-Shamir transformation under the standard model. At present, they either introduce additional strong security assumptions or prove it for a specific protocol, but it seems that there is not much progress.
The power of interaction
It is said that in 1985, when the thesis of the GMR trio was accepted by STOC'85 after many rejections, another similar work was also accepted by STOC'85 at the same time. This is László Babai from the University of Roland, Hungary, and The paper "Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes" written by Shlomo Moran from the Israel Institute of Technology [7] introduced the Public-coin interactive protocol (as the name suggests, Verifier only publicly flips coins) .
King Arthur's method is very simple. Merlin's assertion is tested by repeated "random" challenges, which is in line with the intuition we described earlier: use random challenges to build the "root" of trust. Babai proved an interesting conclusion in the paper: AM[k]=AM[2], where k represents the number of interactions, and the effect of multiple interactions is equivalent to two interactions. The so-called interaction twice means: Arthur sends a challenge number, and then Merlin responds.
Note: There is another type of problem that belongs to MA. The interactive order of this type of problem is different from that of AM. In MA, Merlin first gives the proof, and then Arthur flips a coin for inspection. It has been proved that the problems that MA can handle are a subset of AM.
Not only that, Babai also boldly guessed: AM[poly] is equivalent to IP. This is a magical assertion: the king is lazy, he only needs to flip a polynomial coin to successfully challenge the magician, and the expressive power of this method is completely equivalent to the interactive proof system IP described by GMR. Sure enough, at the STOC'86 conference, a paper from S. Goldwasser and M. Sipser proved this, AM[poly] == IP[12].
This means: the repeated public "random challenge" is infinitely powerful, and it is equivalent to any interactive proof system. However, the relationship between AM[poly] and other computational complexity classes is the next research hotspot.
AM[poly] == IP == PSPACE
Three years later, at the end of November 1989, exactly 30 years ago, the young cryptographer Noam Nisan sent an email, sending his provisional academic conclusions to several cryptographers, and then he ran to the South America is on vacation. But he never thought that this email would detonate a fierce academic competition in history, with a large group of M. Blum, S. Kannan, D. Lipton, D. Beaver, J. Feigenbaum, H. Karloff, C. Lund, etc. The elite began to join the battle. They discussed with each other day and night, and competed to publish their own research results. Finally, on December 26, exactly one month, Adi Shamir proved the following conclusions:
It explains the computational theoretical characteristics of the concept of "effective proof", and explains the computing power covered by the concept of "interactive proof system".
Note: The NP class is a subset of the PSPACE class. The former is more familiar to everyone, and the latter is related to winning strategies in games or chess [13].
And L. Babai then wrote an article called "Email and the unexpected power of interaction" (Email and the unexpected power of interaction) [14], which elaborated on this whole month in "Email interaction" ", and the ins and outs of "interactive proof".
Public reference string - another "root of trust"
Yes, you read that right, there is a "third party" here again! Although the third party does not directly participate in the proof, he must ensure the credibility of the random string generation process. The process of generating CRS is also called "Trusted Setup", which is something that everyone loves and hates. Obviously, bringing in a third party in a real-world scenario can be a headache. What exactly is CRS used for? Where does Trusted Setup's trust go from here? This part will be reserved for the next article in this series.
to be continued
to be continued
Non-interactive zero-knowledge proves that the "root of trust" of NIZK also requires some form of random "challenge". One form of "challenge" is handed over to the "random prophecy elf"; Shared random string to achieve. Both forms of challenge essentially introduce a third party, and both must provide a "back door" that can be exploited by the "simulator", so that the simulator has some "advantage" in the "ideal world", and this This advantage must fail in the "real world".
NIZK exudes infinite charm, which makes me amazed from time to time. In the past thirty years, the pioneers have explored the subtle conclusions, and at the same time there are so many unknown corners, waiting for the light of inspiration.This series of articles is on Githubproject repository
Received the first Pull Request from Jingyu Hu (colortigerhu), only changed a few words, but at that moment, I felt the vitality. The exchange of knowledge, the collision of ideas, is fascinating, isn't it?
"Everyone we interact with becomes a part of us." Everyone we interact with becomes a part of us. ―Jodi Aman
text
references
[1] Schnorr, Claus-Peter. "Efficient signature generation by smart cards." Journal of cryptology 4.3 (1991): 161-174.
[2] Paillier, Pascal, and Damien Vergnaud. "Discrete-log-based signatures may not be equivalent to discrete log." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2005.
[3] Pointcheval, David, and Jacques Stern. "Security arguments for digital signatures and blind signatures." Journal of cryptology 13.3 (2000): 361-396.
[4] Maxwell, Gregory, Andrew Poelstra, Yannick Seurin, and Pieter Wuille. "Simple schnorr multi-signatures with applications to bitcoin." Designs, Codes and Cryptography 87, no. 9 (2019): 2139-2164.
[5] Fiat, Amos, and Adi Shamir. "How to prove yourself: Practical solutions to identification and signature problems." Conference on the Theory and Application of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1986.
[6] Bellare, Mihir, and Phillip Rogaway. "Random Oracles Are Practical: a Paradigm for Designing Efficient Protocols." Proc. of the 1st CCS (1995): 62-73.
[7] László Babai, and Shlomo Moran. "Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes." Journal of Computer and System Sciences 36.2 (1988): 254-276.m
[8] Canetti, Ran, Oded Goldreich, and Shai Halevi. "The random oracle methodology, revisited." Journal of the ACM (JACM)51.4 (2004): 557-594.
[9] Shafi Goldwasser, and Yael Tauman . "On the (in) security of the Fiat-Shamir paradigm." 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.. IEEE, 2003.
[10]Lewis, Sarah Jamie, Olivier Pereira, and Vanessa Teague. "Addendum to how not to prove your election outcome: The use of nonadaptive zero knowledge proofs in the ScytlSwissPost Internet voting system, and its implica tions for castasintended verifi cation." Univ. Melbourne, Parkville, Australia (2019).
[11] Bernhard, David, Olivier Pereira, and Bogdan Warinschi. "How not to prove yourself: Pitfalls of the fiat-shamir heuristic and applications to helios." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2012.
[12] Goldwasser, Shafi, and Michael Sipser. "Private coins versus public coins in interactive proof systems." Proceedings of the eighteenth annual ACM symposium on Theory of computing. ACM, 1986.
[13] Papadimitriou, Christos H. "Games against nature." Journal of Computer and System Sciences 31.2 (1985): 288-301.
[14] Babai, László. "E-mail and the unexpected power of interaction." Proceedings Fifth Annual Structure in Complexity Theory Conference. IEEE, 1990.
[15] Yi Deng. "references" https://zhuanlan.zhihu.com/p/29491567
