Non-Classical Zero Communication Reductions
Abstract: In this work, we establish a non-classical framework for the recently introduced classical zero communication reduction (ZCR) using non-classical resources. The ZCR resembles a trusted delegated computation in which a third party arbitrates a resource and computes a predicate, to which the functionality of interest is reduced. Its strong security setting resembles the privacy implied by secure 2-party computation. Importantly, the parties are not allowed to communicate with each other. We strengthen the ZCR using a non-signaling (NS) resource, a relaxation of shared entanglement, and present a numerical method of identifying secure reductions. Our results include several strongly secure reductions, impossible in the classical setting, including from the significant inner product and oblivious transfer (OT) functionalities. In the latter case, the reductions serve as a novel method for demonstrating results of how to build OT from non-local boxes.