Schnorr signature

The Schnorr signature is a cryptographic scheme for digital signatures designed in 1989/1991 by the German mathematics professor Claus-Peter Schnorr . It is derived from the Schnorr identification in that, as with the Fiat Shamir identification, the interaction is replaced by the use of a cryptographic hash function . The security relies on the complexity of the discrete logarithm in finite groups.

The process is patented by Schnorr , but the term of protection has now expired. It is licensed exclusively to RSA (Siemens has a non-exclusive license). As part of the IEEE P1363 standardization, Schnorr accused NIST of infringing its patent with the Digital Signature Algorithm (DSA) it had developed .

parameter

System-wide parameters

All users can share these parameters:

• A group of prime order . This is cyclical, be a generator ${\displaystyle G}$ ${\displaystyle q=|G|}$ ${\displaystyle g}$
• A cryptographic hash function with a range of values . ${\displaystyle H}$ ${\displaystyle [0,q-1]}$

Schnorr suggests choosing a subgroup of for a primes . He argues that key and signature lengths refer to, while the security level is oriented towards the larger . ${\displaystyle G}$ ${\displaystyle Z_{p}^{*}}$ ${\displaystyle p}$ ${\displaystyle |G|}$ ${\displaystyle |Z_{p}^{*}|}$

Private key

The private key consists of a randomly chosen number:

• ${\displaystyle x}$ With ${\displaystyle 0<x<q}$

Public key

The public key is the corresponding group element : ${\displaystyle x}$ ${\displaystyle y}$

• ${\displaystyle y=g^{x}}$

Sign

To sign a message , do the following: ${\displaystyle m}$

1. Randomly choose with . ${\displaystyle k}$ ${\displaystyle 0<k<q}$
2. Set ${\displaystyle r:=g^{k}}$
3. Set . Here is the concatenation . ${\displaystyle e:=H(r||m)}$ ${\displaystyle ||}$
4. Set . ${\displaystyle s:=(k+xe){\bmod {q}}}$

The signature of the message is the tuple or . ${\displaystyle (e,s)}$ ${\displaystyle (r,s)}$

Formulated for elliptical curves

We consider an elliptic curve over GF (p). The generator G is a point on the curve and let it be . ${\displaystyle Y=x\cdot G}$

1. Randomly choose with . ${\displaystyle k}$ ${\displaystyle 0<k<p}$
2. Set ${\displaystyle R:=k\cdot G}$
3. Set . Here is the concatenation and the coordinate of the point . ${\displaystyle e:=H(R_{x}||m)}$ ${\displaystyle ||}$ ${\displaystyle R_{x}}$ ${\displaystyle x}$ ${\displaystyle R}$
4. Set . If the bit length of is greater than the bit length of , the excess (right) bits of are deleted before the calculation of . ${\displaystyle s:=(k+xe){\bmod {q}}}$ ${\displaystyle e}$ ${\displaystyle q}$ ${\displaystyle s}$ ${\displaystyle e}$

The signature of the message is the tuple or . ${\displaystyle m}$ ${\displaystyle (e,s)}$ ${\displaystyle (R,s)}$

To verify

To verify a signature of a message , the following procedure is used: ${\displaystyle (e,s)}$ ${\displaystyle m}$

1. Set ${\displaystyle r_{v}:=g^{s}\cdot y^{-e}}$
2. Set ${\displaystyle e_{v}:=H(r_{v}||m)}$
3. Accept the signature if and only if is. ${\displaystyle e_{v}=e}$

If the signature is in the format it can be verified as follows: ${\displaystyle (r,s)}$

${\displaystyle g^{s}=r\cdot y^{-H(r||m)}}$

With an elliptical curve

1. Calculate ${\displaystyle R=(s\cdot G)-(e\cdot Y)}$
2. Set ${\displaystyle e_{v}:=H(R_{x}||m)}$
3. Accept the signature if and only if is. ${\displaystyle e_{v}=e}$

If the signature is in the format it can be verified as follows: ${\displaystyle (R,s)}$

${\displaystyle s\cdot G=R+H((R_{x}||m)\cdot Y}$

Multi signature

With Schnorr signatures it is possible to sign a message with several keys in one signature.

One party signatures

1. The signer has several private keys , which means that several public keys also exist ${\displaystyle x_{i}}$ ${\displaystyle y_{i}}$
2. The signer charges ${\displaystyle s:=(k+x_{1}\cdot e+x_{2}\cdot e+x_{3}\cdot e+\dotsb )}$
3. When verifying is ${\displaystyle r_{v}:=g^{s}\cdot y_{1}^{-e}\cdot y_{2}^{-e}\cdot y_{3}^{-e}\cdot \ldots }$

Batch verification

When signed with , it is possible to calculate signatures and public keys together. ${\displaystyle (r,s)}$

${\displaystyle s:=s_{1}+s_{2}+s_{3}+\dotsb }$

${\displaystyle r:=r_{1}\cdot r_{2}\cdot r_{3}\cdot \dotsb }$

${\displaystyle y:=y_{1}\cdot y_{2}\cdot y_{3}\cdot \dotsb }$

This can be used to verify multiple signatures at the same time. This could be used in the Bitcoin blockchain so that not all nodes have to validate all transactions.

Rogue key attack

You should not trust it as a signature, as it is not clear whether it is the sum of the public keys or just the public key of a party. ${\displaystyle y}$

Bellare-Neven procedure

One solution is for each party to co-sign the hash of all public keys.

1. ${\displaystyle L:=H(y_{1}||y_{2}||y_{3}||\dotsb )}$
2. ${\displaystyle r}$ remains the product of the individual noncenes: ${\displaystyle r:=r_{1}\cdot r_{2}\cdot r_{3}\cdot \dotsb }$
3. ${\displaystyle s_{i}}$ is a partial signature that everyone calculates for himself ${\displaystyle s_{i}:=k_{i}+x\cdot H(L,y_{i},r,m)}$
4. which are then added together: ${\displaystyle s:=s_{1}+s_{2}+s_{3}+\dotsb }$

With one can verify it. ${\displaystyle g^{s}=r\cdot y_{1}^{-H(L,y_{1},r,m)}\cdot y_{2}^{-H(L,y_{2},r,m)}\cdot y_{3}^{-H(L,y_{3},r,m)}\cdot \dotsb }$

Idle

1. ${\displaystyle L:=H(y_{1}||y_{2}||y_{3}||\dotsb )}$
2. ${\displaystyle a_{i}:=H(L||y_{i})}$
3. ${\displaystyle y:=y_{1}^{a_{1}}\cdot y_{2}^{a_{2}}\cdot y_{3}^{a_{3}}\cdot \dotsb }$ so that: ${\displaystyle y:=g^{x_{1}+a_{1}+x_{2}+a_{2}+x_{3}+a_{3}+\dotsb }}$
4. ${\displaystyle r:=r_{1}\cdot r_{2}\cdot r_{3}\cdot \dotsb }$so: You should only share with the other parties when you have received a commitment to theirs . ${\displaystyle r:=g^{k_{1}+k_{2}+k_{3}+\dotsb }}$ ${\displaystyle r_{i}}$ ${\displaystyle r_{i}}$
5. ${\displaystyle c:=H(y||r||m)}$
6. ${\displaystyle s_{i}:=r_{i}+ca_{i}x_{i}}$
7. ${\displaystyle s:=s_{1}+s_{2}+s_{3}+\dotsb }$

This procedure has the advantage that only the parties involved need to know the individual public keys. An outsider can use the combined public key to confirm that it is a valid signature. Especially in blockchain applications, where privacy is valuable and storage space is scarce, the Schnorr process, using the Bitcoin blockchain as an example, could save up to 25% storage space.

Security discussion (informal)

The value xe and thus also the value x are securely encrypted by the random number k ( one-time pad ). Security is therefore subject to certain conditions on the used random numbers ( k ) and the hash function ( random oracle model ) to the complexity of discrete logarithms in the used group proved to reduce, ie who can calculate the Schnorr signature scheme, can also compute the discrete logarithm. There is no known method with which the discrete logarithm in multiplicative groups of finite fields can be calculated efficiently with today's computers. This demonstrable reduction to known problems classified as difficult is typical for security proofs in cryptographic systems with public keys.

In the Random Oracle model, it is assumed that the hash function behaves like a random function and an attacker can only calculate the function values ​​using an oracle for the function values. With the help of a contradiction proof , you can now show the correctness of the procedure. Assume that there is a successful forger for the signature process. This can be used to determine the secret key from the public key , i.e. to calculate the discrete logarithm of - contrary to the assumption that the discrete logarithm is difficult. ${\displaystyle y=g^{x}}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle y}$

1. Simulate the algorithm for signing a message , save the state when calling the oracle to calculate. ${\displaystyle m}$ ${\displaystyle e_{1}=H(m||r)}$
2. Repeat the simulation on the saved state, but return a different one (this works in the Random Oracle model) ${\displaystyle e_{2}=H(m||r)}$
3. Be and the two (different) signatures the same message and the same random value or ${\displaystyle s_{1}}$ ${\displaystyle s_{2}}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle r}$
4. It is so ${\displaystyle s_{1}-s_{2}=(k+xe_{1})-(k+xe_{2})=x(e_{1}-e_{2})\mod q}$ ${\displaystyle x=(s_{1}-s_{2})/(e_{1}-e_{2})\mod q}$

Division by is possible: Since is prime, there is also an inverse modulo for every number not equal to 0 . ${\displaystyle e_{1}-e_{2}}$ ${\displaystyle q}$ ${\displaystyle q}$

Requirement for the random numbers

From the above explanation it follows that the random numbers k that are used to calculate the signature must not be repeated under any circumstances. If a random number were used to sign two different messages, the private key x could be calculated from publicly known values. This could then be used to forge signatures by an attacker. Furthermore, the random numbers must not be calculable for the attacker, otherwise he could calculate x .

literature

• Claus-Peter Schnorr : Efficient Signature Generation by Smart Cards Journal of Cryptology, Vol.4, pp.161-174, 1991.
• Bruce Schneier : Applied Cryptography . Addison-Wesley 1996, p. 583, ISBN 3-89319-854-7 .

Web links

• Claus-Peter Schnorr, Lecture Cryptography I / II, Chapter 1.7 , online (PDF, 454 kB)

Individual evidence

1. ↑ Patent EP0384475 : Applied on February 22, 1990 . ‌
2. ↑ Patent US4995082 : Applied February 23, 1990 . ‌
3. ↑ IEEE P1363 Patent Reply from Prof. Dr. Claus Peter Schnorr. (No longer available online.) Archived from the original on October 13, 2016 ; accessed on January 25, 2018 . Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.  
4. ↑ Github: BIP-340 . Retrieved March 15, 2020.
5. ↑ UCSD: Paper . Retrieved March 15, 2020.
6. ↑ Sam Wouters: Why Schnorr signatures will help solve 2 of Bitcoin's biggest problems today , July 4, 2017. Retrieved December 30, 2017.
7. ↑ Blockstream: Schnorr Multisig . Retrieved March 15, 2020.
8. ↑ IARC: Multi-Signatures with Applications to Bitcoin . Retrieved March 15, 2020.
9. ↑ David Pointcheval and Jacques Stern: Security arguments for digital signatures and blind signatures. Journal of Cryptology, 13 (3), pp. 361-396, 2000.