Conditionally-perfect secrecy and a provably-secure randomized cipher (Q1184508)

The design of both practical and provably secure cryptosystems is known to be a hard task, especially if one excludes various contributes to the effort by demonstrating that slightly relaxing the notion of perfect secrecy together with an assumption on computational limitations of the enemy allows for building a provably secure cipher whose secret key is short compared to the length of plaintext. The relaxation consists of replacing ``perfect secrecy'' notion by ``perfect with high probability'' one. One such cipher is described and proof of its information-theoretic security against all feasible attacks is given.