Skip to Main content Skip to Navigation

Codes with locality : constructions and applications to cryptographic protocols

Julien Lavauzelle 1, 2 
2 GRACE - Geometry, arithmetic, algorithms, codes and encryption
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : Locally correctable codes (LCCs) were introduced in order to retrieve pieces of information from a noisy codeword, by using a limited number of queries to its symbols, this number being called the locality. Three main families of LCCs reaching sublinear locality and arbitrarily high rate have been built so far. This specific range of parameters is of particular interest concerning practical applications of LCCs.In this thesis, after giving a state of the art for LCCs, we study how they can be built using block designs. We then give an analogue over projective spaces of the family of affine lifted codes introduced by Guo, Kopparty and Sudan. We exhibit several links between both families, and we give a precise analysis of the monomial structure of the code in the case of the lifting of order 2.The second part of the thesis focuses on the application of these codes to two cryptographic protocols. We first build a new private informatin retrieval (PIR) protocol from codes based on transversal designs, whose block size defines the locality of the code. Our construction features no computation on the server side, low storage overhead and moderate communication complexity. Then, we propose a new generic construction of proof-of-retrievability (PoR) that uses codes equipped with an elaborate structure of low-weight parity-check equations. We give a rigorous analysis of the security of our scheme, and we finally propose practical instantiations based on codes with locality.
Document type :
Complete list of metadata

Cited literature [143 references]  Display  Hide  Download
Contributor : ABES STAR :  Contact
Submitted on : Tuesday, December 11, 2018 - 11:24:17 AM
Last modification on : Saturday, June 25, 2022 - 7:43:40 PM
Long-term archiving on: : Tuesday, March 12, 2019 - 2:09:37 PM


Version validated by the jury (STAR)


  • HAL Id : tel-01951078, version 1


Julien Lavauzelle. Codes with locality : constructions and applications to cryptographic protocols. Information Theory [cs.IT]. Université Paris-Saclay, 2018. English. ⟨NNT : 2018SACLX082⟩. ⟨tel-01951078⟩



Record views


Files downloads