The limits of provable security

I've never quite understood the objections that people have to cryptographic schemes that are provably secure. If you have a proof of security then one of two things must be true: either the scheme is secure or there's a flaw in the proof. There's no other possible case.

All of the technologies that Voltage's products use have such proofs. The Boneh-Franklin IBE, the Boneh-Boyen IBE and our format-preserving encryption technology all have such proofs that have been published in peer-reviewed research journals. Because of this, I often don't understand the questions that I sometimes get about the security of our technologies.

Here's a situation that I've seen more than once. Someone asks about the security of our FPE technology, for example. We'll point them to the paper by cryptographers John Black and Phil Rogaway that has a proof for the security of the scheme. The next question is essentially, "But why should I believe that it's secure?" At that point, I'm never quite sure what to say next. If you have a proof in front of you, then either the proof is correct or there's an error in the proof. If this proof is of the security of a cryptographic scheme, then either the scheme is secure or there's an error in the proof. As mentioned above, there's no other possible alternative.

My recent experiences have led me to believe that there's a fundamental problem with this approach, and that's because many people really aren't comfortable with the idea of a proof. I've seen many cases recently where people essentially accept P and NOT P at the same time and don't seem bothered by doing this.

Every time I see this, I start thinking about the logical implications of it. After all, if you accept both P and NOT P then you can prove that absolutely anything is true. "If 2 = 3 then all cats are dogs" is absolutely true, for example. But because many people either don't understand this or don't believe this, I've come to the conclusion that proofs of security really aren't that useful. They may help specialists make sure that their work is correct, but to non-specialists they really don't say anything useful.

  • Rob Lewis

    You tell’em Luther!
    Sorry, that’s a line from a Don Knotts movie, The Ghost and Mr. Chicken, but it applies here.
    From what you say, the herd isn’t only incapable of understanding the proof, they don’t even understand the concept of a proof.
    Proofs matter more to other mathematicians, but that may not make it a best practice for the herd. Only marketing can make it tip.


  • Mark

    If you have a proof of security then the scheme is secure, or there’s a flaw in the proof, or your proof relies upon an assumption that may not always apply.
    The third option is distinct from a flaw in the proof because I might have a provably secure system that fails because the assumption was violated during deployment.
    Note that an assumption may be tangential to the proof. For example, there are many provable schemes that fail under power analysis. It does not mean that the proof was incorrect, but that the assumptions need to be changed.


  • Luther Martin

    I’d say that things like side-channel attacks really aren’t attacks against an encryption scheme. Instead, they’re attacks against a flawed implementation of one. So I’d say that a proof that a scheme is secure is still valid.
    It took some very smart people quite a while to come up with a reasonable way to define the security of an encryption scheme, like IND-CPA security. I’d guess that it will take even longer for some people who are just as smart to come up with a model for a secure implementation of an encryption scheme. Once we have that in hand, we’ll be able to talk about proving the security of the implementation on encryption schemes. But because we don’t even have a useful definition of a secure implementation right now, talking about whether you have one or not is hard to do in a meaningful way.
    Before we have a good definition of a secure encryption scheme, the only to get a reasonable level of assurance that a scheme was secure was to wait several years to see if any clever cryptanalysts could find a flaw in it. With proofs of security, that should now be much easier.
    Similarly, once we have a good definition for a secure implemenetation of an encryption scheme, it will probably be much easier to talk about secure implementations in a meaningful way.
    Any ideas of how to do that?


Leave a Reply

Your email address will not be published. Required fields are marked *