3
$\begingroup$

When I read the definition of the CPA indistinguishably encryption scheme, I see that the adversary can use an oracle as many times (to get as many encryptions of any messages it choose). An the end of the experiment, it has to distinguish between two messages $m_0$ and $m_1$ while it gets $c_b$ (from some challenger), which may be one of $m_0$ and $m_1$ encryptions.

But what if the adversary uses the oracle to get the encryptions (of $m_0$ and $m_1$)? Does that mean the encryption algorithm uses some probabilistic way and generates an exponential ciphertext space for every key, which does not give the adversary a polynomial advantage?

$\endgroup$
3
$\begingroup$

Yes, your intuition is completely right (assuming a polynomial-time adversary and a super-polynomial message space, which is the usual setting). If the scheme were deterministic, then the adversary could simply use the oracle to distinguish which message was encrypted. Therefore, no deterministic encryption can be CPA-secure. This is a well-known implication of the definition of CPA-security.

$\endgroup$

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.