Welcome to the resource topic for 2022/764
Title:
Efficient Proofs of Retrievability using Expander Codes
Authors: Françoise Levy-dit-Vehel and Maxime Roméas
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.
ePrint: https://eprint.iacr.org/2022/764
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .