Paper 2023/1894

Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography

Yilei Chen, Tsinghua University, Shanghai Qi Zhi Institute
Jiatu Li, Massachusetts Institute of Technology

A recent line of research has introduced a systematic approach to explore the complexity of explicit construction problems through the use of meta problems, namely, the range avoidance problem (abbrev. $\textsf{Avoid}$) and the remote point problem (abbrev. $\textsf{RPP}$). The upper and lower bounds for these meta problems provide a unified perspective on the complexity of specific explicit construction problems that were previously studied independently. An interesting question largely unaddressed by previous works is whether $\textsf{Avoid}$ and $\textsf{RPP}$ are hard for simple circuits such as low-depth circuits. In this paper, we demonstrate, under plausible cryptographic assumptions, that both the range avoidance problem and the remote point problem cannot be efficiently solved by nondeterministic search algorithms, even when the input circuits are as simple as constant-depth circuits. This extends a hardness result established by Ilango, Li, and Williams (STOC '23) against deterministic algorithms employing witness encryption for $\textsf{NP}$, where the inputs to $\textsf{Avoid}$ are general Boolean circuits. Our primary technical contribution is a novel construction of witness encryption inspired by public-key encryption for certain promise language in $\textsf{NP}$ that is unlikely to be $\textsf{NP}$-complete. We introduce a generic approach to transform a public-key encryption scheme with particular properties into a witness encryption scheme for a promise language related to the initial public-key encryption scheme. Based on this translation and variants of standard lattice-based or coding-based PKE schemes, we obtain, under plausible assumption, a provably secure witness encryption scheme for some promise language in $\textsf{NP}\setminus \textsf{coNP}_{/\textsf{poly}}$. Additionally, we show that our constructions of witness encryption are plausibly secure against nondeterministic adversaries under a generalized notion of security in the spirit of Rudich's super-bits (RANDOM '97), which is crucial for demonstrating the hardness of $\textsf{Avoid}$ and $\textsf{RPP}$ against nondeterministic algorithms.

Available format(s)
Publication info
Published elsewhere. Major revision. STOC 2024
lattice-based cryptographicrange avoidancewitness encryptionpublic-key encryptioncircuit lower bound
Contact author(s)
chenyilei ra @ gmail com
jiatuli @ mit edu
2024-05-12: revised
2023-12-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yilei Chen and Jiatu Li},
      title = {Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1894},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.