PIR codes from combinatorial structures

DOI10.1007/978-3-031-22944-2_10MaRDI QIDQ6169010zbMATH OpenOpenAlexFDO

Authors Massimo Giulietti, Arianna Sabatini, Marco Timpanella

Publication date 10 August 2023

Published in Arithmetic of Finite Fields (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2107.01169

zbMATH Keywords

configurationspackingsPIR codesprivacy information retrieval

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Privacy of data (68P27) Linear codes (general theory) (94B05)

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 $1leiles$ 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$. As shown in cite{Fazeli1}, 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.

Recommendations

• PIR codes with short block length
• Optimal possibly nonlinear 3-PIR codes of small size
• General constructions for information-theoretic private information retrieval

Cites work

• scientific article; zbMATH DE number 1101474 (Why is no real title available?)
• Line partitions of internal points to a conic in \(\mathrm{PG}(2,q)\)
• Maximal arcs, codes, and new links between projective planes of order 16
• Nonsymmetric configurations with natural index
• On constructions and parameters of symmetric configurations \(v_k\)
• On parallelisms in finite projective spaces
• On resolvable Golomb rulers, symmetric configurations and progressive dinner parties
• Partitioning the planes of \(AG_{2m}(2)\) into 2-designs
• PIR codes with short block length
• Resolvable configurations
• The CRC handbook of combinatorial designs
• The semigroup of combinatorial configurations

Cited in

(3)

• PIR codes with short block length
• PIR Array Codes With Optimal Virtual Server Rate
• Optimal possibly nonlinear 3-PIR codes of small size

This page was built for publication: PIR codes from combinatorial structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6169010)