Paper 2015/165

The Cryptographic Hardness of Random Local Functions -- Survey

Benny Applebaum

Abstract

Constant parallel-time cryptography allows to perform complex cryptographic tasks at an ultimate level of parallelism, namely, by local functions that each of their output bits depend on a constant number of input bits. A natural way to obtain local cryptographic constructions is to use \emph{random local functions} in which each output bit is computed by applying some fixed $d$-ary predicate $P$ to a randomly chosen $d$-size subset of the input bits. In this work, we will study the cryptographic hardness of random local functions. In particular, we will survey known attacks and hardness results, discuss different flavors of hardness (one-wayness, pseudorandomness, collision resistance, public-key encryption), and mention applications to other problems in cryptography and computational complexity. We also present some open questions with the hope to develop a systematic study of the cryptographic hardness of local functions.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2013
Keywords
local cryptographyconstant-depth circuitsNC0one-way functionspseudorandom generatorshash functionspublic-key encryption
Contact author(s)
benny applebaum @ gmail com
History
2015-02-27: received
Short URL
https://ia.cr/2015/165
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/165,
      author = {Benny Applebaum},
      title = {The Cryptographic Hardness of Random Local Functions -- Survey},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/165},
      year = {2015},
      url = {https://eprint.iacr.org/2015/165}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.