טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentDruk Erez
SubjectLinear Time Encodable Codes and Cryptography
DepartmentDepartment of Computer Science
Supervisor Professor Yuval Ishai
Full Thesis textFull thesis text - English Version


Abstract

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.