Leaky Multi-Message Private Information Retrieval with Differential Privacy Guarantees

Heidarzadeh, Anoosheh; Zhao, Wenyuan; Tian, Chao; Sprintson, Alex

Permalink

https://hdl.handle.net/2142/130293 Copy

Description

Title

Leaky Multi-Message Private Information Retrieval with Differential Privacy Guarantees

Author(s)

• Heidarzadeh, Anoosheh
• Zhao, Wenyuan
• Tian, Chao
• Sprintson, Alex

Issue Date

2025-09-17

Keyword(s)

• Private information retrieval
• Differential privacy
• Information-theoretic privacy

Abstract

The Private Information Retrieval (PIR) problem aims to enable users to privately access data stored on remote servers. Recently, there has been a growing interest in leaky PIR schemes, which enable users to trade off higher rates for a controlled leakage of information about the identities of the downloaded messages. Motivated by applications that require the simultaneous retrieval of multiple data items, we focus on the ϵ-differential privacy framework for Leaky Multi-message PIR (LMPIR). Our paper complements the existing work on multi-message PIR, which has so far focused on perfect privacy. Our main contribution is the construction of an LMPIR scheme based on a randomized query and answer generation mechanism that carefully balances the tradeoff between privacy and efficiency, and is tailored to maximize the retrieval rate under the given privacy parameter ϵ. Our scheme requires a small degree of subpacketization L, which grows at most linearly with the number of servers. We also outline an information-theoretic upper bound on the maximum achievable rate for LMPIR. Our numerical results indicate that our scheme achieves a better privacy-efficiency tradeoff compared to alternatives, such as repeated application of leaky single-message PIR schemes.

Publisher

Allerton Conference on Communication, Control, and Computing

Series/Report Name or Number

2025 61st Allerton Conference on Communication, Control, and Computing Proceedings

ISSN

2836-4503

Type of Resource

Text

Genre of Resource

Conference Paper/Presentation

Language

eng

Handle URL

https://hdl.handle.net/2142/130293&&

Copyright and License Information

Copyright 2025 owned by the authors.

Owning Collections