Posted by: jonkatz | August 26, 2009

## Crypto highlights: Maurer’s talk

(This is a followup to my previous post, prompted by an anonymous comment.)

Ueli Maurer gave an invited talk at Crypto this year that generated quite a bit of discussion afterward. The talk was long, and had lots of pictures and examples; as such, there is no way I will be able to do it justice here. (Hopefully at some point his slides will be posted on the Crypto webpage.) Instead I will just focus on a subset of what he covered. Even there, my apologies in advance if I misinterpret anything he said.

Maurer’s main argument was that everything in cryptography should be abstracted as much as possible. In particular, he proposed that all primitives should be cast as systems, and security defined in terms of indistinguishability of a real system from an ideal system. Constructions should be phrased as compositions of systems, and analyzed accordingly.

If this sounds a lot like Canetti’s Universal Composability (UC) framework, you’re right. Maurer claims that his [Maurer’s] framework encompasses UC as a special case (my reaction to this was “the last thing we need is something more complicated than the UC framework…”), and is also a strict generalization of Maurer’s earlier indifferentiability framework as well as Pfitzmann’s and Waidner’s “reactive systems” framework.

The example Maurer started out with was perfect secrecy. The traditional definition is an information-theoretic one, requiring (roughly) that for any distribution over messages, the conditional probability of any message given the observed ciphertext should equal the a priori probability for that message. One can also phrase this in terms of the more modern notion of indistinguishability, requiring distinguishing advantage 0 even for unbounded adversaries. (See my book with Lindell for more discussion.) Maurer suggested instead to use a definition in terms of systems. First, we look at the “real system”, parameterized by a message $m$, to which the adversary has one interface: an output wire where he gets the ciphertext. In the ideal system there is no interface; the adversary gets nothing. An encryption scheme is secure if there exists a simulator $S$ (who interfaces with the ideal system and provides an interface to an adversary) such that, for every message $m$, no (unbounded) adversary can tell whether it is interacting with the real system (with message $m$), or the simulator. It’s quite a mouthful, but much easier when you see it in pictures. (I also don’t claim that I got all the details right.)

Maurer’s claim was that this definition of perfect security is more intuitive than other definitions. As far as I could tell, he was claiming this to be true even for students taking their first course in cryptography. I don’t see this at all. To me, the classical definition is most intuitive and can be used to motivate the indistinguishability-based definition (since they are equivalent). Talking about abstract systems is very clean in an ideal sense (no pun intended), but very messy once you start worrying about the details.

The next part of Maurer’s talk focused on developing a syntax for dealing with systems and manipulating expressions in this syntax; it was this part that I really liked. For example (and here I am sure to get the syntax wrong, but the spirit should come through), we can define ${\sf Adv}^{\mathcal{A}}(C|C')$ as the maximum advantage of any adversary in class $\mathcal{A}$ in distinguishing system $C$ from system $C'$. Let us also use $BC$ to denote the process of interfacing system $B$ with system $C$ (in some particular way one would have to formalize, that I omit here). Then one can prove the following lemma:

Lemma: ${\sf Adv}^{\mathcal{A}}(BC|BC') \leq {\sf Adv}^{\mathcal{A}\circ B}(C | C')$.

Where $\mathcal{A}\circ B$ denotes the class $\{AB \mid A \in \mathcal{A}\}$. In particular, if $B$ runs in polynomial time and $\mathcal{A}$ is the class of polynomial-time algorithms, then $\mathcal{A}\circ B = \mathcal{A}$.

What is the point? Well, the point is that when analyzing a construction $BC$, where $C$ is a system you know to be indistinguishable from ideal system $C'$, you can appeal to the above lemma and prove security in one line. I.e., this is just a hybrid argument but the point is that instead of writing a 1-paragraph (or more) explanation every time you use a hybrid argument, you can instead write one sentence which accomplishes the same thing purely as a manipulation of symbols. I don’t claim that this would be any more or less intuitive to understand, but I can definitely see how such a proof would be easier to write and, more importantly, easier to verify.

The above covers roughly the first half of Maurer’s talk. To be honest, he lost me (or maybe I just lost interest) in the second half when he continued to generalize the above. It’s not that I found it inherently unappealing, just that it was too much material (for me, anyway) for a 50 minute talk.

Much as in game-playing proofs, the point is not so much to develop any fundamentally new proof techniques, but instead to give people a convenient language in which to prove (and verify!) things. I have become convinced of the utility of game-playing proofs (for some — but definitely not all! — proofs) over the past few years, and I’m open to being convinced by Maurer’s framework as well. (For a particularly nice application of the framework, see the paper “Computational Indistinguishability Amplification: Tight Product Theorems for System Composition” by Maurer and Tessaro that appeared at this year’s Crypto.) What do others think?