Locally Decodable Codes and Private Information Retrieval Schemes (eBook)

Sergey Yekhanin (Autor)

eBook Download: PDF

2010 | 2010
XII, 82 Seiten
Springer Berlin (Verlag)
978-3-642-14358-8 (ISBN)

Infos

Locally decodable codes (LDCs) are codes that simultaneously provide efficient random access retrieval and high noise resilience by allowing reliable reconstruction of an arbitrary bit of a message by looking at only a small number of randomly chosen codeword bits. Local decodability comes with a certain loss in terms of efficiency - specifically, locally decodable codes require longer codeword lengths than their classical counterparts. Private information retrieval (PIR) schemes are cryptographic protocols designed to safeguard the privacy of database users. They allow clients to retrieve records from public databases while completely hiding the identity of the retrieved records from database owners. In this book the author provides a fresh algebraic look at the theory of locally decodable codes and private information retrieval schemes, obtaining new families of each which have much better parameters than those of previously known constructions, and he also proves limitations of two server PIRs in a restricted setting that covers all currently known schemes. The author's related thesis won the ACM Dissertation Award in 2007, and this book includes some expanded sections and proofs, and notes on recent developments.

Inhalt

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

Produkt-Details

• Erscheint lt. Verlag: 2.11.2010
• Reihe/Serie: Information Security and Cryptography
• Reihe/Serie: Information Security and Cryptography
• Zusatzinfo: XII, 82 p.
• Verlagsort: Berlin
• Sprache: englisch
• Themenwelt: Informatik ► Netzwerke ► Sicherheit / Firewall
• Schlagworte: Database • Information Retrieval • Locally decodable codes • Point removal method • privacy • private information retrieval
• ISBN-10: 3-642-14358-X / 364214358X
• ISBN-13: 978-3-642-14358-8 / 9783642143588