Batch codes and their applications

By Yuval Ishai, Eyal Kushilevitz, Rafail M. Ostrovsky, Amit Sahai. 2004

286 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Molecular Biology

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Molecular Biology

Citations in the corpus

Private Stateful Information Retrieval (2018, methodology): “This is an extension of private batched retrieval [30] where only records, instead of sums of records, are retrieved.”
PIR with Compressed Queries and Amortized Query Processing (2018, methodology): “[47]) with our construction based on PBCs, we achieve 3.”
Private Information Retrieval From MDS Coded Data in Distributed Storage Systems (2016, methodology): “PIR on coded data was studied in the literature on Batch Codes [17], where the data is coded to allow parallel processing leading to amortizing the PIR communication cost over multiple retrievals.”
Multi-query Computationally-Private Information Retrieval with Constant Communication Rate (2010, background): “Ishai, Kushilevitz, Ostrovsky and Sahai [7] proposed batch-codes for encoding a database over many separate blocks such that a client can extract m records by querying only a smaller number of records from each block.”
Private information retrieval in distributed storage systems using an arbitrary linear code (2016, background): “Since then, coded PIR schemes have been introduced, where the database is encoded (as opposed to simply being replicated) across several nodes [3].”
Searchable symmetric encryption: Improved definitions and efficient constructions (2006, unknown): “The ﬁrst, which we refer to as non-adaptive , only considers adversaries that make their search queries without taking into account the trapdoors and search outcomes of previous searches.”
Optimal binary switch codes with small query size (2015, methodology): “al [1] demonstrated that the subcube code can solve requests of length 2.”
A Fast Single Server Private Information Retrieval Protocol with Low Communication Cost (2014, methodology): “We will extend the protocol to multi-query PIR [39].”
The Capacity of Robust Private Information Retrieval With Colluding Databases (2016, background): “The significance of PIR also extends beyond security, through its fundamental connections to other prominent topics such as locally decodable codes [8] and batch codes [9] in coding theory, relationships between communi-”
Polynomial Batch Codes for Efficient IT-PIR (2016, background): “The q-batch queries and u -ary encodings respectively discussed in Sections 2 and 3 are both closely related to batch codes, which were introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai [36] as a way to reduce the server-side computation cost of PIR in cases where clients wish to fetch several ”
Sublinear Scaling for Multi-Client Private Information Retrieval (2015, methodology): “[13] use batch codes (discussed in more detail below) to provide multi-query computational speedups for any PIR scheme.”
Can We Access a Database Both Locally and Privately? (2017, background): “The question of reducing the amortized computational cost of multi-query PIR was subsequently studied in [IKOS04, IKOS06].”
Communication-Computation Trade-offs in PIR (2019, background): “[40] proposed a construction based on batch codes, which achieves asymptotic improvements in the communication and computation amortized cost multi-query PIR but remains impractical.”
Linear Batch Codes (2014, background): “Then, we present a number of simple constructions of larger linear batch codes from the smaller ones.”
Scalable and Private Media Consumption with Popcorn (2016, background): “[58], show that one can achieve sub-linear server-side computation by efficiently processing batches of requests from multiple clients.”
On the Computational Practicality of Private Information Retrieval (2006, background): “[44] proposed the use of batch codes to amortize the server-side computation complexity of PIR over k queries performed by a single client.”
Efficient Pseudorandom Correlation Generators: Silent OT Extension and More (2019, methodology): “An MPFSS can be easily obtained by adding t instances of DPF; optimized constructions of MPFSS, using batch codes [48] to speed up the full domain evaluation algorithm, were presented in [14].”