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:1502.05773 · Iran Workshop on Communication and Information Theory (IWCIT)

Multipartite monotones for secure sampling by public discussion from noisy correlations

Pradeep Kr. Banerjee

Published May 1, 2015• 0 citations
arXivHTMLPDF

Abstract

We address the problem of quantifying the cryptographic content of probability distributions, in relation to an application to secure multi-party sampling against a passive t-adversary. We generalize a recently introduced notion of assisted common information of a pair of correlated sources to that of K sources and define a family of monotone rate regions indexed by K. This allows for a simple characterization of all t-private distributions that can be statistically securely sampled without any auxiliary setup of pre-shared noisy correlations. We also give a new monotone called the residual total correlation that admits a simple operational interpretation. Interestingly, for sampling with non-trivial setups (K > 2) in the public discussion model, our definition of a monotone region differs from the one by Prabhakaran and Prabhakaran (ITW 2012).

DOI
10.1109/iwcit.2015.7140210

Related papers

Assisted Common Information With an Application to Secure Two-Party Sampling

Vinod M. Prabhakaran, Manoj Prabhakaran

An important subclass of secure multiparty computation is secure sampling: two parties output samples of a pair of jointly distributed random variables such that neither party learns more about the other party's output than what its own output reveals. The parties make use of a setup - correlated random variables with a different distribution - as well as unlimited noiseless communication. An upperbound on the rate of producing samples of a desired distribution from a given setup is presented. The region of tension developed in this paper measures how well the dependence between a pair of random variables can be resolved by a piece of common information. The bounds on rate are a consequence of a monotonicity property; a protocol between two parties can only lower the tension between their views. Connections are drawn between the region of tension and the notion of common information. A generalization of the Gács-Körner common information, called the assisted common information, which takes into account almost common information ignored by Gács-Körner common information is defined. The region of tension is shown to be related to the rate regions of both the assisted common information and the Gray-Wyner systems (and, a fortiori, Wyner's common information).

arXiv:1002.1916•IEEE Transactions on Information Theory•Apr 7, 2014•48 citations

Assisted common information

Vinod M. Prabhakaran, Manoj Prabhakaran

Secure multi-party computation is a central problem in modern cryptography. An important sub-class of this are problems of the following form: Alice and Bob desire to produce sample(s) of a pair of jointly distributed random variables. Each party must learn nothing more about the other party's output than what its own output reveals. To aid in this, they have available a set up - correlated random variables whose distribution is different from the desired distribution - as well as unlimited noiseless communication. In this paper we present an upperbound on how efficiently a given set up can be used to produce samples from a desired distribution. The key tool we develop is a generalization of the concept of common information of two dependent random variables [Gács-Körner, 1973]. Our generalization - a three-dimensional region - remedies some of the limitations of the original definition which captured only a limited form of dependence. It also includes as a special case Wyner's common information [Wyner, 1975]. To derive the cryptographic bounds, we rely on a monotonicity property of this region: the region of the “views” of Alice and Bob engaged in any protocol can only monotonically expand and not shrink. Thus, by comparing the regions for the target random variables and the given random variables, we obtain our upperbound.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•8 citations

Assisted common information: Further results

Vinod M. Prabhakaran, Manoj M. Prabhakaran

We presented assisted common information as a generalization of Gacs-Korner (GK) common information at last year's ISIT. The motivation for our formulation was to improve upperbounds on the efficiency of protocols for secure two-party sampling (which is a form of secure multi-party computation). Our upperbound was based on a monotonicity property of a rate region (called the assisted residual information region) associated with the assisted common information formulation. In this note we present further results. We explore the connection of assisted common information with the Gray-Wyner system. We show that the assisted residual information region and the Gray-Wyner region are connected by a simple relationship: the assisted residual information region is the increasing hull of the Gray-Wyner region under an affine map. Several known relationships between GK common information and Gray-Wyner system fall out as consequences of this. Quantities which arise in other source coding contexts acquire new interpretations. In previous work we showed that assisted common information can be used to derive upperbounds on the rate at which a pair of parties can securely sample correlated random variables, given correlated random variables from another distribution. Here we present an example where the bound derived using assisted common information is much better than previously known bounds, and in fact is tight. This example considers correlated random variables defined in terms of standard variants of oblivious transfer, and is interesting on its own as it answers a natural question about these cryptographic primitives.

arXiv:1105.6163•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2011•7 citations

On secure multiparty sampling for more than two parties

Manoj Prabhakaran, Vinod M. Prabhakaran

We investigate secure multi-party sampling problems involving more than two parties. In the public discussion model, we give a simple characterization of the distributions that can be sampled without any setup. In a model which allows private point-to-point communication, we reduce the problem of characterizing distributions that can be securely sampled using pairwise setups to the problem of characterizing distributions that can be sampled without any setups.

IEEE Information Theory Workshop (ITW)•Sep 1, 2012•13 citations

Distributed (Correlation) Samplers:A Study on the Round Complexity of Cryptographic Sampling Protocols

Damiano Abram

This thesis presents a theoretical analysis of round complexity in cryptographic sampling protocols. We study the following problem: how can n participants agree on a random sample from the distribution D without anybody knowing any secret information hidden in the chosen sample? How many rounds of interactions are needed in any such protocol? Which assumptions are required? These questions are particularly interesting in the context of multiparty computation (MPC) due to the extensive reliance (often unavoidable) on trusted setups such as common reference strings (CRSs). These are samples from known distributions made public before the beginning of the protocol. Security proofs often require CRSs to hide trapdoors. However, if these trapdoors get leaked, security is often fatally compromised. Since trusted setups are inherently single points of failure, it is desirable to generate CRSs in a distributed fashion using MPC protocols: as long as at least one of the participants remains honest, any trapdoor hidden in the CRS is guaranteed to remain secret. Previous research (Garg et al. TCC ’14) had shown that, in the setting of semi-honest security with dishonest majority, any functionality can be implemented in two rounds. In this thesis, we show that, using strong primitives such as indistinguishability obfuscation (iO), it is possible to build one-round sampling protocols. We call these constructions distributed samplers. We show that these protocols can be used to securely generate large amounts of correlated randomness with sublinear communication in a single round. We study different ways to upgrade our semi-honest construction to active security. First, we try to circumvent Cleve’s impossibility (STOC ’86) by allowing the adversary limited influence on the output of the protocol: we consider the functionality F_D^{Active} that proposes a polynomial number of different outputs to the adversary, letting it choose its favourite one (F_D^{Active} can still be used to generate CRSs). We show how to implement F_D^{Active} in one round by relying on a programmable random oracle. In subsequent work, we show that random oracles are necessary: any actively secure distributed samplers implementing F_D^{Active} needs to rely on a CRS that is non-reusable, as large as a sample from D and structured (unless D is an obliviously samplable distribution). This suggests that, without random oracles, simulation-based, actively secure distributed samplers provide no advantage over trusted dealers. We get around this impossibility by proposing new game-based definitions for actively secure distributed samplers. Hardness-preserving distributed samplers allow the removal of CRSs from MPC protocols preserving at the same time the hardness of search problems. Indistinguishability-preserving distributed samplers, on the other hand, substitute the trusted setup while preserving the functionality, however, the protocol needs to satisfy particular conditions. We show how to build distributed samplers with the defined properties by relying on extremely lossy functions, the subexponential security of iO and other primitives. Next, in the context of active security with dishonest majority, we study the feasibility of protocols producing unbiased samples with guaranteed output: to circumvent Cleve's impossibility, we assume the existence of an auxiliary functionality that, upon invocation, publishes a random , short k-bit string. We first study the question when D is the uniform distribution over {0, 1}^m where m>k. This problem is called coin tossing extension (CTE) (Bellare et al. PODC '96). We show the existence of O(1)-round CTE constructions producing an arbitrarily large quantity of unbiased randomness based on various assumptions (OWFs, DDH, QR and DCR, class groups). Our most important result is an LWE-based, one-round, UC-secure, n-party CTE protocol withstanding adaptive corruption. The protocol can be viewed as an explainable randomness extractor. By relying on distributed samplers and the auxiliary functionality, we build one-round unbiased sampling protocols for any distribution. Finally, we present a lower bound for statistically secure CTE with black-box simulation: an R-round protocol can generate at most k+R·O(log λ) bits of randomness.

•Jun 25, 2024•0 citations

Multipartite classical and quantum secrecy monotones

Nicolas J. Cerf, Serge Massar, Sara Schneider

In order to study multipartite quantum cryptography, we introduce quantities which vanish on product probability distributions, and which can only decrease if the parties carry out local operations or public classical communication. These ``secrecy monotones'' therefore measure how much secret correlation is shared by the parties. In the bipartite case we show that the mutual information is a secrecy monotone. In the multipartite case we describe two different generalizations of the mutual information, both of which are secrecy monotones. The existence of two distinct secrecy monotones allows us to show that in multipartite quantum cryptography the parties must make irreversible choices about which multipartite correlations they want to obtain. Secrecy monotones can be extended to the quantum domain and are then defined on density matrices. We illustrate this generalization by considering tripartite quantum cryptography based on the Greenberger-Horne-Zeilinger state. We show that before carrying out measurements on the state, the parties must make an irreversible decision about what probability distribution they want to obtain.

arXiv:quant-ph/0202103•Physical Review A•Oct 15, 2002•45 citations
We address the problem of quantifying the cryptographic content of probability distributions, in relation to an application to secure multi-party sampling against a passive t-adversary. We generalize a recently introduced notion of assisted common information of a pair of correlated sources to that of K sources and define a family of monotone rate regions indexed by K. This allows for a simple characterization of all t-private distributions that can be statistically securely sampled without any auxiliary setup of pre-shared noisy correlations. We also give a new monotone called the residual total correlation that admits a simple operational interpretation. Interestingly, for sampling with non-trivial setups (K > 2) in the public discussion model, our definition of a monotone region differs from the one by Prabhakaran and Prabhakaran (ITW 2012).
An important subclass of secure multiparty computation is secure sampling: two parties output samples of a pair of jointly distributed random variables such that neither party learns more about the other party's output than what its own output reveals. The parties make use of a setup - correlated random variables with a different distribution - as well as unlimited noiseless communication. An upperbound on the rate of producing samples of a desired distribution from a given setup is presented. The region of tension developed in this paper measures how well the dependence between a pair of random variables can be resolved by a piece of common information. The bounds on rate are a consequence of a monotonicity property; a protocol between two parties can only lower the tension between their views. Connections are drawn between the region of tension and the notion of common information. A generalization of the Gács-Körner common information, called the assisted common information, which takes into account almost common information ignored by Gács-Körner common information is defined. The region of tension is shown to be related to the rate regions of both the assisted common information and the Gray-Wyner systems (and, a fortiori, Wyner's common information).
Secure multi-party computation is a central problem in modern cryptography. An important sub-class of this are problems of the following form: Alice and Bob desire to produce sample(s) of a pair of jointly distributed random variables. Each party must learn nothing more about the other party's output than what its own output reveals. To aid in this, they have available a set up - correlated random variables whose distribution is different from the desired distribution - as well as unlimited noiseless communication. In this paper we present an upperbound on how efficiently a given set up can be used to produce samples from a desired distribution. The key tool we develop is a generalization of the concept of common information of two dependent random variables [Gács-Körner, 1973]. Our generalization - a three-dimensional region - remedies some of the limitations of the original definition which captured only a limited form of dependence. It also includes as a special case Wyner's common information [Wyner, 1975]. To derive the cryptographic bounds, we rely on a monotonicity property of this region: the region of the “views” of Alice and Bob engaged in any protocol can only monotonically expand and not shrink. Thus, by comparing the regions for the target random variables and the given random variables, we obtain our upperbound.
We presented assisted common information as a generalization of Gacs-Korner (GK) common information at last year's ISIT. The motivation for our formulation was to improve upperbounds on the efficiency of protocols for secure two-party sampling (which is a form of secure multi-party computation). Our upperbound was based on a monotonicity property of a rate region (called the assisted residual information region) associated with the assisted common information formulation. In this note we present further results. We explore the connection of assisted common information with the Gray-Wyner system. We show that the assisted residual information region and the Gray-Wyner region are connected by a simple relationship: the assisted residual information region is the increasing hull of the Gray-Wyner region under an affine map. Several known relationships between GK common information and Gray-Wyner system fall out as consequences of this. Quantities which arise in other source coding contexts acquire new interpretations. In previous work we showed that assisted common information can be used to derive upperbounds on the rate at which a pair of parties can securely sample correlated random variables, given correlated random variables from another distribution. Here we present an example where the bound derived using assisted common information is much better than previously known bounds, and in fact is tight. This example considers correlated random variables defined in terms of standard variants of oblivious transfer, and is interesting on its own as it answers a natural question about these cryptographic primitives.
This thesis presents a theoretical analysis of round complexity in cryptographic sampling protocols. We study the following problem: how can n participants agree on a random sample from the distribution D without anybody knowing any secret information hidden in the chosen sample? How many rounds of interactions are needed in any such protocol? Which assumptions are required? These questions are particularly interesting in the context of multiparty computation (MPC) due to the extensive reliance (often unavoidable) on trusted setups such as common reference strings (CRSs). These are samples from known distributions made public before the beginning of the protocol. Security proofs often require CRSs to hide trapdoors. However, if these trapdoors get leaked, security is often fatally compromised. Since trusted setups are inherently single points of failure, it is desirable to generate CRSs in a distributed fashion using MPC protocols: as long as at least one of the participants remains honest, any trapdoor hidden in the CRS is guaranteed to remain secret. Previous research (Garg et al. TCC ’14) had shown that, in the setting of semi-honest security with dishonest majority, any functionality can be implemented in two rounds. In this thesis, we show that, using strong primitives such as indistinguishability obfuscation (iO), it is possible to build one-round sampling protocols. We call these constructions distributed samplers. We show that these protocols can be used to securely generate large amounts of correlated randomness with sublinear communication in a single round. We study different ways to upgrade our semi-honest construction to active security. First, we try to circumvent Cleve’s impossibility (STOC ’86) by allowing the adversary limited influence on the output of the protocol: we consider the functionality F_D^{Active} that proposes a polynomial number of different outputs to the adversary, letting it choose its favourite one (F_D^{Active} can still be used to generate CRSs). We show how to implement F_D^{Active} in one round by relying on a programmable random oracle. In subsequent work, we show that random oracles are necessary: any actively secure distributed samplers implementing F_D^{Active} needs to rely on a CRS that is non-reusable, as large as a sample from D and structured (unless D is an obliviously samplable distribution). This suggests that, without random oracles, simulation-based, actively secure distributed samplers provide no advantage over trusted dealers. We get around this impossibility by proposing new game-based definitions for actively secure distributed samplers. Hardness-preserving distributed samplers allow the removal of CRSs from MPC protocols preserving at the same time the hardness of search problems. Indistinguishability-preserving distributed samplers, on the other hand, substitute the trusted setup while preserving the functionality, however, the protocol needs to satisfy particular conditions. We show how to build distributed samplers with the defined properties by relying on extremely lossy functions, the subexponential security of iO and other primitives. Next, in the context of active security with dishonest majority, we study the feasibility of protocols producing unbiased samples with guaranteed output: to circumvent Cleve's impossibility, we assume the existence of an auxiliary functionality that, upon invocation, publishes a random , short k-bit string. We first study the question when D is the uniform distribution over {0, 1}^m where m>k. This problem is called coin tossing extension (CTE) (Bellare et al. PODC '96). We show the existence of O(1)-round CTE constructions producing an arbitrarily large quantity of unbiased randomness based on various assumptions (OWFs, DDH, QR and DCR, class groups). Our most important result is an LWE-based, one-round, UC-secure, n-party CTE protocol withstanding adaptive corruption. The protocol can be viewed as an explainable randomness extractor. By relying on distributed samplers and the auxiliary functionality, we build one-round unbiased sampling protocols for any distribution. Finally, we present a lower bound for statistically secure CTE with black-box simulation: an R-round protocol can generate at most k+R·O(log λ) bits of randomness.
In order to study multipartite quantum cryptography, we introduce quantities which vanish on product probability distributions, and which can only decrease if the parties carry out local operations or public classical communication. These ``secrecy monotones'' therefore measure how much secret correlation is shared by the parties. In the bipartite case we show that the mutual information is a secrecy monotone. In the multipartite case we describe two different generalizations of the mutual information, both of which are secrecy monotones. The existence of two distinct secrecy monotones allows us to show that in multipartite quantum cryptography the parties must make irreversible choices about which multipartite correlations they want to obtain. Secrecy monotones can be extended to the quantum domain and are then defined on density matrices. We illustrate this generalization by considering tripartite quantum cryptography based on the Greenberger-Horne-Zeilinger state. We show that before carrying out measurements on the state, the parties must make an irreversible decision about what probability distribution they want to obtain.