Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Cryptography in constant parallel time
Applebaum B., Springer Publishing Company, Incorporated, New York, NY, 2014. 210 pp. Type: Book (978-3-642173-66-0)
Date Reviewed: Aug 27 2014

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.

Reviewer:  Burkhard Englert Review #: CR142661 (1411-0921)
Bookmark and Share
  Reviewer Selected
Featured Reviewer
 
 
Data Encryption (E.3 )
 
 
Number-Theoretic Computations (F.2.1 ... )
 
 
Complexity Measures And Classes (F.1.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Data Encryption": Date
ESA/390 integrated cryptographic facility
Yeh P., Ronald M. S. IBM Systems Journal 30(2): 192-205, 1991. Type: Article
Feb 1 1992
Design and implementation of an RSA cryptosystem using multiple DSP chips
Er M., Wong D., Sethu A., Ngeow K. Microprocessors & Microsystems 15(7): 369-378, 1991. Type: Article
Nov 1 1993
An introduction to cryptography
Diffie W. (ed), Hellman M., John Wiley & Sons, Inc., New York, NY, 1984. Type: Book (9780471262336)
Feb 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy