Home » Analytics » Elliptical Training Secrets and Theorem Shaving

Elliptical Training Secrets and Theorem Shaving

Peter Woit, Not Even Wrong, Trust the math? here. So keeping math secrets in 2013 isn’t all that hard? Shapiro used to tell a story about Selberg’s notebooks. Whenever Selberg felt like the literature was gaining on him he would work more results in his notebooks, and then just put them away in his drawer.

The last few days have seen some new revelations about the NSA’s role in compromising NIST standard elliptic curve cryptography algorithms. Evidently this is an old story, going back to 2007, for details see Did NSA Put a Secret Backdoor in New Encryption Standard? from that period. One of the pieces of news from Snowden is that the answer to that question is yes (see here):

Classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency. The N.S.A. wrote the standard and aggressively pushed it on the international group, privately calling the effort “a challenge in finesse.”

Evidently the NSA spends about $440 million/year on cryptography research, about twice the total amount spent by the NSF on all forms of mathematics research. How much they’re getting for their money, and how deeply involved the mathematics research community is are interesting questions. Charles Seife, who worked for the NSA when he was a math major at Princeton, has a recent piece in Slate that asks: Mathematicians, why are you not speaking out?. It asks questions that deserve a lot more attention from the math community than they have gotten so far.
Michael Kelley, BI, The FBI Investigated Knicks Players in the ’80s for Allegedly Fixing Games for a Drug Dealer, here. I’m gonna go ahead and call first on the term-of-art Theorem Shaving.”  A theorem shaving scheme generally involves a sovereign agency, corporate, or administration (party A, the gambler) and one or more players of the team known to be exclusively/uniquely able or expected to prove a theorem (party B scores the points). In exchange for a fee or bribe, the player or players agree to ensure that their team will not “disclose the proof of the given theorem” before a prenegotiated contract termination date (end of the game). The gambler (the risk taker, party A) then monetizes on the spread between party A’s certainty and the  uncertainty surrounding undisclosed theorem among the retail market investors to breakeven or profit on the fee or bribe to produce a positive ROI (return on investment to Party A). Even if the muppets are rational they get arbed by party A on the spread. Party A  is simply looking for specific market liquidity prior to the termination date of the contract. The answer to Charles Seife’s question above … is left as an exercise for the reader.
The Post caught up with the team’s leading scorer, Micheal “Sugar” Ray Richardson, who was banned for life in 1986 for violating the league’s substance abuse policy after struggling with a cocaine addiction.

When asked about the point-shaving allegations, the four-time NBA All-Star told the Post: “Hell no! We never did anything like that.”

Aaronson, Shtetl-Optimized, NSA: Possibly breaking US laws, but still bound by laws of computational complexity, here.

Most importantly, I didn’t clearly explain that there’s an enormous continuum between, on the one hand, a full break of RSA or Diffie-Hellman (which still seems extremely unlikely to me), and on the other, “pure side-channel attacks” involving no new cryptanalytic ideas.  Along that continuum, there are many plausible places where the NSA might be.  For example, imagine that they had a combination of side-channel attacks, novel algorithmic advances, and sheer computing power that enabled them to factor, let’s say, ten 2048-bit RSA keys every year.  In such a case, it would still make perfect sense that they’d want to insert backdoors into software, sneak vulnerabilities into the standards, and do whatever else it took to minimize their need to resort to such expensive attacks.  But the possibility of number-theoretic advances well beyond what the open world knows certainly wouldn’t be ruled out.  Also, as Schneier has emphasized, the fact that NSA has been aggressively pushing elliptic-curve cryptography in recent years invites the obvious speculation that they know somethingabout ECC that the rest of us don’t.


1 Comment

  1. […] W. Appel, Verifiable C, 2013, here. Wow with the Crypto Theorem Shaving allegations it looks like Verification scores on a Hail Mary […]

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

%d bloggers like this: