×

Hash function requirements for Schnorr signatures. (English) Zbl 1165.94323

Summary: We provide two necessary conditions on hash functions for the Schnorr signature scheme to be secure, assuming compact group representations such as those which occur in elliptic curve groups. We also show, via an argument in the generic group model, that these conditions are sufficient. Our hash function security requirements are variants of the standard notions of preimage and second preimage resistance. One of them is in fact equivalent to the Nostradamus attack by J. Kelsey and T. Kohno [in: Vaudenay, Serge (ed.), Advances in cryptology – EUROCRYPT 2006. 25th annual international conference on the theory and applications of cryptographic techniques, St. Petersburg, Russia, May 28–June 1, 2006. Proceedings. Berlin: Springer. Lecture Notes in Computer Science 4004, 183–200 (2006; Zbl 1140.94354)], and, when considering keyed compression functions, both are closely related to the ePre and eSec notions by P. Rogaway and T. Shrimpton [in: Roy, Bimal (ed.) et al., Fast software encryption. 11th international workshop, FSE 2004, Delhi, India, February 5–7, 2004. Revised papers. Berlin: Springer. Lecture Notes in Computer Science 3017, 371–388 (2004; Zbl 1079.68560)].
Our results have a number of interesting implications in practice. First, since security does not rely on the hash function being collision resistant, Schnorr signatures can still be securely instantiated with SHA-1/SHA-256, unlike DSA signatures. Second, we conjecture that our properties require \(O(2^{n})\) work to solve for a hash function with \(n\)-bit output, thereby allowing the use of shorter hashes and saving twenty-five percent in signature size. And third, our analysis does not reveal any significant difference in hardness between forging signatures and computing discrete logarithms, which plays down the importance of the loose reductions in existing random-oracle proofs, and seems to support the use of “normal-size” groups.

MSC:

94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdalla Michel, Lecture Notes in Computer Science 2332 pp 418– · doi:10.1007/3-540-46035-7_28
[2] Andreeva Elena, Lecture Notes in Computer Science 4833 pp 130– · Zbl 1153.94342 · doi:10.1007/978-3-540-76900-2_8
[3] Hashing Collision-Resistant, Lecture Notes in Computer Science 1294 pp 470–
[4] Damgård Ivan, Lecture Notes in Computer Science 435 pp 416– · doi:10.1007/0-387-34805-0_39
[5] Dent Alexander W., Lecture Notes in Computer Science 2501 pp 100– · Zbl 1065.94546 · doi:10.1007/3-540-36178-2_6
[6] Fiat Amos, Lecture Notes in Computer Science 263 pp 186– · Zbl 0636.94012 · doi:10.1007/3-540-47721-7_12
[7] Fischlin Marc, Lecture Notes in Computer Science pp 458– (1976)
[8] DOI: 10.1137/0217017 · Zbl 0644.94012 · doi:10.1137/0217017
[9] Halevi Shai, Lecture Notes in Computer Science 4117 pp 41– · Zbl 1161.94443 · doi:10.1007/11818175_3
[10] Johnson Don, International Journal of Information Security 1 pp 36– (2001)
[11] Kelsey John, Lecture Notes in Computer Science 4004 pp 183– · Zbl 1140.94354 · doi:10.1007/11761679_12
[12] DOI: 10.1007/s00145-005-0432-z · Zbl 1115.68078 · doi:10.1007/s00145-005-0432-z
[13] Lucks Stefan, Lecture Notes in Computer Science 3788 pp 474– · Zbl 1154.94414 · doi:10.1007/11593447_26
[14] Maurer Ueli M., Lecture Notes in Computer Science 1403 pp 72– · doi:10.1007/BFb0054118
[15] Merkle Ralph C., Lecture Notes in Computer Science 435 pp 428– · doi:10.1007/0-387-34805-0_40
[16] Mironov Ilya, Lecture Notes in Computer Science pp 166– (2045)
[17] Ohta Kazuo, Lecture Notes in Computer Science 1462 pp 354– · doi:10.1007/BFb0055741
[18] Paillier Pascal, Lecture Notes in Computer Science 3788 pp 1– · Zbl 1146.94305 · doi:10.1007/11593447_1
[19] DOI: 10.1007/s001450010003 · Zbl 1025.94015 · doi:10.1007/s001450010003
[20] Rogaway Phillip, Lecture Notes in Computer Science 3017 pp 371– · doi:10.1007/978-3-540-25937-4_24
[21] Schnorr Claus-Peter, Lecture Notes in Computer Science 435 pp 239– · doi:10.1007/0-387-34805-0_22
[22] Smart Cards Efficient Signature, Journal of Cryptology 4 pp 161– (1991) · Zbl 0743.68058
[23] Shoup Victor, Lecture Notes in Computer Science 1233 pp 256– · doi:10.1007/3-540-69053-0_18
[24] Stern Jacques, Lecture Notes in Computer Science 2442 pp 93– · doi:10.1007/3-540-45708-9_7
[25] Wang Xiaoyun, Lecture Notes in Computer Science 3621 pp 17– · Zbl 1145.94454 · doi:10.1007/11535218_2
[26] Wang Xiaoyun, Lecture Notes in Computer Science 3494 pp 19– · Zbl 1137.94359 · doi:10.1007/11426639_2
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.