2007 | OriginalPaper | Buchkapitel
Cryptography with Constant Input Locality
(Extended Abstract)
verfasst von : Benny Applebaum, Yuval Ishai, Eyal Kushilevitz
Erschienen in: Advances in Cryptology - CRYPTO 2007
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the following natural question: Which cryptographic primitives (if any) can be realized by functions with constant input locality, namely functions in which every bit of the
input
influences only a constant number of bits of the output? This continues the study of cryptography in low complexity classes. It was recently shown (Applebaum et al., FOCS 2004) that, under standard cryptographic assumptions, most cryptographic primitives can be realized by functions with constant
output
locality, namely ones in which every bit of the
output
is influenced by a constant number of bits from the input.
We (almost) characterize what cryptographic tasks can be performed with constant input locality. On the negative side, we show that primitives which require some form of non-malleability (such as digital signatures, message authentication, or non-malleable encryption)
cannot
be realized with constant input locality. On the positive side, assuming the intractability of certain problems from the domain of error correcting codes (namely, hardness of decoding a random linear code or the security of the McEliece cryptosystem), we obtain new constructions of one-way functions, pseudorandom generators, commitments, and semantically-secure public-key encryption schemes whose input locality is constant. Moreover, these constructions also enjoy constant
output locality
. Therefore, they give rise to cryptographic hardware that has constant-depth, constant fan-in and constant
fan-out
. As a byproduct, we obtain a pseudorandom generator whose output and input locality are both optimal (namely, 3).