Skip to content

Cryptography Is Dead?

March 2, 2013


Comments from a keynote panel

ShamirBonehDiffieRivest

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.

RSA 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 {L(1/4)}. This means that it runs in time

\displaystyle  O(\exp(c(\log q)^{1/4} (\log\log q)^{3/4})),

for some {c>0}. 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.

Open Problems

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]

About these ads
20 Comments leave one →
  1. March 2, 2013 11:25 am

    Thanks for keeping the subtext on the Logic of Science alive, however tangentially. Cryptography, in Newton’s cosmic sense, decoding the Book of Nature, will always be a live subject, eternally engaging long after all the petty secrets and all the petty covers of men are blown.

  2. March 2, 2013 3:59 pm

    It is probably worth pointing out that Joux’s algorithm (and also independent, recent work by Gologlu et el., http://eprint.iacr.org/2013/074) are only applicable to fields of small characteristic. The progress is very significant but its relevance to the standard setting of the discrete logarithm problem in a field of a large, prime characteristic (and, by association, to factoring) is yet to be seen.

  3. Serge permalink
    March 2, 2013 6:37 pm

    It’s often said that mathematical theories thrive on open problems, but cryptography looks like the exception that proves the rule. Indeed, it could be dying actually because its main open problem remains forever unsolved…

    • Serge permalink
      March 4, 2013 1:41 pm

      It’s interesting to note that the absence of theorems about the complexity of deciphering procedures isn’t regarded as a major drawback to the usability of cryptography. Quite possibly, a field whose main duty is to produce secrets shouldn’t be allowed to yield too many theorems, after all – and the open status of P=NP has remained so far the safest warrant to the efficiency of cryptography itself. In a way, theorems are the strict opposite of secrets…

  4. March 2, 2013 10:02 pm

    “$2,295.00″
    What decadence.
    I know lots of people who earn that much in a month.

  5. March 2, 2013 10:41 pm

    RSA, quite the legend. billions of dollars of internet commerce now ride on SSL. … ah, of course your own blog is one of the best in the world for discussing the issue of viability of qm computing via the outstanding/ongoing/world class kalai-harrow debate, so its amusing to hear you turn it over to commenters. however there are some new ideas circulating on a paper by anderson/brady that proposes a soliton-based model for qm and argues that it means that qm crypto with many qubits [but also qm computing!] is not physically possible. aaronson says its all bogus! which inspired my rebuttal =)

  6. March 3, 2013 3:14 pm

    Thanks for the pointer to the discrete log improvement paper.

    The opening of the paper, however, makes me quite sad: “In the present competitive context, timeliness is preferable to completeness. We have thus chosen to publish this preprint in a draft form that includes neither a complete analysis of our results, nor a large number of examples. We apologize to the reader for any inconvenience. In the present competitive context, timeliness is preferable to completeness. We have thus chosen to publish this preprint in a draft form that includes neither a complete analysis of our results, nor a large number of examples. We apologize to the reader for any inconvenience.”

    • John Sidles permalink
      March 4, 2013 10:41 am

      Dave, it’s good that you’re posting! We all hope that Bacon Jr is prospering!

      Supposing that the passage in question is a symptom — a dismal symptom to be sure — then what is the underlying disorder? What are its treatments? And what are the prospects for a cure?

      What’s truly dismaying (to me) is that there is scant serious discussion of these three questions within the STEM blogosphere.

  7. S. Gupta permalink
    March 5, 2013 12:38 pm

    Almost certainly FACTORING will be found to be in P. Crytopgraphy, if indeed dead, will spring back to life immediately.

    • anonymous permalink
      March 10, 2013 3:35 pm

      Can you please mention few points that lead you to say that ” Almost certainly FACTORING will be found to be in P”.

      • Serge permalink
        March 12, 2013 11:12 am

        According to Ladner’s theorem, if P!=NP then there are problems in NP which are neither in P nor NP-complete. FACTORING is often believed to be one of those. If P=NP, here’s my theory: although it still takes infinite time to find an efficient algorithm for NP-complete problems – and so does it to find one for FACTORING – the historical process for FACTORING converges faster toward P than for NP-complete problems.

  8. Moti Yung permalink
    March 7, 2013 12:59 am

    Cryptography is alive because parts of it die all the time!! Technology changes fast while human nature does not!

    Cryptography is the ultimate phoenix !!

  9. April 1, 2013 10:54 am

    is cryptography dead? dont know the answer but have heard of some new contrarian thinking by Anderson/Brady on qm crypto in particular; they assert new new paper(s) it is impossible because QM is actually a surface phenomena of a soliton “LHV” (local hidden variable model). huh! that reminds me of bohms concept of the explicate vs implicate order! scott aaronson apparently felt quite threatened and took it seriously enough to try to lead the charge & launch a cyber comment mob against it… quite the cyberspace drama! see also solitons, cellular automata, quantum mechanics, and disagreeing with scott aaronson

Trackbacks

  1. Compensation and Cryptography are Dead? | Pink Iguana
  2. Cryptography I | Ben Mobley on Security
  3. RSAC 2013 - The Cryptographers' Panel in review - Nikhil Bhalla
  4. Happy St. Patrick’s Day—Again and Again and Again and Again | Gödel's Lost Letter and P=NP
  5. Win Five Hundred Or A Million Dollars, By Recursion? | Gödel's Lost Letter and P=NP
  6. A Most Perplexing Mystery | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,871 other followers