Paper 2009/229

Hardware Implementations of a Variant of the Zémor-Tillich Hash Function: Can a Provably Secure Hash Function be very efficient ?

Giacomo de Meulenaer, Christophe Petit, and Jean-Jacques Quisquater

Abstract

Hash functions are widely used in Cryptography, and hardware implementations of hash functions are of interest in a variety of contexts such as speeding up the computations of a network server or providing authentication in small electronic devices such as RFID tags. Provably secure hash functions, the security of which relies on the hardness of a mathematical problem, are particularly appealing for security, but they used to be too inefficient in practice. In this paper, we study the efficiency in hardware of ZT', a provably secure hash function based on the Zémor-Tillich hash function. We consider three kinds of implementations targeting a high throughput and a low area in different ways. We first present a high-speed implementation of ZT' on FPGA that is nearly half as efficient as state-of-the-art SHA implementations in terms of throughput per area. We then focus on area reduction and present an ASIC implementation of ZT' with much smaller area costs than SHA-1 and even than SQUASH, which was specially designed for low-cost RFID tags. Between these two extreme implementations, we show that the throughput and area can be traded with a lot of flexibility. Finally, we show that the inherent parallelism of ZT' makes it particularly suitable for applications requiring high speed hashing of very long messages. Our work, together with existing reasonably efficient software implementations, shows that this variant of the Zémor-Tillich hash function is in fact very practical for a wide range of applications, while having a security related to the hardness of a mathematical problem and significant additional advantages such as scalability and parallelism.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
Hash functionZémor-TillichHardwareFPGAASIC
Contact author(s)
giacomo demeulenaer @ uclouvain be
History
2009-05-30: received
Short URL
https://ia.cr/2009/229
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/229,
      author = {Giacomo de Meulenaer and Christophe Petit and Jean-Jacques Quisquater},
      title = {Hardware Implementations of a Variant of the Zémor-Tillich Hash Function: Can a Provably Secure Hash Function be very efficient ?},
      howpublished = {Cryptology ePrint Archive, Paper 2009/229},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/229}},
      url = {https://eprint.iacr.org/2009/229}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.