This remarkable new book is one of the few that treats complexity-based approach to cryptography and it links it with two related fields, namely probabilistic proofs and pseudorandomness. Attendents of Crypto '97 will remember Oded Goldreich's invited talk that provided a basis for the first part of the book.
Citing from the preface:
The interplay between randomness and computation is one of the most fascinating scientific phenomena uncovered in the last couple of decades. This interplay is at the heart of modern cryptography and plays a fundamental role in complexity theory at large. Specifically, the interplay of randomness and computation is pivotal to several intriguing notions of probabilistic proof systems and is the focal of the computational approach to randomness. This book provides an introduction to these three, somewhat interwoven domains (i.e., cryptography, proofs and randomness).
This book offers an introduction and extensive survey to each of the three areas mentioned above. It present both the basic notions and the most important (and sometimes advanced) results. The presentation is focused on the essentials and does not ellaborate on details. In some cases it offers a novel and illuminating perspective. The goal is to provide the reader with
- A clear and structured overview of each of these areas.
- Knowledge of the most important notions, ideas, techniques and results in each area.
- Some new insights into each of these areas.
Please send your new book announcements to the newsletter editor at