The Taub Faculty of Computer Science Events and Talks

An error-correcting code with minimal distance d encodes a k-bit message by 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 construct a new family 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 (STOC 2008). 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 (with high probability) the Gilbert-Varshamov bound, the first nontrivial linear-time secret sharing schemes, and the first plausible candidates for linear-time symmetric encryption and identification schemes with exponential security.