Batch codes and their applications

ABSTRACT

A batch code encodes a string x into an m-tuple of strings, called buckets, such that each batch of k bits from x can be decoded by reading at most one (more generally, t) bits from each bucket. Batch codes can be viewed as relaxing several combinatorial objects, including expanders and locally decodable codes. We initiate the study of these codes by presenting some constructions, connections with other problems, and lower bounds. We also demonstrate the usefulness of batch codes by presenting two types of applications: trading maximal load for storage in certain load-balancing scenarios, and amortizing the computational cost of private information retrieval (PIR) and related cryptographic protocols.

REFERENCES

• 1: M. Ajtai , J. Komlos , E. Szemeredi, Deterministic simulation in LOGSPACE, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.132-140, January 1987, New York, New York, United States [doi>10.1145/28395.28410]
• 2: N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, and D. Ron. Testing low-degree polynomials over GF(2). In Proc. RANDOM 2003, pages 188--199.
• 3: Donald Beaver , Joan Feigenbaum, Hiding Instances in Multioracle Queries, Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Science, p.37-48, February 22-24, 1990
• 4: Amos Beimel , Yuval Ishai , Eyal Kushilevitz , Jean-François Raymond, Breaking the O(n1/(2k-1)) Barrier for Information-Theoretic Private Information Retrieval, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.261-270, November 16-19, 2002
• 5: Amos Beimel , Yuval Ishai , Tal Malkin, Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.55-73, August 20-24, 2000
• 6: C. Cachin, S. Micali, and M. Stadler. Computationally private information retrieval with polylogarithmic communication. In Proc. EUROCRYPT '99, LNCS 1592, pages 402--414.
• 7: Ran Canetti , Yuval Ishai , Ravi Kumar , Michael K. Reiter , Ronitt Rubinfeld , Rebecca N. Wright, Selective private function evaluation with applications to private statistics, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.293-304, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384047]
• 8: M. Capalbo, O. Reingold, S. Vadhan, and A. Wigderson. Randomness Conductors and Constant-Degree Expansion Beyond the Degree/2 Barrier. In Proc. 34th STOC, pages 659--668, 2002.
• 9: B. Chor , O. Goldreich , E. Kushilevitz , M. Sudan, Private information retrieval, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.41, October 23-25, 1995
• 10: B. Chor, N. Gilboa, and M. Naor Private information retrieval by keywords. Manuscript, 1998.
• 11: G. Di Crescenzo, T. Malkin, and R. Ostrovsky. Single Database Private Information Retrieval Implies Oblivious Transfer. In Proc. EUROCRYPT 2000, pages 122--138.
• 12: Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985 [doi>10.1145/3812.3818]
• 13: Joan Feigenbaum , Yuval Ishai , Tal Malkin , Kobbi Nissim , Martin Strauss , Rebecca N. Wright, Secure Multiparty Computation of Approximations, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.927-938, July 08-12, 2001
• 14: Yael Gertner , Shafi Goldwasser , Tal Malkin, A Random Server Model for Private Information Retrieval or How to Achieve Information Theoretic PIR Avoiding Database Replication, Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, p.200-217, October 08-10, 1998
• 15: Yael Gertner , Yuval Ishai , Eyal Kushilevitz , Tal Malkin, Protecting data privacy in private information retrieval schemes, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.151-160, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276723]
• 16: O. Goldreich. Secure multi-party computation. Available at http://philby. ucsb. edu/cryptolib/BOOKS, February 1999.
• 17: Russell Impagliazzo , Avi Wigderson, P = BPP if E requires exponential circuits: derandomizing the XOR lemma, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.220-229, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258590]
• 18: Jonathan Katz , Luca Trevisan, On the efficiency of local decoding procedures for error-correcting codes, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.80-86, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335315]
• 19: Joe Kilian, A note on efficient zero-knowledge proofs and arguments (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.723-732, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129782]
• 20: E. Kushilevitz , R. Ostrovsky, Replication is not needed: single database, computationally-private information retrieval, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.364, October 19-22, 1997
• 21: Chi-Jen Lu , Omer Reingold , Salil Vadhan , Avi Wigderson, Extractors: optimal up to constant factors, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780630]
• 22: F. J. MacWilliams and N. J. Sloane. The Theory of Error Correcting Codes. North-Holland, Amsterdam, 1977.
• 23: Moni Naor , Kobbi Nissim, Communication preserving protocols for secure function evaluation, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.590-599, July 2001, Hersonissos, Greece [doi>10.1145/380752.380855]
• 24: Moni Naor , Benny Pinkas, Oblivious transfer and polynomial evaluation, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.245-254, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301312]
• 25: Moni Naor , Benny Pinkas, Oblivious Transfer with Adaptive Queries, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.573-590, August 15-19, 1999
• 26: M. O. Rabin. How to exchange secrets by oblivious transfer. Technical report TR-81, Harvard Aiken Computation Laboratory, 1981.
• 27: Michael O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, Journal of the ACM (JACM), v.36 n.2, p.335-348, April 1989 [doi>10.1145/62044.62050]
• 28: C. Umans, Simple Extractors for All Min-Entropies and a New Pseudo-Random Generator, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.648, October 14-17, 2001
• 29: M. Sipser and D. A. Spielman. Expander codes. IEEE Transactions on Information Theory, 42(6):1710-1722, 1996.
• 30: Madhu Sudan , Luca Trevisan , Salil Vadhan, Pseudorandom generators without the XOR Lemma (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.537-546, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301397]
• 31: Amnon Ta-Shma , Christopher Umans , David Zuckerman, Loss-less condensers, unbalanced expanders, and extractors, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.143-152, July 2001, Hersonissos, Greece [doi>10.1145/380752.380790]
• 32: A. Ta-Shma , D. Zuckerman , S. Safra, Extractors from Reed-Muller Codes, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.638, October 14-17, 2001
• 33: Andrew Chi-Chih Yao, Should Tables Be Sorted?, Journal of the ACM (JACM), v.28 n.3, p.615-628, July 1981 [doi>10.1145/322261.322274]

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Reliability, Theory

Keywords:
coding, distributed storage, load balancing, locally decodable codes, private information retrieval