Limits of Provable Security for Homomorphic Encryption
In this paper the authors revisit the question of basing cryptography on NP-hardness. If P equals NP then computationally secure encryption is impossible. Is the converse true? Despite considerable e orts, there is no candidate encryption scheme whose security can be plausibly reduced to the worst-case hardness of some NP-complete problem. Neither is there conclusive evidence that rules out constructions of secure encryption schemes from NP-complete problems, although several obstacles have been pointed out over the years.