Last time — I know, it has been a while — we argued that a typical, good definition of security should be an assurance that whatever goes wrong, it wont be the cryptographic protocol to blame. And we asked how one could give such a guarantee.
For concreteness let us consider a specific cryptographic task: of secretly sending messages over a public channel. So, Alice wants to send a message to Bob. Now, what can cause things to go wrong here. Intuitively there are at least two causes of worry: something may go wrong because an eavesdropper learned something about the communication, and something may go wrong because of the fact that the message reached the other end (maybe because Alice chose to send the wrong message). If we are devising an encryption scheme for this task, clearly it is only the former concern that we need to address. The second concern is there just because of the functionality of message transmission.
Here is a thought experiment. Suppose Alice could send her message to Bob through a channel which is hidden from everyone else. In such a world, still things could go wrong because of the fact that the message reaches Bob. However the concern of eavesdropping does not exist. Indeed such a world has everything that encryption could offer (and a little more). So this world — which we shall call the ideal world — forms the benchmark to which a world using a proposed encryption scheme would be compared. If whatever could go wrong in a world using the proposed encryption scheme (over a public channel) could go wrong in the ideal world (with private channels) as well, then we contend that it is not the encryption scheme to blame.
It still remains to formalize the guarantee that “whatever could go wrong in the real world could go wrong in the ideal world as well.” We will return to the concept in more detail at a later point in this blog. But if you are curious, take a peek at the CRYPTUTOR definitions of security of encryption: SIM-CPA and SIM-CCA (under construction, I must warn you).
A word about CRYPTUTOR: It’s a wiki tutorial for theoretical cryptography, in the works. In its infancy, I should say. Much of the material currently there was developed during a course this Fall, with the help from the students, and from a most diligent TA Mike Rosulek (who also happens to be my PhD student). If you find any of the pages there in good shape, it must be Mike’s hands behind it!