_d4bj

Thanks! I should probably include some more details on how to program the simulator.

Turing machines are just one simple way for formalizing programs, without all the complexities of modern programming languages. The core idea is that whatever a supercomputer (or any future computer) can compute, so can a Turing machine (it might just take more time): this is called the Church-Turing thesis.

The specifics on how to program Turing machines don't actually matter too much in modern complexity theory, but the rigorous basis is there when needed.

--

A Turing machine is always in some "state," (starts at A) and it's head is always over some cell of the tape, initially all zeros. Then the program, which is the grid in angelic hierarchy, specifies what the Turing machine should do. If it's in state A and the cell the head is at is 0, just go to the corresponding cell (marked in bright red), it will tell you the next state to go to, a number to write down on the tape, and a direction to step toward (Left or Right).

For intuition about why more states allow for more complex programs, try writing a 1-state program that writes two 1s and then halts (it's not possible). Then try it with 2 states.

I think the OP is referring to simulating an oblivious Turing machine on the encrypted data, which itself is a Turing machine and some data.

I don't think this is known to be intractable, just really slow (for now).

If there was no salt in the database, it looks Tumblr used a secret "pepper" (https://en.wikipedia.org/wiki/Pepper_(cryptography))? Why wouldn't they include a salt as well? Or did the database dump just not have the salt column?

>In the history of cryptology, women tend to be either systematically excluded or reduced to objects.

This is probably true, but cryptography/theoretical computer science might be one area where women have better representation than in other subfields of hard sciences.

https://en.wikipedia.org/wiki/Shafi_Goldwasser, who invented a huge portion of modern crypto (zero-knowledge, set lower bound, doubly-efficient proofs, etc.)

https://en.wikipedia.org/wiki/Irit_Dinur, who basically invented property testing as well as a novel proof of the PCP theorem that wasn't hundreds of pages long

http://www.cs.utexas.edu/~danama/, also known for her work on the PCP theorem (wife of Scott Aaronson)

http://elaineshi.com/, several papers on making ORAM and secure multiparty computation practical

Probably notable that the first three listed are all from/at the Weizmann Institute in Israel.

Recurse Center: https://www.recurse.com/. Anecdotally, not so easy to get in.