Opinion
Computing Applications Last byte

Q&A: A Passion For Pairings

Dan Boneh on pairing-based cryptography, multilinear maps, and how an 1,800-year-old "intellectual curiosity" became the foundation of all secure network traffic.
Posted
  1. Article
  2. Author
Dan Boneh

Dan Boneh, recipient of this year’s ACM-Infosys Foundation Award, discovered his passion for computers early; by the time he got to Princeton University, where he earned his Ph.D., he had zeroed in on his line of research: cryptography. Now a professor at Stanford University—and head of the university’s Applied Cryptography Group—Boneh has made groundbreaking contributions to the field, pioneering the use of pairings to solve cryptographic problems and working on a range of broader computer security questions. Here, he discusses his work.

What drew you to computer science?

I fell in love with computers at a very early age. In high school, I learned about the mathematics of cryptography and was completely taken by it. It is a beautiful area involving elegant mathematics, and at the same time, the results are practical and used in real-world systems.

Can you take us through your work in pairing-based cryptography, which is among your best-known contributions to the field?

Let’s start with some context. The story begins 1,800 years ago with a mathematician named Diophantus, who lived in Alexandria and whose work gave rise to many things we learn in high school algebra. The ideas he developed to solve one particular problem described something that is heavily studied in mathematics and called an elliptic curve.


"Cryptography is a beautiful area involving elegant mathematics, and at the same time, the results are practical and used in real-world systems."


At first, the work was theoretical, but eventually, researchers discovered that elliptic curves are extremely useful for cryptography.

If a browser wants to talk to a bank, it needs to exchange keys to encrypt the communication. Whitfield Diffie and Martin Hellman, working at Stanford, invented an ingenious way to do this. The problem is that to make their method secure, you have to make the numbers involved quite large, and that makes it slow.

So in the 1980s, mathematicians Victor Miller and Neal Koblitz suggested using elliptic curves to enable the parameters to be smaller and the key exchange to run faster. And now every time you connect to Google, you are using this modified version of the Diffie-Hellman exchange. It is a remarkable success story of mathematics—something that for 1,800 years has only been studied as an intellectual curiosity suddenly forms the underpinning of all secure network traffic.

Where does your own work come in?

Mathematician André Weil, who studied elliptic curves in the 1960s, discovered something called a pairing, as a side tool in one of his proofs. As it turns out, pairings are a godsend for cryptographers. We already use elliptic curves for key exchange. Now it turns out they have this additional structure, namely pairings, that enables new applications and this was recognized by several researchers. In 2001, Matt Franklin—who is a professor at UC (the University of California at) Davis—and I proposed an application called identity-based encryption.

Thanks to identity-based encryption, any arbitrary string, such as an email address, can function as a user’s public key.

Identity-based encryption is just one application. Our work, and the work of others, kicked off a flood of results: shorter digital signatures, ways to search on encrypted data, content protection, privacy mechanisms, and so on. More and more applications are discovered every day.

Your later work expanded the possibilities even further by describing a generalization of pairings called a multilinear map.

In a 2003 paper with Alice Silverberg, we suggested that if one could construct a multilinear map, which is a generalization of pairings, then it would open the door to many new applications. For many years, the challenge was to construct multilinear maps. I’m thrilled to say that a few years ago, Sanjam Garg, Craig Gentry, and Shai Halevi came up with the first candidate multilinear map that lets us to do many of the things we had hoped for and much more.

Such as?

One of the most beautiful applications of multilinear maps is the work of a group of researchers at IBM, UCLA (the University of California at Los Angeles), and U.T. (the University of Texas at) Austin, who showed how to use them for software obfuscation. Software obfuscation lets you hide secrets in code: I can embed a secret key in software and then give you the software. You can look at the code and run it, but you will never be able to get the key out of the code.

In addition to your theoretical work, you’ve been involved with a number of very practical projects in computer security.

I’ve always been interested in the bigger picture of computer and data security. What I like to do with my students is identify new ways of defending systems against attacks that have not been thought of yet. So we try to predict what tomorrow’s attacks will look like and how we can defend against them. It’s fun for me, it’s fun for the students, and it’s a great way to teach security—see if you can break this thing, and then we all fix it.


"Another way to think of a MOOC is as a 21st-century textbook; it does not replace on-campus learning, but enhances it."


One recent paper of yours demonstrated a way to turn the power meter on a cellphone into a GPS.

Cellphones recently added a power meter so that applications can see how much power is being used and adapt how much they draw. But it turns out the amount of power your cellphone’s radio drains depends on obstacles between it and the base station.

So you can calculate the phone’s location and route, provided you know the configuration of nearby cellular towers.

Exactly. The software systems we build these days are so complex it’s very difficult to reason about all the possible ways things can go wrong. You add a power meter and all of a sudden, you realize it can be used as a GPS.

Let’s talk about some of your educational initiatives. You run a popular MOOC (massive open online course) on cryptography, for instance.

If you build an application that touches user data, you’re going to have to use cryptography to protect it. Cryptography, however, is one of those fields where a little knowledge can be dangerous—the application may work fine, but if the crypto is used incorrectly, the data will be insecure. We want every CS major to be exposed to some crypto so they know what tools exist, what they do, and more importantly, how to use them correctly. I teach an undergraduate course that takes a hands-on look at how to use crypto to protect real data, and I’ve made that class into a free online course, a MOOC.

More than 600,000 have signed up for it.

It’s been very rewarding. Another way to think of a MOOC is as a 21st-century textbook; it does not replace on-campus learning, but enhances it. My on-campus teaching has improved as a result of the MOOC. In the past, I covered every topic at the same level of detail; now, if there’s one topic I think is not as exciting as another, I’ll discuss it quickly in class and refer students to the MOOC for more information. This allows me to spend more time in class on deeper topics that deserve more attention, rather than spend lecture time on mundane topics.

You also run a popular computer security class.

It’s important to teach CS students to always think about security as they write software, because the code they write will come under attack. We give students assignments where the first part is to break something by finding flaws; the second part is to fix all the vulnerabilities. The students enjoy the first part, but complain about the second; they fix all the bugs they can find, but they worry about losing points because of some bug they didn’t find. Well, that’s the real world.

Back to Top

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More