In distributed storage systems, a collection of storage nodes may need to serve multiple data requests simultaneously. Batch codes, introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai [1], address this by encoding $k$ information symbols into $n$ coded symbols distributed across several groups (buckets), such that any batch of up to $t$ distinct information symbols can be retrieved by reading at most $r$ symbols from each bucket. The parameters $(n, k, t, r)$ capture the trade-off between storage overhead, parallelism, and per-node load.

A related notion is that of PIR codes, which enable private information retrieval by ensuring that any single information symbol can be recovered from several disjoint subsets of coded symbols, preventing any single server from learning which symbol was requested. Batch codes and PIR codes share a close structural relationship, and bounds on their respective code lengths have been studied both separately and in a unified framework [3]. Beyond this connection, various constructions of batch codes have been proposed, including graph-based codes [1], combinatorial batch codes [2], and constructions based on classical code families.

The goal of the seminar is to study the original batch codes framework, explore foundational definitions, known constructions and bounds, and examine how batch codes relate to PIR and distributed storage. 

References:

[1] Ishai, Yuval, et al. "Batch codes and their applications." Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. 2004.

[2] Stinson, Douglas R., Ruizhong Wei, and Maura B. Paterson. "Combinatorial batch codes." Advances in Mathematics of Communications 3.1 (2009): 13-27.

[3] Zhang, Yiwei, Tuvi Etzion, and Eitan Yaakobi. "Bounds on the length of functional PIR and batch codes." IEEE Transactions on Information Theory 66.8 (2020): 4917-4934.

Voraussetzungen

Fully Homomorphic Encryption (FHE) allows the evaluation of any function representable as an arithmetic circuit on encrypted data without needing to decrypt first. The main issue hindering the deployment for many practical applications is the high computational overhead incurred by the need to regularly perform a procedure called Bootstrapping, which essentially consists of the homomorphic evaluation of the decryption function.
For almost all known FHE constructions, decryption fails with a certain probability, which results in faulty evaluation outcomes.

In the distributed computing setting, Lagrange Coded Computation (LCC) is a well-known approach to achieving (Byzantine) fault-tolerance and resilience against stragglers for the evaluation of arbitrary multivariate polynomials up to a chosen degree. To achieve this, the data is encoded using a Reed-Solomon code, which allows the correct evaluation result to be obtained by decoding a potentially corrupted codeword. 

It is currently unknown whether the use of LCC to reduce the need for bootstrapping can improve the overall efficiency of FHE. The goal of this research internship is to help answer this question by determining the algebraic circuit complexity of decoding Reed-Solomon codes.

Reed-Solomon (RS) codes are a very popular class of codes with applications in distributed storage, computation and communication. Interleaved RS (IRS) codes can be viewed as multiple parallel codewords of possibly different RS codes. Whenever errors occur within the same subset of positions for all the codewords, with high probability, these codes allow to correct many more random errors than guaranteed by the unique error correction capability of the individual codes [1]. Very recently, the semi-adversarial setting where some errors occur not uniformly random but are potentially adversarial was investigated [3], but many questions remain open. Alternatively, decoding beyond the unique decoding radius is possible by allowing the decoder to output a list of potential codewords. In some cases, if extra information about the transmitted codeword is known, the list can be filtered down to at most one codeword [2]. List-decoding of interleaved RS codes is an underexplored research direction.

Lagrange coded computing (LCC) [4] is a distributed computation scheme which utilizes RS decoding to achieve resilience against adversarial and straggling workers, as well as privacy assuming limited collusion. The objective of this project is to design and analyze decoding techniques for IRS codes with the goal of improving upon LCC.

[1] https://www.cs.umd.edu/~gasarch/TOPICS/pir/breakpir2.pdf

[2] https://ieeexplore.ieee.org/document/1214429

[3] https://arxiv.org/pdf/2504.10399

[4] https://proceedings.mlr.press/v89/yu19b/yu19b.pdf

Voraussetzungen