Codes with locality : constructions and applications to cryptographic protocols

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 :
Theses
Complete list of metadatas

Cited literature [143 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/tel-01951078
Contributor : Abes Star <>
Submitted on : Tuesday, December 11, 2018 - 11:24:17 AM
Last modification on : Friday, May 10, 2019 - 1:47:10 PM
Long-term archiving on : Tuesday, March 12, 2019 - 2:09:37 PM

File

72496_LAVAUZELLE_2018_archivag...
Version validated by the jury (STAR)

Identifiers

  • HAL Id : tel-01951078, version 1

Citation

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

Share

Metrics

Record views

236

Files downloads

237