This course covers the learning outcomes and goals of understanding error correcting codes, locality in error correcting codes, t-query Locally Decodable Codes, t-server Private Information Retrieval, low-communication decoding of Reed-Solomon codes, regenerating codes, communication-efficient secret sharing, and coded Private Information Retrieval with Reed-Solomon codes. The course teaches individual skills in error correction, data storage, and information retrieval techniques. The teaching method involves a presentation format. The intended audience for this course is individuals interested in cryptography, error correction, and distributed storage 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
