Blog

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!

I’d use the next few posts to start a discussion on defining security. Satisfactorily defining security is one of the most important enterprises in the theory of cryptography. There’s much to say, and I’m sure there’re many possible divergent views on this. So all the usual disclaimers are in place.

What should a security definition be like? One would expect to get a reassuring guarantee that if a scheme meets the definition, then nothing can go wrong in an unexpected way, when using the scheme. Now, it would be rather presumptuous on the part of a cryptographer to give such a guarantee, for there are other parts in the system which may have nothing to do with the cryptographic protocol (like, say your trusted buddy turns hostile and decides to publish all the e-mails you sent him or her, or say the stock-market crashes and you lose all your money). You wouldn’t want to blame your misfortunes on the poor cryptographer. On the other hand, if you think that your now-hostile buddy managed to find out some of your secrets because of a flaw in a cryptographic protocol, or that you lost money because your competitors managed to cheat in an auction protocol that ought prevent cheating, then by all means, you can ask for an explanation from your cryptographer.

The security guarantee, then, should be an assurance that whatever goes wrong, it won’t be the cryptographer’s fault.

So, how does one give a guarantee that if something goes wrong it won’t be the cryptographic protocol to blame? We shall come back to that question in subsequent posts. For now I just want to leave you with this thought: traditionally (I’d imagine) one indeed used to think of giving security guarantees as giving an assurance that nothing can go wrong in an unexpected way. The major limitation of this — philosophically speaking — is that we can give such a guarantee only in relatively simple scenarios where we know what all can go wrong. For more variable/complex scenarios, we shall give up on such an absolute security guarantee for a protocol, and instead go for a don’t-blame-me/not-my-fault kind of guarantee; it would leave room for things to “go wrong,” but not because of flaws in the protocol.

(Thanks to Jonathan Katz for prompting me to blog on. Well, more accurately he suggested I should either blog more often or just delete the blog. I don’t know if he would be disappointed at the choice I made )

Theoretical computer science is mostly nice and self-contained, except for a few rough edges where it meets real life (unless you’re happy not to meet real life). One of these intersections is where we abstract some real phenomenon into a mathematical concept (another being when we have a result in our mathematical model and then are trying to interpret its meaning in real life).

If you’re learning theoretical cryptography, the very first abstraction that you’ll have to get to grips with is the use of probability. Our definitions, constructions and proofs of security all vitally depend on probabilistic notions. There is a leap of faith in assuming that something we do (like, obtain a bit-string from some circuitry in our computer) is in fact an instance of a random process. How is it that you can look at a string at hand and say that it was generated according to some probability distribution? If you are already comfortable with the quantum mechanical view of the world, this shouldn’t bother you at all. (You thought you were going to learn computer science, and here I’m talking about physics. But rest assured, it’s just going to be math all along, except at these clumsy interfaces of the abstract and the physical.) But if probabilities and distributions are new for you, well then you just have to keep talking about it until it doesn’t sound funny any more. If it helps, think only about the probability of events in the future, and not of what could have happened, or is happening in parallel universes.

Probability is a concept for which one has to develop an intuitive understanding. But, then again, chances are you have already done it. Don’t you look at a coin which fell heads up and think that it could have been tails up, equally probably? Without being bothered about the aerodynamics of your coin, of course. That’s because you understand the notion at an intuitive level. Maybe you never realized how far this can be taken. But really, that’s all there is to it: millions of coin flips. And you know what a coin flip is.

Once you buy into that completely, you can then start worrying about whether it was alright to do so. But that can wait.

Of course, probability and randomness are not special to cryptography. You must have come across this notion in physics, chemistry, biology, computer science (randomized algorithms), information theory, and perhaps in a course on probability in the math department! That’s probably a good excuse for me to not spend a lot of time on probability in a cryptography course. But I’m making up for that here, bringing it up right at the beginning.