Using Nonclassical Resources to Strengthen Two-Party Zero-Communication Reductions

In this work, we investigate the quantum advantage gained by adapting the recently introduced classical zero-communication reduction (ZCR) framework to non-classical resources (“Zero-communication reductions”, Narayanan et al., Theory of Cryptography, 2020) . This problem may be described as a trusted delegated computation in which two parties aim to compute a function f without communicating, interacting only with a third party that arbitrates a resource and computes a different (predicate) function - this effects a reduction from f to the predicate. We strengthen the ZCR using a non-signaling (NS) resource, a relaxation of shared entanglement. The goal is to guarantee the privacy of the computation. By modeling this reduction as a linear program, we show that replacing the classical resource with the NS resource yields improved feasibility results. Notably a reduction from AND to XOR, insecure in the classical setting, may be achieved securely using a NS resource in both the one-output and two-output setting, in which both parties obtain the output of the function.