Cryptography Is Dead?
Comments from a keynote panel
Whitfield “Whit” Diffie, Ron Rivest, Adi Shamir, and Dan Boneh are all famous cryptographers. They just gave a keynote panel at this year’s RSA Conference. Of course Rivest and Shamir are the ‘R’ and the ‘S’ in ‘RSA,’ while Diffie co-authored a famous 1976 paper long credited as introducing the key ideas in public-key cryptography. In fact many of those ideas had been developed and classified in Britain three years earlier. Moreover in 1874 William Jevons, whom we just posted about, remarked on function-inversion and factoring, writing
The work would probably occupy a good computer for many weeks…
Today I want to talk about the conference, and especially the comments from their panel.
I have never been to an RSA conference before, partly because it is mainly a showcase for security companies. The expo part of the conference consists of a countless number of booths, all with large signs, lots of hype, and lots of noise. As a show it is quite overwhelming. Another reason I have never been there before is that the registration fee is quite large—$2,295.00—so it is quite an expense, no matter who is paying. Besides the expo there are many keynotes, panels, and lots of parallel sessions.
Well, one of the keynotes was really this panel, or the panel was really a keynote—anyway it consisted of three of the founders of the whole field—Diffie, Rivest, and Shamir—plus one other world expert, Boneh. I am biased about Boneh, he is an ex-graduate student of mine, but am a huge fan of all of the panelists. They are not only leaders, but each usually has something interesting to say.
I thought I would give some highlights, in my opinion, of the panel.
The panel started with a recap by Ron of the very first time he gave a public talk on his now famous algorithm. At the time it was unclear what the US government’s position was about public work on cryptography. Ron was threatened in a letter from an NSA employee, and went ahead with his public talk anyway. The panel talked about how far and how deep the changes have been. Today the official US-endorsed symmetric key method is AES, which was not even developed in the US but in Belgium by Joan Daemen and Vincent Rijmen. Things have changed.
Here are some top level highlights from each speaker:
Diffie: Whit mentioned several people who have made important contributions but are not well known. He also talked about what he does as a top level security officer these days. He said with a smile that while he is busy with managing many products, he still finds time to think about cryptography fundamentally. This is good news: I expect that Whit can and will make more important contributions to the field.
Rivest: Ron discussed his main interest these days: e-voting. He is involved in the issue of how to make electronic voting trustworthy. In particular he had is working on audits of electronic voting, which seems to be a very important idea. Ron also urged the audience–thousands of people—to help him get officials of all kinds to not use Internet based voting. His point is simple: the Internet is not a place, using modern crypto methods or not, to do voting. He did acknowledge that some professional societies were starting to do voting over the net, which made him uncomfortable.
Shamir: Adi thought that crypto is “dead.” He did not explain exactly what he meant. He did however explain an idea for protecting databases. He argued that secrets, for example the contents of some important database, should be made very large. This would make it hard to steal, since the amount of data needed to be moved out of the systems would be so large. I like this idea myself. Of course the reason is that I have worked previously on this idea—see here. I always liked this direction: to me the point was why the Hope Diamond is behind a thick glass at the Smithsonian Museum and a Rodin statute is not. One weighs about 9 grams and the other about 5.4 million grams.
Boneh: Dan discussed his quite successful on-line crypto course that he did for Coursera. He explained that in his Stanford “normal” course he usually asks for and gets feedback at the end of each course. In such a course with perhaps one hundred students he reads all the email. He did the same with his on-line course and got 10,000 pages of comments—yes pages. Dan said he tried to read as much of that as possible, but it certainly is a different world.
Dan also talked about some covert-channel work that he recently did. He has developed a method for identifying your cell phone via its hardware. He uses the fact that each phone measures acceleration slightly differently. His attack measures over many times the acceleration of the phone, and then compares the values. Since all phones—it appears–make slightly different errors in their measurements, he can convert this into a unique signature of the phone. Obviously there are ways to stop this: the simplest is to disallow any script from reading the values of the phone’s acceleration measurements. But the fact that this is a viable attack is surprising to me.
Does Crypto Need Shoring Up?
Dan also pointed out that there was a recent improvement to attacks on discrete logarithm. The result in question is due to Antoine Joux, and proves that there is an attack on discrete log that runs in time . This means that it runs in time
for some . This is huge improvement over previous results. Dan also pointed out what I personally believe is one of the greatest open (meta-)questions in all of cryptography:
Why does every improvement in attacks on discrete log always lead to similar improvements in attacks on factoring?
This has alway happened before, even for quantum algorithms. Recall that Peter Shor’s famous work showed that both discrete log and factoring are in quantum polynomial time. How can this be? It seems like morally there should be a classical reduction from one to the other, but no such reduction is known. Yet the improvements always seem to come in pairs.
All: They all have a quite negative view of the potential of quantum attacks on crypto systems. The consensus was that large-scale quantum computing would either be impossible—this was Ron’s suggestion—or possible but a long way in the future. Whit and Adi thought that ‘decades’ was a reasonable guess.
Dan’s view was that the quantum threat raised an interesting question: Why do we not plan now for a possible upheaval in cryptography? Dan’s idea was that we should have already in place classical algorithms that could “instantly” be switched on, and in this way enterprises that use crypto could survive either a classical attack or a quantum attack. The fallback classical protocols might operate more slowly than our popular schemes based on factoring, but at least defenses would be shored up. Adi pointed out that classical breakthroughs by their very nature are less predictable, in his opinion, than quantum breakthroughs.
What do you think about the connection between discrete log and factoring? Can we prove something about it? Also is their view of quantum computing being a long way off a reasonable view?
[made blockquote and other format tweaks, loglog --> loglog q in L-formula]