Skip to main content
SpringerLink
Log in

Locally Decodable Codes and Private Information Retrieval Schemes

  • Book
  • © 2010

Overview

Authors:
  1. Sergey Yekhanin

    1. Silicon Valley Lab., Microsoft Research, Mountain View, USA

    View author publications

    You can also search for this author in PubMed   Google Scholar

  • First book on this topic A fresh look at the theory Related thesis won the ACM Dissertation Award in 2007
  • Includes supplementary material: sn.pub/extras

Part of the book series: Information Security and Cryptography (ISC)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 109.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (4 chapters)

  1. Front Matter

    Pages i-xii
    Download chapter PDF

  2. Introduction

    • Sergey Yekhanin
    Pages 1-17

  3. Locally decodable codes via the point removal method

    • Sergey Yekhanin
    Pages 19-45

  4. Limitations of the point removal method

    • Sergey Yekhanin
    Pages 47-59

  5. Private information retrieval

    • Sergey Yekhanin
    Pages 61-74

  6. Back Matter

    Pages 75-82
    Download chapter PDF
Back to top

Keywords

About this book

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.

Authors and Affiliations

  • Silicon Valley Lab., Microsoft Research, Mountain View, USA

    Sergey Yekhanin

Bibliographic Information

  • Book Title: Locally Decodable Codes and Private Information Retrieval Schemes

  • Authors: Sergey Yekhanin

  • Series Title: Information Security and Cryptography

  • DOI: https://doi.org/10.1007/978-3-642-14358-8

  • Publisher: Springer Berlin, Heidelberg

  • eBook Packages: Computer Science, Computer Science (R0)

  • Copyright Information: Springer-Verlag Berlin Heidelberg 2010

  • Hardcover ISBN: 978-3-642-14357-1Published: 04 November 2010

  • Softcover ISBN: 978-3-642-26577-8Published: 02 January 2013

  • eBook ISBN: 978-3-642-14358-8Published: 02 November 2010

  • Series ISSN: 1619-7100

  • Series E-ISSN: 2197-845X

  • Edition Number: 1

  • Number of Pages: XII, 82

  • Topics: Data Structures and Information Theory

Publish with us

Policies and ethics

Back to top

Search

Navigation