I have reading about how to bring provable security for cryptographic schemes. There are two models: the standard model and the random oracle model. In random oracle model, is necessary to idealize hash functions, and in the standard model are use reductions from crypographic porotocols to well-known NP-problems. My question is why exist the random oracle model?

I make this question because I think that exist reductions from hash functions to NP-problems. For example, in order to reduce SHA-256 to the the SAT problem, we can represent the algorithm SHA-256 in GF(2) expressions and then, we could convert these to boolean expressions.

  • $\begingroup$ The ROM makes stronger assumptions about hash functions which are useful in proofs, but of course is "further from reality" than the standard model. $\endgroup$ – SEJPM Dec 10 '17 at 14:26
  • 1
    $\begingroup$ ok @SEJPM but why no reduce hash functions to SAT problem? and then bye bye ROM? $\endgroup$ – juaninf Dec 10 '17 at 14:30
  • 1
    $\begingroup$ Must read: M. Bellare and P. Rogaway, Random oracles are practical: A paradigm for designing efficient protocols. It explains why the Random Oracle assumption leads to simple proofs of useful protocols. $\endgroup$ – fgrieu Dec 10 '17 at 14:57
  • $\begingroup$ @fgrieu then the ROM there exits because it is necessary simple proofs? $\endgroup$ – juaninf Dec 10 '17 at 15:33
  • $\begingroup$ Yes. One reason the ROM is popular is because assuming a hash function is secure in the ROM allows a clean proof that it is safe to use that hash in some protocol. $\endgroup$ – fgrieu Dec 10 '17 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.