Algebraic coding theory for private information retrieval

Abstract

Private Information Retrieval (PIR) protocols allow a user to retrieve an entry from a database without revealing to the database server which entry was retrieved. The first part of the thesis focuses on multi-server PIR protocols using binary cyclic codes. We construct PIR schemes with improved privacy guarantees by carefully selecting storage and retrieval codes with optimal or near-optimal parameters, comparing our schemes with known Reed–Muller-based constructions.  Afterward, the thesis proposes a novel single-server PIR scheme based on codes over rings, designed to resist linear algebra attacks. This new construction modifies and strengthens the earlier approach by incorporating cyclic inner codes and matrix-product outer codes, providing both efficiency and resistance to known attacks.  This thesis also focuses on the study of monomial–Cartesian codes and their Schur products. These codes are particularly relevant for the construction of  CSS–T quantum codes, which are capable of fault-tolerantly implementing non-Clifford gates like the T-gate. We generalize previous results and prove that J-affine variety codes support efficient componentwise multiplication and subfield-subcodes.  Moreover, we also consider Cartesian codes and their Schur products in the context of secure multi-party computation protocols. In secure multi-party computation, the subfield subcode of the component-wise square of an evaluation code and its dual code must be taken into account. Controlling the various parameters from a single code can be quite challenging. We will present some strategies for addressing these parameters while constructing codes from well-known families of Cartesian product codes.

Los protocolos de Recuperación de Información Privada (Private Information Retrieval, PIR) permiten al usuario recuperar una entrada de una base de datos sin revelar al servidor de la base de datos qué entrada se ha consultado. La primera parte de la tesis se centra en protocolos PIR multi-servidor utilizando códigos cíclicos binarios. Construimos esquemas PIR con mejores garantías de privacidad gracias a la selección cuidadosa de códigos de almacenamiento y de recuperación con parámetros óptimos o casi óptimos, comparando nuestros esquemas con construcciones conocidas basadas en códigos de Reed¿Muller. Posteriormente, se propone un novedoso esquema PIR de un solo servidor basado en códigos sobre anillos, diseñado para resistir ataques de álgebra lineal. Esta nueva construcción modifica y fortalece el enfoque anterior mediante la incorporación de códigos internos cíclicos y códigos externos de producto de matrices, proporcionando tanto eficiencia como resistencia frente a ataques conocidos. La tesis también se centra en el estudio de códigos monomiales¿cartesianos y sus productos de Schur. Estos códigos son particularmente relevantes para la construcción de códigos cuánticos CSS¿T, capaces de implementar con tolerancia a fallos puertas no-Clifford, como la puerta T. Generalizamos resultados previos y demostramos que los códigos de variedades J-afines permiten una multiplicación componente a componente eficiente y subcódigos subcuerpo. Además, consideramos también códigos cartesianos y sus productos de Schur en el contexto de protocolos de computación segura multipartita. En la computación segura multipartita, se debe tener en cuenta el subcódigo subcuerpo del cuadrado componente a componente de un código de evaluación y su código dual. Controlar los distintos parámetros de un sólo código puede ser bastante desafiante. Presentaremos algunas estrategias para abordar estos parámetros mientras construimos códigos a partir de familias conocidas de códigos de producto cartesiano.