I don't really get how this problem should be solved. My main issue is with the random oracle generally, a short explanation of ROs and how they are used in such proofs maybe with this example will hopefully clear that up.

Consider the RSA-based encryption scheme in which a user encrypts a message $m ∈ \{0,1\}^{l}$ with respect to the public key $(N, e)$ by computing $$m':= H(m)\|m$$ and outputting the ciphertext $$c:=m'^{e} \mod N.$$ (Here,let $H:=\{0,1\}^{l}→ \{0,1\}^{n}$ and assume $l+n<\|N\|$, the bit-length of $N$). The receiver recovers m' in the usual way and verifies that it has the correct form before outputting the $l$ least-significant bits as $m$. Prove or disprove that this scheme is CCA-secure if H is modeled as a random oracle.

  • $\begingroup$ Random oracle (RO) quite clear, right? $\endgroup$
    – kelalaka
    Jan 16, 2019 at 22:08
  • $\begingroup$ @kelalaka yes, as a concept on its own.. don't know how to use it practically in the example. $\endgroup$
    – randomMe
    Jan 16, 2019 at 22:17

1 Answer 1


Consider the weaker IND-CPA case. "Textbook RSA" is not CPA-secure since it is deterministic. Hence, you can encrypt both your messages and compare them with the challenge-message. Is your modified RSA scheme also deterministic?

Hint: $H$ is chosen at the beginning of the CPA-game.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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