BACKGROUND:  The two most important characteristics of an error-correcting code are the information rate, which is the ratio of the message size to the codeword size, and the error rate, which is the smallest error such that the message cannot be decoded. Many codes have been found that exhibit both constant information rate and constant error rate, but these codes all share the property that to recover even a small portion of the message x from the codeword y, you must decrypt the entire codeword. A locally-decodable code can recover a single bit of the message by decrypting only a small number of bits from the codeword. Locally-decodable codes are immensely useful in encoding large amounts of data which only needs to be recovered in small portions, such as any kind of database or archive.

INNOVATION:  A message is encrypted into a large alphabet error-correcting code, which is then reduced to a code that can be decoded using a binary error-correcting code with asymptotically optimal rate which is also a semantically secure public key cryptosystem.

POTENTIAL APPLICATIONS:  encryption, cryptography, databases, archiving, and information retrieval.

ADVANTAGES

• Local Decodability - can decode and error-correct with overwhelming probability a single bit of the message by decrypting only a small portion of the codeword, as opposed to having to decrypt the entire codeword.
• A semantically secure Public-Key Encryption
• The Public-Key Encryption function has constant expansion
• A constant rate binary error-correcting code

Reference: UCLA Case No. 2007-455