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
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)
