This tutorial provides an introduction to cryptography, specifically addressed at an information theory and coding theory (as opposed to computer science) audience. It covers, in a rigorous style, a selection of the most fundamental cryptographic concepts and results, as well as some recent research highlights. No specific prerequisites are assumed.

There are two types of cryptographic security. The security of a system can rely either on the computational infeasibility of breaking it (computational or complexity-theoretic security), or on the theoretical impossibility of breaking it, even using infinite computing power (information-theoretic or unconditional security). In contrast to computational security, which always relies on unproven assumptions such as the hardness of factoring large integers, information-theoretically secure systems rely on no such assumptions but tend to be less practical.

The traditional application of information theory in cryptography is for proving impossibility results, like Shannon's lower bound on the required key size for a perfect encryption system, but more recent results on information-theoretic cryptography are positive in nature, making statements about what is possible rather than what is impossible. Moreover, probability-theoretic and information-theoretic techniques have found many application in cryptographic security proofs relative to computational assumptions.

- Basic concepts and security definitions: Encryption, key agreement, authentication, digital signatures, etc.
- Information-theoretic analysis of encryption and authentication
- Privacy amplification and randomness extraction
- Secret-key agreement by public discussion
- Indistinguishability-based security definitions and proofs
- Public-key cryptography and the generic group model
- Zero-knowledge interactive proofs and the simulation paradigm
- Secret Sharing
- Broadcast (or Byzantine agreement) protocols
- Secure multi-party computation protocols

** Ueli Maurer, ** born in 1960, is professor of computer science and head
of the Information Security and Cryptography Research Group at the
Swiss Federal Institute of Technology (ETH), Zurich. His research
interests include information security, the theory and applications of
cryptography, theoretical computer science, discrete mathematics, and
information theory. Maurer graduated in electrical engineering and
received his Ph.D. degree in Technical Sciences from ETH Zurich. From
1990 to 1991 he was DIMACS research fellow at the Department of
Computer Science at Princeton University, and in 1992 he joined the CS
Department at ETH Zurich.

He has served extensively as an editor and a member of program committees. Currently he is Editor-in-Chief of the Journal of Cryptology, Editor-in-Chief (with Ronald Rivest) of Springer Verlag's book series in Information Security and Cryptography, and serves on the Board of Directors of the International Association for Cryptologic Research (IACR). He also served as an associate editor for the IEEE Transactions on Information Theory. He is a Fellow of the IEEE, was the 2000 Rademacher Lecturer of the Department of Mathematics at Penn, and is a frequent invited speaker at scientific conferences.

Maurer holds several patents for cryptographic systems and has served as a consultant for many companies and government organizations, both at the management and the technical level. He serves on a few management and scientific advisory boards and is a co-founder of the Zurich-based security software company Seclutions.

Many problems in science and engineering require that we take into account uncertainties in the observed data and uncertainties in the model that is used to analyze the data. Probability theory (in particular, Bayes rule) provides a way to account for uncertainty, by combining the evidence provided by the data with prior knowledge about the problem. Recently, we have seen an increasing abundance of data and computational power, and this has motivated researchers to develop techniques for solving large-scale problems that require complex chains of reasoning applied to large datasets. For example, a typical problem that my group works on will have 100,000 to 1,000,000 or more unobserved random variables. In such large-scale systems, the structure of the probability model plays a crucial role and this structure can be easily represented using a graph.

Click here (.pdf version) for a preview of the theory and algorithms to be presented.

- Review of the definitions and properties of the main
types of graphical models
- Factor graphs
- Bayesian networks
- Markov random fields

- Lyapunov functions that can be used to formulate approximate solutions to exact inference and parameter estimation problems (which are NP hard)
- Leading-edge,
computationally efficient techniques for approximate inference
- Sum-product algorithm
- Iterative conditional modes
- EM algorithm
- Markov chain Monte Carlo methods
- Mean field techniques
- Structured variational methods
- Wake-sleep algorithm.

Throughout the tutorial, examples will be taken from the application area of computer vision, to demonstrate the concepts. However, applications in image processing, digital communications, speech processing and computational molecular biology will also be described.

** Brendan J. Frey ** was born on August 29, 1968, in Calgary, Alberta
near the foothills of the Rocky Mountains, where he enjoyed hiking
and camping with his family. In 1979, he started writing computer
programs, attaching sensors to his home computer, and building
simple robots. His first publication (Run Magazine, 1981) describes
software for simulating a generative model of images, where the
pixel intensities are independent. His academic education was in
the areas of physics, engineering and computer science, culminating
with a doctorate from Geoffrey Hinton's Neural Networks Research
Group at the University of Toronto in 1997. From 1997 to 1999, Frey
was a Beckman Fellow at the University of Illinois at Urbana-Champaign,
where he continues to be an adjunct faculty member in Electrical
and Computer Engineering. From 1998 to 2001, he was a faculty
member in Computer Science at the University of Waterloo. Currently,
Frey is head of the Probabilistic and Statistical Inference Group,
in the Department of Electrical and Computer Engineering at the
University of Toronto. Frey consults for Microsoft Research Redmond,
and various start-up companies in the Toronto-Waterloo area.
He has received several awards, including the Premier's Research
Excellence Award of Canada, and he has given over 40 invited talks and
published over 100 papers on inference and estimation in complex
probability models, with applications in machine learning, computer
vision, molecular biology, audio processing, image processing and
iterative decoding. In 2003, he co-chaired the * Canadian Workshop on
Information Theory* and the * Workshop on Artificial Intelligence and
Statistics*. He was a Co-Editor-in-Chief of the February 2000 special
issue of the *IEEE Transactions on Information Theory*, titled
* Codes on Graphs and Iterative Algorithms,* and is currently an
Associate Editor of the * IEEE Transactions on Pattern Analysis and
Machine Intelligence. *

Wireless communications are characterized by random propagation
conditions commonly referred to as {\em fading channels}.
Roughly, a fading channel is a linear time-varying channel whose impulse
response is a random process. Reliable communication over a fading channel
is made possible only through the use of diversity techniques. Since the
channel response at any given time and frequency (i.e., channel dimension,
or ``degree of freedom'') is a random variable, it is essential that
each bit of information is * spread * over several dimensions.
This can be achieved, classically, by coding in the time-frequency
domain. Time duration and frequency bandwidth being expensive, the
number of channel degrees of freedom for
diversity can be increased in the space domain, by adding
spatially separated antennas at the receiver and the
transmitter. Antenna diversity
reception and its synergies with channel coding have been
extensively studied in the past, and several techniques are
widely used in practical systems.
Since the mid-90's, driven by the ever-growing demand for higher
wireless link throughputs and better reliability, the research on
multiple-antenna techniques has been focused on
multiple-antenna * transmission *, rather than the conventional
multiple-antenna reception.
Information theoretical studies of multiple-antenna systems promised
a large increase in the throughput over single antenna systems.
Motivated by the theoretical promises, coding over multiple antennas
(*space*) and over *time* has emerged
as a powerful tool to improve the quality of service over wireless
communications. An impressive amount of work has been done on this
field in the last five years. This
body of work involves, often with cross-fertilization and
synergies, the fields of * coding theory, information
theory, signal processing * and * communications *. Therefore,
we will generally refer to this field as * Space-Time Signaling.*
The impact of Space-Time Signaling techniques over today's and
future wireless telecommunications standards is central, and it is
expected to increase due to the ever-growing demand
for better spectral efficiency and better quality of service over
wireless communications.

In this tutorial, we give a comprehensive treatment of space-time signalings under different channel state information (CSI) assumptions. We provide a unified treatment of the different design approaches proposed in the literature. After reviewing the information theoretic foundations, multiple-input multiple-output (MIMO) channels modeling, and the signal design criteria, we elaborate a unified approach to the different space-time signaling schemes in the literature (e.g., orthogonal designs, trellis space-time codes, linear constellations, ...), under different CSI scenarios (i.e., adaptive, coherent, non-coherent, and differentially coherent). Similarly, we elaborate a unified approach to the receiver architecture and the signal processing of the different signaling schemes. We then discuss the diversity versus rate tradeoffs of MIMO channels under different constraints. Some classes of space-time signaling schemes achieving the optimal diversity versus rate tradeoffs are elaborated. Finally, we draw some conclusions and present some problems for future research.

For further information please see the web pages of the speakers: Caire -- Damen -- El Gamal

- Information theoretic background (using space to obtain diversity and create parallel channels).
- Space-time codes over QAM constellations (binary rank criteria).
- Linear space-time constellations (orthogonal designs and linear dispersion codes).
- Differential and training based schemes.
- Receiver architectures (iterative decoding, sphere and sequential decoding).
- The diversity-vs-rate tradeoff: Achieving the optimal diversity-vs-multiplexing tradeoff (Lattice Space-Time coding)
- Diversity from time and frequency selectivity.
- A look into distributed space-time codes in mobile ad-hoc networks (MANETs).
- Open problems, summary and conclusions.

** Giuseppe Caire ** was born in Torino, Italy, in 1965. He received the
B.Sc. in Electrical Engineering from Politecnico di Torino (Italy) in 1990,
the M.Sc. in Electrical Engineering from Princeton University in 1992, and the
Ph.D. from Politecnico di Torino in 1994. He was a recipient of the AEI G.Someda
Scholarship in 1991, was with the European Space Agency (ESTEC, Noordwijk, The
Netherlands) from May 1994 to February 1995, and was a recipient of the COTRAO
Scholarship in 1996 and a CNR Scholarship in 1997. He visited Princeton University
in summer 1997 and Sydney University in summer 2000. He has been Assistant Professor
in Telecommunications at the Politecnico di Torino and presently he is Professor
with the Department of Mobile Communications of the Institute Eurecom, Sophia-Antipolis,
France.

Dr. Caire served as Associate Editor for the * IEEE Transactions on Communications
* in 1998-2001 and as Associate Editor for the * IEEE Transactions on Information
Theory * in 2001-2003. In 2003 he received the Jack Neubauer Best System
Paper Award from the IEEE Vehicular Technology Society. His current interests
are in the field of communications theory, information theory and coding theory
with particular focus on wireless applications.

** Mohamed Oussama Damen ** received a B.Sc. degree in mathematics from
the University of Paris VII in 1995, an M.Sc. degree (with honors) in digital
communications systems from the Ecole Nationale Superieure des Telecommunications
(ENST) de Paris, France, in 1996 and a Ph.D. degree (Summa Cum Laude) in electronics
and communications from the ENST, Paris, France, in October 1999. He was a post-doctoral
researcher at ENST, Paris, France, from November 1999 to August 2000, and at
the Department of Electrical and Computer Engineering at the University of Minnesota
from September 2000 to March 2001. In March 2001, he joined the Department of
Electrical and Computer Engineering at the University of Alberta, where he is
now a senior research associate of Alberta Informatics Circle of Research Excellence
(ICORE). His current research interests are in the areas of communication theory,
coding theory, and information theory, with a special emphasis on coding for
multiple-input multiple-output (MIMO) channels.

** Hesham El Gamal ** received the B.S. and M.S. degrees in Electrical
Engineering from Cairo University, Cairo, Egypt, in 1993 and 1996, respectively,
and the Ph.D. degree in Electrical and Computer Engineering from the University
of Maryland at College Park, in 1999. From 1993 to 1996, he served as a Project
Manager in the Middle East Regional Office of Alcatel Telecom. From 1996 to
1999, he was a Research Assistant in the Department of Electrical and Computer
Engineering, the University of Maryland at College Park. From February 1999
to December 2000, he was with the Advanced Development Group, Hughes Network
Systems, Germantown, Maryland, as a Senior Member of the Technical Staff. In
the Fall of 1999, he served as a lecturer at the University of Maryland at College
Park. Since January 2001 he has been an Assistant Professor in the Electrical
Engineering Department at the Ohio State University in Columbus, Ohio. He held
visiting appointments at UCLA (Fall 2002, Winter 2003) and Eurecom Institute
(Summer 2003)

He is a recipient of the Hughes Networking Systems Annual Achievement Award
(2000), the Ohio State University College of Engineering Lumley Research Award
(2003), the Ohio State University Electrical Engineering Department FARMER Young
Faculty Development Fund (2003-2008), and the National Science Foundation CAREER
Award (2004). He holds 4 patents and has 9 more applications pending. He is
a Senior Member of the IEEE, currently serves as an Associate Editor for Space-Time
Coding and Spread Spectrum for the * IEEE Transactions on Communications,
* and is a member of the SP4COM technical committee.

Quantum mechanics is perhaps the most successful scientific theory of all times. Even though it is often counterintuitive, its predictions have never been observed to be wrong, no matter how strange they appear to be. Information theory is also a very successful theory, but it is firmly rooted in classical physics, which is at best an approximation of the world in which we live. This has prevented us from tapping the full potential of Nature for information processing purposes. Classical and quantum information can be harnessed together to accomplish feats that neither could achieve alone, such as quantum computing, quantum cryptography, quantum teleportation and the computation of distributed tasks with vastly reduced communication cost. Some of these concepts are still theoretical, but others have been implemented in the laboratory.

Quantum Computers can perform more parallel computation in a single piece of hardware than would be possible for a classical computer the size of the Universe. In particular, quantum computers have the potential to bring to its knees the classical cryptographic schemes currently used on the Internet to protect transactions such as the transmission of credit card numbers. Fortunately, Quantum Cryptography makes it possible to fulfill the cryptographers' age-old dream of unconditional confidentiality in communications, regardless of the eavesdropper's computing power and technological sophistication. This technique has been implemented over tens of kilometers, both using ordinary optical fiber and through free space. Implementation via satellites is being considered. Quantum teleportation conjures up images of Star Trek, but it is not science fiction. It uses quantum nonlocality to transmit quantum information through a classical channel between entangled parties. Finally, the same quantum nonlocality gives rise to the possibility of computing in a distributed environment with the expenditure of spectacularly less information transfer between the participants than would be required classically, and sometimes we can do away with communication altogether. Speculation? Future will tell!

- Basic concepts of quantum information: qubits, measurements, transformations.
- Quantum cryptography: a simple and powerful application.
- Quantum entanglement: the soul of quantum information.
- Quantum teleportation: an application of quantum entanglement.
- Quantum computation: an exponential speedup with no classical counterpart.
- Quantum communication: exponential savings in communication needs.
- Pseudo-telepathy: sometimes communication is not needed at all.

** Gilles Brassard ** received a Ph.D. in Computer Science from Cornell
University in 1979. He has been a Professor at the Universite de Montreal since
then. He was Editor-in-Chief for * Journal of Cryptology* from 1991 until
1997, Program Chair for * Crypto '89 * and Program Committee Member for
* Crypto '88 *, * 1992 IEEE Conference on Structures in Complexity Theory
*, * Crypto '97 *, and other international conferences. He is the author
of three books that have been translated into 7 languages. He was awarded the
E.W.R. Steacie Memorial Fellowship and the Prix Urgel-Archambault in 1992, and
the Steacie Prize in 1994. He was chosen ``Scientist of the Year'' by La Presse
in 1995, elected to the Academy of Science of the Royal Society of Canada in
1996, awarded a Killam Research Fellowship in 1997, and elected foreign member
of the Latvian Academy of Science in 1998. He received the Prix Marie-Victorin
in 2000, became Canada Research Chair in Quantum Information Processing in 2001
and he became Fellow of the Canadian Institute for Advanced Research in 2002.
Gilles Brassard is interested in all aspects of quantum information processing,
which lies at the intersection of computer science and quantum mechanics. Among
his main achievements, is the co-invention of quantum cryptography, privacy
amplification, quantum teleportation and quantum entanglement distillation.
Home