Non-cryptographic hash function
The non-cryptographic hash functions (NCHFs[1]) are hash functions intended for applications that do not need the rigorous security requirements of the cryptographic hash functions (e.g., preimage resistance) and therefore can be faster less resource-intensive.[2] Typical examples of CPU-optimized non-cryptographic hashes include FNV-1a, Murmur3.[3]
Applications and requirements
Among the typical uses of the non-cryptographic hash functions are bloom filters, hash tables, count sketches. These applications require, in addition to speed, uniform distribution and avalanche properties.[3] These constructs are used in diverse designs: lexical analyzers, compilers, databases, communication networks, videogames, DNS servers, filesystems - anywhere in computing where there is need to find the information very quickly (preferably in the O(1) time, which will also achieve a perfect scalability).[4]
Estébanez et al. list the "most important" NCHFs:[5]
- Fowler–Noll–Vo hash function (FNV) was created by Glenn Fowler and Phong Vo in 1991 with improvements from Landon Curt Noll. FNV with its two variants, FNV-1 and FNV-1a, is very widely used in software that ranges from Linux and FreeBSD OSes, DNS servers, NFS to Twitter, PlayStation2, and [[xBox console.
Design
In order to minimize the collisions, a typical NCHF is using the Merkle–Damgård construction.[6]
Non-cryptographic hash functions optimized for software frequently involve the multiplication operation. Since in hardware multiplication is resource-intensive and frequency-limiting, ASIC-friendlier designs had been proposed, including SipHash (that has an additional benefit of being able to use a secret key for message authentication), NSGAhash and XORhash. Although technically the lightweight cryptography can be used for the same applications, the latency of its algorithms is usually way too high due to a large number of rounds.[3] Sateesan et al. propose using the reduced-round versions of the lightweight hashes and ciphers as non-cryptographic hash functions.[2]
References
- ^ Estébanez et al. 2013.
- ^ a b Sateesan et al. 2023, p. 1.
- ^ a b c Sateesan et al. 2023, p. 2.
- ^ Estébanez et al. 2013, p. 1.
- ^ Estébanez et al. 2013, pp. 3–4.
- ^ Estébanez et al. 2013, p. 2.
Sources
- Sateesan, Arish; Biesmans, Jelle; Claesen, Thomas; Vliegen, Jo; Mentens, Nele (April 2023). "Optimized algorithms and architectures for fast non-cryptographic hash functions in hardware". Microprocessors and Microsystems. 98: 104782. doi:10.1016/j.micpro.2023.104782. ISSN 0141-9331.
- Estébanez, César; Saez, Yago; Recio, Gustavo; Isasi, Pedro (28 January 2013). "Performance of the most common non-cryptographic hash functions" (PDF). Software: Practice and Experience. 44 (6): 681–698. doi:10.1002/spe.2179. ISSN 0038-0644.
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |