# PRP, PRF and modular arithmetic

Are there any arithmetic or mathematical functions that can be used as PRPs or PRFs ? Since, Conventional block ciphers like AES are that are proven to be good PRPs are not based on mathematics but on other principles like confusion and diffusion etc.

• Please edit your question to give a precise definition of what you mean by an "arithmetic function". Is AES an "arithmetic function"? How about cubing modulo a RSA modulus? Also, please elaborate on what you mean by "simulate". Finally, I suggest you add some context and motivation: why are you asking? what is the real goal? what research have you done to try to solve this on your own?
– D.W.
Commented Feb 24, 2014 at 17:58
• AES does not simulate a PRP, and a PRF ? I'm looking for functions based on hard mathematical problems, like factoring, or DH... Maybe the term "simulates" is not OK... ? Commented Feb 24, 2014 at 18:41
• Do you want DDH/RSA-based PRFs? If so, we have them and I will answer. Commented Feb 25, 2014 at 13:57
• @xagawa Yes, I want that :-) Commented Feb 25, 2014 at 16:49
• Are you asking for an arithmetic function $(k,x)\mapsto F(k,x)$ such that, for some random unknown $k$, $x\mapsto F(k,x)$ would be computationally indistinguishable from a random permutation or function? That seems to be a good question with some useful characterization of arithmetic, which is missing. Ultimately, AES or SHA-1 can be written as a long composition of arithmetic functions, if you consider $(a,b)\mapsto a\bmod b$ to be arithmetic. Any interesting definitions of arithmetic that I can think of uses a threshold; like, at most some number of operators.
– fgrieu
Commented Feb 26, 2014 at 13:30

Do you want DDH/RSA-based PRFs? If so, we have them and I will answer. – xagawa

@xagawa Yes, I want that :-) – Dingo13

I list the PRFs based on the number-theoretical assumptions. They are arithmetic or mathematical function.'' You can use the Feistel network to obtain (S)PRPs from PRFs in theory.

# From the DDH assumption

The Naor-Reingold Pseudorandom Function is a PRF based on the DDH assumption. Let $\mathbb{G}$ be a finite group of order prime $q$ with a generator $g$, on which the DDH problem is hard. Let $\{0,1\}^\ell$ be a domain. The function is defined as $$\mathrm{PRF_{NR}}(k, x) = g^{a_0 \prod_{i=1}^{\ell} a_i^{x_i}},$$ where $k = (a_0,a_1\dots,a_{\ell}) \in \mathbb{Z}_q^{\ell}$. For the proof, see the original article in J. ACM.

Lewko and Waters generalized the NR PRFs in CCS 2009 (and ePrint 2009/486). Their PRFs are based on the decisional linear assumption (and its weaker variants).

## Most efficient one

Under stronger assumptions such as the DHI assumption, we have a cute PRF, say, the Dodis-Yampolskiy PRF proposed as Verifiable Random Function (VRF).

Let $\{0,1\}^{\ell}$ be the domain of PRF. Suppose that $2^{\ell}$ is a polynoimal of the security parameter. The DY PRF is defined on a symmetric bilinear group as follows: $$\mathrm{PRF}_{DY}(k,x) = e(g,g)^{1/(x+k)},$$ where $k \in \mathbb{Z}_q$.

# From the factoring assumption

This is a classical result obtained by a combining the Blum-Blum-Shub PRG and the Goldreich-Goldwasser-Micali PRF from any PRG. Naor, Reingold, and Rosen improved efficiency of factoring-based PRFs. See the original article available at ECCC TR 2001-064,

# From the hardness of lattice problems

Nowadays, the lattice problems are often employed to construct cryptogrphic primitives. You can find the PRFs from lattices in Banerjee, Peikert, and Rosen (EUROCRYPT 2012), Alwen, Krenn, Pietrzak, and Wichs (CRYPTO 2013), and Banerjee and Peikert (ePrint 2014/074).

• I do not understand " $2^{\ell}$ is a polynoimal of the security parameter", and that has nothing to do with the minor typo. The answer is still great.
– fgrieu
Commented Feb 26, 2014 at 14:48
• Correctly speaking, the size of domain $2^{\ell}$ should be small, because the construction is based on $2^{\ell}$-DBDHI assumption. Commented Feb 26, 2014 at 14:51
• A note: the results in the Alwen et al paper are actually not strong enough to yield PRFs (contrary to what the paper says), because they are limited to an a priori bounded polynomial number of samples. Commented Aug 17, 2014 at 4:53

No. Conceptually , not so strongly close but similar ones that would come closer is $k$-wise Independent Distributions/Functions .

• I've downvoted this answer because I don't think it has sufficient explanation or depth Commented Feb 24, 2014 at 11:41
• I've upvoted it because I think it is correct and points the original poster to the key technical term, from which they can find more. You can look up what $k$-wise independent hash functions are pretty easily; I expect they're probably in Wikipedia and in good textbooks on derandomization/randomized algorithms.
– D.W.
Commented Feb 24, 2014 at 17:56
• Possibly. Even just the addition of a relevant link would I think satisfy my worries Commented Feb 24, 2014 at 18:16
• I believe , what could be found out from google , can be left for seekers exercise and save some time of one who answers it. Commented Feb 25, 2014 at 5:26