## Mapping Crypto to Capabilities

I’ve been thinking.

Let me preface this by suggesting: if there were a globally trusted capability-secure computing fabric, we would have no need of (some kinds of) crypto.

Why? What do we do with crypto? We sign things, and we encrypt things. How do we do this with our GTCSCF? Easy. To sign something, I hand that something to the relying party. He then exercises his capability to me that checks authenticity of somethings, and I respond that it is authentic.

Encryption is even easier – I just send the something down a capability leading to the intended recipient.

So, I claim, there is effectively a mapping between crypto (at least for signing and encrypting) and a great capability machine in the sky (i.e. the GTCSCF).

Considering this idea further, it seems to me that this is essentially the core idea behind Universal Composability. If I can show that my crypto system does indeed map to a GTCSCF, then I have a crypto system that can clearly be composed with other crypto systems, and only have the consequences we would expect from a capability-secure system that implemented the same functionality.

What would it mean to make such a proof? My, perhaps amateur, understanding is that you would have to show that the corresponding capabilities have the properties we expect of them: that they are opaque, unforgeable, and only obtainable by being handed them in some way.

This sounds doable to me, modulo assumptions about the hardness of the discrete log problem, and the like.

Interesting stuff. Could I persuade you to post a pointer to this on cap-talk?

Comment by Toby — 27 Aug 2007 @ 11:49

What you’re describing is more generally the idea of indistinguishability from a world where a trusted third party (TTP) does the work for you. Universal Composability adds a few extra constraints, for example the fact that the indistinguishability remains true from the point of view of an observer that sees the whole protocol and can “interrogate” the adversary at any moment in time. In technical terms, this makes “simulation by rewinding” difficult, and it means you have to use all sorts of crazy tricks to satisfy the UC definition.

But yeah, in general, this concept of comparing two worlds, one with a TTP, one with a crypto protocol, and declaring them equivalent, is definitely the trend in crypto. The indistinguishability is generally computational, and depends on specific assumptions you make about what’s hard to compute, e.g. a discrete log.

Comment by Ben Adida — 27 Aug 2007 @ 23:47

I think your equation is right but your conclusion is wrong. To be clear: I agree with you that “crypto = GTCSCF” (to within epsilon); in fact I think this view is pretty conventional.

You think this equation means that both are doable; I think it means neither is.

I also have other issues; I don’t think universal (or even local) composability is likely to be possible. I also deeply distrust basing security claims on assumptions like the harness of discrete log. Even if discrete log IS hard, I am deeply suspicious of our current “proof” techniques which translate these assumptions into statements about security.

The main issue, though, is that if we had to choose between a crypto-free (and secret-free) GTCSCF and one which used crypto extensively (or even at all), I’d choose the former rather than the latter. Why? Well, fundamentally because I don’t think secrets work as well in the real world as they do in the mathematical world. And in fact I do have some hope that a crypto-free GTCSCF may be achievable, but I don’t have room in the margins of this book to explain why….

Comment by Bob Blakley — 29 Aug 2007 @ 1:51

I don’t think it means both are doable, that was not my point at all. The capability machine in the sky is an imaginary machine, but if you can prove equivalence to it, then you know something useful about your crypto.

I agree with your reservations about DL and the like, but do not believe that changes my underlying argument, at all. That is, such assumptions are not needed to have the equivalence be useful, but may be needed to prove equivalence for existing crypto systems.

I totally doubt that it is possible to make a GTCSCF in reality, using crypto or otherwise. I’d love to know why you think it is possible.

Comment by Ben — 29 Aug 2007 @ 20:25