Relativized cryptography
- 1 October 1979
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 383-391
- https://doi.org/10.1109/sfcs.1979.36
Abstract
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.Keywords
This publication has 11 references indexed in Scilit:
- Cryptology in TransitionACM Computing Surveys, 1979
- Relativized cryptographyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- A note on the complexity of cryptography (Corresp.)IEEE Transactions on Information Theory, 1979
- On the cryptocomplexity of knapsack systemsPublished by Association for Computing Machinery (ACM) ,1979
- Secure communications over insecure channelsCommunications of the ACM, 1978
- A method for obtaining digital signatures and public-key cryptosystemsCommunications of the ACM, 1978
- Riemann's hypothesis and tests for primalityJournal of Computer and System Sciences, 1976
- New directions in cryptographyIEEE Transactions on Information Theory, 1976
- Communication Theory of Secrecy Systems*Bell System Technical Journal, 1949
- A Mathematical Theory of CommunicationBell System Technical Journal, 1948