I have been learning about ROM in class and was wondering what an example of an encryption scheme that is multi-message secure in the random oracle model would look like? I have learned how to prove multi-message security in the standard model but I'm not sure how this translates to multi-message security in ROM, what are the main differences / things I need to look out for between these?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The random oracle model is needed, if you work with hash-functions and want to prove security with them. The reason is, that collision resistance often does not satisfy all condition you want for a proof.
For proofs under the ROM you need a cryptosystem that uses a Hash-function. One example is the RSA Full Domain Hash Signature. I think you learned about the reduction proof. When you build the reduction you have to simulate the RO. So if you assume an adversary for the reduction, you have to simulate the communication between the adversary and the RO. This is mainly just rewriting the definition of RO, but you can also make use of some tricks: The reduction knows the communication and the reduction can "program" the result of the RO. In Katz & Lindell's textbook (2nd edition) on page 448ff you can find such a proof for the RSA Full Domain Hash Signature.
I couldn't find a proof for EAV-Mult security under ROM. But it should be pretty similar to EVA-Mult in general, expect simulating the RO.
