Locally Decodable Codes and Private Information Retrieval Schemes
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 code
- PDF / 1,066,327 Bytes
- 88 Pages / 439.37 x 666.142 pts Page_size
- 0 Downloads / 191 Views
For further volumes: http://www.springer.com/series/4752
Sergey Yekhanin
Locally Decodable Codes and Private Information Retrieval Schemes
123
Dr. Sergey Yekhanin Microsoft Research Silicon Valley Lab La Avenida 1065 Mountain View, CA 94043 USA [email protected] Series Editors Prof. Dr. David Basin Prof. Dr. Ueli Maurer ETH Zürich Switzerland [email protected] [email protected]
ISSN 1619-7100 ISBN 978-3-642-14357-1 e-ISBN 978-3-642-14358-8 DOI 10.1007/978-3-642-14358-8 Springer Heidelberg Dordrecht London New York Library of Congress Control Number: 2010938962 ACM Computing Classification (1998): E.4 c Springer-Verlag Berlin Heidelberg 2010 This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Cover design: KuenkelLopka GmbH, Heidelberg Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)
To my sister Yulia
Preface
This book studies two closely related notions, namely locally decodable codes (LDCs) and private information retrieval (PIR) schemes. Locally decodable codes are a class of error-correcting codes. Error-correcting codes help ensure reliable transmission of information over noisy channels, as well as reliable storage of information on a medium that may become partially corrupted over time or whose reading device is subject to errors. Such codes allow one to add redundancy, or bit strings, to messages, encoding them into longer bit strings, called codewords, in such a way that the message can still be recovered even if a certain fraction of the codeword bits are corrupted. In typical applications of errorcorrecting codes the message is first partitioned into small blocks, each of which is then encoded separately. This encoding strategy allows efficient random-access retrieval of the information, since one needs to decode only the portion of data in which one is interested. Unfortunately, this strategy yields poor noise resilience, since when even a single block (out of possibly tens of thousands) is completely corrupted, some information is lost. In view of this limitation, it would seem preferable to encode the whole message into a single codeword of an error-correcting code. Such a solution improves the robustness to noise but is hardly satisfactory, since one ne
Data Loading...
