# From block-wise Universal Hash Function to bit-wise UHF

Let's assume we have an $\epsilon$-bounded Universal Hash Function Family $H = \{H_K:\mathcal{X}^{\leq m}\rightarrow \mathcal{X}\mid \forall K\in \mathcal{K}\}$ with $\mathcal{X} = \mathcal{K} = \{0,1\}^{128}$. $H_K$ only takes messages $M$ as input, that are a multiple of the blocksize ($M\in\mathcal{X}^{\leq m}$) and are at most $m$ blocks long. Is it sufficient to apply an injective encoding $enc(\cdot)$ on the message, so that we get a bit-wise Universal Hash Function Family $H^* = \{H^*_K:\{0,1\}^*\rightarrow \mathcal{X}\mid \forall K\in \mathcal{K}\}$ with $H^*_K(M) = H_K(enc(M))$, $M\in\{0,1\}^*$ ?

Intuitively I would say yes, but the reason why I ask is the following:

(Section 7.2.2) states, that the rawCBC construction and any other prefix-free PRF $F_K$ with the following extension property yields an UHF:

if $F_K(x) = F_K(y) \Rightarrow F_K(x \| a) = F_K(y\|a)$

Furthermore, (Section 6.8.) states, that a block-wise PRF can be turned into a bit-wise PRF by applying an injective encoding on the input.

Now consider the following injective encoding function:

1. pad with $n$ zeros until message is a multiple of the block size
2. Append a length block $L$ that contains the bit-length of the original message

This bit-wise PRF has lost its extension property, so we cannot simply turn it into an UHF. But we can view it as an UHF with injective encoding on its input. So I am not sure, if the extension property is a sufficient or a necessary condition. This is the motivation for my question.

• I'm not quite sure what you're asking. Are you asking whether a block cipher in a modified CBC-MAC mode is a universal hash function? Or, are you asking whether a fixed-length universal hash can be used with a CBC-MAC setting, and the resulting mode would be universal? – poncho Aug 9 '17 at 14:18
• I want to build a provably secure bit-wise UHF based on CBC. I just struggle with the order to get there. Either I start with a bit-wise PRF based on CBC (then I can't prove it as a UHF due to missing extentability) or I start with a block-wise UHF based on CBC and append a length block to get a bit-wise UHF (injective encoding). But I dont't know, if this is a valid way to go. (By the way I consider multiple messages with variable but polynomial message lengths and only PPT adversaries. The term 'block-wise' denotes messages with a length that is a multiple of the block size.) – Patrick K Aug 10 '17 at 7:54