Towards Foundations of Cryptography: Investigation of Perfect Secrecy
H. Jürgensen (Department of Computer Science, The University of Western Ontario, Canada)
L. Robbins (Department of Computer Science, The University of Western Ontario, Canada)
Abstract: In the spirit of Shannon s theory of secrecy systems we analyse several possible natural definitons of the notion of perfect secrecy, these definitions are based on arguments taken from probability theory, information theory, the theory of computational complexity, and the theory of program-size complexity or algorithmic information. It turns out that none of these definitions models the intuitive notion of perfect secrecy completely: Some fail because a cryptographic system with weak keys can be proven to achieve perfect secrecy in their framework, others fail, because a system which, intuitively, achieves perfect secrecy cannot be proven to do so in their framework.
To present this analysis we develop a general formal framework in which to express and measure secrecy aspects of information transmission systems.
Our analysis leads to a clarification of the intuition which any definition of the notion of perfect secrecy should capture and the conjecture, that such a definition may be impossible, that is, that only secrecy by degrees can be defined rigorously.
This analysis also leads to a clarification of what the cryptographic literature refers to as the one-time pad. On the basis of the arguments used for its strength in the literature, one has to distinguish between two quite different systems: the first kind uses randomly chosen strings of some given length, the second kind uses random strings, that is, patternless strings of some given length. The former achieves perfect secrecy in the sense of Shannon, but permits weak keys - like the all-zero key, the latter, while intuitively stronger, does not achieve perfect secrecy in any of the proposed senses.
Finally, the analysis exposes the need for a formal, non-operational, but mathematical definition of the notion of weak key.
1.) C. Calude (ed.). The Finite, the Unbounded and the Infinite, Proceedings of the Summer School "Chaitin Complexity and Applications", Mangalia, Romania, 27 June - 6 July, 1995. The research reported in this paper was supported by the Natural Sciences and Engineering Council of Canada, Grant OGP0000243.
Keywords: computational complexity, cryptography, information theory, perfect secrecy, program-size complexity