Abstract cryptography

World, Hello! ...hmmm, that did not come out right. Oh well...it's clear what I ment.

I was at research meeting at Dagstuhl this past week and this seems like a good opportunity to cave in to outside pressure and to the revelation that our blog is actively read to start blogging about something (that I find) interesting and that is somehow related to cryptography.

There have been many very very interesting talks (see Program). I particularly liked Eike's construction of a lossy trapdoor permutation from LWE (a much simpler and direct approach than in the original work by Peikert and Waters) and Yuval Ishai's talk on generalizing the Yao circut construction from boolean circuits to arithmetic ones. However, the talk that I found most intriguing was Ueli Maurer's talk on "Constructive cryptography" and this post is about this subject.

There were many ideas compressed in the only 30 minutes talk, and there was a hail of questions at the end. I'll sketch two ideas that stood out for me.

The first idea is a shift in the way we define security (and even functionality) of cryptographic primitives: instead of thinking of the security of systems in isolation, define security by explicitly including in the picture the task for which the primitive is intended. For example, a secure encryption scheme would be whatever allows one to implement a private channel. An authenticated encryption scheme would be whatever allows for the construction of an authenticated channel. Ueli termed the approach constructive cryptography. It was unclear to me how the idea would work for security properties that look very directly at the properties of the implementation and for the case of more complex primitives (e.g. direct anonymous attestation protocols). More generally, it is unclear how far can this idea go but this is something I'm very interesting in understanding.

An idea that I found even more exciting is what underlies "Abstract cryptography", a program Ueli is in the process of developing. Let me try to explain through an example what is the problem that this framework tries to solve.

We have by now several frameworks that allow for some form of general composability results. These include the reactive simulatability framework of Pfitzman and Waidner,the framework of universal composability (and its many variants) by Canetti, the task PIOA framework of Canetti, Cheung, Lynch, Kaynar, and Pereira, the one based on inexhaustible Turing machines by Kusters etc, etc, etc. All of these framworks come with a composability theorem that allows for some form of modular desing of cryptosystems.

I conjecture that a thorough reader raises his hands in despair when confronted with these papers (raise your hand if you did). Reading usually starts with tons of unplesant technical details that define (as precisely as the authors care to) the different components of the frameworks, execution, and adversarial models, specific notions of efficiency etc. Then, when reaching the composition theorem one cannot help but have a sense of deja vu. Despite the different technicalities, all of these frameworks share the same nice and simple definitional idea of security and in turn this leads to similar proofs of the composition theorem.

This suggests the existence of a domain which abstracts away the nasty technical details irrelevant for the validity of the composition theorem. Proving the theorem in this domain would still be simple (if not simpler) and, importantly, existing composition theorems would follow. It should be sufficient to observe that existing frameworks are concrete instantiations of the abstract framework. It is this abstract framework that Ueli advocates developing and which he calls abstract cryptography. In category theory terms, what is desired is an initial object in the category of cryptographic frameworks with composition theorems.

I find this research direction fascinating and useful. Unencumbered by useless details the core ideas behind theorems and proofs can be more easily grasped and explained. Similarities shared by apparently different problems can be more easily evidenced and their solutions reused. For example, Ueli sketched how to cast the impossibility of UC commitments and ZK proofs, in a unified way, as the impossibility of solving a system of equations. It would be great if all UC-like results could be explained equally simple.

I hope that abstract cryptography will mature soon: using simulation frameworks may turn out to be way simpler than it is nowadays and would save cryptographers a significant amount of sleepless nights (A first paper on abstract cryptography had appeared in Innovations in Computer Science'11 and can be downloaded here).