I know that Dual_EC_DRBG's security is based on the ellitpic curve discrete logarithm problem, Micali-Schnorr is based on the difficulty of factorization, and MQ_DRBG is based on multivariate cryptography. Are there any others based on known hard problems instead of intricate designs?

  • $\begingroup$ Do you consider reversing a (particular) cryptographic hash or CCA against a particular cipher a "known hard problem"? Or are we restricting ourselves to known hard mathematical problems/prims. $\endgroup$ – Thomas M. DuBuisson Feb 16 '15 at 17:47
  • $\begingroup$ @ThomasMDubuisson I'm restricting it to known hard mathematical problems. Reversing a hash, while difficult, I'm told is not something that has security proofs like RSA, Diffie-Hellman, and the like. In other words, hashes are more or less designed by trial-and-error. $\endgroup$ – Melab Feb 16 '15 at 18:44
  • $\begingroup$ Algorithms can be designed on proven trapdoor/one-way functions. The Feistel construction (have a look at the simple picture in en.wikipedia.org/wiki/Feistel_cipher ), either used as hash, cipher , padding or PRG, has crypto-analysis and security evaluations ( iacr.org/archive/crypto2003/27290510/27290510.pdf ). $\endgroup$ – Pierre Feb 16 '15 at 21:12
  • 1
    $\begingroup$ @Melab: can you please point me to the security proofs for RSA or Diffie-Hellman? That is, the ones that don't start off assuming that the "RSA problem" or the "Diffie-Hellman problem" is hard? $\endgroup$ – poncho Feb 17 '15 at 15:09
  • 1
    $\begingroup$ There is Blum-Blum-Shub, which is related to factoring. But the security proof isn't very tight. $\endgroup$ – CodesInChaos Feb 17 '15 at 23:22

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.