Is Secret sharing REALLY REALLY REALLY used?

Since I am teaching Cryptography this semester I am teaching things people REALLY REALLY REALLY (RRR) use. For some topics this is RRR true, like RSA (that it is used to transmit a private key that is then used is FINE.)

I was wondering if Information-Theoretic Secret Sharing is RRR used. I am asking non-cynically and non-rhetorically. So I want to be taken seriously AND literally.

  I Googled and got some answers but could not verify them.

1) At this site: here we can read

Every modern HSM (hardware secure module, for crypto applications) uses Shamir's secret sharing.

I tried to verify this but was unable to.

I also read

The DNSSEC root key is 5-out-of-7 shared see, e.g., here or here

The link leads to a story about how there are 7 people and if any 5 get together they can shut down the internet. The story does not say they use secret sharing.

2) Threshold cryptography (see here) would seem to use it, but is Threshold crypto used? There is a startup who is trying to use it: see here. I don't count that as RRR since they don't have customers yet. Not sure what the threshold is for whether I count it.

3) Some papers mention that secret sharing COULD be used if you want to make sure nuclear missiles are not launched unless x out of y people say so. But I doubt it really is used. If so this might be very hard to verify.

4) Shamir's secret sharing scheme is pretty simple and does not have big constants so if there is a need it really could be used. But is there a need?

I am not quite sure what I count as proof that someone RRR  using it. A random person at a random website just saying that HSM uses it does not seem convincing. A Wikipedia article saying its being used I would find convincing (should I? Until recently Wikipedia couldn't even get my year of birth straight, see here)

If some companies website said they used Shamir's Secret Sharing I would believe that-- but a companies website is not likely to say that. NOT for reasons of company secrets but because its not what most customers go to the website to find.

SO- if someone RRR knows that Secret Sharing is RRR being used then please leave a comment.

Simons and Amazon

I'm spending this week at the Simons Institute in smokey Berkeley, California. This fall Simons has a program in Lower Bounds in Computational Complexity. Scroll down that page and you'll see the rather strong collection of participants that are spending much of the fall at the Institute.

I purposely chose a week without a workshop--I'd rather talk to people than sit in talks. My former PhD student Rahul Santhanam is hosting me and we are having some fun discussions about the minimum circuit-size problems, pseudorandom generators and white vs black box algorithms. I've grown a little rusty in complexity during my years as department chair and have to work to keep up with Rahul. The student has become the master.

Even a quiet week at Simons is not that quiet. Every night seems to have a theme: trivia, board games, pub night, music night. I participated in a discussion with the "journalist in residence" on how to make lower bounds interesting to the general public. As part of a Turing awardee lecture series, Andy Yao gave a talk on Game Theory in Auction and Blockchain which included some reminiscing of Yao's golden time in Berkeley back in the early 80's when he helped lay the mathematical foundations of modern cryptography.

Simons started as a competition and, while I was on team Chicago, I have to admit Berkeley has done a wonderful job with the institute. We've just seen the results from another competition, with Amazon splitting their "second headquarters" between Northern Virginia and Queens, missing an awesome opportunity in Atlanta (not that I'm biased). Not surprised about the DC area, but pretty surprised about separating the HQ into two locations, neither planned to reach the level of activity of HQ1 in Seattle. Amazon stated that they didn't think they could find the tech talent to fill 50,000 positions in a single city. So much for "build it and they will come".

And the winner is again, Harambe: A pre election poll of my class that was truly a referenum on the Prez

I had meant to post this before the election but I didn't quite time it right. Oh well.

It has been said that this midterm election (more than others) was a referendum on the prez.  Every prez election year I have my students (or someone's students) vote (Secret Ballot of course) for president. ((see 2016 , 2012, 2008) This year, for the first time, I had a midterm election, though rather than ask them which Maryland people they would vote for, I made it truly a referendum on Trump by asking two questions:

1) Who did you vote for in 2016?

2) Knowing what you know now, who would have have voted for in 2016?

Full Disclosure: I am in the Clinton/Clinton Camp. However, this is an information-post not an opinion-post, so my vote is not relevant nor was it counted.

I give the full results at the end of the post; however, I will summarize the most interesting data: the change-mind people and my thoughts.

4 voted Trump and now wish they voted differently: Harmabe, Clinton, Nobody, Gasarch

Only 12 people had voted for Trump in 2016 and of those 4
regret it. While I can see wanting Clinton, Nobody, or Gasarch,
I'm surprised someone wanted Harmabe. Is he even a citizen?

5 voted Clinton and now wish they voted differently: 2-Johnson, Trump, Kanye, Gasarch.

Since Clinton hasn't done anything to merit rejection since the election,

I deduce these people are more going TOWARDS the one they picked rather

than AWAY from her. Trump has been Prez and has done stuff, so Clinton/Trump

makes sense -- the student's opinion is that Trump is doing better

than expected. Gary Johnson hasn't done anything to merit a change towards

him, so thats a puzzler.  Kanye, similar. As for Gasarch, if the reasoning

is `he's doing a good job teaching crypto, lets make him president' doesn't

really work since he's not doing THAT good a job. If it was Ramsey theory

then I could see it.

Misc:

1 Underwood(House of Cards)/Satan (For those tired of picking the LESSER of two evils)

1 Stein/Clinton

1 Johnson/Clinton

1 Kruskal/Gasarch (some people can't tell them apart)

The two who went to Clinton I interpret as thinking Trump is worse

than expected.

ALSO: Hillary had 28 Hillary/Hillary. Hence Trump had the largest percentage of people who regret voting for him, but still only 1/3. And the numbers are to small to make much of them.

MY OPINON: FORTNOW in 2020!

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

61 students did the poll.

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

Stayed the same:

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

Stayed the same:

28 Clinton/Clinton

8 Trump/Trump

4 Stein/Stein

3 Johnson/Johnson

1 Kasich/Kasich

1 Sanders/Sanders

1 Jerry White/Jerry White (Socialist Party)

1 Bofa/Bofa (this is a joke)

1 Thomas Adam Kirkman/Thomas Adam Kirkman (prez on TV show Designated Survivor)

48 do not regret their vote.

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

Trump/XXX

1 Trump/Harmabe (Harambe is the Gorilla who got shot in a zoo.)

1 Trump/Clinton

1 Trump/Nobody

1 Trump/Gasarch (Gasarch would prove the problems of government are unsolvable rather than solve them)

FOUR people voted Trump and now regret it.

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

Clinton/XXX

2 Clinton/Johnson

1 Clinton/Trump

1 Clinton/Kanye

1 Clinton/Gasarch

FIVE people voted Clinton and now regret it.

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

MISC changed

1 Underwood(House of Cards)/Satan (For those tired of picking the LESSER of two evils)

1 Stein/Clinton

1 Johnson/Clinton

1 Kruskal/Gasarch (some people can't tell them apart)

TWO people who voted third party now would have voted Clinton.

I interpret this as not-liking-Trump since I don't think Clinton

has done anything since the election to make anyone thing better

or worse of her, while as Trump as president has done enough

to change people's opinions of him.

The Data Transformation of Universities

With all the news about elections, caravans, shootings and attorney generals, maybe you missed the various stories about real transformations at our top universities.

On October 15 MIT announced the Stephen A. Schwarzman College of Computing. Schwarzmann donated $350 million to the effort as part of an expected billion-dollar commitment that will pay for a new building and fifty new faculty.

“As computing reshapes our world, MIT intends to help make sure it does so for the good of all,” says MIT President L. Rafael Reif. “In keeping with the scope of this challenge, we are reshaping MIT. The MIT Schwarzman College of Computing will constitute both a global center for computing research and education, and an intellectual foundry for powerful new AI tools. Just as important, the College will equip students and researchers in any discipline to use computing and AI to advance their disciplines and vice-versa, as well as to think critically about the human impact of their work. 

Two weeks later the University of California at Berkeley announced a Division of Data Science to be led by an associate provost reporting directly to the provost (like a dean).

“Berkeley’s powerful research engine, coupled with its deep commitment to equity and diversity, creates a strong bedrock from which to build the future foundations of this fast-changing field while ensuring that its applications and impacts serve to benefit society as a whole,” said Paul Alivisatos, executive vice chancellor and provost. “The division’s broad scope and its facilitation of new cross-disciplinary work will uniquely position Berkeley to lead in our data-rich age. It will simultaneously allow a new discipline to emerge and strengthen existing ones.”

Sorry Berkeley, you are anything but unique. Every major research university is trying to build up expertise in computing and data science given the demands of students, industry and researchers across nearly all academic disciplines who need help and guidance in collecting, managing, analyzing and interpreting data.

Here at Georgia Tech, where we've had a College of Computing since 1990, we recently started an Interdisciplinary Research Institute in Data Science and Engineering and a Interdisciplinary Research Center in Machine Learning both to be housed in a twenty-one story CODA building that will open next year in Midtown Atlanta (sounds impressive when I write it down).

I could go on for pages on how other universities are rethinking and transforming themselves. Earlier this year Columbia (who hired Jeannette Wing to run their data science institute) held a summit of academic data science leadership. The report shows we have much to do.

The real secret is that none of us have really figured it out, how to meet the escalating needs for computing and data and integrating it across campus. We aim at a moving target problem as we sit just at the beginning of the data revolution that will reshape society. The future looks rocky, scary and fun.

Is Fuzzy Sets Common Knowledge? How about Napier as inventing (or something) logs?

Darling: Bill, help me with this crossword puzzle. 6 letter word that begins with N, clue is log man

Bill: Napier

Darling: Who was that?

Bill: A famous lumberjack

Darling: Give me a serious answer

Bill: Okay. He is said to have invented logarithms. Like most things in math its not quite clear who gets the credit, but he was involved with logarithms early on.

Darling: I said give me a serious answer. That is rather obscure and would not be in a crossword puzzle.

While darling is wrong about the answer being wrong she is right about it being obscure. How would your typical crossword puzzler know the answer? Perhaps Napier appears in a lot of crosswords since it has lots of vowels, so they just word-associate `log man' to `Napier'  But in any case this does seem odd for a crossword puzzle.

In the quiz show Jeopardy, in round two, the following was an $800 question under philosophy (the questions are 400,800,1200,1600,2000, so 800 is supposed to be easy)

In 1965 Lotfi Zadeh introduced this type of set with no clear boundaries leading to the same type of ``logic''

1) I suspect that all my readers know that the correct response is `Fuzzy' (or formally `What is Fuzzy')

2) Why is this in Philosophy? There IS an entry of it in the Stanford Enc of Phil (see here). Some Philosophers work on Logic, but do they work on Fuzzy Logic? The wikipedia page for Fuzzy Logic (see here) has only one mention of phil and its to the Stanford Enc of Phil chapter.

3) (more my point) Is Fuzzy Logic so well known as to be an easy question on Jeop? See next point

4) Can someone get this one right WITHOUT knowing ever having heard of Fuzzy Logic. I suspect yes and, indeed, the contestant DID get it right and I think she had never heard of Fuzzy Logic. While I can't be sure one tell is that when a contestant says `what is fuzzy logic' and it actually sounds like a question, then they are partially guessing.

Anyway, I am surprised that this obscure bit of math made it into an easy question on Jeop. But since the contestant got it right, it was appropriate.

P = NP Need Not Give a SAT Algorithm

In Bill's post earlier this week, he asks if there is a fixed algorithm such that if P = NP, this algorithm will correctly compute satisfiability on all inputs. While I believe this statement is true because P ≠ NP, I would like to argue we won't prove it anytime soon.

Bill links to a TCS Stack Exchange answer by Marzio De Biasi giving a fixed algorithm that would get SAT correct except on a finite number of inputs if P = NP. Here is Marzio's algorithm.

Input: x   (boolean formula)
Find the minimum i such that
  1) |M_i| < log(log(|x|))  [ M_1,M_2,... is a standard fixed TM enumeration] 
  2) and  M_i solves SAT correctly 
       on all formulas |y| < log(log(|x|))
          halting in no more than |y|^|M_i| steps
          [ checkable in polynomial time w.r.t. |x| ]
  if such i exists simulate M_i on input x 
      until it stops and accept/reject according to its output
      or until it reaches 2^|x| steps and in this case reject;
  if such i doesn't exist loop for 2^|x| steps and reject.

This proof relativizes: There is a fixed relativizing Turing machine M such that for all A, if P^A = NP^A then L(M^A) runs in polynomial time and differs from SAT^A on only a finite number of strings. SAT^A is a relativizable form of SAT with a built in relations that answer whether a sequence of variables encode an string in A. SAT^A is NP^A-complete for all A.

The following shows any proof that a fixed algorithm can compute all of SAT correctly if P = NP cannot relativize.

Theorem: For every deterministic Turing machine M, there is an A such that P^A = NP^A and either M^A does not compute SAT^A correctly on all inputs or M^A takes at least exponential time.

Proof:

Define B = {0x | x in TQBF}. TQBF is the PSPACE-complete problem containing all the true quantified Boolean formula. P^TQBF = PSPACE = NP^TQBF and thus P^B = NP^B.

Let φ_n be the formula that is true if there exists a string z of length n such that 1z is in A. Let n be the smallest n such that M^B(φ_n) takes less than 2ⁿ computational steps. If no such n exists let A = B and we are done.

If M^B(φ_n) accepts we are done by letting A=B since B has no string beginning with 1.

If M^B(φ_n) rejects and uses less than 2ⁿ steps there must be some z such that M^B(φ_n) did not query 1z. Let A = B ∪ {1z}.

M^A(φ_n) still rejects but now φ_n is in SAT^A. Also P^A = NP^A since adding a single string to an oracle won't affect whether two classes collapse.

If P=NP then we HAVE an alg for SAT.

I am writing up the result of my survey of peoples opinion of P vs NP (it will be in a SIGACT News, in Lane's Complexity Column, in 2019.) Some  people wrote:

                          P=NP but the proof will be nonconstructive and have a large constant.

Large constant could happen.

If by nonconstructive they mean not practical, then yes, that could happen.

The following does not quite show it can't happen but it does give one pause:  an old result of Levin's shows that there is a program you could write NOW such that if P=NP then this program decides SAT except for a finite number of formulas (all of which are NOT in SAT) and can be proven to work in poly time (I will later give three pointers to proofs). The finite number of formulas is why the people above may still be right. But only a finite number- seems like a weak kind of nonconstructive.

Since I am teaching crypto I wondered about Factoring. An old result of Gasarch (I proved it this morning -- I am sure it is already known) shows that there is a program you could write NOW such that if Factoring is in P then this program factors a number ALWAYS (none of this finite exception crap) and can be proven to work in poly time. Even so, the algorithm is insane. If someone thought that factoring in P might be nonconstructive, my construction disproves it in such an absurd  way that  the notion that factoring could be in P nonconstructively should be taken seriously but not literally. There should be a way to say formally:

I believe that FACTORING is in P but  any poly-time algorithm is insane (not even looking at the constants) and hence could never be implemented.


Not sure how to define insane.

Three pointers:

Stack Exchange TCS:  here

Wikipedia: here

My slides (also include factoring result): here

Question: Can the SAT result be improved to be an algorithm that is ALWAYS right? Is there a way to show that it can't be (unless, say P=NP).

Question: What can be said about Graph Isomphism in this context? The proof for SAT is easily adpated to this case (all we used about SAT was that it was self-reducible). But can we get our GI algorithm to never make a mistake?

Good Results Made Meaningless

Sometimes you see a beautiful theorem A that you love to talk about. Then another beautiful theorem B comes around, making the first one meaningless since B trivially implies A. Not just a mere extension of A but B had a completely different proof of something much stronger. People will forget all about A--why bother when you have B? Too bad because A was such a nice breakthrough in its time.

Let me give two examples.

In STOC 1995 Nisan and Ta-Shma showed that Symmetric logspace is closed under complement. Their proof worked quite differently from the 1988 Immerman-Szelepcsenyi nondeterministic logpsace closed under complement construction. Nisan and Ta-Shma created monotone circuits out of undirected graphs and used these monotone circuits to create sorting networks to count the number of connected components of the graph.

Ten years later Omer Reingold showed that symmetric logspace was the same as deterministic logspace making the Nisan-Ta-Shma result an trivial corollary. Reingold's proof used walks on expander graphs and the Nisan-Ta-Shma construction was lost to history.

In the late 80's we had several randomized algorithms for testing primality but they didn't usually give a proof that the number was prime. A nice result of Goldwasser and Kilian gave a way to randomly generate certified primes, primes with proofs of primeness. Adleman and Huang later showed that one can randomly find a proof of primeness for any prime.

In 2002, Agrawal, Kayal and Saxena showed Primes in P, i.e., primes no longer needed a proof of primeness. As Joe Kilian said to me at the time, "there goes my best chance at a Gödel Prize".