Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 2 down vote favorite

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.

share|improve this question
2  
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

1 Answer

up vote 1 down vote

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.

share|improve this answer
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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