Hi this question is regarding a proof from the book "INTRODUCTION TO MODERN CRYPTOGRAPHY" (https://eclass.uniwa.gr/modules/document/file.php/CSCYB105/Reading%20Material/[Jonathan_Katz%2C_Yehuda_Lindell]_Introduction_to_Mo(2nd).pdf?fbclid=IwAR1hf1OTKAhf4ZHvswERpcZ3ZVDQMxHuP2FWRg2tvlo3-tUMSdFIPLWZR_8) by katz & lindell page 30. The question does contain some specific cryptography notation that will be implicit, it is explained very well in the book. First we have this definition of perfect secrecy:
Pr[M=m | C = c] = Pr[M = m]
And then we have this definition of perfect secrecy:
Pr[EncK(m)=c] = Pr[EncK(m') =c].
and now I have the following lemma:
An encryption scheme(Gen,Enc,Dec) with message spaceMis perfectly secret if and only if Equation
(2.1) holds for everym, m′∈Mand every c∈C.
so we want to improve indistinguishability implies perfect secrecy. indistinguishability -> perfect secrecy.
There then is a proof that starts with perfect secrecy, and ends up at
Pr[M=m | C = c] =
= ....
= ....
= Pr[M = m]
The proof is not so much what I want to ask about, it is moreso the general structure.
If I want prove indistinguishability -> perfect secrecy or A -> B, wouldnt it make the most sense to start with A, and then do a bunch of algebra, until I reach B, such that I can prove that they are the same. Such that my proof would look like A = = ... = ... = B in the proof for perfect secrecy, in my mind all we seem to be doing is showing at perfect secrecy is.. perfect secrecy?
So could someone put into natural language what the general idea in a proof like this is
I'll try an educated guess.
$A==\ldots =\ldots =B$ would be a proof of $A=B$, not of $A\to B$. Here we are rather in a situation where the proposition $B$ itself is of the form $X=Y$. So the proof that $A\to B$ looks like $X=\ldots =\ldots =Y$ and the argument for some of the intermediate "$=$" uses the hypothesis $A$. Thus overall we prove that $X=Y$ (i.e., $B$) holds under the hypothesis $A$. In other words $A\to B$.