Project topics and materials
Get Complete Project Material File(s) Now! »
Elementary notions in coding theory
This section is devoted to recall basic notions related to coding theory. Here we choose to use the tuple representation for elements in SS since it is the most commonly used in the literature. When meaningful, we also give correspondence of the definitions and results in the functional representation. In the whole section, we refer to [HP10] for details and proofs. Generic notions. Given an alphabet S and a finite set S, an error-correcting code over S is a subset C SS. The set S is the set of coordinates of the code, and its size n = jSj is the length of the code. Elements c 2 C are called codewords. As its name suggests, an error-correcting code is usually employed to correct errors and erasures that can occur in messages, for instance during transmission. Given a codeword c 2 C SS and a noisy version y 2 (S [ f?g)S of c, where ? denotes the erasure symbol, an error is a symbol yi /2 fci,?g for some i 2 S, while an erasure is a symbol yj =? for some j 2 S. If not stated otherwise, we assume in this thesis that only errors can occur in words. A well-suited metric for modelling errors is the Hamming distance, defined by d(y, z) := jfi 2 S, yi 6= zigj for any two words y, z 2 SS. The distance of y 2 SS to a code C is then d(y, C) := minfd(y, c), c 2 Cg, and the minimum distance of the code C is dmin(C) := minfd(c, c0) j (c, c0) 2 C2, c 6= c0g. It is also convenient to consider the relative distance between two words y, z 2 SS, defined by d(y, z) := d(y, z)/jSj. Similarly one can define the relative distance of a word to a code, and the relative minimum distance of a code.
A nearest-neighbour correcting algorithm for C is an algorithm which takes as input any word y 2 SS, and outputs a word c 2 C such that d(y, c) = d(y, C). Let t := j dmin(C)1 2 k be the packing radius of C. Clearly, if d(y, C) t, then the output is unique. Therefore, a half-distance correcting algorithm for C is an algorithm that outputs the unique c 2 C nearest to y, provided y 2 SS satisfies d(y, C) t. More generally, one can also consider T-bounded-distance correcting algorithms when d(y, C) is bounded by some integer T t.
Some algebraic constructions of LCCs
This section is devoted to presenting families of locally correctable codes that are built by evaluating polynomials over vector spaces. In Subsection 2.2.1, we detail two smooth local correcting algorithms for Reed-Muller codes. We show how perfect smoothness can be achieved, and we depict qualitative relations between the three parameters of LCCs. Next subsections are then devoted to more evolved algebraic constructions leading to high-rate LCCs, namely multiplicity codes and lifted codes.
Other constructions and bounds
In this section we quickly report recent constructions and current bounds related to LDCs and LCCs. Notice that, when their dimension is small, it is not clear that LDCs and LCCs can achieve the same parameters since we require local correction of much more symbols in LCCs. Different regimes must be taken into account:
– The positive rate, or high-rate regime consists in studying families of codes whose asymptotic rate is non-zero. We then look for codes admitting the lowest possible locality ` as a function of the dimension k (or equivalently the length n).
– In the constant locality regime, we consider families of LCCs with fixed locality `, and we focus on finding codes with lowest length n compared to the dimension k. Usually, the settings ` = 2, ` = 3 and ` > 3 are studied separately.
– The sublinear locality regime consists in seeing ` as a sublinear function of the dimension k (or of the length n if the code rate is non-zero). In this context we can write ` = kb for some constant 0 < b < 1 (that can be made arbitrary close to 0), and we try to find codes with highest possible rate, or approaching well-known bounds such as the Singleton bound.
Table of contents :
Remerciements
Contents
Résumé
Introduction
I Codes with locality
1 Basics of coding and design theory
1.1 Elementary notions in coding theory
1.2 Algebraic constructions of codes
1.2.1 Reed-Solomon codes
1.2.2 Reed-Muller codes
1.2.3 Hadamard codes
1.3 Combinatorial constructions through block designs
1.3.1 Designs
1.3.2 Design-based codes
2 Locally decodable and correctable codes
2.1 Motivation and definitions
2.1.1 Historical points
2.1.2 Definitions
2.1.3 A first example: the binary Hadamard code
2.2 Some algebraic constructions of LCCs
2.2.1 Reed-Muller codes
2.2.2 Multiplicity codes
2.2.3 Lifted codes
2.2.4 A short comparison between multiplicity and lifted codes
2.3 Other constructions and bounds
2.3.1 Constructions
2.3.2 Bounds
2.4 LCCs from a design theory perspective
2.4.1 Formulating some LCCs as design-based codes
2.4.2 Design-based codes for low-error LCCs
2.4.3 Generalised design-based codes
2.4.4 Further perspectives
3 Projective lifted codes
3.1 Preliminaries
3.1.1 Affine and projective evaluation codes
3.1.2 Reduced degree sets
3.1.3 Isomorphisms and embeddings
3.2 Definition and first properties of projective lifted codes
3.2.1 Affine lifted codes
3.2.2 Projective lifted codes
3.2.3 Monomiality of projective lifted codes
3.2.4 Degree sets of lifted codes
3.3 Local correction
3.4 Intertwined relations between affine and projective lifted codes
3.4.1 Motivation and similar results
3.4.2 Shortening and puncturing projective lifted codes
3.4.3 Projective lifted codes as generalised design-based codes
3.5 Other properties towards practicality
3.5.1 Automorphisms and (quasi-)cyclicity
3.5.2 Explicit information sets
3.5.3 Estimation of the minimum distance
3.6 Rate and degree sets of lifted codes
3.6.1 Computation of degree sets
3.6.2 The case m = 2
II Cryptographic applications
4 Private information retrieval from transversal designs
4.1 Private information retrieval
4.1.1 PIR models
4.1.2 First constructions, and links with locally decodable codes
4.2 A 1-private protocol based on transversal designs
4.2.1 Transversal designs
4.2.2 The protocol
4.3 Instances
4.3.1 Transversal designs from affine geometries
4.3.2 Transversal designs from projective geometries
4.3.3 Orthogonal arrays and the incidence code construction
4.3.4 High-rate incidence codes from divisible codes
4.4 The t-private construction
4.4.1 Generic construction and analysis
4.4.2 Instances
4.5 Recent PIR constructions and bounds
4.5.1 PIR capacity, and capacity achieving protocols
4.5.2 Is PIR rate the only criterion to consider?
5 Proofs of retrievability from codes with locality
5.1 Introduction
5.1.1 Motivation
5.1.2 Previous works
5.1.3 Our approach
5.1.4 Organisation
5.2 Proofs of retrievability
5.2.1 Definition
5.2.2 Security models
5.3 The PoR construction
5.3.1 Verification structures for codes
5.3.2 A PoR scheme based on codes with locality
5.3.3 Analysis
5.3.4 Estimation of the bias
5.3.5 Pairwise uncorrelation of variables fXugu2D
5.4 Performance
5.4.1 Efficient scrambling of the encoded file
5.4.2 Parameters
5.5 Instantiations
5.5.1 Tensor-product codes
5.5.2 Reed-Muller and related codes
5.5.3 Experimental estimate of the bias a
Conclusion
