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

Lecture notes in computer science

Private Computation with Shared Randomness over Broadcast Channel

Clemente Galdi, Pino Persiano

Published Jan 1, 2002• 1 citation
Publisher
DOI
10.1007/3-540-45861-1_19

Related papers

Private Capacity of Broadcast Channels

Ning Cai

Lecture notes in computer science•Jan 1, 2006•1 citation

Multiplication triples from entangled quantum resources

Maxwell Gold, Eric Chitambar

An efficient paradigm for multi-party computation (MPC) are protocols structured around access to shared pre-processed computational resources. In this model, certain forms of correlated randomness are distributed to the participants prior to their computation. The shared randomness is then consumed in a computation phase that involves public communication with efficient round complexity, and the computation is secure in this second phase provided the initial correlations were distributed securely. Usually the latter requires some strong setup assumptions, such as a trusted dealer and private channels. We present a novel approach for generating these correlations from entangled quantum graph states and yield information-theoretic privacy guarantees that hold against a malicious adversary, with limited assumptions. Our primary contribution is a tripartite resource state and measurement-based protocol for extracting a binary multiplication triple, a special form of shared randomness that enables the private multiplication of a bit conjunction. Here, we employ a third party as a Referee and demand only an honest pair among the three parties. The role of this Referee is weaker than that of a Dealer, as the Referee learns nothing about the underlying shared randomness that is disseminated. We prove perfect privacy for our protocol, assuming access to an ideal copy of the resource state, an assumption that is based on the existence of graph state verification protocols. Finally, we demonstrate its application as a primitive for more complex Boolean functionalities such as 1-out-of-2 oblivious transfer (OT) and MPC for an arbitrary $N$-party Boolean function, assuming access to the proper broadcasting channel.

arXiv:2505.10385•May 15, 2025•0 citations

Random Sources in Private Computation

Geoffroy Couteau, Adi Rosén

Lecture notes in computer science•Jan 1, 2022•2 citations

Computing Functions of a Shared Secret

Amos Beimel, Mike V. D. Burmester, Yvo Desmedt +1 more

In this work we introduce and study threshold (t-out-of-n) secret sharing schemes for families of functions ${\cal F}$. Such schemes allow any set of at least t parties to compute privately the value f(s) of a (previously distributed) secret s, for any $f\in {\cal F}$. Smaller sets of players get no more information about the secret than what follows from the value f(s). The goal is to make the shares as short as possible. Results are obtained for two different settings: we study the case when the evaluation is done on a broadcast channel without interaction, and we examine what can be gained by allowing evaluations to be done interactively via private channels.

SIAM Journal on Discrete Mathematics•Jan 1, 2000•15 citations

A Randomness-Rounds Tradeoff in Private Computation

Eyal Kushilevitz, Adi Rosén

Springer eBooks•Aug 9, 2007•22 citations

Entanglement-assisted private communication over quantum broadcast channels

Haoyu Qi, Kunal Sharma, Mark M. Wilde

Abstract We consider entanglement-assisted (EA) private communication over a quantum broadcast channel, in which there is a single sender and multiple receivers. We divide the receivers into two sets: the decoding set and the malicious set. The decoding set and the malicious set can either be disjoint or can have a finite intersection. For simplicity, we say that a single party Bob has access to the decoding set and another party Eve has access to the malicious set, and both Eve and Bob have access to the pre-shared entanglement with Alice. The goal of the task is for Alice to communicate classical information reliably to Bob and securely against Eve, and Bob can take advantage of pre-shared entanglement with Alice. In this framework, we establish a lower bound on the one-shot EA private capacity. When there exists a quantum channel mapping the state of the decoding set to the state of the malicious set, such a broadcast channel is said to be degraded. We establish an upper bound on the one-shot EA private capacity in terms of smoothed min- and max-entropies for such channels. In the limit of a large number of independent channel uses, we prove that the EA private capacity of a degraded quantum broadcast channel is given by a single-letter formula. Finally, we consider two specific examples of degraded broadcast channels and find their capacities. In the first example, we consider the scenario in which one part of Bob’s laboratory is compromised by Eve. We show that the capacity for this protocol is given by the conditional quantum mutual information of a quantum broadcast channel, and so we thus provide an operational interpretation to the dynamic counterpart of the conditional quantum mutual information. In the second example, Eve and Bob have access to mutually exclusive sets of outputs of a broadcast channel.

arXiv:1803.03976•Journal of Physics A Mathematical and Theoretical•Jul 26, 2018•29 citations
An efficient paradigm for multi-party computation (MPC) are protocols structured around access to shared pre-processed computational resources. In this model, certain forms of correlated randomness are distributed to the participants prior to their computation. The shared randomness is then consumed in a computation phase that involves public communication with efficient round complexity, and the computation is secure in this second phase provided the initial correlations were distributed securely. Usually the latter requires some strong setup assumptions, such as a trusted dealer and private channels. We present a novel approach for generating these correlations from entangled quantum graph states and yield information-theoretic privacy guarantees that hold against a malicious adversary, with limited assumptions. Our primary contribution is a tripartite resource state and measurement-based protocol for extracting a binary multiplication triple, a special form of shared randomness that enables the private multiplication of a bit conjunction. Here, we employ a third party as a Referee and demand only an honest pair among the three parties. The role of this Referee is weaker than that of a Dealer, as the Referee learns nothing about the underlying shared randomness that is disseminated. We prove perfect privacy for our protocol, assuming access to an ideal copy of the resource state, an assumption that is based on the existence of graph state verification protocols. Finally, we demonstrate its application as a primitive for more complex Boolean functionalities such as 1-out-of-2 oblivious transfer (OT) and MPC for an arbitrary NNN-party Boolean function, assuming access to the proper broadcasting channel.
In this work we introduce and study threshold (t-out-of-n) secret sharing schemes for families of functions F{\cal F}F. Such schemes allow any set of at least t parties to compute privately the value f(s) of a (previously distributed) secret s, for any f∈Ff\in {\cal F}f∈F. Smaller sets of players get no more information about the secret than what follows from the value f(s). The goal is to make the shares as short as possible. Results are obtained for two different settings: we study the case when the evaluation is done on a broadcast channel without interaction, and we examine what can be gained by allowing evaluations to be done interactively via private channels.
Abstract We consider entanglement-assisted (EA) private communication over a quantum broadcast channel, in which there is a single sender and multiple receivers. We divide the receivers into two sets: the decoding set and the malicious set. The decoding set and the malicious set can either be disjoint or can have a finite intersection. For simplicity, we say that a single party Bob has access to the decoding set and another party Eve has access to the malicious set, and both Eve and Bob have access to the pre-shared entanglement with Alice. The goal of the task is for Alice to communicate classical information reliably to Bob and securely against Eve, and Bob can take advantage of pre-shared entanglement with Alice. In this framework, we establish a lower bound on the one-shot EA private capacity. When there exists a quantum channel mapping the state of the decoding set to the state of the malicious set, such a broadcast channel is said to be degraded. We establish an upper bound on the one-shot EA private capacity in terms of smoothed min- and max-entropies for such channels. In the limit of a large number of independent channel uses, we prove that the EA private capacity of a degraded quantum broadcast channel is given by a single-letter formula. Finally, we consider two specific examples of degraded broadcast channels and find their capacities. In the first example, we consider the scenario in which one part of Bob’s laboratory is compromised by Eve. We show that the capacity for this protocol is given by the conditional quantum mutual information of a quantum broadcast channel, and so we thus provide an operational interpretation to the dynamic counterpart of the conditional quantum mutual information. In the second example, Eve and Bob have access to mutually exclusive sets of outputs of a broadcast channel.