Proving the semantic security of the One Time pad
Currently hearing a lecture on cryptography, and the professor gave us the definition of semantic security, which is roughly the following (formally not quite complete, but you get the idea):
Given a function $ INFO(1^n,m) $ which determines the information the attacker is interested in (e.g. $ INFO(1^n,m)=m $ would mean that the attacker wants to know the plaintext message $ m $ ) and any polynomial-time attacker $ A(1^n,C) $ in posession of the cipher text $ C $ , it is possible to construct a Simulator $ S(1^n) $ without knowledge of the cipher text that has an equal chance of determining $ INFO(1^n,m) $ .
(From reading this stackexchance, it seems like the definition of semantic security that others use here is what was called Indistinguishability (IND) in our lecture. I am not interested in IND, only in semantic security as outlined above)
He then proceeded to talk about how the one-time-pad (OTP) fulfills this requirement, and offered the beginning of a proof. The basic idea of the proof went something like this:
Given any attacker $ A(1^n,C) $ , we construct the Simulator $ S(1^n) $ in the following way: $ S $ will pick a random binary string $ C \leftarrow {0,1}^n $ and then return the result of $ A(1^n,C) $ . This would mean that the chance of $ S $ to succeed would be as high as the chance of $ A $ .
Now, to me, that does not make any sense. I mean, it works if you already know that the OTP is secure and that the chance of $ A $ to succeed is $ 2^{-n} $ (for $ INFO(1^n,m)=m $ ), because $ S $ also has a chance of $ 2^{-n} $ to pick the correct binary string. But as we are trying to proove the security, we can’t argue that way. And as soon as we can no longer use that knowledge, the proof no longer works in my eyes.
I tried to come up with a proof of the semantic security of the one time pad, and failed so far. I also tried to find an existing proof on the internet, and failed as well. I would have an idea on how to proove indistinguishability, and as far as I know, IND and semantic security are practically equivalent, but I’d be interested in a proof using the above definition.
Any pointers to existing proofs I may have overlooked, or pointers on how I could proove this myself, would be appreciated. Alternatively, an explanation on how the proof the professor outlined could actually work would be appreciated as well. This is not homework, I am doing this because I am interested in the subject matter and because I will go mad if I cannot find a proper proof or an explanation why the proof by the professor works.
The proof for the perfect secrecy property of the one time pad is quite simple.
It makes use of basic probabilities and it says that:
$$ Pr[M=m|C=c]=Pr[M=m] $$ for a probability distribution M $ {0,1}^n $ for the message space and a probability space C for the ciphertext space.
Proof:
- $$ Pr[C=c]=\sum{Pr[C=c|M=m’]\cdot Pr[M=m’]} =\sum{Pr[K=m’\oplus c]}\cdot Pr[M=m’] =\sum{2^{-n}}\cdot Pr[M=m’] =2^{-n} $$
- (from bayes theorem)$$ Pr[M=m|C=c] = \frac{Pr[C=c|M=m]\cdot Pr[M=m]}{Pr[C=c]} = \frac{Pr[k=m \oplus c]\cdot Pr[M=m]}{2^{-n}} =\frac{2^{-n}\cdot Pr[M=m]}{2^{-n}} =Pr[M=m] $$
What the last equation states, is the following: The success probability of an attacker to correctly guess the plaintext m by inspecting its ciphertext c is equal with the probability of correctly guessing the message without obtaining its ciphertext. The latter argument is the perfect secrecy property.
Perfect secrecy is hard to achieved in real world due to its two constraints:
- It’s one time: the key should be used only for 1 encryption
- The key should be as long as the underlying message
So people started to think:"…hmmm maybe we can weak this security definition in order to be more efficient in practise…". And they end up with the computational semantic security which relaxes the perfect secrecy as follows: No polynomially bounded adversary can with non negligible probability infer any information from the ciphertext. This is the semantic version and the indistinguishable version states that no polynomially bounded adversary can with non negligible probability distinguish two ciphertexts.
In real world the second drawback can be mitigated with the use of pseudorandom generators that very briefly take as input a short “random” looking seed and produce a longer pseudorandom number that is indistinguishable from random. In order to come up with the proof following the reductionist approach for the security of the one-time-real-world pad we substitute the key k with the outputs of a PRG and we make the assumption that PRG outputs are indistinguishable from random. The proof now for its semantic security (which is equivalent with IND security) proceeds as follows:
Assuming that $ \mathcal{A} $ breaks the semantic security of our OTRWP attacker $ \mathcal{B} $ that tries to break the security of the PRG will use it to break PRG security. If we manage to do so we will end up in a contradiction so the truth statement would be that OTRWP is secure. Let’s see how it briefly works: Whenever $ \mathcal{A} $ is asking for encryption of messages m the attacker $ \mathcal{B} $ :
- Gets the output of the PRG when it is fed up with a seed that comes from a uniform distribution.
- Gets the output of the PRG when it is fed up with a pseudorandom seed.
We made the assumption that PRG is pseudorandom so the success probability of $ \mathcal{B} $ distinguishing between 1 and 2 is negligible: $ Pr[|PRG_{pseudorandom seed}-PRG_{uniform seed}|]=neg(1^k) $ But $ Pr[PRG_{pseudorandom seed}] $ is exactly equal the probability of the OTRWP for attacker A and $ Pr[PRG_{uniform seed}]=1/2 $ because it is independent from the view of $ \mathcal{A} $ .
So:
$$ Pr[\mathcal{A}^{OTRWP}]=neg(1^k)+ 1/2 $$ which concludes the proof.