how to prove our algorithm is secure against chosen plaintext attack?

Question

I am working on a topic in cryptography where I have tried to develop an encryption scheme.

How could I prove mathematically that my algorithm is secure against chosen plaintext attacks?.
Will it be sufficient to say that as my algorithm is uniformly distributed, it is secure against chosen plaintext attacks?

You can show (for example) that the encryption of a chosen plaintext is indistinguishable from an element drawn uniformly at random from the ciphertext space. Stronger security models also assume that an attacker is getting access to an encryption oracle and/or a decryption oracle. — user94293, May 30 '16 at 14:05

cygnusv · Accepted Answer · 2016-05-30 14:52:30Z

9

The usual approach to prove IND-CPA security is to construct a logical argumentation called "reduction". In this argumentation you first start with the assumption that certain computational problem is hard (for example, the Decisional Diffie-Hellman assumption), and then you proceed to demonstrate that if your crypto scheme were insecure with respect to IND-CPA (which means that the adversary has access to an encryption oracle), then you could construct an algorithm that uses your scheme to break the hard problem. If our current knowledge dictates that indeed the chosen problem is hard, then your scheme must be IND-CPA-secure.
No. A trivial counterexample would be a deterministic encryption scheme. It is a well-known fact that an encryption function that is deterministic cannot be IND-CPA-secure. This is true regardless if its output is uniformly distributed.

answered May 30 '16 at 6:50

cygnusv

4,4421 gold badge16 silver badges38 bronze badges

$\begingroup$ What does it even mean to say the output is uniformly distributed? You won't have enough memory to store the full distribution of output + input bits. $\endgroup$ – user9070 May 30 '16 at 9:06
1

$\begingroup$ Dunno, but it doesn't matter :P $\endgroup$ – cygnusv May 30 '16 at 9:08
$\begingroup$ @cygnusv It is incorrect to say that deterministic public-key encryption cannot be be IND-CPA secure. I guess you meant "cannot be IND-CCA secure"; i.e., indinstinguishable under chosen-ciphertext attacks). $\endgroup$ – user94293 May 30 '16 at 13:59
1

$\begingroup$ @user94293 Nope, deterministic PKE cannot be CPA-secure: crypto.stackexchange.com/questions/22730/… $\endgroup$ – cygnusv May 30 '16 at 14:01
$\begingroup$ @TruthSerum I took "uniform distribution" to refer to the statistical quality of of the ciphers output (i.e. testing with ent for entropy/chi square/etc). $\endgroup$ – Ella Rose May 30 '16 at 15:55

| show 3 more comments

1 Answer 1