M.Sc Student | Druk Erez |
---|---|

Subject | Linear Time Encodable Codes and Cryptography |

Department | Department of Computer Science |

Supervisor | Professor Yuval Ishai |

Full Thesis text |

An error-correcting code with minimal distance d encodes a k-bit message into an n-bit codeword such that any two distinct codewords differ in at least d coordinates. It is well known that a random code, or even a random linear code, has a good minimal distance with high probability. Moreover, the conjectured intractability of decoding random linear codes has recently found several applications in cryptography.

A major disadvantage of random linear codes is that their encoding complexity grows quadratically with the message length. Motivated by this disadvantage, we present a new randomized construction of linear error-correcting codes which can be encoded in linear-time and yet enjoy several useful features of random linear codes. Our construction is based on a linear-time computable hash function due to Ishai, Kushilevitz, Ostrovsky and Sahai [IKOS08].

We demonstrate the usefulness of our new codes by presenting several applications in coding theory and cryptography. These include the first family of linear-time encodable codes whose minimal distance meets the Gilbert-Varshamov bound, the first nontrivial linear-time secret sharing schemes, and plausible candidates for symmetric encryption and identification schemes which can be conjectured to achieve better asymptotic efficiency/security tradeoffs than all current candidates.