3
$\begingroup$

A private-key encryption scheme Π = (Gen, Enc, Dec) has perfectly indistinguishable encryptions under a chosen-plaintext attack, if for all probabilistic polynomial-time adversaries A it holds that Pr[PrivK_cpa(n) = 1] = 1/2. I need to show that there is no encryption scheme that can satisfy this definition.

The perfect indistinguishably under a chosen-plaintext attack: Pr[PrivK_cpa = 1] = 1/2

implicates

the perfect indistinguishably in the presence of eavesdropper: Pr[PrivK_eav = 1] = 1/2.

Which, in turn, implicates perfect secrecy: Pr[Enc_K (m) = c] = Pr[Enc_K (m') = c] for all m, m' from M, c from C.

Is my argumentation correct to this point? If so, could you, please, tell how can I now find the contradiction between the scheme being perfectly secret and perfectly indistinguishable under a chosen-plaintext attack? Should I find the contradiction using the definition of the perfect secrecy (above-mentioned) or should I use the fact that |K| should be >= |M|?

I saw this post Is there such a thing as perfect CPA security? with the same question but it does not help as there the fact that Enc is probabilistic rather than deterministic is mostly discussed.

Improve this question
$\endgroup$
1
  • $\begingroup$ Perfect indistinguishability does not make any sense, since you would have to argue that exactly $0.5$ answer correctly. And for that you need to actually iterate somehow over all adversaries, if you restrict those to PPTs. Additionally, a CPA adversary trivially breaks deterministic encryption by querying both messages - so it makes sense to only consider probabilistic encryption. $\endgroup$
    – tylo
    Commented Jul 10, 2018 at 15:39

2 Answers 2

Reset to default
0
$\begingroup$

This notion does not really make sense since the way that perfect secrecy is reached is by there not being enough information in a given ciphertext to tell anything about the message, so without the key an attacker knowns nothing.

This is information theoretic security and is unbounded.

If we intruduce a encryption oracle, given enough time and adversary will find the message by trying them all untill one works.

We can add extra constraints like making the adversary ppt but then we are not longer talking information theoretic security.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ No need to introduce an oracle. An adversary can just try and encrypt all possible messages with all possible random input (if the cipher is non-deterministic). As long as the cipher is not perfectly secret it should be possible to determine that the correct plaintext was entered: just check if the ciphertext matches. Completely computationally infeasible of course, but yeah, theoretic security... $\endgroup$
    – Maarten Bodewes ♦
    Commented Aug 9, 2018 at 13:00
0
$\begingroup$

I suspect the answer to this question will somewhat depend on your definition of an encryption scheme. In particular, can the key have an infinite number of bits, and can the encryption function Enc be stateful (so that it can make sure to never use the same key bits twice)?

If the answer to both questions is yes, then I believe it should be possible to define a one-time-pad-like scheme that is perfectly CPA-secure. The basic idea is that the key should consist of (or can be bijectively mapped into) an infinite number of infinitely long bit streams, and the encryption algorithm stores a message counter. To encrypt a message, it first increments the counter, extracts the bit stream indicated by the counter from the key, takes the prefix of this bit stream equal to the message in length, and XORs it with the message. Finally, it prepends the current value of the counter to the message (in some manner that allows it to be unambiguously extracted by the decryption algorithm) and returns the result. If I'm not mistaken, a scheme like this should provide perfect secrecy for an unlimited number of messages, and thus be perfectly CPA-secure even against arbitrarily powerful adversaries.

On the other hand, if the encryption algorithm is not stateful (and so cannot remember which key streams it has already used), then there's a non-zero change that it will use the same key material to encrypt two messages. And if the key material itself is finite, then this must eventually happen after sufficiently many encryptions, whether the encryption algorithm is stateful or not. Either way, an attacker with unlimited oracle access can exploit this by repeatedly querying the oracle for encryptions of their challenge messages until the result matches the challenge ciphertext.

In fact, for non-stateful encryption algorithms, the attacker doesn't even need unlimited oracle access to have a non-zero advantage, since there's always a non-zero probability that even a single query will just happen to yield a match. We can make this probability negligible, but not zero. On the other hand, a stateful encryption algorithm could be designed to avoid reusing a keystream for any given number of encryptions, but only if the key was long enough to permit this. In particular, asymptotically, a super-polynomial number of queries before a keystream is reused would seem to require a super-polynomial key length (and thus, presumably, a super-polynomial running time for the key generator).

Improve this answer
$\endgroup$

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.