Linear-time encodable codes meeting the gilbert-varshamov bound and their cryptographic applications
Erez Druk, Yuval Ishai · 2014
A random linear code has good minimal distance with high probability. The conjectured intractability of decoding random linear codes has recently found many applications in cryptography. One disadvantage of random linear codes is that their encoding complexity grows quadratically with the message length. Motivated by this disadvantage, we present a 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 [25].