Paper 2023/696

Universal Hashing Based on Field Multiplication and (Near-)MDS Matrices

Koustabh Ghosh, Radboud University Nijmegen
Jonathan Fuchs, Radboud University Nijmegen
Parisa Amiri Eliasi, Radboud University Nijmegen
Joan Daemen, Radboud University Nijmegen

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.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Africacrypt 2023
PrimitiveKeyed hashingParallelForgeryMulti-265
Contact author(s)
koustabh ghosh @ ru nl
jonathan fuchs @ ru nl
parisa eliasi @ ru nl
joan daemen @ ru nl
2023-05-16: approved
2023-05-16: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.