Batch codes and their applications

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.

Authors

• Yuval Ishai
• Eyal Kushilevitz
• Rafail Ostrovsky
• Amit Sahai

Keywords

• coding
• distributed storage
• load balancing
• locally decodable codes
• private information retrieval