Talk:Ciphertext indistinguishability

References would be nice! —Preceding unsigned comment added by 141.201.6.60 (talk) 12:50, 25 February 2008 (UTC)

Incorrect definition for IND-CPA

I've changed the previous definition, which was as follows:

A cryptosystem is indistinguishable under chosen plaintext attack if no adversary can win the above game with probability greater than $(1/2)+\epsilon$, where $\epsilon$ is a negligible function in the security parameter k...

This definition is incorrect, because clearly $\epsilon =0$ is a negligible function, but there exists adversaries which which have a winning probability greater than 1/2. Moreover the term negligible function redirected to Colombeau algebra, where negligible functions have a different definition. To avoid confusion the link was removed. 62.167.39.178 17:49, 28 May 2006 (UTC)

Minor Tweak

Added the bolded portion to this sentence: "and comparing the resulting ciphertexts with the challenge ciphertext does not afford any non-negligible advantage to the adversary." Since clearly there might be some nonzero advantage to an adversary with this strategy.

Adversary in form of a probabilistic polynomial time machine

In my Opinion it should be described earlier in the article, that the attacker is in form of a probabilistic polynomial time machine. This is import because otherwise it would be possible for the attacker to just encrypt every possible plaintext. Yes, I know it is described in the certain subsections, but I think it should mentioned it the introduction in form of 'there exists no effictive adversary' and in detail in the formal definition section. (I would prefer it could do somebody else because my english isn't the best, but if not I could try it when I have time). --Wohingenau (talk) 19:44, 29 March 2010 (UTC)

Indistinguishable from random noise => CPA

I am removing the following section:

If an encryption algorithm E can be designed such that an attacker (typically defined as a polynomial-time observer) who knows a plaintext message m is unable to distinguish between E(m), the encryption of that message, and a freshly-generated random bit string of the same length as E(m), then it follows that when E(m1) is the same length as E(m2), those two encrypted messages will be indistinguishable from each other by that attacker, even if that attacker knows the plaintext m1 and m2 (IND-CPA).

This is not true, or at least not formulated correctly. Assume a secure (doesn't really matter by which definition) encryption algorithm indistinguishable from random noise E'_k'(m) with the key generation function Gen'() (assumed for simplicity to return a bit string). Construct the following encryption function:

- Gen():

 - k' ← Gen'()
 - p_0 ← {0,1}^|k'|
 - k ← (k', p_0, p_0 xor k')

- Enc_(k', p_0, p_1)(m):

 - b ← {0, 1}
 - c ← E'_k'(m) || p_b

p_0 is indistinguishable from uniformly random because it is picked randomly. p_1 is indistinguishable from uniformly random because p_0 is, and k' is not picked dependent on p_0. Thus, given a single ciphertext, you cannot distinguish that ciphertext from a uniformly random string, even given the plaintext. However, if you have *two* ciphertexts, there is a 0.5 chance that different ps are revealed, at which point you can simply do k'=p_0 xor p_1, allowing you access to the key of E' and thus allowing you to decrypt the ciphertext and distinguish.

The basic idea of this counterexample is leaking half the key per encryption, which means you cannot attack a single ciphertext but the attack becomes possible with two or more ciphertexts. There is

There is also the issue that IND-CPA is not the same as "encrypted messages will be indistinguishable from each other by that attacker, even if that attacker knows the plaintext m1 and m2" as the removed paragraph suggested, because under CPA the attacker gets to pick the messages and gets an encryption oracle too.

The source also does not state what is said here sufficiently. There may be a way to formulate a similar statement that would make it correct, however since the source given is not sufficient for this and there are at least two issues with it, I am not going to try to find a better version.

Yawkat (talk) 18:14, 22 February 2019 (UTC)

References