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.
Cryptography, Local Decoding, and Distributed Storage
Overview
Syllabus
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
Taught by
TheIACR
