# Moni Noar One Way Function: What does input is partioned mean?

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 $$ and repeat this process until we covered the whole $$m$$ bitstring?

• 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... – poncho Jan 24 '19 at 17:45
• 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." – 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).
• If you pad with zeroes it's no longer 2-universal. For $R\ge4$ $1$ and $10$ for example would collide with probability $1$. – Maeher Jan 25 '19 at 17:04
• A "one-and-zeroes" padding would work. I.e., always add a 1 and then pad with zeroes to a multiple of $n$. – Maeher Jan 25 '19 at 17:32