Name
Abstract | ||
|---|---|---|
For adversarial but computationally bounded models of error, we construct appealingly simple and efficient cryptographic encoding and unique decoding schemes whose error-correction capability is much greater than classically possible. In particular: 1) For binary alphabets, we construct positive-rate coding schemes that are uniquely decodable under a 1/2 - γ error rate for any constant γ > 0. 2) For large alphabets, we construct coding schemes that are uniquely decodable under a 1 - R error rate for any information rate R > 0. Our results for large alphabets are actually optimal, since the "computationally bounded but adversarial channel" can simulate the behavior of the q-ary symmetric channel, where q denotes the size of the alphabet, the capacity of which is known to be upper-bounded by 1 - R. Our results hold under minimal assumptions on the communication infrastructure, namely: 1) we allow the channel to be more powerful than the receiver and 2) we only assume that some information about the sender-a public key-is known. (In particular, we do not require any shared secret key or joint local state between sender and receivers). |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/TIT.2010.2070370 | IEEE Transactions on Information Theory |
Keywords | Field | DocType |
binary codes,decoding,error correction,public key cryptography,binary alphabets,communication infrastructure,computationally bounded noise,construct coding schemes,cryptographic encoding,error-correction capability,optimal error correction,positive-rate coding schemes,q-ary symmetric channel,sender-a public key,unique decoding schemes,Adversarial error,channel modelling,computationally bounded channels | Discrete mathematics,Code rate,Computer science,Upper and lower bounds,Binary code,Word error rate,Communication channel,Algorithm,Error detection and correction,Decoding methods,Bounded function | Journal |
Volume | Issue | ISSN |
56 | 11 | 0018-9448 |
Citations | PageRank | References |
5 | 0.45 | 16 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Silvio Micali | 1 | 11434 | 2581.31 |
| Chris Peikert | 2 | 3840 | 154.98 |
| Madhu Sudan | 3 | 5616 | 591.68 |
| David A. Wilson | 4 | 61 | 5.01 |