Simple candidates for pseudorandom permutations? Even though it is not known whether one-way functions exist, there are several candidate functions used in practice for cryptographic applications that are efficiently computable but are conjectured to be hard to invert (such as modular exponentiation, the Rabin function etc.) Moreover, many of these functions are relatively simple to compute in some sense.

Are there any simple candidates for strongly pseudorandom permutations? By a simple candidate, I mean one with small circuit complexity (or maybe small complexity under some different complexity measure). For example, are there any candidates for PRPs that can be computed by $NC^1$ circuits? (I am looking for PRPs which work with arbitrarily long inputs, as opposed to block ciphers operating on fixed-length strings.)
Yes.  The following paper presents a candidate for a PRF that is implementable in $NC^1$, whose security is based on a lattice assumption (hardness of LWE):

Abhishek Banerjee, Chris Peikert, Alon Rosen.  Pseudorandom Functions and Lattices.  EUROCRYPT 2012.

It also has some discussion of related literature that might be helpful.



Also, here are two trivial observations.

First, there is a PRP that can be computed in $NC^1$ if and only if there is a PRF that can be computed in $NC^1$.  The "only if" part is immediate, as any PRP with large domain is also a PRF.  The "if" part follows from the Luby-Rackoff construction (i.e., the Feistel cipher), as that shows how to build a PRP out of any PRF; it increases the depth by only a constant factor.

Second, the following paper shows that no PRF can be computed by an AC0 circuit.

Nathan Linial, Yishay Mansour, Noam Nisan.  Constant depth circuits, Fourier transform, and learnability.  Journal of the ACM, 40(3):607--620, 1993.

It follows that no PRP can be computed by an $AC^0$ circuit.