RSA-OAEP versus RSA with Fujisaki-Okamoto construction

I was wondering why the Fujisaki-Okamoto construction (or one of its variants) is not (at least commonly) used with RSA to achieve CCA2 security? Does anyone know of any speed comparisons between RSA w/ F-O and RSA-OAEP? Perhaps the reason is simply historical since F-O is newer.

-
Do you have a link to a description of this construction? Looks like I'm too tired now to find it on Google. –  Paŭlo Ebermann Mar 7 '12 at 19:29
add comment

1 Answer

The Fujisaki-Okamoto construction requires a non-deterministic public key encryption scheme. Textbook RSA is not randomized, but deterministic, and so it cannot be applied to it to obtain CCA-security. It can be applied to schemes like Elgamal and Paillier that take randomness to create indistinguishable encryptions of the same message.

-
What if I use padded RSA by padding with a constant number of random bits? Then if $H_1$ and $H_2$ are two hash functions, $e$ the public exponent, $m$ the message and $r$ a random number, encryption would be $$m \mapsto <(r||H_1(r,m))^e, H_2(r)\oplus m>$$ and this seems to be much easier than OAEP. –  Kim Mar 7 '12 at 23:57
There seem be a hundred CCA-secure variants of Elgamal. It generally comes down to efficiency, ciphertext size, and your appetite for non-standard assumptions (random oracles, weird DH variants, etc). There is a good relatively recent paper that proposes a Elgamal variant (based on a new "twin DH" assumption) that does a nice job comparing to Elgamal, hashed Elgamal, FO Elgamal & Cramer-Shoup: iacr.org/archive/eurocrypt2008/49650126/49650126.pdf That is just scratching the surface: there is Naor-Young and a bunch of key encapsulation mechanisms (KEM) –  PulpSpy Mar 8 '12 at 0:11
(That was in reply to your previous comment). –  PulpSpy Mar 8 '12 at 0:13
In terms of your RSA construction, it is hard to say without trying to find a reduction. These things are very tricky. It does have a larger ciphertext than RSA-OAEP which is a drawback. (Also, "easier" isn't typically a design parameter. Unless if you mean more efficient or a more direct reduction to a known intractable problem. But easier to implement, to understand, etc., get trumped by efficiency.). –  PulpSpy Mar 8 '12 at 0:20
Thanks. By easier I meant possibly faster to compute but I guess the F-O type construction is really complicated, like you said, and outside the random oracle model it's really hard to say anything. –  Kim Mar 8 '12 at 1:08
add comment