Andrej Bogdanov, On Breaking Encryption with a Statistical Zero-knowledge Oracle

Basing security of encryption on NP-hardness is a longstanding challenge in the foundations of cryptography. Under standard complexity-theoretic assumptions, such encryption should be secure even if the adversary had access to a statistical zero-knowledge (SZK) oracle, which is believed to have the ability to solve some intractable problems but not NP-complete ones. I will show some examples of classical and newer public-key encryption schemes that are vulnerable to SZK attacks, and some for which an SZK attack is not known.