« search calendars« Beyond Crypto: A TCS Perspective

« Cryptography, Local Decoding, and Distributed Storage

Cryptography, Local Decoding, and Distributed Storage

August 19, 2018, 2:50 PM - 3:40 PM


Corwin Pavilion West

University of California, Santa Barbara

Mary Wootters, Stanford University

In this talk, I’ll give an overview of locality in error correcting codes, highlighting connections in cryptography. Error correcting codes encode data to protect it from noise, and broadly we say that an error correcting code exhibits “locality” if it is possible to recover a piece of information without looking at very much of the encoded data. Connections between locality and cryptography go back a long way; a famous example is the tight relationship between locally decodable codes and private information retrieval. This talk will survey these connections, but with a focus on newer notions of locality. These newer notions—inspired primarily by distributed storage—have already found a few connections to cryptography, but have potential for many more.