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.
翻译:我们在发送者和接收者共享秘密密钥或频道受资源约束的设置中建立本地可下载代码(LDC),以纠正在发送者和接收者共享秘密密钥或频道受资源约束的设置中插入删除错误。我们的构造依赖于所谓的“Hamming-InsDel”编译器(Ostrovsky和Paskin-Cherniavsky,ITS '15 & Block等人,FSTTCS '20),该代码将任何本地可下载的含汞代码编译成一个适合插入删除错误的本地可下载代码。虽然编译器是为经典编码设置设计的,但我们显示编译者仍然在一个秘密密钥或受资源约束的设置中工作。将我们的成果应用到Ostrovsky、Pandey和Sahai的私人密钥Hamming最不发达国家(ICCAP '07),我们得到了一个具有恒定速率率和多logy位置的InsDel最不发达国家的私人密钥。将我们的结果应用到布基、Kulkarni和Zhou(IT20)的构建中,但我们获得类似的时间将空间用于这样的频道。