In cryptography

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, a Schnorr signature is a digital signature

Digital signature

A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, and that it was not altered in transit...

 produced by the Schnorr signature algorithm. Its security is based on the intractability of certain discrete logarithm

Discrete logarithm

In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...

 problems. It is considered the simplest digital signature scheme to be provably secure in a random oracle

Random oracle

In cryptography, a random oracle is an oracle that responds to every query with a random response chosen uniformly from its output domain, except that for any specific query, it responds the same way every time it receives that query...

 model . It is efficient and generates short signatures. It is covered by , which expired in February 2008.

Choosing parameters

• All users of the signature scheme agree on a group
  Group (mathematics)
  In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
  
    with generator of prime order in which the discrete log problem is hard. Typically a Schnorr group is used.
• All users agree on a cryptographic hash function
  Cryptographic hash function
  A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
  
   .

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
• , the set of finite bit strings
• , the set of congruence classes modulo excluding
• , the set of congruence classes modulo
• .

Key generation

• Choose a private signing key from the allowed set.
• The public verification key is .

Signing

To sign a message :

• Choose a random from the allowed set.
• Let .
• Let , where || denotes concatenation and is represented as a bit string.
• Let .

The signature is the pair .

Note that ; if , then the signature representation can fit into 40 bytes.

Verifying

• Let
• Let

If then the signature is verified.

Demonstration of correctness

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

, and hence .

The other direction goes through using the fact that and the assumption that the hash function is collision-resistant.

Public elements: , , , , , , .
Private elements: , .