Paper 2023/696
Universal Hashing Based on Field Multiplication and (Near-)MDS Matrices
Abstract
In this paper we propose a new construction for building universal hash functions, a specific instance called multi-265, and provide proofs for their universality. Our construction follows the key-then-hash parallel paradigm. In a first step it adds a variable length input message to a secret key and splits the result in blocks. Then it applies a fixed-length public function to each block and adds their results to form the output. The innovation presented in this work lies in the public function: we introduce the multiply-transform-multiply-construction that makes use of field multiplication and linear transformations. We prove upper bounds for the universality of key-then-hash parallel hash functions making use of a public function with our construction provided the linear transformation are maximum-distance-separable (MDS). We additionally propose a concrete instantiation of our construction multi-265, where the underlying public function uses a near-MDS linear transformation and prove it to be $2^{-154}$-universal. We also make the reference code for multi-265 available.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. Africacrypt 2023
- Keywords
- PrimitiveKeyed hashingParallelForgeryMulti-265
- Contact author(s)
-
koustabh ghosh @ ru nl
jonathan fuchs @ ru nl
parisa eliasi @ ru nl
joan daemen @ ru nl - History
- 2023-05-16: approved
- 2023-05-16: received
- See all versions
- Short URL
- https://ia.cr/2023/696
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/696, author = {Koustabh Ghosh and Jonathan Fuchs and Parisa Amiri Eliasi and Joan Daemen}, title = {Universal Hashing Based on Field Multiplication and (Near-){MDS} Matrices}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/696}, year = {2023}, url = {https://eprint.iacr.org/2023/696} }