Conditionally-perfect secrecy and a provably-secure randomized cipher

✍ Scribed by Ueli M. Maurer

• Book ID: 104657557
• Publisher: Springer
• Year: 1992
• Tongue: English
• Weight: 788 KB
• Volume: 5
• Category: Article
• ISSN: 0933-2790
• DOI: 10.1007/bf00191321

✦ Synopsis

Shannon's pessimistic theorem, which states that a cipher can be perfect 0nly when the entropy of the secret key is at least as great as that of the plaintext, is relativized by the demonstration of a randomized cipher in which the secret key is short but the plaintext can be very long. This cipher is shown to be "perfect with high probability." More precisely, the eavesdropper is unable to obtain any information about the plaintext when a certain security event occurs, and the probability of this event is shown to be arbitrarily close to one unless the eavesdropper performs an infeasible computation. This cipher exploits the assumed existence of a publiclyaccessible string of random bits whose length is much greater than that of all the plaintext to be encrypted; this is a feature that our cipher has in common with the previously considered "book ciphers". Two modifications of this cipher are discussed that may lead to practical provably-secure ciphers based on either of two assumptions that appear to be novel in cryptography, viz., the (sole) assumption that the enemy's memory capacity (but not his computing power) is restricted and the assumption that an explicit function is, in a specified sense, eontrollably-difticult to compute, but not necessarily one-way.