Cryptography, Local Decoding, and Distributed Storage

Explore cryptography, local decoding, and distributed storage in this 48-minute conference talk by Mary Wootters at "Beyond Crypto: A TCS Perspective". Delve into error-correcting codes, including repetition codes and locally decodable codes, and their applications in adversarial scenarios. Examine the concept of locality in error-correcting codes and its relevance to t-query locally decodable codes and t-server private information retrieval. Investigate Reed-Solomon codes as regenerating codes and their role in distributed storage systems. Learn about low-communication decoding of RS codes and their application in communication-efficient secret sharing. Conclude with an exploration of coded private information retrieval using Reed-Solomon codes, providing a comprehensive overview of the intersection between cryptography, coding theory, and distributed systems.

Intro
The point of this talk
Outline
What are error correcting codes?
Dumb Example: Repetition Code
What is "locality" in error correcting codes?
t-query Locally Decodable Code
Locally Decodable Codes Adversary introduces a 0.01 fraction of errors. Bob can recover a single symbol using a few queries (whp)
t-server Private Information Retrieval
Back to distributed storage
Low-communication decoding of RS codes?
Reed-Solomon codes are regenerating codes!
What do these look like?
Summary so far: Regenerating Codes
Application 1 Communication-Efficient Secret Sharing
A slightly different setting for PIR
RECALL What one of these schemes looks like
Example: Coded PIR with RS codes