It seems to me that all that exists for universal hash functions used in Carter–Wegman MACs is finite field multiplication. Are there any others?
$\begingroup$ $\endgroup$
1 
- 2$\begingroup$ I suppose you intended to say polynomial evaluation hashes, since finite field multiplication may mean anything. $\endgroup$Marc Ilunga– Marc Ilunga2025-07-05 20:09:46 +00:00Commented Jul 5 at 20:09
Add a comment |
3 Answers
$\begingroup$ $\endgroup$
Of course there are. One example that springs immediately to mind is UMAC. It is based on modular multiplication over a composite, which is a ring, not a field.
Other examples would be VMAC and Square Hash
On the other hand, polynomial based CW hashes have the advantage that they use a short key (unlike UMAC), and the message processing is just a field multiplication and addition (unlike VMAC). And, polynomial based universal hash functions are done in fields (as something where multiplying two nonzero values can give you a zero yields a weaker hash).
$\begingroup$ $\endgroup$
Universal hashes are important to understand the security analysis of the ECBC, FCBC, and CMAC (XCBC) constructions, all of which are based on CBC-MAC. The analysis goes as follows:
Plain CBC-MAC is (famously) not secure as a variable-input-length MAC. But it is secure as a variable-input-length universal hash.
$\textsf{PRF}(K_2, \textsf{UHF}(K_1, X))$ is a secure PRF. Note that the UHF can be secure for variable input lengths and the underlying PRF only needs to be secure for a single input length.
So CBC-MAC is a natural and non-algebraic UHF.
$\begingroup$ $\endgroup$
Carter-Wegman MACs are usually described as using universal hashing from polynomial evaluation hashes. In fact, for the usual CW hashes, universality is not enough, but we'll get back to that later. The question at hand now is, are there other options for universal hashing that could fit in the CW hash? Yes, quite a few. Here are some options:
- Polynomial evaluation that we know already from Poly1305 or GHASH. There are a few variation depending on the expected security
- Polynomial division aka CRCs: Cryptographic CRCs are built by sampling a random irreducible polynomial
- Matrix multiplication with families of Toeplitz hashes
- Inner product hashes: that is the message and key are seen as vectors.
Now for the normal CW mac, just being universal is not enough; we actually need the hash to have different unpredictability. So one has to be careful which is used to implement a CW hash.
