Cryptography in constant parallel time (Q625101)

Function is locally computable or ``computationally simple'' (can be implemented by a class \(N{C^0}\) circuit), if every bit of the output can be computed by reading a constant number of bits of the input. The author proved in his PhD dissertation in 2007 [Cryptography in constant parallel time, \url{http://www.eng.tau.ac.il/~bennyap/pubs/thesis.pdf}], that under standard intractability assumptions used in cryptography (e.g. that factoring large integers is computationally hard) most cryptographic primitives (one-way functions, pseudorandom generators, symmetric and public key encryption schemes, digital signatures, message authentication schemes, commitment schemes, collision resistant hash functions, zero-knowledge proofs) can be implemented as locally computable functions, actually as functions where every output bit depends only on four input bits; he also provided a compiler that transforms an implementation of a cryptographic primitive in a relatively high complexity class into an \(N{C^0}\) implementation. This book is based on the author's dissertation with some additions [\textit{B. Applebaum} et al., Comput. Complexity 15, No. 2, 115--162 (2006; Zbl 1143.94009)] and references to recent results in parallel cryptography. The book requires only minimal knowledge in computational complexity and cryptography and can be used as a textbook for advanced or graduate students, but it is useful also for researchers.