Relativized Cryptography

It seems very difficult to give a formal definition of computational security for Public Key Cryptography. We define a slightly different notion, called Transient-Key Cryptography, for which a natural definition of security against chosen-plaintext-attacks can be given. The main result presented here is the existence of a relativized model of computation under which there exists a provably secure transientkey cryptosystem. Indeed, there exists a computable oracle that can be used by cryptographers to efficiently encipher and decipher messages, yet it is of no help to the cryptanalyst trying to decode messages not intended for him. As a corollary, there exists a length-preserving permutation, the inverse of which is hard to compute on most elements of its domain even if arbitrary evaluations of the function itself are allowed for free.

Authors

• Gilles Brassard

Keywords

• Public key cryptography
• Computational complexity
• Information security
• Decoding
• Art
• Computational modeling
• Delay
• Communication system security
• Public key
• Distributed computing
• Computational Model
• Multi-party Computation
• Security Proof
• Definition Of Security
• Standard Model
• Encryption
• Secret Key
• Binary String
• Secure Communication
• Secure Channel
• Message Length
• Random String
• Cryptanalysis
• Shannon’s Information Theory