17

Unfortunately, this doesn't seem to work (see below for details), and it seems hard to find a way to make this kind of idea yield a provably secure scheme. The problem with your general idea You're not the first to think of the idea of trying to base cryptography on NP-complete problems. The problem is that NP-hardness only ensures worst-case hardness, ...


12

The main thrust of Cao and Luo's argument is that in the variant of the algorithm that was implemented, the first register—that eventually contains the output—contains only 1 bit. And if you only get 1 bit of output from the algorithm, that's insufficient for factorization. (For one thing, although this isn't their argument, 1 bit clearly does not contain ...


5

Don't worry too much about understanding everything in one source. Try reading several different articles and from their summaries and technical details, you may build up your own understanding. Symbolic Execution for Software Testing: Three Decades Later, Cristian Cadar and Koushik Sen, 2013. All You Ever Wanted to Know about Dynamic Taint Analysis and ...


2

The Wikipedia page on "Post-quantum cryptography" provides a list of proposals for PKE resistant to quantum attacks. Quantum algorithms can solve DL in finite abelian groups (as well as a few nonabelian and infinite abelian ones), so they get very close to the spirit of the question you are asking. The learning with errors problem mentioned by one of the ...


1

Check Supersingular Isogeny Key Exchnage for some nice work on a Diffie-Hellman like Key Exchange based on isogenies between supersingular elliptic curves. This will compute computationally secure key. The authors mention that even though the key exchange is secure it will most likely be interesting purely for research/ pedagogical reasons. There also is a ...


1

Being a beginner to Symbolic Execution (SE) myself, I would suggest: Symbolic execution and program testing: this is the paper to cite when you mention SE. It is easy to read, and provides the key idea without much logical formulation. All you ever wanted to know...: this paper surveys SE and its applications to Security. The third step may be to ...


1

How about the de-anonymization of the Netflix Prize dataset? "Robust De-anonymization of Large Sparse Datasets" by Arvind Narayanan and Vitaly Shmatikov https://www.cs.utexas.edu/~shmat/shmat_oak08netflix.pdf It's ~5 years old, it's got a strong theory element to it, it's been implemented, and it's /sexy/ -- because Netflix. It's possible that ...


1

Today you should probably use Tabulation hashing for Linear Probing. In The Power of Simple Tabulation Hashing by Mihai Pătrașcu and Mikkel Thorup, this is shown to have at least the same guarantees as 5 independent hashing. Later work shows that it gives you better concentration (worst case bounds) as well. Tabulation hashing is also a lot faster than even ...


1

One potential issue is when reading from a hash table, the elements should not be read in the order of the slots if all hash tables use the same hash function. This is because those elements, in that order, can cause the insert procedure on a smaller hash table with the same hash function to go quadratic, assuming that the max fill factor is over $1/2$. See: ...


Only top voted, non community-wiki answers of a minimum length are eligible