Paper 2026/1740 Original: eprint.iacr.org/2026/1740 ↗

Non-Local Search-to-Decision Reduction over $\mathbb{F}_2$, and More

Abstract

Non-local search-to-decision asks whether the difficulty of two non-communicating (non-local) parties both predicting $x$ given a bipartite state (that possibly depends on $x$) implies the difficulty of non-local parties both predicting the inner product $\langle r,x\rangle$, for a uniformly random $r$. This problem and its variants have been extensively studied and are motivated by applications to unclonable cryptographic primitives such as unclonable encryption and copy-protection. We study the identical-challenge setting, in which both parties receive the same uniformly random vector $r$, in contrast to the independently sampled challenges considered in prior works. We demonstrate positive results for the cases when $x$ and $r$ are vectors over $\mathbb{F}_2$ and over large finite fields. As a consequence, we obtain a conceptually different proof of indistinguishability-secure unclonable encryption.