A New Derivation of the Leftover Hash Lemma

S. Alencar, Marcelo; D. R. Assis, Karcius

doi:10.22042/isecure.2021.271070.622

A New Derivation of the Leftover Hash Lemma

Document Type : Research Article

Authors

Marcelo S. Alencar ¹

Karcius D. R. Assis ²

¹ Institute for Advanced Studies in Communications (Iecom), Campina Grande, Brazil

² Federal University of Bahia (PPgEE), Salvador, Brazil

https://doi.org/10.22042/isecure.2021.271070.622

Abstract

This paper reviews the characteristics of the main digest algorithms, and presents a new derivation of the leftover hash lemma, using the collision probability to derive an upper bound on the statistical distance between the key and seed joint probability, and the hash bit sequence distribution. The paper discussed the use of the hash function in cryptography and presented a new derivation of the upper bound on the statistical distance between the joint distribution of the key and the seed, and the distribution of the hash bit distribution, based on the collision probability. A cryptographic hash function is used to verify whether a data file maps onto a certain hash value. On the other hand, it is difficult to reconstruct the information based on the hash value. Therefore, it is used to assure data in- integrity, and is the building block of a Hash-based Message Authentication Code (HMAC), which provide message authentication.

Keywords

Hash Lemma

Coding

Probability

20.1001.1.20082045.2020.12.3.8.8

[1] Deepti Bahel, Prerana Ghosh, Arundhyoti Sarkar, and Matthew A Lanham. Predicting blood donations using machine learning techniques. In CONFERENCE PROCEEDINGS BY TRACK, page 323.

[2] Bart Preneel. Cryptographic hash functions. European Transactions on Telecommunications, 5(4): 431–448, 1994.

[3] Charles H Bennett, Gilles Brassard, Claude Cr´epeau, and Ueli M Maurer. Generalized privacy amplification. IEEE Transactions on Information Theory, 41(6):1915–1923, 1995.

[4] Wikipedia contributors, “cryptographic hash function - wikipedia, the free encyclopedia,”. [Online; acesso em 16 de julho de 2019]. [Online]. Available: https://en.wikipedia.org/w/index.php?title=Cryptographic hash function&oldid=905916305, 2019.

[5] Alfr´ed R´enyi et al. On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics. The Regents of the University of California, 1961.

[6] Stefan Berens. Conditional renyi entropy. PhD thesis, Masters thesis, Mathematisch Instituut, Universiteit Leiden, 2013.

[7] J Lawrence Carter and Mark N Wegman. Universal classes of hash functions. Journal of computer and system sciences, 18(2):143–154, 1979.

[8] Douglas R. Stinson. Universal hashing and authentication codes. Designs, Codes and Cryptography, 4(3):369–380, 1994.

[9] Marcelo S Alencar and R T Alencar. Probability Theory. ISBN-13: 978-1-60650- 747-6 (print). New York, USA: Momentum Press, LLC, 2016.