Paper 2022/764

Efficient Proofs of Retrievability using Expander Codes

Françoise Levy-dit-Vehel, Computer Science Laboratory of the École Polytechnique, ENSTA Paris, Inria Saclay - Île-de-France Research Centre, Institut Polytechnique de Paris
Maxime Roméas, Computer Science Laboratory of the École Polytechnique, École Polytechnique, Inria Saclay - Île-de-France Research Centre, Institut Polytechnique de Paris, French National Centre for Scientific Research
Abstract

Proofs of Retrievability (PoR) protocols ensure that a client can fully retrieve a large outsourced file from an untrusted server. Good PoRs should have low communication complexity, small storage overhead and clear security guarantees. We design a good PoR based on a family of graph codes called expander codes. We use expander codes based on graphs derived from point-line incidence relations of finite affine planes. Høholdt et al. showed that, when using Reed-Solomon codes as inner codes, these codes have good dimension and minimum distance over a relatively small alphabet. Moreover, expander codes possess very efficient unique decoding algorithms. We take advantage of these results to de- sign a PoR scheme that extracts the outsourced file in quasi-linear time and features better concrete parameters than state-of-the-art schemes w.r.t storage overhead and size of the outsourced file. Using the Con- structive Cryptography framework of Maurer, we get sharper and more rigourous security guarantees for our scheme than the ones given by the usual epsilon-adversary model. We follow an unbounded-use audit procedure to ensure that the extraction of the outsourced file will succeed w.h.p.. The properties of our expander codes yield an audit with communication complexity comparable to other code-based PoRs.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Proofs of retrievability Expander codes Outsourced storage
Contact author(s)
levy @ ensta fr
romeas @ lix polytechnique fr
History
2022-06-16: approved
2022-06-14: received
See all versions
Short URL
https://ia.cr/2022/764
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2022/764,
      author = {Françoise Levy-dit-Vehel and Maxime Roméas},
      title = {Efficient Proofs of Retrievability using Expander Codes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/764},
      year = {2022},
      url = {https://eprint.iacr.org/2022/764}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.