Most padding schemes for asymmetric encryption (OAEP, OAEP+) are only proven secure in the random oracle model. Although no attacks are known, it would be nice to find a padding scheme with provable security in the standard model. Are such padding schemes known?

  • $\begingroup$ sure, if you only want to encrypt a single bit per message, this is no problem. $\endgroup$ – SEJPM May 22 '16 at 18:38
  • 1
    $\begingroup$ @SEJPM : ​ That's only for IND-CPA, in which case one can similarly get O(log(k)) bits per message. ​ ​ ​ ​ $\endgroup$ – user991 May 22 '16 at 18:40
  • $\begingroup$ Or actually, even we've said so far depends on what you mean by "padding schemes". ​ Is it specifically "pairs $\langle \hspace{-0.03 in}$encode,decode$\hspace{-0.03 in}\rangle$ such that encode's range is a subset of the trapdoor injection's domain and [the PKE scheme whose encryption operation is their composition and whose decryption operation is the composition of decode with inverting the TDI] is secure"? ​ ​ ​ ​ $\endgroup$ – user991 May 23 '16 at 14:54

To the best of my knowledge, there is no padded scheme for RSA (or general trapdoor permutation) that has been proven secure in the standard model. To be exact, let's call a padded scheme one where a padding transformation is carried out independently of the public key, and then the trapdoor permutation is applied once to the result.

Of course, as noted, we can do this to encrypt log(k) bits. However, for more than that, we don't know much. There is a very interesting result by Smith and Zhang that shows that under a "lossy" assumption about RSA, it's possible to prove security for about 1/4 of the bits of RSA. Concretely, you can encrypt 249 bits using a 2048-bit modulus. This is quite good.

  • $\begingroup$ "Of course, as noted, we can do this to encrypt log(k) bits." Could you give a reference to that? $\endgroup$ – cygnusv May 24 '16 at 8:27
  • $\begingroup$ This is just the fact that any trapdoor permutation has a hard-core function of log(k) bits. See Oded Goldreich's foundation of cryptography. $\endgroup$ – Yehuda Lindell May 24 '16 at 8:51

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.