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

Symposium on Discrete Algorithms

An efficient protocol for unconditionally secure secret key exchange

Michael J. Fischer, Rebecca N. Wright

Published Jan 1, 1993• 20 citations
Publisher

Abstract

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 ...

DOI
10.5555/313559.313862

Related papers

Achieving perfect secrecy using correlated random variables

Michael J. Fischer, Rebecca N. Wright

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.)

•Jan 1, 1994•4 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

AN APPLICATION OF ST-NUMBERING TO SECRET KEY AGREEMENT

Takaaki Mizuki, SATORU NAKAYAMA, Hideaki Sone

Assume that there are players and an eavesdropper Eve, where several pairs of players have shared secret keys beforehand. We regard each player as a vertex of a graph and regard each pair of players sharing a key as an edge. Consider the case where Eve knows some of the keys according to a certain probability distribution. In this paper, applying the technique of st-numbering, we propose a protocol which allows any two designated players to agree on a secret key through such a "partially leaked key exchange graph." Our protocol is optimal in the sense that Eve's knowledge about the secret key agreed on by the two players is as small as possible.

International Journal of Foundations of Computer Science•Aug 1, 2011•2 citations

The case of the hidden hand

Hans van Ditmarsch

In unconditionally secure protocols, a sender and receiver are able to communicate their secrets to each other without the eavesdropper(s) being able to learn the secret, even when the eavesdropper intercepts the entire communication. We investigate such protocols for the special case of deals of cards over players, where two players aim to communicate to each other their hand of cards without the remaining player(s) learning a single card from either hand. In this contribution we show that a particular protocol of length strictly larger than two (i.e., consisting of more than just one announcement by one player, and one other announcement by the other player) is after all not acceptable, and therefore does not constitute a new solution. The demonstration requires a detailed case-based analysis. The result may bring a general approach to arbitrary finite-length protocols closer.

Journal of Applied Non-Classical Logics•Jan 1, 2005•8 citations

ABSOLUTELY SECURE MESSAGE TRANSMISSION USING A KEY SHARING GRAPH

YOSHIHIRO INDO, Takaaki Mizuki, Takao Nishizeki

Assume that there are players and an eavesdropper Eve of unlimited computational power and that several pairs of players have shared secret keys beforehand. In a key sharing graph, each vertex corresponds to a player, and each edge corresponds to a secret key shared by the two players corresponding to the ends of the edge. Given a key sharing graph, a player wishes to send a message to another player so that the eavesdropper Eve and any other player can get no information on the message. In this paper, we first give a necessary and sufficient condition on a key sharing graph for the existence of such a unicast protocol. We then extend the condition to the case where a multiple number of players other than the sender and receiver passively collude. We finally give a sufficient condition for the existence of a secure multicast protocol.

Discrete Mathematics Algorithms and Applications•Sep 25, 2012•1 citation

Necessary and Sufficient Numbers of Cards for Sharing Secret Keys on Hierarchical Groups (New Developments of Theory of Computation and Algorithms)

Takaaki Mizuki, Takao Nishizeki

Suppose that there are players in two hierarchical groups and acomputationally unlim- ited eavesdropper.Using arandom deal of cards, aplayer in the higher group wishes to send aone-bit message information-theoretically securely either to all the players in her group or to all the players in the two groups.This can be done by the s0-called 2-level key set protocol.In this paper we give anecessary and sufficient condition for the 2-level key set protocol to succeed.

•May 1, 2001•0 citations
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 ...
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≥d \ged≥ (42.8) ⋅\cdot⋅ (1/$\beta)\sp{2.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$\sp{n}$. (Abstract shortened by UMI.)
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)
Assume that there are players and an eavesdropper Eve, where several pairs of players have shared secret keys beforehand. We regard each player as a vertex of a graph and regard each pair of players sharing a key as an edge. Consider the case where Eve knows some of the keys according to a certain probability distribution. In this paper, applying the technique of st-numbering, we propose a protocol which allows any two designated players to agree on a secret key through such a "partially leaked key exchange graph." Our protocol is optimal in the sense that Eve's knowledge about the secret key agreed on by the two players is as small as possible.
In unconditionally secure protocols, a sender and receiver are able to communicate their secrets to each other without the eavesdropper(s) being able to learn the secret, even when the eavesdropper intercepts the entire communication. We investigate such protocols for the special case of deals of cards over players, where two players aim to communicate to each other their hand of cards without the remaining player(s) learning a single card from either hand. In this contribution we show that a particular protocol of length strictly larger than two (i.e., consisting of more than just one announcement by one player, and one other announcement by the other player) is after all not acceptable, and therefore does not constitute a new solution. The demonstration requires a detailed case-based analysis. The result may bring a general approach to arbitrary finite-length protocols closer.
Assume that there are players and an eavesdropper Eve of unlimited computational power and that several pairs of players have shared secret keys beforehand. In a key sharing graph, each vertex corresponds to a player, and each edge corresponds to a secret key shared by the two players corresponding to the ends of the edge. Given a key sharing graph, a player wishes to send a message to another player so that the eavesdropper Eve and any other player can get no information on the message. In this paper, we first give a necessary and sufficient condition on a key sharing graph for the existence of such a unicast protocol. We then extend the condition to the case where a multiple number of players other than the sender and receiver passively collude. We finally give a sufficient condition for the existence of a secure multicast protocol.