Why doesn PGP use a “provably secure” cipher?
Because there are no practical ciphers which offer a general proof of security! Some ciphers offer provable security against certain specific classes of attacks (e.g. DFC [GGH+98]), and others offer a more general proof of security based upon some currently unproven underlying assumptions (e.g. Bear [AB96]). But none of these algorithms have undergone a significant amount of analysis. The Twofish paper [SKWWHF98] states that “Any reasonable proof of general security for a block cipher would also prove P != NP”. Similarly, [Bih99] states that “The search for provable security is still in progress, but it is not expected that a full proof of security of any cipher will be found in the next decades, as this proof is closely related to proving lower bounds of computational complexity, and to the problem of the relation of the classes P and NP.” [MOV96] says about unconditional security: “…it requires as many bits of secret key as plaintext and cannot be provided by a block cipher used to
