Question

a) What does indistinguishability mean when we say that two ciphertexts are indistinguishable in a CPA attack? What does indistinguishability mean when we say that two successive games are indistinguishable in a security proof?

b) Can these two notions of indistinguishability rely on different underlying computational hardness assumptions? Can they rely on the same underlying computational hardness assumption? (Explain the implications of each approach.)

Answer 1

A)Ciphertext indistinguishability is an important security property of many encryption schemes. Intuitively, if a cryptosystem possesses the property of indistinguishability, then an adversary will be unable to distinguish pairs of ciphertexts based on the message they encrypt.

The property of indistinguishability under chosen plaintext attack is considered a basic requirement for most provably secure public key cryptosystems, though some schemes also provide indistinguishability under chosen ciphertext attack and adaptive chosen ciphertext attack.

Security in terms of indistinguishability has many definitions, depending on assumptions made about the capabilities of the attacker. It is normally presented as a game, where the cryptosystem is considered secure if no adversary can win the game with significantly greater probability than an adversary who must guess randomly.

Consider a selective security notation defined as two games H0 and H1 being indistinguishable .A security proof often uses a hybrid argument : one defines a sequence of hybrid games(H0......HT) where the first and last game corresponds to the original selective games(i.e. H0=H0 and H1=HT). One then proves that any two consecutive hybrids are indistinguishable .

B) Computational hardness assumptions are of particular importance in cryptography. A major goal in cryptography is to create cryptographic primitives with provable security. In some cases, cryptographic protocols are found to have information theoretic security; the one-time pad is a common example. However, information theoretic security cannot always be achieved; in such cases, cryptographers fall back to computational security.