Private and Resource-Bounded Locally Decodable Codes for Insertions and Deletions

Abstract

We construct locally decodable codes (LDCs) to correct insertion-deletion errors in the setting where the sender and receiver share a secret key or where the channel is resource-bounded. Our constructions rely on a so-called "Hamming-to-InsDel" compiler (Ostrovsky and Paskin-Cherniavsky, ITS '15 & Block et al., FSTTCS '20), which compiles any locally decodable Hamming code into a locally decodable code resilient to insertion-deletion (InsDel) errors. While the compilers were designed for the classical coding setting, we show that the compilers still work in a secret key or resource-bounded setting. Applying our results to the private key Hamming LDC of Ostrovsky, Pandey, and Sahai (ICALP '07), we obtain a private key InsDel LDC with constant rate and polylogarithmic locality. Applying our results to the construction of Blocki, Kulkarni, and Zhou (ITC '20), we obtain similar results for resource-bounded channels; i.e., a channel where computation is constrained by resources such as space or time.

References in corpus (8)

• On Single-Deletion-Correcting Codes
• Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound
• Locally Decodable/Correctable Codes for Insertions and Deletions
• Synchronization Strings: List Decoding for Insertions and Deletions
• Private and Resource-Bounded Locally Decodable Codes for Insertions and Deletions
• Locally Decodable Codes with Randomized Encoding
• Efficient Document Exchange and Error Correcting Codes with Asymmetric Information
• Efficient Linear and Affine Codes for Correcting Insertions/Deletions

Cited by in corpus (3)

• Private and Resource-Bounded Locally Decodable Codes for Insertions and Deletions
• Computationally Relaxed Locally Decodable Codes, Revisited
• Relaxed Local Correctability from Local Testing