A k-server Private Information Retrieval (PIR) code is a binary linear [m, s]-code admitting a generator matrix such that for every integer i with 1≤i≤s there exist k disjoint subsets of columns (called recovery sets) that add up to the vector of weight one, with the single 1 in position i. A k-server PIR code is useful to reduce the storage overhead of a traditional k-server PIR protocol. Finding k-server PIR codes with a small blocklength for a given dimension has recently become an important research challenge. In this work, we propose new constructions of PIR codes from combinatorial structures, introducing the notion of k-partial packing. Several bounds over the existing literature are improved.

PIR Codes from Combinatorial Structures

Giulietti, Massimo;Timpanella, Marco
2023

Abstract

A k-server Private Information Retrieval (PIR) code is a binary linear [m, s]-code admitting a generator matrix such that for every integer i with 1≤i≤s there exist k disjoint subsets of columns (called recovery sets) that add up to the vector of weight one, with the single 1 in position i. A k-server PIR code is useful to reduce the storage overhead of a traditional k-server PIR protocol. Finding k-server PIR codes with a small blocklength for a given dimension has recently become an important research challenge. In this work, we propose new constructions of PIR codes from combinatorial structures, introducing the notion of k-partial packing. Several bounds over the existing literature are improved.
2023
978-3-031-22943-5
978-3-031-22944-2
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/1538473
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact