After these years of development, various improvements and functions have been realized on the original Schnorr mechanism, and high-performance digital signatures and complex signature mechanisms including ring signatures and threshold signatures have been realized.
Referring to Schnorr's papers and other references, the original mechanism and implementation of Schnorr mechanism are analyzed. The mainstream implementation of EdDSA ED255 19 and how to establish a complex signature mechanism based on Schnorr mechanism are also analyzed.
The original Schnorr mechanism is an interactive mechanism. It is allowed to prove that one party owns the private key without exchanging the private key directly between any protocol participants with the same generator (in the discrete logarithm problem). The generator owned by both parties is set to, and the prover owns the private key. The verifier obtains the public key from the prover.
The protocol flow of the original Schnorr signature is as follows:
Because the discrete logarithm problem is difficult, the verifier will not know the value, but only the calculated value. But the verifier can verify whether it is correct by the following calculation:
The generator is known to both parties and the verifier, so the verifier can easily verify the simplified formula.
This process is zero-knowledge, because the verifier can't get the value of the private key, but it can be verified by calculation and communication that the verifier does have the private key.
However, such an interactive process will lead the verifier to obtain the private key through "fork". The verifier can simply provide two different random values and ask the prover to calculate them. In this way, this process cannot be verified publicly, because once two verifiers collude with each other and exchange their own values, the private key can be deduced.
In order to solve this problem, Fiat-Shamir will transform the existing protocol and use random Oracle to transform this algorithm, so that the original Schnorr scheme will become a publicly verifiable non-interactive algorithm.
The problem of private key disclosure in the original Schnorr scheme mentioned above makes the algorithm unable to be used in an open environment. This problem can be solved by changing the original interactive protocol into a non-interactive protocol.
Fiat-Shamir transform is a method to generate digital signature by using interactive zero-knowledge proof scheme. According to Fiat-Shamir transform, we can replace the prover in the original scheme with a random oracle and construct a digital signature.
Random number predictor, that is, random number function, is a function that the output obtained from any input is uniformly distributed with the independent tangents of the terms. The ideal random number predictor does not exist. In implementation, cryptographic hash function is usually used as a random number predictor.
In the original design, Schnorr signature is an interactive protocol, which needs an actual verifier and participant. According to Fiat-Shamir transform, a specific verifier can be replaced by a random number predictor. After replacing the verifier with a random number predictor, the external verifier cannot derive the private key through exchange, and it is represented by the original random number generated by the random number predictor.