# Pseudorandom functions

The usual case to distinguish a pseudorandom function from a random function is to assume that the adversary can choose the plaintext blocks. Is there another case (game) in which the adversary can not choose the plaintext blocks ?

There are various adversary models, in fact it is typical to test our schemes against multiple adversaries to prove various nuances of security.

The most intuitive of all is an adversary that can produce the plaintext (or a part of it) given only the ciphertext. An extension to this model, stronger than the other, is the one you mentioned, letting the adversary select a number of plaintexts $n$ (which could be infinite), give him the ciphertexts and some random data and let him decide which is which.

In general we require the adversary to produce a result in polynomial time because while many of the primitives can in theory be broken, the probability of this happening in polynomial time is considered negligible.

• I don't remember seeing a model allowing the adversary to ask an infinite number of questions. It seems hard to formalize such a model without giving the adversary an infinite computing power. Do you have any pointer ? Jul 8, 2013 at 19:20
• Good point. The runtime of the adversary (algorithm) is determined by big-O notation $O()$ which does not make a claim on computing power available. The adversary doesn't always have to lose, he sometimes wins. However, an easy example of a scheme that isn't affected by computing power is the OTP.
– rath
Jul 8, 2013 at 19:29
• Yes,the OTP is not affected by the power of the adversary because it is information theoretically secure, but the OTP with keys of infinite length is rarely considered (but see: eprint.iacr.org/2010/001.pdf). However, for computation-based security, I only know of two options: concrete security (Bellare-Rogaway style) where the adversary's ressources are bounded and asymptotic security where the ressources are $O(\nu)$ where $\nu$ is the security parameter. Neither case seems to allow for infinite number of queries. Jul 8, 2013 at 19:47
• I noticed a typo in my previous comment. I meant $O(f(\nu))$ for some function. I think I misinterpreted what you meant by infinite. Reading your later comments, I now understand that what you wanted to convey is that the number of queries may tend to infinity asymptotically in the security parameter. I misunderstood and thought you spoke about actual infinity as in the paper I mentionned. Jul 8, 2013 at 20:47
• @rath. Done. I did not realize the confusion that was going on. To come back to the original question, a good thing to do is to look up the various style of IND-security, IND-KPA (know plaintext), IND-CPA (chosen plaintext), IND-CCA (chosen ciphertext). You also have IND$(ciphertext indistinguishable from random strings: cs.ucdavis.edu/~rogaway/papers/nonce.pdf). Instead of IND, you could also consider the ROR (real-or-random) security definitions. Jul 9, 2013 at 5:05 These are called weakly pseudorandom function families. • Thank you. Are weakly pseudorandom functions more general than pseudorandom functions ? Can pseudorandom functions be considered as Weakly ones to prove the security of a system that relies on PRFs but were the inputs can not be choosed by the adversary ? Thank you. Jul 9, 2013 at 6:27 • Yes, and those things should be clear from the definitions.$\:\$
– user991
Jul 9, 2013 at 7:09
• This doesn't seem to answer the question. Jan 31, 2014 at 17:43