Improved Achievable Rate for Single-Server SPIR over Binary Erasure Channels

Shekofteh, Amirhossein; Chou, Rémi A.

Permalink

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

Description

Title

Improved Achievable Rate for Single-Server SPIR over Binary Erasure Channels

Author(s)

• Shekofteh, Amirhossein
• Chou, Rémi A.

Issue Date

2025-09-17

Keyword(s)

• SPIR
• Symmetric private information retrieval
• Private information retrieval

Abstract

In 1-out-of-D Symmetric Private Information Retrieval (SPIR) protocols, the client privately selects and retrieves one of the D files stored on a server, learns nothing about the remaining D − 1 files, and keeps its choice hidden from the server. We propose an achievable rate scheme for 1-out-of- D SPIR in a single-server setting over a binary erasure channel (BEC) with parameter ϵ, where the server controls the BEC input and the client observes the output. Existing 1-out-of-D SPIR protocols over BEC that build on repeated 1-out-of-2 primitives define the achievable rate as the number of bits transmitted per channel use. We propose a 1-out-of-D SPIR scheme over the BEC by repeating a novel 1-out-of-M SPIR scheme where [Editor’s note: see paper for mathematical equation]. Our derived achievable rate surpasses existing rates for ϵ ∈ [1/2, 1], and achieves the SPIR capacity for D = 2, and for D > 2 when [Editor’s note: see paper for mathematical equation].

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/130304&&

Copyright and License Information

Copyright 2025 is held by Amirhossein Shekofteh and Rémi A. Chou.

Owning Collections