Non-Local Search-to-Decision Reduction over F2, 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 , 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 F_2 and over large finite fields. As a consequence, we obtain a conceptually different proof of indistinguishability-secure unclonable encryption.

Understanding Search and Decision Errors in Liver Metastasis Detection and the Effects of Lower Radiation Dose
Parmita Mondal, Rickey Carter, Andrew D Missert +7
arXiv9 Sep 2026PreprintCC BY 4.0Full textBiological & medical physicsarXiv
Revealing more on complex energy landscapes by passing less local information: Cavity approach with trust region in non-convex optimization problems
Zhiqi Xu, Chi Ho Yeung
arXiv7 Oct 2026PreprintarXiv licenceFull textCondensed matter Statistical & nonlinear physicsarXiv
Several results on the almost good reduction property to the q-discrete Painlevé equations over the field of p-adic numbers
Masataka Kanki
arXiv27 Sep 2026PreprintCC BY 4.0Full textStatistical & nonlinear physicsarXiv
Simultaneous Reduction of Observables and Measured Qudits in Entanglement-Assisted Quantum Local Recovery
Ryutaroh Matsumoto
arXiv20 Sep 2026PreprintarXiv licenceFull textGeneral mathematics Quantum physics & quantum informationarXiv
Let CSP Be Your ANCHOR: Adaptive Crystal Search over Frozen Structure Priors
Emma Lei Hovmand, Jonas Elsborg, Melih Kandemir +1
arXiv30 Sep 2026PreprintCC BY 4.0Full textComputational physics Condensed matterarXiv

Cite

BibTeX RIS

BibTeX

@misc{ananth2026nonlocal,
  title = {{Non-Local Search-to-Decision Reduction over F2, and More}},
  author = {Prabhanjan Ananth},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2608.19091},
  eprint = {2608.19091},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.19091},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Non-Local Search-to-Decision Reduction over F2, and More
AU  - Prabhanjan Ananth
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2608.19091
UR  - https://arxiv.org/abs/2608.19091
AB  - 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 , 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 F_2 and over large finite fields. As a consequence, we obtain a conceptually different proof of indistinguishability-secure unclonable encryption.
ER  -

Abstract

Related

Cite