TY - GEN
T1 - Vectorized Batch Private Information Retrieval
AU - Mughees, Muhammad Haris
AU - Ren, Ling
N1 - This work is partly funded by a gift from Google.
PY - 2023
Y1 - 2023
N2 - This paper studies Batch Private Information Retrieval (BatchPIR), a variant of private information retrieval (PIR) where the client wants to retrieve multiple entries from the server in one batch. BatchPIR matches the use case of many practical applications and holds the potential for substantial efficiency improvements over PIR in terms of amortized cost per query. Existing BatchPIR schemes have achieved decent computation efficiency but have not been able to improve communication efficiency at all. Using vectorized homomorphic encryption, we present the first BatchPIR protocol that is efficient in both computation and communication for a variety of database configurations. Specifically, to retrieve a batch of 256 entries from a database with one million entries of 256 bytes each, the communication cost of our scheme is 7.5x to 98.5x better than state-of-the-art solutions.
AB - This paper studies Batch Private Information Retrieval (BatchPIR), a variant of private information retrieval (PIR) where the client wants to retrieve multiple entries from the server in one batch. BatchPIR matches the use case of many practical applications and holds the potential for substantial efficiency improvements over PIR in terms of amortized cost per query. Existing BatchPIR schemes have achieved decent computation efficiency but have not been able to improve communication efficiency at all. Using vectorized homomorphic encryption, we present the first BatchPIR protocol that is efficient in both computation and communication for a variety of database configurations. Specifically, to retrieve a batch of 256 entries from a database with one million entries of 256 bytes each, the communication cost of our scheme is 7.5x to 98.5x better than state-of-the-art solutions.
KW - Homomorphic-Encryption
KW - Private-data
KW - Private-information-retrieval
UR - http://www.scopus.com/inward/record.url?scp=85166465156&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85166465156&partnerID=8YFLogxK
U2 - 10.1109/SP46215.2023.10179329
DO - 10.1109/SP46215.2023.10179329
M3 - Conference contribution
AN - SCOPUS:85166465156
T3 - Proceedings - IEEE Symposium on Security and Privacy
SP - 437
EP - 452
BT - Proceedings - 44th IEEE Symposium on Security and Privacy, SP 2023
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 44th IEEE Symposium on Security and Privacy, SP 2023
Y2 - 22 May 2023 through 25 May 2023
ER -