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)$.


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.