Our understanding of the foundations of (quantum) cryptography has changed in the past couple of years. 

Arguably, the most important problem in computer science, the P vs. NP problem (which I will explain in the talk), restricts our ability to prove the security of modern cryptographic schemes: If P=NP, there can't be any classical cryptography, such as encryption, digital signatures, commitments. 

Recently, it has been shown that quantum cryptography can exist even if P=NP.

In this talk, I will focus on these recent advancements, focusing on two surprising relations that may be of special interest to physicists:

* Pseudorandom states were used in the context of AdS/CFT to argue that the dictionary map is exponentially complex.

* Pseudo-entangled states demonstrate that one cannot calculate or even approximate the entanglement entropy of a quantum state, even when given (polynomially) many copies of it.

I will not assume any background in computer science, quantum computing, or cryptography.