11th Estonian Winter School in Computer Science (EWSCS)
XI Eesti Arvutiteaduse Talvekool
Palmse, Estonia, March 5-10, 2006
under the auspices of European Educational Forum
James Massey
Copenhagen, DK
Information Theory and Cryptography
Abstract
These three lectures are unified by their application of information-theoretic techniques, particularly coding theory, to cryptographic problems. The first lecture will review Shannon's theory of secrecy with its notion of perfect secrecy and required key length. Simmons' theory of authenticity will also be reviewed and explained with the aid of Blahut's information-theoretic approach to hypothesis testing as formulated by Maurer. The second lecture will exploit the close relationship between error-correcting codes and orthogonal arrays in which dual codes play a central role. The necessary coding background will be presented, then applied to the study of functions useful in cryptography, including correlation-immune functions, resilient functions and local randomizers. The third lecture will deal with Shamir's formulation of secret sharing for which error-correcting codes provide a simple and powerful generalization to arbitrary access structures. Linear complexity will be introduced and related to properties of the Discrete Fourier Transform, then applied to the study of stream ciphers. The Reed-Muller codes will be formulated in a manner that permits an insightful characterization of an important class of stream ciphers.Course materials
- J. L. Massey. Lecture I: Shannon's theory of secrecy and its extension to authenticity. Slides. [pdf]
- J. L. Massey. Lecture II: Orthogonal arrays and error-correcting codes in cryptography. Slides. [pdf]
- J. L. Massey. Lecture III: Secret sharing and linear complexity. Slides. [pdf]
About the Lecturer
URL: Page at ETH Zürich