Part of a sponge construction (like SHA3 uses) is a fixed permutation $p$; which is clearly not one-way.
Could we, theoretically, exchange the permutation $p$ with any other permutation? What basic characteristics should such a permutation have – or would, for example, a simple LFSR already represent a valid replacement, assuming it spans the whole bit-range ($r+c$)?
The security of the sponge construction rely on two parts:
This permutation is expected to have at least the following requirement:
In the case of Keccak, $\theta$ is an operation mainly columns oriented.
Which is why $\pi$ will ensure that every bits of a column is evenly spread in the slice. This prevent the creation of patterns.
$\chi$ is the main ingredient in Keccak-$f$. It is the only part that is not linear. Without it Keccak would be super weak to cryptanalysis.
propagation of a difference through $\chi$
Lastly, Keccak-$f$ provides a weak alignment (resistance to truncated differential cryptanalysis). The idea is to make sure that the differences are not constrained by a subdivision of the state (byte for AES or a group of 5 bits in the case of Keccak). However, due to the weak alignment of Keccak-f, finding the lower security bounds of the algorithm is harder.
If another permutation provide such characteristics (NORX permutation? I'll let Richie Frame answer that part. He loves NORX). Then I guess it would be another decent choice.
I haven't studied LFSR.
TL;DR: The candidate permutation must provide strong diffusion, confusion and if possible a weak alignment.
The permutation should be as close to a random permutation as possible. This is essentially a block-cipher with a fixed key.
A random permutation with given width $b$ is a permutation drawn randomly and uniformly from the set of all $2^b!$ $b$-bit permutations.
Unfortunately realizing random permutations suffers from similar problems as realizing random oracles, with the most important limitation being that all practical permutations have a short, efficiently computable description, which a random permutation does not.
The Keccak paper says:
The Keccak-f permutations should have no propagation properties significantly different from that of a random permutation
The design philosophy underlying Keccak is the hermetic sponge strategy. This consists of using the sponge construction for having provable security against all generic attacks and calling a permutation (or transformation) that should not have structural properties with the exception of a compact description
The authors of Keccak have a website about the sponge construction which says:
In fact, these results show that any attack against a sponge function implies that the permutation it uses can be distinguished from a typical randomly-chosen permutation. This naturally leads to the following design strategy, which we called the hermetic sponge strategy: adopting the sponge construction and building an underlying permutation f that should not have any properties exploitable in attacks. We have called such properties structural distinguishers.
The paper Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles van Assche - Cryptographic sponge function says:
First, as an iterated permutation can be seen a block cipher with a fixed and known key, it should be impossible to construct for the full-round versions distinguishers like the known-key distinguishers for reduced-round versions of DES and AES given in [39]. This includes differentials with high differential probability (DP), high input-output correlations, distinguishers based on integral cryptanalysis or deviations in algebraic expressions of the output in terms of the input. We call this kind of distinguishers structural, to set them apart from trivial distinguishers that are of no use in attacks such as checking that $f(a)=b$ for some known input-output couple $(a,b)$ or the observation that f has a compact description.
