#jsDisabledContent { display:none; } My Account | Register | Help

# Schnorr signature

Article Id: WHEBN0000450536
Reproduction Date:

 Title: Schnorr signature Author: World Heritage Encyclopedia Language: English Subject: Collection: Digital Signature Schemes Publisher: World Heritage Encyclopedia Publication Date:

### Schnorr signature

In cryptography, a Schnorr signature is a digital signature produced by the Schnorr signature algorithm. Its security is based on the intractability of certain discrete logarithm problems. The Schnorr signature is considered the simplest[1] digital signature scheme to be provably secure in a random oracle model.[2] It is efficient and generates short signatures. It is covered by U.S. Patent 4,995,082, which expired in February 2008.

## Contents

• Algorithm 1
• Choosing parameters 1.1
• Notation 1.2
• Key generation 1.3
• Signing 1.4
• Verifying 1.5
• Proof of correctness 1.6
• Security argument 1.7
• References 3

## Algorithm

### Notation

In the following,

• Exponentiation stands for repeated application of the group operation
• Juxtaposition stands for multiplication on the set of congruence classes or application of the group operation (as applicable)
• Subtraction stands for subtraction on set of equivalence groups
• M \in \{0,1\}^*, the set of finite bit strings
• s, e, e_v \in \mathbb{Z}_q, the set of congruence classes modulo q
• x, k \in \mathbb{Z}_q^\times, the multiplicative group of integers modulo q (for prime q, \mathbb{Z}_q^\times = \mathbb{Z}_q \setminus \overline{0}_q)
• y, r, r_v \in G.

### Key generation

• Choose a private signing key x from the allowed set.
• The public verification key is y = g^x.

### Signing

To sign a message M:

• Choose a random k from the allowed set.
• Let r = g^k.
• Let e = H(M \| r), where \| denotes concatenation and r is represented as a bit string.
• Let s = (k - xe).

The signature is the pair (s,e).

Note that s, e \in \mathbb{Z}_q; if q < 2^{160}, then the signature representation can fit into 40 bytes.

### Verifying

• Let r_v = g^s y^e
• Let e_v = H(M \| r_v)

If e_v=e then the signature is verified.

### Proof of correctness

It is relatively easy to see that e_v = e if the signed message equals the verified message:

r_v = g^s y^e = g^{k - xe} g^{xe} = g^k = r, and hence e_v = H(M \| r_v) = H(M \| r) = e.

Public elements: G, g, q, y, s, e, r. Private elements: k, x.

### Security argument

The signature scheme was constructed by applying the Fiat–Shamir transform[3] to Schnorr's identification protocol.[4] Therefore (per Fiat and Shamir's arguments), it is secure if H is modeled as a random oracle.

Its security can also be argued in the generic group model, under the assumption that H is "random-prefix preimage resistant" and "random-prefix second-preimage resistant".[5] In particular, H does not need to be collision resistant.

In 2012, Seurin[2] provided an exact proof of the Schnorr signature scheme. In particular, Seurin shows that the security proof using the

• Schnorr IETF draft