<p>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):</p>

<p>Abhishek Banerjee, Chris Peikert, Alon Rosen.  <a href="http://www.cc.gatech.edu/~cpeikert/pubs/prf-lattice.pdf" rel="nofollow">Pseudorandom Functions and Lattices</a>.  EUROCRYPT 2012.</p>

<p>It also has some discussion of related literature that might be helpful.</p>

<hr>

<p>Also, here are two trivial observations.</p>

<p>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.</p>

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

<p>Nathan Linial, Yishay Mansour, Noam Nisan.  <a href="http://www.cs.columbia.edu/~rocco/Teaching/S12/Readings/LMN.pdf" rel="nofollow">Constant depth circuits, Fourier transform, and learnability</a>.  Journal of the ACM, 40(3):607--620, 1993.</p>

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

CC BY-SA 3.0
2015-04-16T09:24:35.443Z
@RickyDemer, in complexity-theoretic crypto, if I recall correctly, a PRP is technically an infinite family of PRPs $\{\pi_n : n \in \mathbb{N}\}$, indexed by $n$, where $n$ is the length of the input.  (This is necessary for the asymptotics to kick in.)  So if a PRP exists, then there exists one where the input size is large enough.  Therefore, this doesn't seem like it's actually an issue.  Am I missing something?  I suspect you know this area better than I.
D.W.
CC BY-SA 3.0
2015-04-14T20:35:23.273Z
2015-04-15T04:33:28.853Z
2015-04-15T04:33:28.853Z
D.W.
<p>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.</p>

<p>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.)</p>

<cr.crypto-security><circuit-complexity><pseudorandomness>
Simple candidates for pseudorandom permutations?
Adam Lelkes
# Simple candidates for pseudorandom permutations?

(Asked by: username_0 on 2015-04-14)

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

**Tags:** cr.crypto-security, circuit-complexity, pseudorandomness

---

## 1 answers

### Answer by username_1 on 2015-04-14. Score: 4 | Accepted answer

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](http://www.cc.gatech.edu/~cpeikert/pubs/prf-lattice.pdf). 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](http://www.cs.columbia.edu/~rocco/Teaching/S12/Readings/LMN.pdf). Journal of the ACM, 40(3):607--620, 1993.

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

> **Comments:**
> **username_1**: @RickyDemer, in complexity-theoretic crypto, if I recall correctly, a PRP is technically an infinite family of PRPs $\{\pi_n : n \in \mathbb{N}\}$, indexed by $n$, where $n$ is the length of the input.  (This is necessary for the asymptotics to kick in.)  So if a PRP exists, then there exists one where the input size is large enough.  Therefore, this doesn't seem like it's actually an issue.  Am I missing something?  I suspect you know this area better than I.  

---

