Locally Decodable Codes and Private Information Retrieval Schemes (eBook)

Preface 6
Acknowledgments 8
Contents 9
1 Introduction 11
1.1 Locally decodable codes 11
1.1.1 Hadamard code 12
1.1.2 A code based on polynomial interpolation 13
1.2 Private information retrieval schemes 14
1.2.1 A PIR scheme based on polynomial interpolation 15
1.3 The history of LDCs and PIR schemes 16
1.3.1 The first generation: interpolation 17
1.3.2 The second generation: recursion 18
1.3.3 The third generation: point removal 19
1.3.4 Lower bounds 22
1.4 Applications of LDCs and PIR schemes 23
1.4.1 Secure multiparty computation 23
1.4.2 Other models of private information retrieval 24
1.4.3 Average-case complexity 26
1.5 Organization of the book 26
1.6 Addendum 27
2 Locally decodable codes via the point removal method 28
2.1 Notation 28
2.2 Locally decodable codes 29
2.3 Binary LDCs via point removal 29
2.3.1 Regular intersecting families of sets 30
2.3.2 Basic construction 31
2.3.3 The main construction: point removal 33
2.4 General LDCs via point removal 35
2.5 Combinatorially nice subsets of Fp* 39
2.6 Algebraically nice subsets of Fp* 41
2.6.1 3-dependences between p-th roots: sufficient conditions 43
2.6.2 k-dependences between p-th roots: a sufficient condition 44
2.6.3 Summary 48
2.7 Results 48
2.7.1 Results for three-query binary codes 49
2.7.2 Results for general codes 50
2.8 Addendum 51
2.8.1 The code 53
3 Limitations of the point removal method 55
3.1 Attaining subexponential length requires a nice sequence 55
3.1.1 Point removal method 55
3.1.2 Point removal and bounds for P(rt-1) 56
3.1.3 Our results 56
3.2 A nice sequence yields short dependences between p-th roots 57
3.2.1 Algebraically nice subsets of Fq* 58
3.2.2 Combinatorially nice subsets of Fq* 61
3.2.3 Summary 63
3.3 k-dependences between p-th roots: a necessary condition 64
3.4 3-dependences between p-th roots: a necessary condition 65
3.5 Summary 66
3.6 Conclusions 67
3.7 Addendum 67
4 Private information retrieval 68
4.1 Preliminaries 68
4.2 From LDCs to PIR schemes 69
4.2.1 Upper bounds for three-server binary PIR schemes 71
4.2.2 Upper bounds for general PIR schemes 72
4.3 A combinatorial view of two-server PIR 73
4.3.1 Bilinear PIR 76
4.3.2 Group-based PIR 76
4.4 Complexity of bilinear group-based PIR 77
4.4.1 Algebraic preliminaries 77
4.4.2 Algebraic formulation 78
4.4.3 Low-dimensional principal ideals in group algebras 79
4.5 Summary of lower bounds for two-server PIR 80
4.6 Addendum 81
References 82
Index 87