Cryptography with constant input locality (Q1037233)

The paper continues the study of cryptography in low complexity classes, and deals with the problem: Which cryptographic primitives can be realized by functions (with constant input locality) in which every bit of the input influences only a constant number of bits of the input? This is the inverse problem to one discussed in [SIAM J. Comput. 36, No. 4, 845--888 (2006; Zbl 1126.94014)]. It has been characterized what cryptographic tasks can be performed with constant input locality. Assuming the intractability of some problems from the domain of error correcting codes, the constructions of pseudorandom generators, commitments and semantically secure public key encryption schemes with constant input locality and constant output locality has been obtained. On the other hand, primitives which require some form of nonmalleability (such as signatures, MACs, and nonmaleable encryption schemes [\textit{D. Dolev, C. Dwork} and \textit{M. Naor}, SIAM J. Comput. 30, No. 2, 391--437 (2000; Zbl 0963.68067)]) cannot be realized with constant input locality.