In
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...
, a Schnorr signature is a
digital signature
A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature, where the prerequisites are satisfied, gives a recipient very high confidence that the message was created b ...
produced by the Schnorr signature algorithm that was described by
Claus Schnorr. It is a digital signature scheme known for its simplicity,
among the first whose security is based on the
intractability of certain
discrete logarithm
In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log'' ...
problems.
It is efficient and generates short signatures.
It was covered by which expired in February 2008.
Algorithm
Choosing parameters
*All users of the signature scheme agree on a
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
,
, of prime order,
, with generator,
, in which the
discrete log
In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b' ...
problem is assumed to be hard. Typically a
Schnorr group A Schnorr group, proposed by Claus P. Schnorr, is a large prime-order subgroup of \mathbb_p^\times, the multiplicative group of integers modulo p for some prime p. To generate such a group, generate p, q, r such that
:p = qr + 1
with p, q prime. ...
is used.
*All users agree on a
cryptographic hash function
A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with fixed size of n bits) that has special properties desirable for cryptography:
* the probability of a particular n-bit output re ...
.
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 the set of congruence classes
*
, the set of finite bit strings
*
, the
set of congruence classes modulo
*
, the
multiplicative group of integers modulo (for prime
,
)
*
.
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.
Proof of correctness
It is relatively easy to see that
if the signed message equals the verified message:
, and hence
.
Public elements:
,
,
,
,
,
,
. Private elements:
,
.
This shows only that a correctly signed message will verify correctly; many other properties are required for a secure signature algorithm.
Key leakage from nonce reuse
Just as with the closely related signature algorithms
DSA,
ECDSA
In cryptography, the Elliptic Curve Digital Signature Algorithm (ECDSA) offers a variant of the Digital Signature Algorithm (DSA) which uses elliptic-curve cryptography.
Key and signature-size
As with elliptic-curve cryptography in general, the b ...
, and
ElGamal
In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1985. ElGamal encryption is used in th ...
, reusing the secret nonce value
on two Schnorr signatures of different messages will allow observers to recover the private key.
[https://ecc2017.cs.ru.nl/slides/ecc2017-tibouchi.pdf ] In the case of Schnorr signatures, this simply requires subtracting
values:
:
.
If
but
then
can be simply isolated. In fact, even slight biases in the value
or partial leakage of
can reveal the private key, after collecting sufficiently many signatures and solving the
hidden number problem
Hidden or The Hidden may refer to:
Film and television Film
* ''The Hidden'' (film), a 1987 American science fiction/horror film
* ''Hidden'' (2005 film) or ''Caché'', a French thriller film
* ''Hidden'' (2009 film), a Norwegian horror film
...
.
[
]
Security argument
The signature scheme was constructed by applying the Fiat–Shamir transformation to Schnorr's identification protocol. Therefore, (as per Fiat and Shamir's arguments), it is secure if is modeled as a random oracle
In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every ''unique query'' with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time th ...
.
Its security can also be argued in the generic group model The generic group model is an idealised cryptographic model, where the adversary is only given access to a randomly chosen encoding of a group, instead of efficient encodings, such as those used by the finite field or elliptic curve groups used in ...
, under the assumption that is "random-prefix preimage resistant" and "random-prefix second-preimage resistant". In particular, does ''not'' need to be collision resistant.
In 2012, Seurin provided an exact proof of the Schnorr signature scheme. In particular, Seurin shows that the security proof using the forking lemma The forking lemma is any of a number of related lemmas in cryptography research. The lemma states that if an adversary (typically a probabilistic Turing machine), on inputs drawn from some distribution, produces an output that has some property w ...
is the best possible result for any signature schemes based on one-way group homomorphism
In mathematics, given two groups, (''G'', ∗) and (''H'', ·), a group homomorphism from (''G'', ∗) to (''H'', ·) is a function ''h'' : ''G'' → ''H'' such that for all ''u'' and ''v'' in ''G'' it holds that
: h(u*v) = h(u) \cdot h(v)
...
s including Schnorr-type signatures and the Guillou–Quisquater signature schemes. Namely, under the ROMDL assumption, any algebraic reduction must lose a factor in its time-to-success ratio, where is a function that remains close to 1 as long as " is noticeably smaller than 1", where is the probability of forging an error making at most queries to the random oracle.
Short Schnorr signatures
The aforementioned process achieves a ''t''-bit security level with 4''t''-bit signatures. For example, a 128-bit security level would require 512-bit (64-byte) signatures. The security is limited by discrete logarithm attacks on the group, which have a complexity of the ''square-root'' of the group size.
In Schnorr's original 1991 paper, it was suggested that since collision resistance in the hash is not required, then therefore shorter hash functions may be just as secure, and indeed recent developments suggest that a ''t''-bit security level can be achieved with 3''t''-bit signatures.[ Then, a 128-bit security level would require only 384-bit (48-byte) signatures, and this could be achieved by truncating the size of ''e'' until it is half the length of the ''s'' bitfield.
]
See also
* DSA
* EdDSA
In public-key cryptography, Edwards-curve Digital Signature Algorithm (EdDSA) is a digital signature scheme using a variant of Schnorr signature based on twisted Edwards curves.
It is designed to be faster than existing digital signature schemes ...
* ElGamal signature scheme
The ElGamal signature scheme is a digital signature scheme which is based on the difficulty of computing discrete logarithms. It was described by Taher Elgamal in 1985. (conference version appeared in CRYPTO'84, pp. 10–18)
The ElGamal signature ...
Notes
References
* Menezes, Alfred J. et al. (1996), ''Handbook of Applied Cryptography'', CRC Press.
* C.P. Schnorr (1990), "Efficient identification and signatures for smart cards", in G. Brassard, ed. ''Advances in Cryptology—Crypto '89'', 239-252, Springer-Verlag. Lecture Notes in Computer Science
''Lecture Notes in Computer Science'' is a series of computer science books published by Springer Science+Business Media since 1973.
Overview
The series contains proceedings, post-proceedings, monographs, and Festschrifts. In addition, tutorials, ...
, nr 435
* Claus-Peter Schnorr (1991), "Efficient Signature Generation by Smart Cards", ''Journal of Cryptology
The ''Journal of Cryptology'' () is a scientific journal in the field of cryptology and cryptography. The journal is published quarterly by the International Association for Cryptologic Research. Its editor-in-chief is Vincent Rijmen
Vincent R ...
'' 4(3), 161–17
(PS)(PDF)
External links
RFC 8235
{{Cryptography navbox , public-key
Digital signature schemes