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

Achieving perfect secrecy using correlated random variables

Michael J. Fischer, Rebecca N. Wright

Published Jan 1, 1994• 4 citations
OpenAlex

Abstract

We present a general model for communication among a of players, $P\sb{1}$ through $P\sb{k}$, overheard by a passive eavesdropper, Eve, in which all players including Eve are given private inputs that may be correlated. We define and explore secret key exchange in this model. A protocol specifies how the team players behave. A source specifies a distribution on the team players' inputs. Together, a protocol and a source are a system. An adequate notion of secrecy must depend not only on the protocol, but on any relevant Eve may have about the source. We provide precise mathematical definitions of the multiparty secret key exchange problem that take Eve's into account, and allow us to determine whether a given system achieves secret key exchange with respect to any particular type of knowledge for Eve. Our secrecy requirements are information-theoretic and hold even if Eve is computationally unlimited. We explore the properties of secret key exchange systems and show formally the intuitive result that the team players' inputs must be correlated in order for secret key exchange to be achieved. We show that any source has a finite capacity for secret key exchange even if the team players are allowed unlimited independent randomization. Specifically, the capacity of a source is the largest number of output values of any secret key exchange system using that source. We present an upper bound on the capacity of arbitrary sources. In the second half of the dissertation, we focus our attention on sources yielding inputs consisting of hands of prespecified sizes from a randomly shuffled deck of cards. We exhibit several secret key exchange protocols designed to work even if Eve is allowed to see the remaining cards in the deck. Let each team player $P\sb{i}$ hold $s\sb{i}$ cards, let Eve hold $s\sb{e}$ cards, and let k be the number of team players. We present a family of key set protocols, a simple family of protocols that achieve one-bit secret key exchange provided that max $s\sb{i}$ + min $s\sb{i} \ge k$ + $s\sb{e}$. We use a game-theoretic argument to exhibit an optimal key set protocol. Of particular interest is the symmetric case in which each player receives the same fraction $\beta$ of the cards in the deck. The efficiency of a secret key exchange protocol is measured by the smallest deck size $d\sb{0}$ for which the protocol is guaranteed of success. The best previous bound (Fischer, Paterson, and Rackoff, 1991) was super-polynomial in 1/$\beta$ and only handled the special case of k = 2 and n = 1. We present the transformation protocol, which achieves n-bit secret key exchange in the symmetric case for any deck size $d > d\sb{0}$ = O(n(1/$\beta)\sp{2.71}$). Using the transformation protocol, we show that if $d \ge$ (42.8) $\cdot$ (1/$\beta)\sp{2.71}$(n + 0.07), then the capacity of a source in which each team player receives $\beta d$ cards is at least 2$\sp{n}$. (Abstract shortened by UMI.)

Related papers

An efficient protocol for unconditionally secure secret key exchange

Michael J. Fischer, Rebecca N. Wright

The multiparty secret key exchange problem is to find a k-player protocol for generating an n-bit random key. At the end of the protocol, the key should be known to each player but remain completely secret from a computationally unlimited eavesdropper, Eve, who overhears all communication among the players. The players are initially dealt hands of cards of prespecified sizes from a deck of distinct cards; any remaining cards are given to Eve. Considered here is the case in which each player receives the same fraction fi of the cards in the deck, for fi in the interval (0; 1=k]. The efficiency of a secret key exchange protocol is measured by the smallest deck size d 0 for which the protocol is guaranteed of success. A secret key exchange protocol is presented with d 0 = O(n(1=fi) 2:71 ). The best previous bound, by Fischer, Paterson, and Rackoff (1991), was super-polynomial in 1=fi and only handled the special case of k = 2 and n = 1. 1 Introduction The problem of multiparty secret ...

Symposium on Discrete Algorithms•Jan 1, 1993•20 citations

Secret bit transmission using a random deal of cards

Michael J. Fischer, Michael S. Paterson, Charles Rackoff

Abstract : Protocols are developed and analyzed for transmitting a secret bit between a sender and a receiver process using only the information contained in a random deal of hands of specified sizes from a deck of n distinct cards. The sender's and receiver's algorithms are known i advance, and all conversation between sender and receiver is public and is heard by all. A correct protocol always succeeds in transmitting the secret bit, and the other player(s), who receive the remaining cards and are assumed to have unlimited computing power, gain no information whatsoever about the value of the secret bit. In other words, their probability of correctly guessing the secret is bit exactly the same after listening to a run of the protocol as it was before. Both randomized and deterministic protocols are considered. A randomized protocol is described which works whenever the sender's and receiver's hands comprise a constant fraction of the deck, for all sufficiently large decks. A deterministic protocol is also described, but it requires the sender and receiver to each have approximately 44% of the cards. A general condition is presented that provides a lower bound on sizes of the sender's and receiver's hands in order for a protocol to exist. There is still a considerable gap between the upper and lower bounds, and improving the bounds remains an open problem. (kr)

DIMACS series in discrete mathematics and theoretical computer science•Apr 3, 1991•26 citations

Resource-Efficient Common Randomness and Secret-Key Schemes

Badih Ghazi, T. S. Jayram

We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with connections to communication under uncertainty and locality sensitive hashing. We take the approach of treating correlated sources as a critical resource, and ask whether common randomness can be generated resource-efficiently. We consider two notable sources in this setup arising from correlated bits and correlated Gaussians. We design the first explicit schemes that use only a polynomial number of samples (in the key length) so that the players can generate shared keys that agree with constant probability using optimal communication. The best previously known schemes were both non-constructive and used an exponential number of samples. In the amortized setting, we characterize the largest achievable ratio of key length to communication in terms of the external and internal information costs, two well-studied quantities in theoretical computer science. In the relaxed setting where the two parties merely wish to improve the correlation between the generated keys of length k, we show that there are no interactive protocols using o(k) bits of communication having agreement probability even as small as 2–o(k). For the related communication problem where the players wish to compute a joint function f of their inputs using i.i.d samples from a known source, we give a simultaneous message passing protocol using 2O(c) bits where c is the interactive randomized public-coin communication complexity of f. This matches the lower bound shown previously while the best previously known upper bound was doubly exponential in c. Our schemes reveal a new connection between common randomness and unbiased error-correcting codes, e.g., dual-BCH codes and their analogues in Euclidean space.

arXiv:1707.08086•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2018•14 citations

A Bit of Secrecy for Gaussian Source Compression

Eva C. Song, Paul Cuff, H. Vincent Poor

In this paper, the compression of an independent and identically distributed Gaussian source sequence is studied in an unsecure network. Within a game theoretic setting for a three-party noiseless communication network (sender Alice, legitimate receiver Bob, and eavesdropper Eve), the problem of how to efficiently compress a Gaussian source with limited secret key in order to guarantee that Bob can reconstruct with high fidelity while preventing Eve from estimating an accurate reconstruction is investigated. It is assumed that Alice and Bob share a secret key with limited rate. Three scenarios are studied, in which the eavesdropper ranges from weak to strong in terms of the causal side information she has. It is shown that one bit of secret key per source symbol is enough to achieve perfect secrecy performance in the Gaussian squared error setting, and the information theoretic region is not optimized by joint Gaussian random variables.

arXiv:1307.7365•Jul 28, 2013•1 citation

A bit of secrecy for Gaussian source compression

Eva C. Song, Paul Cuff, H. Vincent Poor

In this paper, the compression of an independent and identically distributed Gaussian source sequence is studied in an unsecure network. Within a game theoretic setting for a three-party noiseless communication network (sender Alice, legitimate receiver Bob, and eavesdropper Eve), the problem of how to efficiently compress a Gaussian source with limited secret key in order to guarantee that Bob can reconstruct with high fidelity while preventing Eve from estimating an accurate reconstruction is investigated. It is assumed that Alice and Bob share a secret key with limited rate. Three scenarios are studied, in which the eavesdropper ranges from weak to strong in terms of the causal side information she has. It is shown that one bit of secret key per source symbol is enough to achieve perfect secrecy performance in the Gaussian squared error setting, and the information theoretic region is not optimized by joint Gaussian random variables.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•6 citations

Who holds the best card? Secure communication of optimal secret bits.

Hans van Ditmarsch, David Fernández–Duque, Vaishnavi Sundararajan +1 more

In the Russian cards problem, a group of communicating agents and an eavesdropper, Eve, draw cards from a deck. The agents then wish to inform each other about their hand without Eve learning any 'protected' information, typically in the sense of weak possibilistic security. We consider a weakening of this original problem, whereby the cards are linearly ordered by value. The agents wish to know the value of the best card held between them, without Eve knowing who holds said card. We consider standard solutions to the problem based on combinatorial designs, as well as novel solutions based on secret-bit-exchange protocols. Our results show that this version of the problem can be solved in many instances where the size of each agent's hand is linear on that of the eavesdropper's.

Australas. J Comb.•Jan 1, 2021•0 citations
We present a general model for communication among a of players, P\sb1P\sb{1}P\sb1 through P\sbkP\sb{k}P\sbk, overheard by a passive eavesdropper, Eve, in which all players including Eve are given private inputs that may be correlated. We define and explore secret key exchange in this model. A protocol specifies how the team players behave. A source specifies a distribution on the team players' inputs. Together, a protocol and a source are a system. An adequate notion of secrecy must depend not only on the protocol, but on any relevant Eve may have about the source. We provide precise mathematical definitions of the multiparty secret key exchange problem that take Eve's into account, and allow us to determine whether a given system achieves secret key exchange with respect to any particular type of knowledge for Eve. Our secrecy requirements are information-theoretic and hold even if Eve is computationally unlimited.
We explore the properties of secret key exchange systems and show formally the intuitive result that the team players' inputs must be correlated in order for secret key exchange to be achieved. We show that any source has a finite capacity for secret key exchange even if the team players are allowed unlimited independent randomization. Specifically, the capacity of a source is the largest number of output values of any secret key exchange system using that source. We present an upper bound on the capacity of arbitrary sources.
In the second half of the dissertation, we focus our attention on sources yielding inputs consisting of hands of prespecified sizes from a randomly shuffled deck of cards. We exhibit several secret key exchange protocols designed to work even if Eve is allowed to see the remaining cards in the deck. Let each team player P\sbiP\sb{i}P\sbi hold s\sbis\sb{i}s\sbi cards, let Eve hold s\sbes\sb{e}s\sbe cards, and let k be the number of team players. We present a family of key set protocols, a simple family of protocols that achieve one-bit secret key exchange provided that max s\sbis\sb{i}s\sbi + min s\sbi≥ks\sb{i} \ge ks\sbi≥k + s\sbes\sb{e}s\sbe. We use a game-theoretic argument to exhibit an optimal key set protocol.
Of particular interest is the symmetric case in which each player receives the same fraction β\betaβ of the cards in the deck. The efficiency of a secret key exchange protocol is measured by the smallest deck size d\sb0d\sb{0}d\sb0 for which the protocol is guaranteed of success. The best previous bound (Fischer, Paterson, and Rackoff, 1991) was super-polynomial in 1/β\betaβ and only handled the special case of k = 2 and n = 1. We present the transformation protocol, which achieves n-bit secret key exchange in the symmetric case for any deck size d>d\sb0d > d\sb{0}d>d\sb0 = O(n(1/β)\sp2.71\beta)\sp{2.71}β)\sp2.71). Using the transformation protocol, we show that if d≥d \ged≥ (42.8) ⋅\cdot⋅ (1/β)\sp2.71\beta)\sp{2.71}β)\sp2.71(n + 0.07), then the capacity of a source in which each team player receives βd\beta dβd cards is at least 2\spn\sp{n}\spn. (Abstract shortened by UMI.)
The multiparty secret key exchange problem is to find a k-player protocol for generating an n-bit random key. At the end of the protocol, the key should be known to each player but remain completely secret from a computationally unlimited eavesdropper, Eve, who overhears all communication among the players. The players are initially dealt hands of cards of prespecified sizes from a deck of distinct cards; any remaining cards are given to Eve. Considered here is the case in which each player receives the same fraction fi of the cards in the deck, for fi in the interval (0; 1=k]. The efficiency of a secret key exchange protocol is measured by the smallest deck size d 0 for which the protocol is guaranteed of success. A secret key exchange protocol is presented with d 0 = O(n(1=fi) 2:71 ). The best previous bound, by Fischer, Paterson, and Rackoff (1991), was super-polynomial in 1=fi and only handled the special case of k = 2 and n = 1. 1 Introduction The problem of multiparty secret ...
Abstract : Protocols are developed and analyzed for transmitting a secret bit between a sender and a receiver process using only the information contained in a random deal of hands of specified sizes from a deck of n distinct cards. The sender's and receiver's algorithms are known i advance, and all conversation between sender and receiver is public and is heard by all. A correct protocol always succeeds in transmitting the secret bit, and the other player(s), who receive the remaining cards and are assumed to have unlimited computing power, gain no information whatsoever about the value of the secret bit. In other words, their probability of correctly guessing the secret is bit exactly the same after listening to a run of the protocol as it was before. Both randomized and deterministic protocols are considered. A randomized protocol is described which works whenever the sender's and receiver's hands comprise a constant fraction of the deck, for all sufficiently large decks. A deterministic protocol is also described, but it requires the sender and receiver to each have approximately 44% of the cards. A general condition is presented that provides a lower bound on sizes of the sender's and receiver's hands in order for a protocol to exist. There is still a considerable gap between the upper and lower bounds, and improving the bounds remains an open problem. (kr)
We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with connections to communication under uncertainty and locality sensitive hashing. We take the approach of treating correlated sources as a critical resource, and ask whether common randomness can be generated resource-efficiently. We consider two notable sources in this setup arising from correlated bits and correlated Gaussians. We design the first explicit schemes that use only a polynomial number of samples (in the key length) so that the players can generate shared keys that agree with constant probability using optimal communication. The best previously known schemes were both non-constructive and used an exponential number of samples. In the amortized setting, we characterize the largest achievable ratio of key length to communication in terms of the external and internal information costs, two well-studied quantities in theoretical computer science. In the relaxed setting where the two parties merely wish to improve the correlation between the generated keys of length k, we show that there are no interactive protocols using o(k) bits of communication having agreement probability even as small as 2–o(k). For the related communication problem where the players wish to compute a joint function f of their inputs using i.i.d samples from a known source, we give a simultaneous message passing protocol using 2O(c) bits where c is the interactive randomized public-coin communication complexity of f. This matches the lower bound shown previously while the best previously known upper bound was doubly exponential in c. Our schemes reveal a new connection between common randomness and unbiased error-correcting codes, e.g., dual-BCH codes and their analogues in Euclidean space.
In this paper, the compression of an independent and identically distributed Gaussian source sequence is studied in an unsecure network. Within a game theoretic setting for a three-party noiseless communication network (sender Alice, legitimate receiver Bob, and eavesdropper Eve), the problem of how to efficiently compress a Gaussian source with limited secret key in order to guarantee that Bob can reconstruct with high fidelity while preventing Eve from estimating an accurate reconstruction is investigated. It is assumed that Alice and Bob share a secret key with limited rate. Three scenarios are studied, in which the eavesdropper ranges from weak to strong in terms of the causal side information she has. It is shown that one bit of secret key per source symbol is enough to achieve perfect secrecy performance in the Gaussian squared error setting, and the information theoretic region is not optimized by joint Gaussian random variables.
In this paper, the compression of an independent and identically distributed Gaussian source sequence is studied in an unsecure network. Within a game theoretic setting for a three-party noiseless communication network (sender Alice, legitimate receiver Bob, and eavesdropper Eve), the problem of how to efficiently compress a Gaussian source with limited secret key in order to guarantee that Bob can reconstruct with high fidelity while preventing Eve from estimating an accurate reconstruction is investigated. It is assumed that Alice and Bob share a secret key with limited rate. Three scenarios are studied, in which the eavesdropper ranges from weak to strong in terms of the causal side information she has. It is shown that one bit of secret key per source symbol is enough to achieve perfect secrecy performance in the Gaussian squared error setting, and the information theoretic region is not optimized by joint Gaussian random variables.
In the Russian cards problem, a group of communicating agents and an eavesdropper, Eve, draw cards from a deck. The agents then wish to inform each other about their hand without Eve learning any 'protected' information, typically in the sense of weak possibilistic security. We consider a weakening of this original problem, whereby the cards are linearly ordered by value. The agents wish to know the value of the best card held between them, without Eve knowing who holds said card. We consider standard solutions to the problem based on combinatorial designs, as well as novel solutions based on secret-bit-exchange protocols. Our results show that this version of the problem can be solved in many instances where the size of each agent's hand is linear on that of the eavesdropper's.