Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
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. Feb 24 '14 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... ? –  Dingo13 Feb 24 '14 at 18:41
Do you want DDH/RSA-based PRFs? If so, we have them and I will answer. –  xagawa Feb 25 '14 at 13:57
@xagawa Yes, I want that :-) –  Dingo13 Feb 25 '14 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 Feb 26 '14 at 13:30

2 Answers 2

up vote 7 down vote accepted

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

share|improve this answer
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 Feb 26 '14 at 14:48
Correctly speaking, the size of domain $2^{\ell}$ should be small, because the construction is based on $2^{\ell}$-DBDHI assumption. –  xagawa Feb 26 '14 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. –  Chris Peikert Aug 17 '14 at 4:53

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

share|improve this answer
I've downvoted this answer because I don't think it has sufficient explanation or depth –  figlesquidge Feb 24 '14 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. Feb 24 '14 at 17:56
Possibly. Even just the addition of a relevant link would I think satisfy my worries –  figlesquidge Feb 24 '14 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. –  sashank Feb 25 '14 at 5:26
Thanks for the edit sashank, it's better. –  Dingo13 Feb 25 '14 at 6:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.