Talk:Pseudorandom function family

Cryptography: Computer science Low‑importance

	This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography articles
Low	This article has been rated as Low-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed as Low-importance).

Untitled

I don't know much about the subject, but "The guarantee of a PRG is that a single output appears random if the input was chosen at random" sounds a very empty guarantee. Any calculation, say, input + 42, or possibly even input + 0, would do this job. Surely the guarantee of a PRG is that the first few outputs aren't predictable, even though it may quickly become obvious that they aren't random.

Anyway I'm too naive about randomness to actually edit the page, and am probably just confused due to not reading other useful pages first. Also language seems very awkward in this area since "predictable" and "apparently random" both depend on the ability of a human to guess correctly whether they're dealing with a truly random process or not, and that itself has a probability which depends on the human and the outputs. (I can imagine a really annoying RNG, which appeared to be a PRG, but turned out just be giving results in a pattern. Or a really annoying human, who kept missing or doubting obvious patterns.) Oh, and also there's the little matter that there might not be any truly random processes, if physics is deterministic. Unpredictability seems to be the important thing. 213.122.25.1 (talk) 15:36, 17 January 2009 (UTC)[reply]

Pseudorandomness has a strict formal definition, see Pseudorandomness#Complexity-based_pseudorandomness. A distribution is pseudorandom if no efficient algorithm is a good statistical test to distinguish the distribution from random. It has nothing to do with humans guessing things. input+42 or input+0 would give a random output if the input is random, but pseudorandomness is only useful/meaningful when the output range is much larger than the input domain of the PRG/PRF (i.e., given k randomly chosen bits, generate 2k pseudorandom bits). BTW, Unpredictability and pseudorandomness are equivalent definitions, though I don't know that this is covered here on wikipedia. Anyway, the current article makes sense to me, but probably only because I wrote it! Of course any improvements / rewordings / missing wikilinks are welcome. Blokhead (talk) 16:59, 17 January 2009 (UTC)[reply]

I know what a PRF is, and I know what a PRG is, but that sentence was uncomprehensible to me, too. ;) If you want the differentiation in, please try to reformulate. Nageh (talk) 20:29, 6 April 2009 (UTC)[reply]

So much formalism?

Maybe the "Formal definition" section should be detailed. As is, it is difficult to understand. — Preceding unsigned comment added by 78.245.105.95 (talk) 18:00, 18 March 2020 (UTC)[reply]

i think it is fine for the formal definition to be formal. a description or rationale section could be added. however, i don't really see why the formulation insists on deferring the definition of n until later in the description, instead of defining it right away. it would lead to a clearer definition, and also closer to real world applications, in which function families always have a single security parameter. i also don't understand the role of lambda here, to me it sounds like unnecessary complication. idk. Krisztián Pintér (talk) 19:12, 18 March 2020 (UTC)[reply]