Cryptography in constant parallel time
type: Item
instance of: scholarly article
title: Cryptography in constant parallel time
zbMATH Open document ID: 1298.94001
DOI: 10.1007/978-3-642-17367-7
author: Benny Applebaum
published in: Information Security and Cryptography
publication date: 2011-02-14T00:00:00Z
review text: 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.
reviewed by: Jaak Henno
Mathematics Subject Classification ID: 94-01
Mathematics Subject Classification ID: 68-01
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 94A62
Mathematics Subject Classification ID: 68P25
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5851567
zbMATH Keywords: cryptography
zbMATH Keywords: parallel time-complexity
zbMATH Keywords: class \(N{C^0}\) circuit
zbMATH Keywords: one-way function
zbMATH Keywords: pseudorandom generator
zbMATH Keywords: symmetric encryption
zbMATH Keywords: public key encryption
zbMATH Keywords: digital signature
zbMATH Keywords: message authentication scheme
zbMATH Keywords: commitment scheme
zbMATH Keywords: collision resistant hash function
zbMATH Keywords: zero-knowledge proof
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/978-3-642-17367-7
OpenAlex ID: W1603472107
Recommended article: Cryptography with constant input locality
Recommended article: Cryptography with Constant Input Locality
Recommended article: Complexity and Cryptography
Recommended article: Complexity theory and cryptology. An introduction to cryptocomplexity.
Recommended article: Tutorials on the foundations of cryptography. Dedicated to Oded Goldreich
Recommended article: Q4941849
Recommended article: Q3413440
Recommended article: Fine-grained cryptography revisited
Recommended article: Cryptographic hardness of random local functions. Survey
description: scientific article; zbMATH DE number 5851567