ISIT Tutorial on Information-Theoretic SecurityInformation-theoretic Security: Theory and Practice
João Barros, University of Porto
Slides: Powerpoint File [4.6MB]
A typical graduate course in cryptography and security always starts by discussing Shannon's notion of perfect secrecy - widely accepted as the strictest notion of security -, and by emphasizing its conceptual beauty. Right after that, it questions the practicality of information-theoretic security. Such an introduction, which is indeed pervasive, provides the perfect motivation for state-of-the-art encryption algorithms that are insensitive to the characteristics of the communications channel and rely on mathematical operations assumed to be hard to compute, such as prime factorization and the discrete logarithm function.
In this tutorial, we shall do exactly the opposite. First, we will present in detail the necessary tools and background for basic concepts of information theoretic security, highlighting the differences between information theoretic security and classical cryptography. Next we discuss the major achievements of information-theoretic security and then we will demonstrate its potential to strengthen significantly the security of digital communications, well beyond what can be achieved by cryptographic means alone. The basic idea is to exploit the randomness of the communication channels at the physical layer of a communications network to guarantee that the sent messages cannot be decoded by a third party maliciously eavesdropping: security is ensured not relatively to a hard mathematical problem but by the physical uncertainty inherent to the noisy channel - the crux of Shannon's information theory.
Euro-NGI Tutorial on Network Information TheoryNetwork Information Theory: Principles and Applications
João Barros, University of Porto
Slides: PDF file
Since Shannon's A Mathematical Theory of Communication a lot has been accomplished in terms of characterizing and achieving the maximum achievable rate (i.e. the capacity) at which two partners can communicate over a noisy channel with arbitrarily small probability of error. Given the success of information theory in mastering point-to-point communications, one would be tempted to believe that a complete treatment of information flows over large networks with multiple communicating partners should not stay elusive for long. As it turns out, establishing the fundamental limits of communication over networks and designing near-to-optimal protocols and algorithms remain formidable tasks, which require a strong leap in conceptual tools and technical sophistication. Under the motto "there is nothing more practical than a good theory", this tutorial priviliges intuition over mathematical proofs in order to provide an introductory overview of some of the main results, applications and challenges that characterize the general area of network information theory. Particular attention will be given to multiple access communications, broadcast channels, distributed compression and relay networks. We shall also highlight the emergent area of network coding, where intermediate nodes are allowed to mix different packets, thus providing robust solutions for wireless networking and peer-to-peer content distribution.