# 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 ?

-
Yes. You give a ciphertext and a random text to the adversary and ask him to distinguish between the two. That's just one possibility. At the risk of taking this question to the direction of reference request I suggest you search for adversary models. – rath Jul 8 '13 at 14:34
@rath You could as well have posted your comments as an answer since it sure answers the question. – e-sushi Jul 8 '13 at 18:57

## 2 Answers

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 ? – minar Jul 8 '13 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 '13 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. – minar Jul 8 '13 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. – minar Jul 8 '13 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. – minar Jul 9 '13 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. – Dingo13 Jul 9 '13 at 6:27 Yes, and those things should be clear from the definitions.$\:\$ – Ricky Demer Jul 9 '13 at 7:09
Thank you Ricky. – Dingo13 Jul 10 '13 at 9:43
This doesn't seem to answer the question. – figlesquidge Jan 31 '14 at 17:43