ebook ebooks e-book e-books downloaden bei MyEbooks.ch downloaden

Locally Decodable Codes and Private Information Retrieval Schemes

:	Sergey Yekhanin
:	Locally Decodable Codes and Private Information Retrieval Schemes
:	Springer-Verlag
:	9783642143588
:	1
:	CHF 85.60
:

:	Informatik
:	English

:	82
:	Wasserzeichen/DRM
:	PC/MAC/eReader/Tablet
:	PDF

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.

	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