3 | Public Key Cryptography
4.6 Semantic Security
attack can then begin by Mallory intercepting this communication. She keeps the key for herself, and sends a forged message to Alice that give the impression of coming from Bob. Instead this is Mallory’s public key. Alice, believing this public key to be Bob’s, encrypts her message with Mallory’s key and sends the encrypted message back to Bob.
Mallory again intercepts, decrypts the ciphertext using her private key, possibly alters it if she wants, and re-encrypts it using the public key Bob originally sent to Alice. When Bob receives the newly encrypted message, he believes it came from Alice.
Both the chosen-ciphertext attacks and the man-in-the-middel attacks can be encoun-tered for, or they may be of no concern in the environment in which the public key encryption scheme is to be used, but subject is out of scope for this thesis.
4.6 Semantic Security
A public key cryptosystemhasto be secure in the chosen-plaintext model, if it is supposed to offer any security at all. This is so because the encryption key is public, so if the adversary wants to encrypt some messages of her choosing, she can just do it. So in the rest of this thesis, if nothing else is said, we are situated in the chosen-plaintext adversarial model, and the standard security model.
The ideal encryption scheme would be one that for every ciphertext, the probability of finding the corresponding message only given the public key, should be negligible.
Definition 4.10. A function f from the natural numbers to the non-negative real numbers is negligible if for every positive polynomial pol there is a T such that for all integerst > T it holds thatf(t)< pol(t)1 , [21].
As we talked about in the beginning of this chapter, it is not possible to use such ideal encryption schemes in practice. Instead we need another definition of security in the chosen-plaintext model. The answer to this is the notion of semantic security.
Semantic security is the computational complexity analogue to Shannon’s concept of information-theoretical security, and it is often called complexity-theoretical security.
What we want to show is that given the ciphertext of a certain message m, and maybe also the length of the message, we cannot determine any partial information of the mes-sage with probability non-negligibly higher than all other ppts that only have access to
44 Chapter 4. Security
the length of the message (and not the ciphertext). This is the same as saying that knowledge of the ciphertext (and maybe the length) of some unknown message does not reveal any additional information on the message that can be feasibly extracted. The notion of semantic security intuitively says that a ppt adversary cannot effectively dis-tinguish between the encryption of two messages of his choosing. In [32], Victor Shoup formalize this as a game between an adversary and a challenger:
Definition4.11. A public key cryptosystem defined by(K,E,D)isindistinguishability under chosen plaintext attack, abbreviatedIND-CPAif the outcome of the following game between a challenger and a ppt bounded adversary satisfies the probability requirements defined below:
1. The challenger generate a pair of keys(ek, dk) by runningK.
2. The adversary (who knowsdk and can perform any ppt bounded number of oper-ations) chooses two distinct messagesm0 andm1 from the possible plaintexts, and gives them to the challenger.
3. The challenger selects a bit b∈ {0,1}, computes c=E(dk, mb) and gives c to the adversary.
4. The adversary (still able to perform any ppt bounded number of operations) output the valueb0 for which she thinks the message m0b is the decryption of c.
The advantage of the adversary, defined as P(b=b0)−12, is negligible.
Definition 4.12. We define a public key cryptosystem to be semantically secure if it satisfies the IND-CPA requirement. In this case, we assume that the cryptosystem is secure in the chosen-ciphertext model.
It is important to notice that an encryption algorithm that are not probabilistic, will not be secure in this model. It is enough noticing that in this case, the adversary can just compute the ciphertext ofm0 and m1, and by this be able to choose which message the ciphertextc belongs to with probability one.
The IND-CPA proves in this thesis are very simple, so it goes without saying that the advantage of the adversary is negligible.
There is also a similar concept which is known to be equivalent to IND-CPA.
Definition 4.13. A public key cryptosystem defined by (K,E,D) is real-or-random
4.6. Semantic Security 45
secure, abbreviatedRoR if the outcome of the following game between a challenger and a ppt bounded adversary satisfies the probability requirements defined below:
1. The challenger generates a pair of keys (ek, dk)by running K.
2. The adversary (who knows dk and can perform any ppt bounded number of oper-ations chooses a messagem0 and gives it to the challenger.
3. The challenger chooses a random message m1, a bit b ∈ {0,1}, computes c = E(dk, mb) and givesc to the adversary.
4. The adversary outputs the valueb= 0if she thinks the messagem0bis the decryption ofm0and the valueb= 1if she thinks the messagem0bis the decryption of a random message.
The advantage of the adversary, defined as P(b=b0)−12, is negligible.
Proposition4.14.
For a public key cryptosystem, IND-CPA ⇔ RoR.
Proof. We will now show an example of how we can use games to prove a statement.
⇒: This is the same as proving that if we have an adversary, AROR with non-negligible advantage in the RoR game, then we can create an adversary AIND with non-negligible advantage in the IND-CPA game. We do as follows:
1. AROR start a RoR game by choosing a messagem0.
(a) We start a IND-CPA game by choosing two messages m˜0 =m0 and m˜1
and send it to the challenger.
(b) The challenger selects a bit b ∈ {0,1}, computes c = E(dk, mb) and outputsc.
(c) We sendcto AROR.
2. AROR decides ifcis an encryption ofm0 or a random message.
(a) IfAROR says m0, we saym0.
(b) IfAROR says random message, we say m1.
IfAROR win, we win. So if AROR has an non-negligible advantage then we have a non-negligible advantage.
⇒: We will not prove this here, but refer the interested reader to [15]
46 Chapter 4. Security