Ebook: Information-theoretic Cryptography

This book offers a mathematical foundation for modern cryptography. It is primarily intended as an introduction for graduate students. Readers should have basic knowledge of probability theory, but familiarity with computational complexity is not required. Starting from Shannon's classic result on secret key cryptography, fundamental topics of cryptography, such as secret key agreement, authentication, secret sharing, and secure computation, are covered. Particular attention is drawn to how correlated randomness can be used to construct cryptographic primitives. To evaluate the efficiency of such constructions, information-theoretic tools, such as smooth min/max entropies and information spectrum, are developed. The broad coverage means the book will also be useful to experts as well as students in cryptography as a reference for information-theoretic concepts and tools.

Cryptography is the science underlying all online payment systems and more recent blockchain and crypto engineering waves. Despite its popularity and its importance, it is quite difficult for most people outside the theoretical cryptography community to verify the security of basic cryptographic primitives. The reason for this is that cryptography has evolved rather rapidly and using a language which is not easily accessible by outsiders. Even for people working in related theoretical areas such as information theory or quantum physics, it is not easy to follow the ideas and details.

Admittedly, most exciting developments in practical cryptography have relied on computationally secure primitives, which can only be treated formally using these abstractions. Nonetheless, one would expect that information-theoretically secure cryptography could be understood without overly subscribing to these abstractions. Unfortunately, these details are scattered across technical papers and online lecture notes. This book is an attempt to collate this information in one place, in a form that is accessible to anyone with basic knowledge of probability.

Specifically, computational cryptography assumes the availability of certain computational primitives such as one-way functions which are easy to compute but computationally hard to invert. Using such primitives, we design cryptographic protocols that remain secure as long as the adversary is computationally restricted to using polynomial-time algorithms. On the other hand, information-theoretic cryptography seeks to establish cryptographic protocols that are information-theoretically secure. Often this requires additional resources; for instance, encryption is possible only when the parties share secret keys and two-party secure computation requires the availability of nontrivial correlated observations (such as oblivious transfer).

This book is a comprehensive presentation of information-theoretically secure cryptographic primitives, with emphasis on formal security analysis.