|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.