Suppose P=NPP = NP and a fast linear-time algorithm for SAT appears tomorrow. Suddenly RSA is insecure, much of our modern communication system is broken, and we need to reconsider how to keep secrets from each other. Question: Is there a good single reference (or short list) to gain a big-picture view of what is possible in crypto (and in the allied field of "security") without intractability assumptions? This could save civilization one day, and would also be nice to peruse in the meantime. Discussion: Most of the cryptographic tasks we now study (OWFs, PRGs, PKE) are provably impossible in the P=NPP = NP world (a world dubbed "Algorithmica" in an influential essay by Impagliazzo), but some things remain possible: communication with a one-time pad; distributed secret sharing; private info retrieval; and some other nice things.

cr.crypto security - Cryptography without assumptions -- seeking an overview - Theoretical Computer Science Stack Exchange Thursday, April 3, 2014 @ 11:47am