Single-Server SPIR over Binary Erasure Channels: Benefits of Noisy Side Information

Shekofteh, Amirhossein; Chou, Rémi A.

Permalink

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

Description

Title

Single-Server SPIR over Binary Erasure Channels: Benefits of Noisy Side Information

Author(s)

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

Issue Date

2025-09-17

Keyword(s)

• Symmetric private information retrieval
• SPIR
• Side information
• Oblivious transfer

Abstract

We study single-server Symmetric Private Information Retrieval (SPIR), where the server and the client communicate over a binary erasure channel (BEC) and a public noiseless channel. The server stores D files, and the client has access to private noisy side information (PNSI) for each file, which is generated by passing the files through a set of discrete memoryless test channels. The statistics of these test channels are shared between the client and the server, but the mapping that links each file to a specific test channel remains private to the client. Our objective is to design a protocol that allows the client to retrieve one file while ensuring that (i) the server cannot deduce the mapping or the client’s file choice, and (ii) the client does not gain additional information about the remaining D − 1 files. We define the SPIR capacity under PNSI as the supremum of the ratio between the length of the requested file to the number of BEC uses. We characterize the SPIR capacity for D = 2 and derive upper and lower bounds on the SPIR capacity for D > 2. Our results show that PNSI about each file can help reduce the number of times the BEC is used compared to cases where the client has no side information or full knowledge of a subset of files, except in the special case where the client already knows D − 1 files perfectly.

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

Copyright and License Information

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

Owning Collections