Cryptography enables secure communication and computation even when those interested in infiltrating data are present. Today the application of cryptography has become indispensable for individuals and organizations, and cryptographic tools are widely employed.
This exciting new book focuses on the computational cost of cryptography overall and two cryptographic primitives in particular: computing a function that is hard to invert (a one-way function), and computing a function that expands “a short random seed into a longer ‘random-looking’ string” (a pseudorandom generator). The book explores the minimal computational complexity of these cryptographic primitives necessary to keep them secure.
We would like a cryptographic primitive to be as easy as possible to compute while at the same time being hard to invert (no efficient inversion algorithm exists). This book gives a surprising answer to this question and makes a significant breakthrough in the study of the theoretical foundations of cryptography. The author shows that one-way functions and pseudorandom generators can be made so computationally simple that “each bit of their output is only influenced by a constant number of input bits [they are in NC0], independently of the desired level of security.” Functions in NC0 are simpler than all current implementations of cryptographic primitives, and can be computed in constant parallel time, that is on a parallel computer with a polynomial number of processors they can be computed in constant time. Hence, for a problem in NC0, only the number of processors on a parallel machine but not the parallel computation time depends on the size of the problem. Problems in NC are tractable on a parallel computer.
Chapter 1 offers a brief introduction and an outline of the rest of the text. Chapter 2 provides preliminaries and definitions. In chapter 3, the randomized encoding of functions, both information-theoretic variants and a computational variant, are defined. Chapter 4 then moves on to cryptography in NC0, and the author shows that “randomized encoding preserves the security of many cryptographic primitives.” He then constructs an information-theoretic encoding in NC0 for any function in NC1.
Chapter 5 covers “computationally private randomizing polynomials and their applications.” In chapter 6, the existence of one-way functions in NC03 is shown. Chapter 7 examines the existence of “pseudorandom generators with linear stretch in NC0.” The author discusses “the possibility of carrying out cryptographic tasks by functions in which each input bit affects a constant number of output bits” in chapter 8.
This is an important book with groundbreaking results that will continue to influence research in this area for years to come. The book is based on the author’s PhD dissertation, and as such is really only accessible to readers with a solid background in cryptography and complexity theory. The ideal audience for this book comprises advanced graduate students or other researchers in the same field. The author, however, has added helpful examples and intuition in key locations to his original text, greatly helping the reader to absorb this inherently difficult material.