Interview with Yael Tauman Kalai, a cryptographer at Microsoft | Hacker News Reader

Interview with Yael Tauman Kalai, a cryptographer at Microsoft

quantamagazine.org

116 pointsdigital559 comments

Some of Yael's most prominent works include the original paper on ring signatures [1], some important results around the Fiat-Shamir paradigm for signatures [2], the invention of One-Time Programs [3], some important work on interactive proofs [4], and a bunch of early fundamental (negative) results on obfuscation [5]. And these are just the things that spring to mind immediately, nowhere near the majority of her output.

[1] https://people.csail.mit.edu/rivest/pubs/RST01.pdf [2] https://eprint.iacr.org/2003/034.pdf [3] https://www.semanticscholar.org/paper/One-Time-Programs-Gold... [4] https://www.microsoft.com/en-us/research/wp-content/uploads/... [5] https://arxiv.org/abs/1401.0348

One-time programs are very interesting. They depend on specialized hardware (not surprising), but we already have precedent for such hardware, like TPMs. As usual, this would have uses like DRM, but also lots of other uses that most users will be more interested in.

>Kalai was born and raised in Tel Aviv, Israel, in an academic family. Her father, Yair Tauman, is an economist and game theorist. Her high school classes bored her — one report card documented something like 150 school absences, she recalls, as she preferred to spend her time water skiing and socializing. But her analytical skills were always there.

>“When my parents didn’t let me go out, often the only way to get my dad to agree was to tell him, ‘OK, give me a math riddle. As hard as you want, but if I solve, I go.’” She usually went.

wow

What kind of parent wouldn't give a kid something they had a chance of solving? I would have some "first solve the Riemann hypothesis" kind of problems on hand for when I really wanted her in the house.

> I was a bit upset, because I thought, “I can’t believe I could have enjoyed this when I was much younger!”

Yea, wish I had known about Galois theory when I was younger got sucked into junk lit and computer games instead, now I have to wait until I retire or get some economic buffer from grinding to learn what I want.

Sometimes I think a powerful factor in high-level accomplishment is appreciating something valuable sooner than others, which may depend on opportunity, luck, and the capability to appreciate (e.g.) high-level art or math as a teenager.

Of course, Galois and his fatal pistol duel were a long time ago, soooo, there are many polished presentations of Galois theory.

E.g., in the abstract algebra text by I. N. Herstein can learn the basics of Galois theory in a few hours of study.

Apparently the idea of using abstract algebra, especially fields (each of the rational, reals, and complex numbers are fields but not finite), for applications, especially to error correcting codes and, eventually, cryptography, date from Hamming back at Bell Labs.

In college and grad school, I got dragged into finite fields and related topics over and over. I was too patient and tolerant: I just don't like that math. I DO like linear algebra, especially for its connections with Hilbert space, differential equations, the math used in Maxwell's equations, differential geometry, optimization, relativity theory, Markov processes, and more but somehow I just don't like cryptography and error correcting codes. Back in college one of my profs just observed and remarked that I'm an analyst and not an algebraist! So, this situation may help others here at HN: Some people like math analysis while mostly others like math abstract algebra!

Still, just for Galois theory, if want to learn it, then can do that in a few hours!

Heh, just an example. But at the level of my interest it's not a few hours, I like to learn math so that "you could have invented galois theory", and I want to go up to Grobner basis at least.

The I. N. Herstein text does Galois theory with fully precise proofs. Learn those and could see how to "invent" Galois theory yourself. As I recall Herstein does not cover Gröbner basis. By now don't really have to look for a book and, instead, can use the Internet -- yes, some Internet material does provide careful proofs.

Reply on news.ycombinator.com