, at least guess) a key ? such that Init(m, ?) = w, 2. build m = m such that Init(m , ?) = w , and 3. define a malicious response word r ? P (w ) which (i) successfully passes every audit and (ii) leads to the extraction of m = m
, Hence, we choose to use a weaker but still realistic security model, where informally, the Prover only knows what he stores (that is, w) and has no information on the initial message m. Therefore, this security model is also conform with the one given by
, we need to look for (sequences of) codes C and associated verification structures (Q, V) such that: 1. the response code R(C) admits a good relative distance ? =, vol.18
, 5 characterise conditions under which the last two points are fulfilled. Then, in Section 5.5 we study some response codes in the perspective of achieving good relative distance, PORS FROM CODES WITH LOCALITY Lemma 5.23. Let C = Par() ? F N q as above
, Résumé de la construction d'un protocole de PIR à base de codes d'incidences.. xiii 2 Outline of the construction of a distributed PIR protocol using incidence codes
,
Comparison of high-rate lifted and multiplicity codes ,
Representation of degree sets R 2 (2, 4), R 2 (2, 2) and A 2 (2, 2), p.74 ,
Illustration of recursive patterns in degree sets ,
Partition of discrete triangles into polygons ,
, Illustration of a sequence of degree sets with increasing extension field, p.78
, Asymptotic rates of comparable Reed-Muller and affine lifted codes, p.79
Degree sets in odd characteristic ,
, A 1-private distributed PIR protocol from a TD-based code, p.91
, Steps leading to the construction of a TD-based PIR scheme, p.91
, Rate of binary codes coming from T A (m, q) and T P (m, q)
, Construction of a transversal design from an orthogonal array, p.98
, Construction of a distributed PIR protocol using incidence codes, p.99
Rate of incidence codes used in t-private PIR protocols ,
A tentative PoR scheme that is not sound ,
, , p.123
141 List of Tables 2.1 A summary of constructions of locally decodable or correctable codes presented earlier ,
, Elementary divisors ? Z (M q ) of the incidence matrix M q of the inversive plane over F
Degree sets of some classical monomial codes ,
Dimension and rate of binary codes arising from T A (m, q) ,
Summary of parameters of the PoR construction ,
Tests 1 and 2 for the estimation of the bias ,
Test 3 for the estimation of the bias ,
Remote Data Checking using Provable Data Possession, ACM Trans. Inf. Syst. Secur, vol.14, issue.1, p.114, 2011. ,
Designs and Their Codes, Cambridge Tracts in Mathematics, vol.63, 1992. ,
A Linear Time Erasure-Resilient Code with Nearly Optimal Recovery, IEEE Trans. Information Theory, vol.42, issue.6, p.35, 1996. ,
Proof Verification and the Hardness of Approximation Problems, J. ACM, vol.45, issue.3, p.16, 1998. ,
, Noga Alon. Combinatorial Nullstellensatz. Combinatorics, Probability and Computing, vol.8, issue.1-2, p.63, 1999.
A StorageEfficient and Robust Private Information Retrieval Scheme Allowing Few Servers, Cryptology and Network Security-13th International Conference, CANS 2014, Heraklion, vol.8813, pp.222-239, 2014. ,
URL : https://hal.archives-ouvertes.fr/hal-01094807
Probabilistic Checking of Proofs: A New Characterization of NP, J. ACM, vol.45, issue.1, p.16, 1998. ,
Nearly Optimal Constructions of PIR and Batch Codes, 2017 IEEE International Symposium on Information Theory, p.111, 2017. ,
New Bounds for Matching Vector Families, SIAM J. Comput, vol.43, issue.5, p.31, 2014. ,
Algebraic Algorithms and Error-Correcting Codes, 14th International Symposium, AAECC-14, vol.2227, p.66, 2001. ,
Tight Lower Bounds for Linear 2-query LCCs over Finite Fields, Combinatorica, vol.36, issue.1, p.36, 2016. ,
Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, p.36, 2011. ,
PIR Array Codes with Optimal PIR Rates, 2017 IEEE International Symposium on Information Theory, p.111, 2017. ,
PIR Schemes with Small Download Complexity and Low Storage Requirements, 2017 IEEE International Symposium on Information Theory, p.111, 2017. ,
Checking Computations in Polylogarithmic Time, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, p.16, 1991. ,
DOI : 10.1145/103418.103428
A New Family of Locally Correctable Codes Based on Degree-Lifted Algebraic Geometry Codes, Symposium on Theory of Computing Conference, STOC'13, vol.35, p.34, 2013. ,
Breaking the O(n 1/(2k?1) ) Barrier for Information-Theoretic Private Information Retrieval, 43rd Symposium on Foundations of Computer Science (FOCS 2002, vol.87, pp.261-270, 2002. ,
DOI : 10.1109/sfcs.2002.1181949
On Locally Decodable Codes, SelfCorrectable Codes, and t-Private PIR. Algorithmica, vol.58, p.36, 2010. ,
Proofs of Retrievability: Theory and Implementation, Proceedings of the first ACM Cloud Computing Security Workshop, p.115, 2009. ,
Self-Testing/Correcting with Applications to Numerical Problems, J. Comput. Syst. Sci, vol.47, issue.3, p.16, 1993. ,
Symmetric LDPC Codes are not Necessarily Locally Testable, Proceedings of the 26th Annual IEEE Conference on Computational Complexity, p.26, 2011. ,
DOI : 10.1109/ccc.2011.14
URL : http://people.csail.mit.edu/madhu/papers/2010/aff-non-ltc.pdf
Limits on the Rate of Locally Testable AffineInvariant Codes ,
, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques-14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, vol.6845, p.26, 2011.
The Capacity of Private Information Retrieval From Coded Databases, IEEE Trans. Information Theory, vol.64, issue.3, p.110, 2018. ,
Orthogonal arrays of index unity, The Annals of Mathematical Statistics, vol.23, issue.3, p.99, 1952. ,
Distance Properties of Expander Codes, IEEE Trans. Information Theory, vol.52, issue.1, p.33, 2006. ,
Handbook of Combinatorial Designs ,
Computationally Private Information Retrieval, Proceedings of the TwentyNinth Annual ACM Symposium on the Theory of Computing, p.86, 1997. ,
DOI : 10.1145/258533.258609
Private Information Retrieval, 36th Annual Symposium on Foundations of Computer Science, pp.41-50, 1995. ,
Codes cycliques étendus affines-invariants et antichaînes d'un ensemble partiellement ordonné, Discrete Mathematics, vol.80, issue.3, p.73, 1990. ,
DOI : 10.1016/0012-365x(90)90244-c
URL : https://doi.org/10.1016/0012-365x(90)90244-c
Private Information Retrieval for Coded Storage, IEEE International Symposium on Information Theory, ISIT 2015, p.110, 2015. ,
Minimum Weight and Dimension Formulas for Some Geometric Codes, Des. Codes Cryptography, vol.17, issue.1-3, p.13, 1999. ,
Private Information Retrieval, J. ACM, vol.45, issue.6, pp.965-981, 1998. ,
Filecoin: A Cryptocurrency Operated File Storage Network, 2017. ,
Correcting on Curves and Highly Sound Locally Correctable Codes of High Rate, 2014 IEEE International Symposium on Information Theory, p.42, 2014. ,
2-Server PIR with Subpolynomial Communication, J. ACM, vol.63, issue.4, 2016. ,
DOI : 10.1145/2968443
URL : http://arxiv.org/pdf/1407.6692
Matching Vector Codes, SIAM J. Comput, vol.40, issue.4, p.31, 2011. ,
DOI : 10.1137/100804322
Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits, SIAM J. Comput, vol.36, issue.5, p.36, 2007. ,
DOI : 10.1137/05063605x
Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals. Theory of Computing, vol.13, p.36, 2017. ,
The Decoding of Extended Reed-Solomon Codes, Discrete Mathematics, vol.90, issue.1, pp.21-40, 1991. ,
Proofs of Retrievability via Hardness Amplification, Theory of Cryptography, 6th Theory of Cryptography Conference, vol.5444, p.115, 2009. ,
3-Query Locally Decodable Codes of Subexponential Length, SIAM J. Comput, vol.41, issue.6, pp.1694-1703, 2012. ,
Private Information Retrieval from Coded Databases with Colluding Servers ,
DOI : 10.1137/16m1102562
URL : http://epubs.siam.org/doi/pdf/10.1137/16M1102562
, SIAM J. Appl. Algebra Geometry, vol.1, issue.1, p.110, 2017.
Codes for Distributed PIR with Low Storage Overhead, IEEE International Symposium on Information Theory, ISIT 2015, p.111, 2015. ,
DOI : 10.1109/isit.2015.7282977
PIR with Low Storage Overhead: Coding instead of Replication, p.111, 2015. ,
A New Algorithm for Decoding Reed-Solomon Codes, Communications, Information and Network Security, pp.55-68, 2003. ,
DOI : 10.1007/978-1-4757-3789-9_5
On a Class of Majority-Logic Decodable Cyclic Codes, IEEE Trans. Information Theory, vol.14, issue.2, p.12, 1968. ,
List-Decoding Algorithms for Lifted Codes, IEEE Trans. Information Theory, vol.62, issue.5, pp.2719-2725, 2016. ,
New Affine-Invariant Codes from Lifting, Innovations in Theoretical Computer Science, ITCS '13, pp.529-540, 2013. ,
DOI : 10.1145/2422436.2422494
URL : http://people.csail.mit.edu/madhu/papers/2012/lifts-v2-eccc.pdf
Lower Bounds for Linear Locally Decodable Dodes and Private Information Retrieval, Computational Complexity, vol.15, issue.3, p.36, 2006. ,
, Ronitt Rubinfeld, Madhu Sudan, and Avi Wigderson. Self-Testing/Correcting for Polynomials and for Approximate Functions
, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, p.16, 1991.
Superpolynomial Size Set-Systems with Restricted Intersections mod 6 and Explicit Ramsey Graphs, Combinatorica, vol.20, issue.1, p.32, 2000. ,
Constructing Set Systems with Prescribed Intersection Sizes, J. Algorithms, vol.44, issue.2, p.32, 2002. ,
Highly Resilient Correctors for Polynomials, Inf. Process. Lett, vol.43, issue.4, p.16, 1992. ,
High-Rate Locally Correctable Codes via Lifting, IEEE Trans. Information Theory, vol.62, issue.12, pp.6672-6682, 2016. ,
Linear-Algebraic List Decoding for Variants of Reed-Solomon Codes, IEEE Trans. Information Theory, vol.59, issue.6, p.24, 2013. ,
The rank of the incidence matrix of points and d-flats in finite geometries, Journal of Science of the Hiroshima University, Series A-I (Mathematics), vol.32, issue.2, p.12, 1968. ,
, Local Correctability of Expander Codes. Inf. Comput, vol.243, pp.178-190, 2015.
Fundamentals of Error-Correcting Codes, 2010. ,
On Decoding Doubly Extended Reed-Solomon Codes, Proceedings of 1995 IEEE International Symposium on Information Theory, p.280, 1995. ,
PORs: Proofs of Retrievability for Large Files, Proceedings of the 2007 ACM Conference on Computer and Communications Security, pp.584-597, 2007. ,
Exponential Lower Bound for 2-query Locally Decodable Codes via a Quantum Argument, J. Comput. Syst. Sci, vol.69, issue.3, pp.395-420, 2004. ,
Decoding Reed-Muller Codes over Product Sets. Theory of Computing, vol.13, p.25, 2017. ,
Some Results on Cyclic Codes which Are Invariant under the Affine Group and Their Applications, Information and Control, vol.11, issue.5/6, p.73, 1967. ,
New Generalizations of the Reed-Muller Codes-I: Primitive Codes, IEEE Trans. Information Theory, vol.14, issue.2, pp.189-199, 1968. ,
High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity, J. ACM, vol.64, issue.2, p.35, 2017. ,
Testing Polynomials over General Fields, SIAM J. Comput, vol.36, issue.3, pp.779-802, 2006. ,
Private Information Retrieval in Distributed Storage Systems using an Arbitrary Linear Code, 2017 IEEE International Symposium on Information Theory, p.110, 2017. ,
Algebraic Property Testing: the Role of Invariance, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, vol.72, p.68, 2008. ,
High-Rate Codes with Sublinear-Time Decoding, J. ACM, vol.61, issue.5, 2014. ,
On the Efficiency of Local Decoding Procedures for Error-Correcting Codes, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, vol.87, pp.80-86, 2000. ,
Projective Reed-Muller Codes, Coding Theory and Applications, vol.311, p.48, 1986. ,
The Parameters of Projective Reed-Muller Codes, Discrete Mathematics, vol.81, issue.2, p.48, 1990. ,
A Cooperative Internet Backup Scheme, USENIX Annual Technical Conference, p.114, 2003. ,
New Proofs of Retrievability using Locally Decodable Codes, IEEE International Symposium on Information Theory, vol.138, p.116, 2016. ,
URL : https://hal.archives-ouvertes.fr/hal-01413159
, Ramanujan Graphs. Combinatorica, vol.8, issue.3, p.33, 1988.
On the p-Rank of the Design Matrix of a Difference Set, Information and Control, vol.12, issue.5/6, p.12, 1968. ,
The Theory of Error-Correcting Codes, 1977. ,
A Dynamic Proof of Retrievability (PoR) Scheme with O(log n) Complexity, Proceedings of IEEE International Conference on Communications, ICC 2012, p.115, 2012. ,
The Complexity of Online Memory Checking, J. ACM, vol.56, issue.1, p.114, 2009. ,
A Coding Theory Foundation for the Analysis of General Unconditionally Secure Proof-ofRetrievability Schemes for Cloud Storage, J. Mathematical Cryptology, vol.7, issue.3, pp.183-216, 2013. ,
, J. Mathematical Cryptology, p.115, 2018.
List Decoding of q-ary Reed-Muller Codes, IEEE Trans. Information Theory, vol.50, issue.4, pp.679-682, 2004. ,
Polynomial Codes over Certain Finite Fields, Journal of the Society for Industrial and Applied Mathematics, vol.8, issue.2, pp.300-304, 1960. ,
Simplified Algorithm for Correcting both Errors and Erasures of Reed-Solomon Codes. Institution of Electrical Engineers, vol.126, pp.961-963, 1979. ,
Reed-Muller Codes: an Ideal Theory Approach, Communications in Algebra, vol.25, issue.2, p.47, 1997. ,
Lower Bound on the Redundancy of PIR Codes, p.111, 2016. ,
The Capacity of Private Information Retrieval, IEEE Trans. Information Theory, vol.63, issue.7, p.110, 2017. ,
Private Information Retrieval from MDS Coded Data With Colluding Servers: Settling a Conjecture by Freij-Hollanti et al, IEEE Trans. Information Theory, vol.64, issue.2, p.110, 2018. ,
The Capacity of Robust Private Information Retrieval With Colluding Databases, IEEE Trans. Information Theory, vol.64, issue.4, p.110, 2018. ,
Batch and PIR Codes and Their Connections to Locally Repairable Codes, Network Coding and Subspace Designs, p.111, 2018. ,
On the p-rank of the incidence matrix of points and hyperplanes in a finite projective geometry, Journal of Combinatorial Theory, vol.7, issue.2, p.12, 1969. ,
Projective Reed-Muller Codes, IEEE Trans. Information Theory, vol.37, issue.6, p.48, 1991. ,
Efficient Proofs of Retrievability with Public Verifiability for Dynamic Cloud Storage, p.115, 2016. ,
One Extra Bit of Download Ensures Perfectly Private Information Retrieval, 2014 IEEE International Symposium on Information Theory, vol.111, p.110, 2014. ,
Expander Codes, IEEE Trans. Information Theory, vol.42, issue.6, p.33, 1996. ,
Combinatorial Designs-Constructions and Analysis, vol.11, p.9, 2004. ,
, Compact Proofs of Retrievability. J. Cryptology, vol.26, issue.3, pp.442-483, 2013.
Noisy Interpolation of Sparse Polynomials, and Applications, Proceedings of the 26th Annual IEEE Conference on Computational Complexity, p.31, 2011. ,
Private Information Retrieval Schemes for Coded Data with Arbitrary Collusion Patterns, ISIT, p.110, 2017. ,
Private Information Retrieval from MDS Coded Data in Distributed Storage Systems, IEEE International Symposium on Information Theory, p.110, 2016. ,
Storj: A Peer-to-Peer Cloud Storage Network, 2016. ,
New Bounds on Cyclic Codes from Algebraic Curves, Coding Theory and Applications, p.73, 1989. ,
New Lower Bounds for General Locally Decodable Codes, Electronic Colloquium on Computational Complexity (ECCC), vol.14, issue.006, p.36, 2007. ,
A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field, J. Comput. Sci. Technol, vol.27, issue.4, pp.678-686, 2012. ,
Any Errors in this Dissertation Are Probably Fixable: Topics in Probability and Error Correcting Codes, p.33, 2014. ,
Revisiting the Multiplicity Codes: A New Class of High-Rate Locally Correctable Codes, 53rd Annual Allerton Conference on Communication, Control, and Computing, p.29, 2015. ,
Enabling Public Auditability and Data Dynamics for Storage Security in Cloud Computing, IEEE Trans. Parallel Distrib. Syst, vol.22, issue.5, pp.847-859, 2011. ,
A Geometric Approach to InformationTheoretic Private Information Retrieval, 20th Annual IEEE Conference on Computational Complexity (CCC 2005, p.41, 2005. ,
Towards 3-query Locally Decodable Codes of Subexponential Length, J. ACM, vol.55, issue.1, 2008. ,
Locally Decodable Codes, Foundations and Trends in Theoretical Computer Science, vol.6, issue.3, pp.139-255, 2012. ,
On Expander Codes, IEEE Trans. Information Theory, vol.47, issue.2, p.33, 2001. ,
On the Access Complexity of PIR Schemes, p.111, 2018. ,