Transcript Graphs with tiny vector chromatic numbers and huge

Private codes
or
Succinct random codes that are
(almost) perfect
Michael Langberg
California Institute of Technology
1
Coding theory
A
w
{0,1}k
B
Noise
c
C(w)  {0,1}n
decode
Error correcting codes
C: {0,1}k
w
{0,1}n
2
Consider: 2 types of channels
Design of C depends on properties of channel.
BSCp: Binary Symmetric Channel.
Each bit flipped with probability p.
ADVCp: Adversarial Channel.
p-fraction of bits are flipped maliciously.
A
Noise
B
3
A
BSCp
C(w)
e
B
C(w)+e
What’s known:
C: {0,1}k
• Thm.
Can construct codes that allow
[Shannon]:
{0,1}n ?
communication over BSCp for any p<½ with rate
k/n~1-H(p).
In particular: there exist codes for BSC½-.
4
ADVCp
A
C(w)
e
B
C(w)+e
Can we match these results in presence of ADVCp ? No!
Consider for example p=½- :
• Need codes of minimum distance = 2pn ~ n.
• Do not exist (with constant rate) !
• In general: for p<½ we need codes of minimum distance
2pn and rate k/n~1-H(p).
• Such codes are close to being perfect and are known
not to exist (asymptotically).
5
This talk
• Seen: BSC strictly weaker than ADVC.
• Goal: Relax framework as to allow communication over
ADVC with parameters of BSC.
• Relaxation: Introduce “private randomness”.
• Assume that the sender and receiver have a shared
random string (hidden from channel).
Q: Can we match parameters of BSC ? (e.g. ADVC½-?)
6
The model: Private codes
r
m random bits
A
w  {0,1}k
C: {0,1}k x {0,1}m
C(w,r)  {0,1}n
B
Adversary
c  {0,1}n
{0,1}n
D(c,r)
w
7
Private codes
m random bits
r
A
C(w,r)
e
B
C(w,r)+e
Roughly speaking:
Private codes are said to allow communication over
ADVCp if for every w and for any adversary:
The communication of w will succeed with high
probability over the shared random string r.
D w ADV Pr[D( C(w,r)+error, r)=w]=large
8
Private codes: related work
• Private codes have been studied in the past
[Shannon,BlackwellBreimanThomasian,Ahlswede].
• Private codes in the presence of adversarial
channels have also been studied:
•[
Lipton]:
“Code scrambling”.
9
Private codes: properties
r
m random bits
A
B
Do private codes enable communication over ADVC½- ?
• Yes!!  private codes that allow communication over
ADVCp with rate k/n~1-H(p).
• Matching parameters in BSC model.
p
10
r
Our results
A
m random bits
B
• Study framework of private codes.
• Match parameters obtainable in BSC model.
• [Lipton]: many shared random bits, m ~ nlog(n).
• Analyze the amount of shared randomness needed to
obtain private codes that match BSC parameters.
• We show that a shared random string of size ~ log(n) is
necessary and sufficient.
Present connection between list decodable codes and
private codes.
11
List decoding vs. Private decoding
Thm: List decoding implies (unique) private codes.
• Using shared randomness:
•Any list decodable code can be used to
construct a uniquely decodable private code.
• Reduction is efficient and needs only log(n)
shared random bits.
12
r
Proof technique
A
B
• Let C be standard code.
C
X
• Use C to construct private code C*(w,r).
X
• Use C to construct standard codes C*| .
X
• Define C*| as a subcode of C.
X
X
• C*:
Desired
of C*|
{0,1} properties
x {0,1}
{0,1}:
Radius pn:
List{0,1}
size ≤ L
•
Ideally - Unique decoding:
C*| : {0,1}
{0,1}
r B only one codeword in ball of radius pn.
• Sufficient cond.: “hide” r + unique decoding on average:
r
r
k
r
m
k
r
n
n
n
B and most r only one codeword in ball.
• C is list decodable: sufficient condition can be obtained
efficiently with poly # of subcodes!
13
Concluding remarks
A
• Study private codes.
r
random bits
B
• Match param. of BSC model w/ log(n) shared bits.
• Shared randomness: enables unique decoding
whenever list decoding was possible.
• Multiple messages:
• Need fresh randomness for each message.
• May assume cryptographic private key setting.
• Public key setting [MicaliPeikertSudanWilson].
• Thanks.
14