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 ...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 AlgorithmsJan 1, 199320 citations

Secret Key Sharing Based On Authenticated Group Key Transfer Protocol

Anna Suganthi.S, Rajini Girinath D

Jan 1, 20150 citations

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.)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, 19944 citations

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