Practice-oriented Provable-Security

In 2009, Mihir Bellare and Phil Rogaway shared the ACM's prestigous Paris Kanellakis Theory and Practice Award for their creation of the idea of "Practice-Oriented Provable-Security." Here's the citation for the award that explains why they received it:

Historically, cryptographic schemes used in practice were designed in ad hoc ways and subject to failure. Practice-Oriented, Provable-Security (POPS), developed by Bellare and Rogaway in a series of papers in the 1990s, changed this, giving us the means to create high-assurance practical cryptography, meaning schemes that were backed by the theoretical guarantee of provable security while meeting practical needs and expectations.

Today, POPS-based schemes are cornerstones of Internet security, implemented in most communication security protocols and software – these schemes are used every time someone makes a credit card-based Internet purchase. Meanwhile, the models, techniques and approaches that Bellare and Rogaway introduced, including the random oracle model, have become the foundation of a new subfield of cryptography, inspiring a great amount of follow-on work. Their papers are amongst the most cited in cryptography and their work is discussed in dozens of textbooks.

Bellare and Rogaway changed the perception of theory in practice. Prior to their work, practitioners ignored theory or were even antagonistic to it. Today, they not only choose to implement and standardize proven-secure schemes, but make provable security a requirement in some of their calls for algorithms. That this requirement can be met owes much to Bellare and Rogaway's work. 

In other words, Bellare and Rogaway created a framework for cryptographers to use to prove the security of their inventions and this framework is really the single thing that's most responsible for transforming cryptography from an art into a science.

Before POPS, the only way to ensure that a cryptographic scheme was secure was to wait a while to see if anyone could find a weakness with it. With the invention of POPS that's no longer necessary. It might even be a waste of time to wait to see if a weakness can be found because if there's a valid proof because the very existence of the proof tells you that there can't be one.

Many of the technologies that we use at Voltage have proofs of security. This includes both our Identity-based Encryption and Format-Preserving Encryption. The things that we use that don't have proofs of their security are just things that older standards define: techniques standardized before POPS typically don't have proofs of their security, but there's no really alternative to using them.

I'd hope that newer standards won't have this problem. All of the discussions that I've seen recently in various standards groups have required a proof of security before a new crypotgraphic scheme is taken seriously.

Leave a Reply

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