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