I am trying to understand An Implementation of Efficient Pseudo-Random Functions.

There, the following hash function is defined:

We define $\hat{h}=\hat{h}_{r}: {\{0,1\}}^* \rightarrow {\bf Z}_R$ as follows: $$ \hat{h}_r(m) = ({\sum_{i=1}^{k} m_i \cdot r^{i-1}}) \bmod R $$ where $R$ is a 161-bit prime, $r$ (the key of $\hat{h}$) is a uniformly distributed element in ${\bf Z}_{R}^*$ and the input $m$ is partitioned into a sequence, $\langle m_1 \dots m_k\rangle$, of elements in ${\bf Z}_{R}$.

I am having trouble understanding what "$m$ is partioned into a sequence, of elements in $\textbf{Z}_R$ means. Does this mean we understand $m$ as a bitstring, iterate through it from left to right as long as the resulting number is $<R$ and repeat this process until we covered the whole $m$ bitstring?

  • $\begingroup$ That function wouldn't appear to be secure; there's an obvious key recovery attack (given a singe $\hat{h}_r(m), m$ pair, and once you have the key, computing collisions and preimages would be easy... $\endgroup$
    – poncho
    Jan 24 '19 at 17:45
  • $\begingroup$ Since this function is just used to extend the length of the output of an already pseudorandom function, it is not clear to me whether that would be an issue. The only requirement that is mentioned is, that "the probability of collision, $\Pr_{\hat{h}}[\hat{h}(x)=\hat{h}(y)]$, is negligible." $\endgroup$
    – CryptoFan
    Jan 24 '19 at 18:31

I am having trouble understanding what "$m$ is partioned into a sequence $\langle m_1, ..., m_k\rangle$ of elements in $\textbf{Z}_R$ means.

This is essentially what you said. Consider $n$ such that $\{0,1\}^n$, seen as integers, is a subset of $\textbf{Z}_R$ (e.g. $n = \lfloor\log_2R\rfloor$). Then regard $m$ as a long string $m = m_1\|\cdots\|m_N$ where each $m_i$ is in $\{0,1\}^n$ (if $n$ does not divide the bit-length of $m$ then apply a "good" padding to $m$, i.e. one that is prefix-free).

Just take into account that, as noticed by @poncho in the comments, this is not a PRF. This is a 2-universal hash function, and as shown in the post you cite, it is an ingredient for the construction of an actual PRF.

  • 1
    $\begingroup$ If you pad with zeroes it's no longer 2-universal. For $R\ge4$ $1$ and $10$ for example would collide with probability $1$. $\endgroup$
    – Maeher
    Jan 25 '19 at 17:04
  • $\begingroup$ A "one-and-zeroes" padding would work. I.e., always add a 1 and then pad with zeroes to a multiple of $n$. $\endgroup$
    – Maeher
    Jan 25 '19 at 17:32
  • $\begingroup$ @Maeher thanks, you're right, I edited the answer. $\endgroup$
    – Daniel
    Jan 26 '19 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.