Abstract
In this paper, we present a construction of hash functions. These functions are collision free in the sense that under some cryptographic assumption, it is provably hard for an enemy to find collisions. Assumptions that would be sufficient are the hardness of factoring, of discrete log, or the (possibly) more general assumption about the existence of claw free sets of permutations.
The ability of a hash function to improve security and speed of a signature scheme is discussed: for example, we can combine the RSA-system with a collision free hash function based on factoring to get a scheme which is more efficient and much more secure.
Also, the effect of combining the Goldwasser-Micali-Rivest signature scheme with one of our functions is studied. In the factoring based implementation of the scheme using a k-bit modulus, the signing process can be speeded up by a factor roughly equal to k·O (log2(k)), while the signature checking process will be faster by a factor of O (log2(k)).
This research was supported by the Danish Natural Science Research Council.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Brassard and Crepeau: Non transitive transfer of confidence: a perfect zero-knowledge interactive protocol for SAT and beyond. Proc. of FOCS 86.
Damgård: Application of claw free functions in cryptography; unconditional protection in cryptographic protocols. Phd Thesis, in preparation.
Denning: Digital signatures with RSA and other public key cryptosystems. CACM, v.27, nr 4, 1984, pp.388–392.
Goldwasser, Micali and Rivest: A “paradoxical” solution to the signature problem. Proc. of 25th FOCS, 1984, pp.441–448.
Berstel and Perrin: Theory of codes, Academic Press, 1985.
Davis and Price: The application of digital signatures based on public key cryptosystems. Proc. of 5th Int. CompCom, 1980, pp.525–530.
Winternitz: Producing a one-way hash function from DES. Proc. of Crypto 83, pp.203–208
Coppersmith: Another birthday attack. Proc. of Crypto 85.
Stephens: Lentras factoring method based on elliptic curves. Proc. of Crypto 85.
Wegman and Carter: New hash functions. JCSI, v.22,1981.
Goldreich, Goldwasser and Micali: How to construct random functions. MIT.LCS.TM-244, 1983.
Blum and Micali: How to generate cryptographically strong sequences of pseudorandom bits. SIAM J. of Computing, v.13, 1984.
Goldreich: Two remarks concerning the GMR-signature scheme. Proc. of Crypto 86.
Goldwasser, Micali and Rivest: A digital signature scheme secure against adaptive chosen message attacks. To appear.
Bert den Boer: private communication.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1988 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Damgård, I.B. (1988). Collision Free Hash Functions and Public Key Signature Schemes. In: Chaum, D., Price, W.L. (eds) Advances in Cryptology — EUROCRYPT’ 87. EUROCRYPT 1987. Lecture Notes in Computer Science, vol 304. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-39118-5_19
Download citation
DOI: https://doi.org/10.1007/3-540-39118-5_19
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-19102-5
Online ISBN: 978-3-540-39118-0
eBook Packages: Springer Book Archive