Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.38452

Quantum Secure Non-Interactive Reductions

Maxwell Gold, Sarah Hagen, Daniel Alabi, Eric Chitambar

quant-phSubmitted Sep 29, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

Efficient models for secure computation often rely on offline preprocessed correlations, which subsequently enable private online computation from minimal assumptions. Within these models, the study of secure non-interactive reductions (SNIR) formalizes when one classical correlation can be non-interactively transformed into another, while guaranteeing information-theoretic simulation-based privacy. In this work, we introduce quantum secure non-interactive reductions (QSNIR), a natural extension of SNIR, in which the source and target resource are each a bipartite quantum state. Specifically, when the target resource is classical, our framework enables us to analyze the problem of disseminating private correlations from entanglement, in addition to classical resources. Our primary technical result is that QSNIR privacy in this context can be computed exactly via a semidefinite program (SDP) pair that quantifies an error operationally rooted in a simulation-based cheating advantage. We prove that QSNIR privacy is lower-bounded by a decision problem related to minimum-error state discrimination (MED), and use both definitions to compute exact one-shot privacy errors for universal two-party computation (2PC) preprocessing correlations.

AI Summary

The paper asks when a shared bipartite quantum state can be converted non-interactively into another resource while preserving information-theoretic, simulation-based privacy. Its main application is extracting classical preprocessing correlations for two-party computation from entanglement, quantifying leakage beyond what an ideal sample reveals. Quantum secure non-interactive reductions (QSNIRs) are defined using trace-distance correctness and privacy: a local simulator must reconstruct the corrupted party’s retained quantum system from its ideal target resource. Parallel composition on product resources and sequential composition have at most additive errors, proved by trace-distance contractivity and hybrid arguments. For computational-basis measurements of canonical coherent embeddings, the optimal one-shot privacy error is formulated as a strongly dual SDP. The primal optimizes simulator output states; the dual describes environmental distinguishing witnesses. Perfect privacy holds exactly for trivial classical correlations, recovering the known zero-leakage boundary. The increase in minimum-error guessing probability, $\delta_{\mathrm{MED}}$, lower-bounds the simulation error but need not characterize it. Symmetry reductions and matching primal–dual constructions give exact errors for standard correlations. Binary oblivious key has $\delta_{\mathrm{MED}}=(2\sqrt{2}-1)/8\approx0.229$ and $\delta_{\mathrm{QSNIR}}=(\sqrt{5}-1)/4\approx0.309$ against either party. Binary symmetric correlations have zero MED advantage despite positive simulation error at every nontrivial noise parameter; binary erasure correlations exhibit both equality and strict gaps between the measures. The explicit optima concern canonical, zero-phase embeddings. Optimization over embedding phases remains open, as does a general characterization of the MED–simulation gap. Composition is established within QSNIR; integration into broader composable cryptographic frameworks is left for future work.

No sign of AI-generated text

Error found: The claimed monotonicity of zero-error conditional entropies under arbitrary local stochastic maps is false: locally adding binary noise to a shared uniform bit increases H(X↘Y|Y) from zero to h(q). The displayed quantum conditional min-entropy definition reverses the required operator inequality, so it does not have the subsequently asserted guessing-probability interpretation. The corrupt-A binary-erasure example incorrectly lists the erasure-state prior as q/2 rather than q, although subsequent calculations use q correctly.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
39 pages, 3 figures, 1 table

Related papers

Private quantum decoupling and secure disposal of information

Francesco Buscemi

Given a bipartite system, correlations between its subsystems can be understood as the information that each one carries about the other. In order to give a model-independent description of secure information disposal, we propose the paradigm of private quantum decoupling , corresponding to locally reducing correlations in a given bipartite quantum state without transferring them to the environment. In this framework, the concept of private local randomness naturally arises as a resource, and total correlations are divided into eliminable and ineliminable ones. We prove upper and lower bounds on the quantity of ineliminable correlations present in an arbitrary bipartite state, and show that, in tripartite pure states, ineliminable correlations satisfy a monogamy constraint, making apparent their quantum nature. A relation with entanglement theory is provided by showing that ineliminable correlations constitute an entanglement parameter. In the limit of infinitely many copies of the initial state provided, we compute the regularized ineliminable correlations to be measured by the coherent information, which is thus equipped with a new operational interpretation. In particular, our results imply that two subsystems can be privately decoupled if their joint state is separable.

arXiv:0901.4506•New Journal of Physics•Dec 1, 2009•11 citations

Lower Bounds for Quantum Secure Function Evaluation Reductions

Esther Hänggi, Severin Winkler

One-sided output secure function evaluation is a cryptographic primitive where the two mutually distrustful players, Alice and Bob, both have a private input to a bivariate function. Bob obtains the value of the function for the given inputs, while Alice receives no output. It is known that this primitive cannot be securely implemented if the two players only have access to noiseless classical and quantum communication. In this work, we first show that Bob can extract the function values for all his possible inputs from any implementation of a non-trivial function that is correct and preserves the privacy of Bob's input. Our result holds in the non-asymptotic setting where the players have finite resources and the error is a constant. Then we consider protocols for secure function evaluation in a setup where the two players have access to trusted distributed randomness as a resource. Building upon the first result, we prove a bound on the efficiency of such cryptographic reductions for any non-trivial function in terms of the conditional entropies of the trusted randomness. From this result, we can derive lower bounds on the number of instances of different variants of OT needed to securely implement a given function.

arXiv:2405.12121•May 20, 2024•0 citations

Quantum preprocessing for information-theoretic security in two-party computation

Li Zhi Yu

In classical two-party computation, a trusted initializer who prepares certain initial correlations, known as one-time tables, can help make the inputs of both parties information-theoretically secure. We propose some bipartite quantum protocols with possible aborts for approximately generating such bipartite classical correlations with varying degrees of privacy, without introducing a third party. Under some weak requirements for the parties, the security level is nontrivial for use in bipartite computation. We show that the security is sometimes dependent on the noise level, but we propose a method for dealing with noise. The security is "forced security", which implies that the probability that some useful one-time tables are generated can approach $1$ in the noiseless case under quite weak assumptions about the parties, although the protocols allow aborts. We show how to use the generated one-time tables to achieve nontrivial information-theoretic security in generic two-party classical or quantum computation tasks, including (interactive) quantum homomorphic encryption. Our methods provide check-based implementations of some no-signaling correlations, including the PR-box type, with the help of communication which carry no information about the inputs in the generated correlations.

arXiv:1908.05584•Aug 15, 2019•2 citations

Efficient Two-Round OT Extension and Silent Non-Interactive Secure Computation

Elette Boyle, Geoffroy Couteau, Niv Gilboa +4 more

We consider the problem of securely generating useful instances of two-party correlations, such as many independent copies of a random oblivious transfer (OT) correlation, using a small amount of communication. This problem is motivated by the goal of secure computation with silent preprocessing, where a low-communication input-independent setup, followed by local ("silent") computation, enables a lightweight "non-cryptographic" online phase once the inputs are known. Recent works of Boyle et al. (CCS 2018, Crypto 2019) achieve this goal with good concrete efficiency for useful kinds of two-party correlations, including OT correlations, under different variants of the Learning Parity with Noise (LPN) assumption, and using a small number of "base'' oblivious transfers. The protocols of Boyle et al. have several limitations. First, they require a large number of communication rounds. Second, they are only secure against semi-honest parties. Finally, their concrete efficiency estimates are not backed by an actual implementation. In this work we address these limitations, making three main contributions: Eliminating interaction. Under the same assumption, we obtain the first concretely efficient 2-round protocols for generating useful correlations, including OT correlations, in the semi-honest security model. This implies the first efficient 2-round OT extension protocol of any kind and, more generally, protocols for non-interactive secure computation (NISC) that are concretely efficient and have the silent preprocessing feature. Malicious security. We provide security against malicious parties without additional interaction and with only a modest overhead; prior to our work, no similar protocols were known with any number of rounds. Implementation. Finally, we implemented, optimized, and benchmarked our 2-round OT extension protocol, demonstrating that it offers a more attractive alternative to the OT extension protocol of Ishai et al. (Crypto 2003) in many realistic settings.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 6, 2019•228 citations

Entanglement cost of bipartite quantum channel discrimination under positive partial transpose operations

Chengkai Zhu, Shuyu He, Gereon Koßmann +1 more

Quantum channel discrimination is a fundamental task in quantum information processing. In the one-shot regime, discrimination between two candidate channels is characterized by the diamond norm. Beyond this basic setting, however, many scenarios in distributed quantum information processing remain unresolved, motivating notions of distinguishability that capture the power of the available resources. In this work, we formulate a theory of testers for bipartite channel discrimination, leading to the concept of the entanglement cost of bipartite channel discrimination: the minimum Schmidt rank $k$ of a shared maximally entangled state required for local protocols to achieve the globally optimal success probability. We introduce $k$-injectable testers as a tester-based description of entanglement-assisted local discrimination and, in particular, study the class of $k$-injectable positive-partial-transpose (PPT) testers, which constitutes a numerically tractable relaxation of the practically relevant class of LOCC testers. For every $k$, we derive a semidefinite program (SDP) for the optimal success probability, which in turn yields an efficiently computable one-shot PPT entanglement cost. To render these optimization problems numerically feasible, we prove a symmetry-reduction principle for covariant channel pairs, thereby reducing the effective dimension of the associated SDPs. Finally, by dualizing the SDP, we derive bounds on the composite channel-discrimination problem and illustrate our framework with proof-of-principle examples based on the depolarizing channel, the depolarized SWAP channel, and the Werner--Holevo channels.

quant-pharXiv:2603.12130•Mar 13, 2026•0 citations

Unextendible Entanglement of Quantum Channels

Vishal Singh, Mark M. Wilde

Quantum communication relies on the existence of high quality quantum channels to exchange information. In practice, however, all communication links are affected by noise from the environment. Here we investigate the ability of quantum channels to perform quantum communication tasks by restricting the participants to use only local operations and one-way classical communication (one-way LOCC) along with the available quantum channel. In particular, a channel can be used to distill a highly entangled state between two parties, which further enables quantum or private communication. In this work, we invoke the framework of superchannels to study the distillation of a resourceful quantum state, such as a maximally entangled state or a private state, using multiple instances of a point-to-point quantum channel. We use the idea ofk-extendibility to obtain a semidefinite relaxation of the set of one-way LOCC superchannels and define a class of entanglement measures for quantum channels that decrease monotonically under such superchannels; therefore these measures, dubbed collectively the “unextendible entanglement of a channel”, yield upper bounds on several communication-theoretic quantities of interest in the regimes of resource distillation and zero error.We then generalize the formalism ofk-extendibility to bipartite superchannels, thus obtaining functions that are monotone under two-extendible superchannels. This allows us to analyze probabilistic distillation of ebits or secret key bits from a bipartite state when using a resourceful quantum channel. Moreover, we propose semidefinite programs to evaluate several of these quantities, providing a computationally feasible method of comparison between quantum channels for resource distillation.

arXiv:2407.15944•IEEE Transactions on Information Theory•May 7, 2025•3 citations
Efficient models for secure computation often rely on offline preprocessed correlations, which subsequently enable private online computation from minimal assumptions. Within these models, the study of secure non-interactive reductions (SNIR) formalizes when one classical correlation can be non-interactively transformed into another, while guaranteeing information-theoretic simulation-based privacy. In this work, we introduce quantum secure non-interactive reductions (QSNIR), a natural extension of SNIR, in which the source and target resource are each a bipartite quantum state. Specifically, when the target resource is classical, our framework enables us to analyze the problem of disseminating private correlations from entanglement, in addition to classical resources. Our primary technical result is that QSNIR privacy in this context can be computed exactly via a semidefinite program (SDP) pair that quantifies an error operationally rooted in a simulation-based cheating advantage. We prove that QSNIR privacy is lower-bounded by a decision problem related to minimum-error state discrimination (MED), and use both definitions to compute exact one-shot privacy errors for universal two-party computation (2PC) preprocessing correlations.
The paper asks when a shared bipartite quantum state can be converted non-interactively into another resource while preserving information-theoretic, simulation-based privacy. Its main application is extracting classical preprocessing correlations for two-party computation from entanglement, quantifying leakage beyond what an ideal sample reveals.
Quantum secure non-interactive reductions (QSNIRs) are defined using trace-distance correctness and privacy: a local simulator must reconstruct the corrupted party’s retained quantum system from its ideal target resource. Parallel composition on product resources and sequential composition have at most additive errors, proved by trace-distance contractivity and hybrid arguments.
For computational-basis measurements of canonical coherent embeddings, the optimal one-shot privacy error is formulated as a strongly dual SDP. The primal optimizes simulator output states; the dual describes environmental distinguishing witnesses. Perfect privacy holds exactly for trivial classical correlations, recovering the known zero-leakage boundary. The increase in minimum-error guessing probability, δMED\delta_{\mathrm{MED}}δMED​, lower-bounds the simulation error but need not characterize it.
Symmetry reductions and matching primal–dual constructions give exact errors for standard correlations. Binary oblivious key has δMED=(22−1)/8≈0.229\delta_{\mathrm{MED}}=(2\sqrt{2}-1)/8\approx0.229δMED​=(22​−1)/8≈0.229 and δQSNIR=(5−1)/4≈0.309\delta_{\mathrm{QSNIR}}=(\sqrt{5}-1)/4\approx0.309δQSNIR​=(5​−1)/4≈0.309 against either party. Binary symmetric correlations have zero MED advantage despite positive simulation error at every nontrivial noise parameter; binary erasure correlations exhibit both equality and strict gaps between the measures.
The explicit optima concern canonical, zero-phase embeddings. Optimization over embedding phases remains open, as does a general characterization of the MED–simulation gap. Composition is established within QSNIR; integration into broader composable cryptographic frameworks is left for future work.
Given a bipartite system, correlations between its subsystems can be understood as the information that each one carries about the other. In order to give a model-independent description of secure information disposal, we propose the paradigm of private quantum decoupling , corresponding to locally reducing correlations in a given bipartite quantum state without transferring them to the environment. In this framework, the concept of private local randomness naturally arises as a resource, and total correlations are divided into eliminable and ineliminable ones. We prove upper and lower bounds on the quantity of ineliminable correlations present in an arbitrary bipartite state, and show that, in tripartite pure states, ineliminable correlations satisfy a monogamy constraint, making apparent their quantum nature. A relation with entanglement theory is provided by showing that ineliminable correlations constitute an entanglement parameter. In the limit of infinitely many copies of the initial state provided, we compute the regularized ineliminable correlations to be measured by the coherent information, which is thus equipped with a new operational interpretation. In particular, our results imply that two subsystems can be privately decoupled if their joint state is separable.
One-sided output secure function evaluation is a cryptographic primitive where the two mutually distrustful players, Alice and Bob, both have a private input to a bivariate function. Bob obtains the value of the function for the given inputs, while Alice receives no output. It is known that this primitive cannot be securely implemented if the two players only have access to noiseless classical and quantum communication. In this work, we first show that Bob can extract the function values for all his possible inputs from any implementation of a non-trivial function that is correct and preserves the privacy of Bob's input. Our result holds in the non-asymptotic setting where the players have finite resources and the error is a constant. Then we consider protocols for secure function evaluation in a setup where the two players have access to trusted distributed randomness as a resource. Building upon the first result, we prove a bound on the efficiency of such cryptographic reductions for any non-trivial function in terms of the conditional entropies of the trusted randomness. From this result, we can derive lower bounds on the number of instances of different variants of OT needed to securely implement a given function.
In classical two-party computation, a trusted initializer who prepares certain initial correlations, known as one-time tables, can help make the inputs of both parties information-theoretically secure. We propose some bipartite quantum protocols with possible aborts for approximately generating such bipartite classical correlations with varying degrees of privacy, without introducing a third party. Under some weak requirements for the parties, the security level is nontrivial for use in bipartite computation. We show that the security is sometimes dependent on the noise level, but we propose a method for dealing with noise. The security is "forced security", which implies that the probability that some useful one-time tables are generated can approach 111 in the noiseless case under quite weak assumptions about the parties, although the protocols allow aborts. We show how to use the generated one-time tables to achieve nontrivial information-theoretic security in generic two-party classical or quantum computation tasks, including (interactive) quantum homomorphic encryption. Our methods provide check-based implementations of some no-signaling correlations, including the PR-box type, with the help of communication which carry no information about the inputs in the generated correlations.
We consider the problem of securely generating useful instances of two-party correlations, such as many independent copies of a random oblivious transfer (OT) correlation, using a small amount of communication. This problem is motivated by the goal of secure computation with silent preprocessing, where a low-communication input-independent setup, followed by local ("silent") computation, enables a lightweight "non-cryptographic" online phase once the inputs are known. Recent works of Boyle et al. (CCS 2018, Crypto 2019) achieve this goal with good concrete efficiency for useful kinds of two-party correlations, including OT correlations, under different variants of the Learning Parity with Noise (LPN) assumption, and using a small number of "base'' oblivious transfers. The protocols of Boyle et al. have several limitations. First, they require a large number of communication rounds. Second, they are only secure against semi-honest parties. Finally, their concrete efficiency estimates are not backed by an actual implementation. In this work we address these limitations, making three main contributions: Eliminating interaction. Under the same assumption, we obtain the first concretely efficient 2-round protocols for generating useful correlations, including OT correlations, in the semi-honest security model. This implies the first efficient 2-round OT extension protocol of any kind and, more generally, protocols for non-interactive secure computation (NISC) that are concretely efficient and have the silent preprocessing feature. Malicious security. We provide security against malicious parties without additional interaction and with only a modest overhead; prior to our work, no similar protocols were known with any number of rounds. Implementation. Finally, we implemented, optimized, and benchmarked our 2-round OT extension protocol, demonstrating that it offers a more attractive alternative to the OT extension protocol of Ishai et al. (Crypto 2003) in many realistic settings.
Quantum channel discrimination is a fundamental task in quantum information processing. In the one-shot regime, discrimination between two candidate channels is characterized by the diamond norm. Beyond this basic setting, however, many scenarios in distributed quantum information processing remain unresolved, motivating notions of distinguishability that capture the power of the available resources. In this work, we formulate a theory of testers for bipartite channel discrimination, leading to the concept of the entanglement cost of bipartite channel discrimination: the minimum Schmidt rank kkk of a shared maximally entangled state required for local protocols to achieve the globally optimal success probability. We introduce kkk-injectable testers as a tester-based description of entanglement-assisted local discrimination and, in particular, study the class of kkk-injectable positive-partial-transpose (PPT) testers, which constitutes a numerically tractable relaxation of the practically relevant class of LOCC testers. For every kkk, we derive a semidefinite program (SDP) for the optimal success probability, which in turn yields an efficiently computable one-shot PPT entanglement cost. To render these optimization problems numerically feasible, we prove a symmetry-reduction principle for covariant channel pairs, thereby reducing the effective dimension of the associated SDPs. Finally, by dualizing the SDP, we derive bounds on the composite channel-discrimination problem and illustrate our framework with proof-of-principle examples based on the depolarizing channel, the depolarized SWAP channel, and the Werner--Holevo channels.
Quantum communication relies on the existence of high quality quantum channels to exchange information. In practice, however, all communication links are affected by noise from the environment. Here we investigate the ability of quantum channels to perform quantum communication tasks by restricting the participants to use only local operations and one-way classical communication (one-way LOCC) along with the available quantum channel. In particular, a channel can be used to distill a highly entangled state between two parties, which further enables quantum or private communication. In this work, we invoke the framework of superchannels to study the distillation of a resourceful quantum state, such as a maximally entangled state or a private state, using multiple instances of a point-to-point quantum channel. We use the idea ofk-extendibility to obtain a semidefinite relaxation of the set of one-way LOCC superchannels and define a class of entanglement measures for quantum channels that decrease monotonically under such superchannels; therefore these measures, dubbed collectively the “unextendible entanglement of a channel”, yield upper bounds on several communication-theoretic quantities of interest in the regimes of resource distillation and zero error.We then generalize the formalism ofk-extendibility to bipartite superchannels, thus obtaining functions that are monotone under two-extendible superchannels. This allows us to analyze probabilistic distillation of ebits or secret key bits from a bipartite state when using a resourceful quantum channel. Moreover, we propose semidefinite programs to evaluate several of these quantities, providing a computationally feasible method of comparison between quantum channels for resource distillation.