Talk:Random oracle

From Wikipedia, the free encyclopedia

WikiProject on Cryptography This article is part of WikiProject Cryptography, an attempt to build a comprehensive and detailed guide to cryptography on Wikipedia. If you would like to participate, you can choose to edit the article attached to this page, or visit the project page, where you can join the project and see a list of open tasks.

Contents

[edit] 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)

[edit] 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)

[edit] 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)

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. SeahenNeonMerlin 03:30, 15 July 2006 (UTC)
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)
The 5-minute oracle could have some neat applications! But of course it wouldn't work for everything (for example, md5sums for CD images), since some hashes need a long lifetime. As to using a CSPRNG for an actual random oracle, that undoes the value of building an actual random oracle -- if you're going to rely on algorithms, why not just use a normal hash function? True random bits aren't that hard to generate compared to the effort of setting up an online service. Lunkwill 20:45, 18 November 2006 (UTC)
Wouldn't true random bits require something like HotBits, gathering information from radioactive decay? Ruakh 21:17, 18 November 2006 (UTC)
Most physical processes involve some true randomness. Decay is unquestionably random, but pointing a video camera at a lava lamp also involves a huge amount of true randomness. See Hardware random number generator. Lunkwill 08:21, 19 November 2006 (UTC)
Hmmm, but if the oracle is queried at t = 0, t = 4, and t = 8, the first two results must be equal, and the second two results must be equal, so the first and third results must be equal. So the 5-minute oracle practically reduces to a regular random oracle, unless it actually kept a list of which inputs were "live" and created a new random output iff the input was not in the "live" table. (or just creates a new result whenever a "live" input times out). —Preceding unsigned comment added by 152.23.52.55 (talk) 18:37, 5 September 2007 (UTC)

[edit] Random oracle does not imply mathematical problem believed hard

"Such a proof generally shows that a system or a protocol is secure by showing that an attacker must require impossible behavior from the oracle, or solve some mathematical problem believed hard, in order to break the protocol."

I'm not an expert but I do not believe that the random oracle models demonstrates an attacker must ``solve some mathematical problem believed hard." I think this is a property of complexity theoretic security (or computational security). See also Provably secure, the discussion page may be of more use. Bah23 10:05, 8 May 2007 (UTC)

[edit] What does, "No real function..." mean?

The last paragraph of the article says, "No real function can implement a true random oracle."

I seems as if the author was trying to say that there is no practical way to write a computer program that behaves like a random oracle. That would make sense: The only conceivable way to do it is with a lookup table that maps each possible input to the corresponding output—Somewhat of a problem if the domain is infinite.

I would change the section myself if I weren't too much of a tyro to know for sure... Maybe a real function is something special that I don't understand. (I thought a random oracle was a function.) Maybe it's some obscure term of art when somebody says that a function implements something.

I wish that someone who knows better than I would edit that section to make it more clear. —Preceding unsigned comment added by 192.55.12.36 (talk) 17:27, 19 May 2008 (UTC)


O.K., after reading a little further on the subject, I bet that about three paragraphs worth of the article could be boiled down to two sentences;

  • In cryptography, a random oracle is an ideal hash function, H(m), that can not computed by any computer program smaller than the complete lookup table for H(m), and
  • A cryptographic protocol is "provably secure in the random oracle model" if it is provably secure when random oracles are substituted for the actual hash functions used in the protocol.

Any comments? 192.55.12.36 (talk) 18:31, 19 May 2008 (UTC)