2024-05-15
最近在理论计算机领域对于显示构造问题的研究中，引入了一种系统性的方法，通过使用元问题（meta problems）来探索显式构造问题的复杂性，即值域规避问题（缩写为Avoid）和远点问题（缩写为RPP）。这些元问题的上限和下限为之前独立研究的特定显式构造问题的复杂性提供了统一的视角。以前的工作很大程度上未解决的一个有趣问题是：Avoid和RPP 对于简单电路（例如低深度电路）是否困难。
论文题目：Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography
论文作者：Yilei Chen, Jiatu Li
论文链接：https://eprint.iacr.org/2023/1894.pdf
陈一镭团队证明，在合理的密码学假设下，即使输入电路与常数深度电路一样简单，值域规避问题和远程点问题也无法通过非确定性搜索算法有效解决。这扩展了由 Ilango、Li 和 Williams (STOC’23) 针对采用 NP 见证加密（Witness encryption）的确定性算法建立的困难度结果，其中值域规避问题的输入是通用布尔电路。
团队的主要技术贡献是一种新颖的见证加密结构，其灵感来自于 NP 中某些不太可能是 NP 完全的承诺语言（promise language）的公钥加密。团队引入了一种通用方法，将具有特定属性的公钥加密方案转换为与初始公钥加密方案相关的语言的见证加密方案。通过这种通用方法，团队提出基于标准格或基于编码的 PKE 方案的变体，团队在合理的假设下获得了 NP\ coNP/poly 中某些语言的可证明安全的见证加密方案。此外，陈一镭团队证明，在Rudich的超级比特（RANDOM'97）的广义安全概念下，陈一镭团队见证加密结构对于非确定性敌手来说也可能是安全的，这对于证明Avoid和RPP针对非确定性算法的难度至关重要。
