# For a hash over a finite space without size reduction, is a public permutation sufficient?

Suppose the application is a Lamport signature scheme.

Is the following a secure hash $$\{0,1\}^n \rightarrow \{0,1\}^n$$? $$H(x) = x \oplus P(x)$$ where $$P$$ is a public permutation that permutes an input of length $$n$$.

Lamport's signature requires a hash function $$H$$ that is a one-way function. So your question is whether $$H(x) = x \oplus P(x)$$ is one-way when $$P$$ is a public permutation.

I will assume that $$P$$ is a public random permutation (a.k.a., an ideal permutation). In that case, yes the construction is one-way. It is very closely related to the Matyas-Meyer-Oseas (MMO) construction of a collision-resistant hash function from an ideal block cipher.

To hash a sequence of blocks $$m_1 m_2 \cdots$$, the MMO construction works by iterating the function $$s \gets E(s, m_i) \oplus m_i$$, where $$s$$ is the continuously updating internal state and $$E$$ is an ideal cipher. If you could find inverses in $$H(x) = x \oplus P(x)$$, for a public permutation $$P$$, then you could easily find collisions (even second preimages) in an MMO hash. Since MMO hash is provably secure in the ideal cipher model, this impiles that $$H$$ is one-way:

Consider a 2-block message $$m_1 m_2$$ and its hash which is computed as:

• $$s_1 = E(s_0, m_1) \oplus m_1$$
• $$s_2 = E(s_1, m_2) \oplus m_2$$

To find another message that collides with this one, pick $$m_1' \ne m_1$$ arbitrarily and set:

• $$s'_2 = E(s_0, m_1') \oplus m'_1$$

If you had an $$m'_2$$ that satisifed

• $$s_2 = E(s'_1, m_2') \oplus m'_2$$

then $$m'_1 m'_2$$ would be the desired collision. Note that everything in this expression is known except $$m'_2$$, and so $$E(s'_1, \cdot)$$ is a public random permutation. So the task reduces to that of finding preimages of a function of the form $$x \mapsto P(x) \oplus x$$, where $$P(x) = E(s'_2,x)$$.