5
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ "any PRP" with large domain "is also a PRF". $\:$ $\endgroup$
    – user6973
    Apr 15, 2015 at 0:44
  • $\begingroup$ I now notice that your last sentence has the corresponding problem. $\hspace{1.9 in}$ For example, "if keylength is zero then the input else the xor of the input with the $\hspace{.79 in}$ leftmost bit of the key" is a PRP family on $\{\hspace{-0.02 in}0,\hspace{-0.04 in}1\hspace{-0.03 in}\}$. $\;\;\;\;$ $\endgroup$
    – user6973
    Apr 16, 2015 at 5:59
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Apr 16, 2015 at 9:24
  • $\begingroup$ Hmm. $\:$ More of them seem to define it that way than the way I'd thought. $\:$ (So you're right about that not being an issue.) $\:$ However, handling infinitely many input lengths is not necessary for the asymptotics to kick in, since my construction can handle arbitrary key lengths. $\;\;\;\;$ $\endgroup$
    – user6973
    Apr 16, 2015 at 9:42

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.