summaryrefslogtreecommitdiff
path: root/bip-schnorr.mediawiki
diff options
context:
space:
mode:
authorJonas Nick <jonasd.nick@gmail.com>2019-09-27 09:00:37 +0000
committerPieter Wuille <pieter.wuille@gmail.com>2020-01-19 14:47:33 -0800
commitfe8f5f68caa9c8da00fcd2cff4a02303766097c1 (patch)
tree6ba56b29602ee0a851f08c6eed37e4bea84eec96 /bip-schnorr.mediawiki
parent05cc92b9adbe1eac754ca8c25ba022759b20975f (diff)
downloadbips-fe8f5f68caa9c8da00fcd2cff4a02303766097c1.tar.xz
Standardize on secret key in bip-schnorr
Diffstat (limited to 'bip-schnorr.mediawiki')
-rw-r--r--bip-schnorr.mediawiki6
1 files changed, 3 insertions, 3 deletions
diff --git a/bip-schnorr.mediawiki b/bip-schnorr.mediawiki
index 0473a29..5ae6e87 100644
--- a/bip-schnorr.mediawiki
+++ b/bip-schnorr.mediawiki
@@ -26,7 +26,7 @@ transactions. These are [http://www.secg.org/sec1-v2.pdf standardized], but have
compared to [https://en.wikipedia.org/wiki/Schnorr_signature Schnorr signatures] over the same curve:
* '''Security proof''': The security of Schnorr signatures is easily [https://www.di.ens.fr/~pointche/Documents/Papers/2000_joc.pdf provable] in the random oracle model assuming the elliptic curve discrete logarithm problem (ECDLP) is hard. Such a proof does not exist for ECDSA.
-* '''Non-malleability''': ECDSA signatures are inherently malleable; a third party without access to the private key can alter an existing valid signature for a given public key and message into another signature that is valid for the same key and message. This issue is discussed in [https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki BIP62] and [https://github.com/bitcoin/bips/blob/master/bip-0066.mediawiki BIP66]. On the other hand, Schnorr signatures are provably non-malleable<ref>More precisely they are '' '''strongly''' unforgeable under chosen message attacks '' (SUF-CMA), which informally means that without knowledge of the secret key but given a valid signature of a message, it is not possible to come up with a second valid signature for the same message. A security proof in the random oracle model can be found for example in [https://eprint.iacr.org/2016/191 a paper by Kiltz, Masny and Pan], which essentially restates [https://www.di.ens.fr/~pointche/Documents/Papers/2000_joc.pdf the original security proof of Schnorr signatures by Pointcheval and Stern] more explicitly. These proofs are for the Schnorr signature variant using ''(e,s)'' instead of ''(R,s)'' (see Design above). Since we use a unique encoding of ''R'', there is an efficiently computable bijection that maps ''(R, s)'' to ''(e, s)'', which allows to convert a successful SUF-CMA attacker for the ''(e, s)'' variant to a successful SUF-CMA attacker for the ''(r, s)'' variant (and vice-versa). Furthermore, the aforementioned proofs consider a variant of Schnorr signatures without key prefixing (see Design above), but it can be verified that the proofs are also correct for the variant with key prefixing. As a result, the aforementioned security proofs apply to the variant of Schnorr signatures proposed in this document.</ref>.
+* '''Non-malleability''': ECDSA signatures are inherently malleable; a third party without access to the secret key can alter an existing valid signature for a given public key and message into another signature that is valid for the same key and message. This issue is discussed in [https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki BIP62] and [https://github.com/bitcoin/bips/blob/master/bip-0066.mediawiki BIP66]. On the other hand, Schnorr signatures are provably non-malleable<ref>More precisely they are '' '''strongly''' unforgeable under chosen message attacks '' (SUF-CMA), which informally means that without knowledge of the secret key but given a valid signature of a message, it is not possible to come up with a second valid signature for the same message. A security proof in the random oracle model can be found for example in [https://eprint.iacr.org/2016/191 a paper by Kiltz, Masny and Pan], which essentially restates [https://www.di.ens.fr/~pointche/Documents/Papers/2000_joc.pdf the original security proof of Schnorr signatures by Pointcheval and Stern] more explicitly. These proofs are for the Schnorr signature variant using ''(e,s)'' instead of ''(R,s)'' (see Design above). Since we use a unique encoding of ''R'', there is an efficiently computable bijection that maps ''(R, s)'' to ''(e, s)'', which allows to convert a successful SUF-CMA attacker for the ''(e, s)'' variant to a successful SUF-CMA attacker for the ''(r, s)'' variant (and vice-versa). Furthermore, the aforementioned proofs consider a variant of Schnorr signatures without key prefixing (see Design above), but it can be verified that the proofs are also correct for the variant with key prefixing. As a result, the aforementioned security proofs apply to the variant of Schnorr signatures proposed in this document.</ref>.
* '''Linearity''': Schnorr signatures have the remarkable property that multiple parties can collaborate to produce a signature that is valid for the sum of their public keys. This is the building block for various higher-level constructions that improve efficiency and privacy, such as multisignatures and others (see Applications below).
For all these advantages, there are virtually no disadvantages, apart
@@ -40,7 +40,7 @@ made:
[[File:bip-schnorr/speedup-batch.png|frame|This graph shows the ratio between the time it takes to verify ''n'' signatures individually and to verify a batch of ''n'' signatures. This ratio goes up logarithmically with the number of signatures, or in other words: the total time to verify ''n'' signatures grows with ''O(n / log n)''.]]
-By reusing the same curve as Bitcoin has used for ECDSA, we are able to retain existing mechanisms for choosing private and public keys, and we avoid introducing new assumptions about elliptic curve group security.
+By reusing the same curve as Bitcoin has used for ECDSA, we are able to retain existing mechanisms for choosing secret and public keys, and we avoid introducing new assumptions about elliptic curve group security.
== Description ==
@@ -83,7 +83,7 @@ Implicit Y coordinates are not a reduction in security when expressed as the num
'''Tagged Hashes''' Cryptographic hash functions are used for multiple purposes in the specification below and in Bitcoin in general. To make sure hashes used in one context can't be reinterpreted in another one, hash functions can be tweaked with a context-dependent tag name, in such a way that collisions across contexts can be assumed to be infeasible. Such collisions obviously can not be ruled out completely, but only for schemes using tagging with a unique name. As for other schemes collisions are at least less likely with tagging than without.
-For example, without tagged hashing a bip-schnorr signature could also be valid for a signature scheme where the only difference is that the arguments to the hash function are reordered. Worse, if the bip-schnorr nonce derivation function was copied or independently created, then the nonce could be accidentally reused in the other scheme leaking the private key.
+For example, without tagged hashing a bip-schnorr signature could also be valid for a signature scheme where the only difference is that the arguments to the hash function are reordered. Worse, if the bip-schnorr nonce derivation function was copied or independently created, then the nonce could be accidentally reused in the other scheme leaking the secret key.
This proposal suggests to include the tag by prefixing the hashed data with ''SHA256(tag) || SHA256(tag)''. Because this is a 64-byte long context-specific constant and the ''SHA256'' block size is also 64 bytes, optimized implementations are possible (identical to SHA256 itself, but with a modified initial state). Using SHA256 of the tag name itself is reasonably simple and efficient for implementations that don't choose to use the optimization.