Talk:Random oracle

Cryptography: Computer science Unassessed

	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
???	This article has not yet received a rating on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the importance scale.
	This article is supported by WikiProject Computer science.

ROM vs Random oracle articles?

Discussion copied from Talk:One way function.

But the Random Oracle Model is precisely such a definition (although many now consider it too idealistic to be achievable, even to an approximation). Unfortunately we don't yet have an article on the ROM. Arvindn 03:06, 18 Nov 2004 (UTC)

We have Random oracle - but this should be re-titled "Random Oracle Model" since that's mostly what it's about. It's possible a separate article on random oracles would be appropriate, or a redirect to ROM would be appropriate. The ROM isn't such a definition - it's an idealization. See the Random oracle article for more - including how no hash function can reach the bar the ROM sets. I've just heard about some interesting new problems with the ROM, but I can't quite follow the papers, so I've asked David Molnar for help...

I would be in favor of separate articles for "random oracle" and "random oracle model/methodology." The reason is that random oracles are of independent use in complexity theory, e.g. people are able to prove that complexity classes, relative to a random oracle, are the same/different with probability 1. (I don't know much more about this, though.) In contrast, in cryptography the random oracle model is a methodology for cryptographic design.

This discussion really doesn't have anything to do with one-way functions, though. Even cryptographic hash functions are a far cry from one-way functions; we desire completely different things from them. --Chris Peikert 22:00, 18 Nov 2004 (UTC)

Standard model versus Random Oracle

I was redirected from Standard Model (cryptography) to Random Oracle, suggesting that they are the same thing. Yet the article talks about '"random oracle model", as opposed to the "standard model". ' So are they not different?

I haven't really read the article, and I don't know anything about cryptography, but I'm already confused by this little thing. And I agree that Random Oracle Model would problably be a better name for the article. If Standard Model is a different thing, it's worth a separate article.--HelgeStenstrom 08:38, 25 April 2006 (UTC)[reply]

Constructing a random oracle

I imagine that a random oracle could actually be constructed using a database of all previous inputs and a true random input (perhaps a radioactive decay sensor). I foresee trust issues and database size issues. Meneth 09:53, 12 June 2006 (UTC)[reply]

I think you could come pretty close with a software implementation. Here's how: Run it on a Web server, so that every member of the public can and does use the same oracle. Keep the database sorted by input value by inserting each new input-output pair in the correct position. Then, a binary search can be used to check for previously used inputs as quickly as possible. New inputs could be generated using a CSPRNG. The program, including the CSPRNG, could be open-source, but the database and initial CSPRNG seed would be kept secret. (An attacker with the latter two pieces of information could predict the output for the next new input; hiding both adds some extra entropy.)

I would like to see some calculations on how closely this would resemble a true random oracle assuming (a) an ideal CSPRNG and (b) the best known CSPRNG. _SeahenNeon Merlin 03:30, 15 July 2006 (UTC)[reply]

Here's another thought on random oracles. Since time is a factor in real life security (has to be, to avoid reply attacks), how about a "5 minute random oracle" -- guaranteed to give identical, but random, results if the same string is presented within 5 minutes, and no guarantee after that. Since something 5 minutes old should be considered a fake anyways, would that suffice for a random oracle?

--Keybounce 19:07, 15 November 2006 (UTC)[reply]