this paper from 2015 cracks Diffie-Hellman. What to tell the students?

I am teaching cryptography this semester for the second time (I taught it in Fall 2019) and will soon tell the students about the paper from 2015:
Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. There are 14 authors.

The upshot is that as Diffie-Hellman was implemented in 2015, many cases were crackable. In summary (and probably too simple):

DH in a 512-bit group can be cracked by the authors

DH in a 1024-bit group they speculate can be cracked with nation-state resources.



Is this a big deal? If YES then what is being done, and if NOT then why not?

I have come up with some statements that I DO NOT KNOW if they are true, but I am ASKING you, to shed some light on the BIG DEAL or NO BIG DEAL question. (Note- Idea for a game show: BIG DEAL or NO BIG DEAL where contestants are asked if a news story is a BIG DEAL or not.)

So, please comment on the following question:

1) Since 2015 the people who use DH have upped their game and are now using bigger parameters. (I doubt this is true)

2) DH is mostly not used on things that hackers are not interested in, so this is not a big deal.

3) The expertise required to crack DH via this paper is rather difficult, so hackers don't have the skills.

4) This paper is not a problem for a bad reason: Hackers don't need to use the number field sieve DL algorithm when all they need to do is (1) guess that the pin numer is 1234 or the year the user was born (or close to it), (2) put on a uniform from Geek-Squad or some such organization and claim they are here to help, (3) exploit a known security flaw that the company has not bothered fixing.

5) The 14 authors have mysteriously disappeared. (I doubt this is true.)


(Misc: My spell checker thinks that Diffie and crackable are not words, but Hellman is.)

Are there any natural problems complete for NP INTER TALLY? NP INTER SPARSE?

Recall:

A is a tally set if A ⊆ 1^*.


A is a sparse set if there is a polynomial p such that the number of strings of length n is ≤ p(n).


If there exists a sparse set A that is NP-hard under m-reductions (even btt-reductions) then P=NP. (See this post.)

If there exists a sparse set A that is NP-hard under T-reductions then PH collapses. (See this post.)

Okay then!

I have sometimes had a tally set or a sparse set that is in NP and I think that its not in P. I would like to prove, or at least conjecture, that it's NP-complete. But alas, I cannot since then P=NP. (Clarification: If my set is NP-complete then P=NP. I do not mean that the very act of conjecturing it would make P=NP. That would be an awesome superpower.)

So what to do?

A is NPSPARSE-complete if A is in NP, A is sparse, and for all B that are in NP and sparse, B ≤_m A.

Similar for NPTALLY and one can also look at other types of reductions.

So, can I show that my set is NPSPARSE-complete? Are there any NPSPARSE-complete sets? Are there NATURAL ones? (Natural is a slippery notion- see this post by Lance.)

Here is what I was able to find out (if more is known then please leave comments with pointers.)

1) It was observed by Bhurman, Fenner, Fortnow, van Velkebeek that the following set is NPTALLY-complete:

Let M₁, M₂, ... be a standard list of NP-machines. Let

A = { 1^(i,n,t) : M_i(1ⁿ) accepts on some path within t steps }'

The set involves Turing Machines so its not quite what I want.


2) Messner and Toran show that, under an unlikely assumption about proof systems there exists an NPSPARSE-complete set. The set involves Turing Machines. Plus it uses an unlikely assumption. Interesting, but not quite what I want.


3) Buhrman, Fenner, Fortnow, van Melkebeek also showed that there are relativized worlds where there are no NPSPARSE sets (this was their main result). Interesting but not quite what I want.

4) If A is NE-complete then the tally version: { 1^x : x is in A } is likely NPTALLY-complete. This may help me get what I want.

Okay then!

Are there any other sets that are NPTALLY-complete. NPSPARSE-complete? The obnoxious answer is to take finite variants of A. What I really want a set of such problems so that we can proof other problems NPTALLY-complete or NPSPARSE-complete with the ease we now prove problems NP-complete.

Transitioning

You may have noticed, or not, that I haven't posted or tweeted much in the last month. I've had a busy time moving back to Chicago and starting my new position as Dean of the College of Science at Illinois Tech.

Part of that trip involved driving my electric Chevy Bolt from Atlanta to Chicago. You can do it, but it got a bit nerve wracking. There is only one high-speed charging station between Indianapolis and Chicago and you pray the charger outside the Lafayette Walmart actually works (it did). We passed many Tesla charging superstations, I will have to admit they have the better network. 

Theoremwise, Ryan Alweiss, Shachar Lovett, Kewen Wu and Jiapeng Zhang had significant improvements on the sunflower conjecture. I posted on the sunflower theorem for Richard Rado's centenary. Nice to see there is still some give in it.

I probably will post less often in this new position. Bill asked me "Why is being a dean (or maybe its just the move) more time then being a chair? Were you this busy when you moved and first became chair?"

When I moved to Atlanta, I moved a year ahead of the rest of the family and rented a condo. We had plenty of time to search for a house in Atlanta and plan the move. Here it all happened in a much more compressed time schedule and, since we've bought a condo, into a much more compressed space.

Being a chair certainly ate up plenty of time but it feels different as dean with a more external focus. I won't give up the blog but you'll probably hear a lot more from Bill than from me at least in the near future.

Can Mathematicians Fix Iphones? Can anyone?

In my last post I noted that if I am asked (since I am a CS prof)

Can you fix my iphone

is

No, I work on the math side of CS

Some readers emailed me (I told them to comment instead but they were worried that other readers would argue with them) that NO, this is a tired and incorrect stereotype. Here are some samples:

1) People in Mathematics are no better or worse at fixing iphones, fixing cars, programming their VCR's, etc than the public.

2) For that matter, people in academica, even in practical sounding fields like Systems, are no better.

3) Is your nephew Jason who used to fix forklifts for a living better at these things then the general public? I asked him. Answer: No, though he is better at fixing forklifts.

I think something else is going on here. Lets look at fixing your own car. I think this is the sort of thing that some people used to be able to do but now very few can do it. Cars have gotten more complicated.

Iphones are not quite there yet but its getting that way.

Of course somethings have gotten easier--- programming a DVR is much easier than programming a VCR. And people can easily use WORD or write programs without having to know any hardware.

OKAY, after all these random thoughts, here is the question: What do you think?

Are people in CS or Math or CS theory better at X than the general public where X is NOT CS, Math or CS theory, but something like fixing their cars?

And

What has gotten harder? What has gotten easier?

`Are you a math genius?' `Can you fix my Iphone?' `What do you think about Facebook and Privacy?'

When I meet non-math people and tell them I am a computer science professor I get a range of responses. Here are some and my responses.


1) Are you a math genius?

Here is the answer I give:

I know some things in math, frankly obscure things, that most people in math don't know. On the other hand, I probably can't help your teenage daughter with her trigonometry homework. Academics, like most people, forget what they don't use, and there are some things in math I rarely use, so I've forgotten them.

I wonder how a Fields' Medal winner would answer the question.

Although the above is the answer I give I really think its an ill defined and pointless question. Its very hard to measure genius or even define what it means (there are exceptions). After a certain age, what you've done is more important than how smart you allegedly are.

2) Can you fix my iPhone?

That's an easy one: No. I work on the math end of computer science. I don't elaborate.

3) What do you think of Facebook and privacy?

This is an odd one. I DO have opinions on this but they are NOT better informed just because I'm a comp sci professor. Since I don't have a Facebook account my opinions might be worse informed. So how do I respond? I show them

this Onion News Network Video about how the CIA created Facebook

Some think it's real. They may be right.

Obstacles to improving Classical Factoring Algorithms

In Samuel Wagstaff's excellent book The Joy of Factoring (see here for a review) there is a discussion towards the end about why factoring algorithms have not made much progress recently. I
paraphrase it:


--------------------------------------------------------

The time complexities of the fastest known algorithms can be expressed as a formula of the following form (where N is the number to be factored):

(*) exp(c(ln N)^t (ln(ln N))^{1-t})

for some constants c and for 0 < t < 1. For the Quadratic Sieve (QS) and Elliptic Curve Method (ECM) t=1/2. For the Number Field Sieve (NFS) t=1/3. The reason for this shape for the time complexity is the requirement of finding one or more smooth numbers (numbers that have only small primes as factors).

----------------------------------------------------------

This got me thinking: Okay, there may not be a drastic improvement anytime soon but what about just improving t? Is there a mathematical reason
why an algorithm with (say) t=1/4 has not been discovered? In an earlier era I would have had to write a letter to Dr. Wagstaff to ask him. Buy an envelope, buy a stamp, find his address, the whole nine yards (my younger readers should ask their grandparents what envelopes and stamps were). In the current era I emailed him. And got a response.


Samuel Wagstaff:

The fastest known factoring algorithms find smooth numbers subject to parameter choice(s). In all these algorithms, one parameter choice is the smoothness bound B: a number is smooth if all its prime factors are < B. The NFS has the degree of a polynomial as an additional parameter.

One analyzes the complexity of these algorithms by estimating the total work required (to find enough smooth numbers) for an arbitrary parameter choice using Dickman's function to predict the density of smooth numbers. Then one uses calculus to find the parameter choice(s) that minimize the total work function. Calculus also yields the optimal values for the parameter(s).

If you have k parameters to choose, you will get the time complexity (*) with t = 1/(1+k). If you have no parameters (k = 0),you get (*) with t = 1, basically exponential time N^c. With one parameter to optimize, as in CFRAC (continued fractions algorithm) and QS, you get t = 1/2. NFS has two parameters, so t = 1/3. ECM also has t = 1/2 because it uses only one parameter, the smoothness bound B. If you want to get t = 1/4, you have to find a third parameter to optimize. No one has found one yet. That is the answer to your question.

Note that some choices made in some factoring algorithms don't count as parameters. For example, the number of polynomials used in the multiple-polynomial quadratic sieve, and the upper bound on large primes kept, don't affect t. They affect the running time only in making c smaller. So you have to find a third parameter that matters in order to get (*) with t = 1/4. Or find three completely different new parameters.

Turing to be on the Bank of England 50 pound note, giving me an excuse to talk about Turing

BILL: Darling, guess who is soon going to be on the Bank of England 50 pound note?

DARLING: Alan Turing.

BILL: How did you deduce that? (She is right, see here.)

DARLING: Since you asked it, it couldn't be a member of the Royal Family (you don't care about that) or some British Politician (you don't care about that either). It had to be a mathematician or computer scientist.

BILL: It could have been Hardy. I wonder if Ramanujan could qualify---do they need to be British? At this website it says



Of course, banknotes need to be universally accepted. We therefore look for UK characters who have made an important contribution to our society and culture through their innovation, leadership or values. We do not include fictional characters, or people who are still living (except the monarch on the front of the note). Finally, we need to have a suitable portrait of the person which will be easy to recognise.

(They spell recognise with an s instead of a z, so spellcheck flagged it, but I won't change it.)

Note that people on the banknotes have to be UK characters. I honestly don't know if that means they must be citizens.

OKAY, so here are a few thoughts on Turing.

1) When I visited Bletchley Park there was a booklet that bragged about the fact that Bletchley Park was much better at cracking codes than Germany because they allowed people to work there based only on ability (unlike Germany) - women worked there, Turing who was Gay worked there. I think this is simplistic. Did any Jews work there (anti-semitism was widespread in England, and the world, at the time)? I doubt any blacks worked there since if they did that would be well known by now (if I am wrong let me know). Women DID work there but was their work respected and used? (I honestly don't know). Did Germany also use women at their codebreaking centers? Was Turing known to be gay (if not then Bletchley gets no points for tolerating him). Was JUST having Turing the reason they could crack codes. Plus I am sure there were other factors aside from merit-only.

2) Turing was given a Pardon for his ``crimes'' in August 2014. When I see things like this I wonder who was against it and why and if they were an obstacle.

a) Human Rights Advocate Peter Tatchell noted that its wrong to just single out Turing. Other people prosecuted under that law who did not help beat the German's in WW II should also be pardoned. The government later DID such a pardon in 2017.

b) Judge Minister Lord McNally objected to the pardon:

A posthumous pardon was not considered appropriate as Alan Turing was properly convicted of what at the time was a criminal offence. He would have known that his offence was against the law and that he would be prosecuted. It is tragic that Alan Turing was convicted of an offence that now seems both cruel and absurd—particularly poignant given his outstanding contribution to the war effort. However, the law at the time required a prosecution and, as such, long-standing policy has been to accept that such convictions took place and, rather than trying to alter the historical context and to put right what cannot be put right, ensure instead that we never again return to those times.


While I disagree with him, I do note that, based on what he wrote and his general record, I think he is not saying this from being anti-gay. There is a hard general question here: how does a society right past wrongs? I think pardoning and apologizing is certainly fine, but frankly it seems to weak. What else could a society due? Financial renumeration to living relatives? I don't think giving Inagh Payne (Turing's niece, who I think is still alive) would really help here.

c) At the bill's second reading in the House of Commons on 29 November 2013, Conservative MP Christopher Chope objected to the bill, delaying its passage


I couldn't find Chope's reasons. On the one hand, they may be similar to McNally's. On the other hand he is against same sex marriage so its possible (though I do not know this) that he anti-gay and that is why he is against the pardon. If someone can find what his explanation for blocking the Turing bill is, or other evidence that he is anti-gay, please leave it in the comments.

3) Did the delay matter? I was surprised to find out---Yes. Here is the full passage from Wikipedia:


At the bill's second reading in the House of Commons on 29 November 2013, Conservative MP Christopher Chope objected to the bill, delaying its passage. The bill was due to return to the House of Commons on 28 February 2014,[175] but before the bill could be debated in the House of Commons,[176] the government elected to proceed under the royal prerogative of mercy. On 24 December 2013, Queen Elizabeth II signed a pardon for Turing's conviction for "gross indecency", with immediate effect.[17] Announcing the pardon, Lord Chancellor Chris Grayling said Turing deserved to be "remembered and recognised for his fantastic contribution to the war effort" and not for his later criminal conviction.[16][18] The Queen officially pronounced Turing pardoned in August 2014.[177] The Queen's action is only the fourth royal pardon granted since the conclusion of the Second World War.[178] Pardons are normally granted only when the person is technically innocent, and a request has been made by the family or other interested party; neither condition was met in regard to Turing's conviction.[179]

This amazed me! I thought the Queen had NO power (too bad--- I wish she could just say NO BREXIT). Or that she formally has power but if she ever used it, it might be blocked somehow and taken away. So I am surprised she has a power she can use at all.

4) I wonder if the Pardon had to happen before they put him on the Banknote. I have been told that this is a very American Question--- England has no Constitution and operates more on Custom and Tradition than on written rules.

5) I had always assumed that Turing committed suicide. Without going into detail, the Wikipedia site on Turing does give intelligent counterarguments to this. See here

The Advisor/Advisee Relationship

I've always felt a strong advisor/advisee relationship is the single most important factor in a successful PhD career. At its best, the advisor works closely with the student to successful research agenda and help mentor them through their graduate career and beyond. The advisor/advisee relationship can feel like a parent/child relationship that lasts an entire career. Nothing gives me more pleasure as an academic than to see the success of my current and former students.

Take your time when picking an advisor. Don't choose an advisor based solely on research area or because they are "famous". Pick the advisor that will best guide you to a successful academic career.

At its worst, a bad advisor/advisee relationship will destroy your graduate career, making you feel miserable, perhaps dropping out of graduate school or worse, particularly if a student doesn't feel like they are being treated fairly.

Two incidents prompted this post. On TCS-Stack Exchange, a student has authorship issues with their advisor. Unfortunately these kinds of incidents happen more often than one suspects. If you can't work it out with the advisor, go talk to someone about it, another faculty, the graduate or department chair, a grad student ombudsperson if your institution has one. We care about our students, and will work hard to resolve problems.

In a much more tragic event, a student felt it easier to take his own life than feeling that he had to cover up potential academic misconduct. Again, if you ever find yourself in such a situation please reach out. Giving up is never the answer.