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.
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.
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 ...
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.
The problem of generating a shared secret key S by two parties knowing dependent random variables X and Y, respectively, but not sharing a secret key initially, is considered. An enemy who knows the random variable Z, jointly distributed with X and Y according to some probability distribution P/sub XYZ/, can also receive all messages exchanged by the two parties over a public channel. The goal of a protocol is that the enemy obtains at most a negligible amount of information about S. Upper bounds on H(S) as a function of P/sub XYZ/ are presented. Lower bounds on the rate H(S)/N (as N to infinity ) are derived for the case in which X=(X/sub 1/, . . ., X/sub N/), Y=(Y/sub 1/, . . ., Y/sub N/) and Z=(Z/sub 1/, . . ., Z/sub N/) result from N independent executions of a random experiment generating X/sub i/, Y/sub i/ and Z/sub i/ for i=1, . . ., N. It is shown that such a secret key agreement is possible for a scenario in which all three parties receive the output of a binary symmetric source over independent binary symmetric channels, even when the enemy's channel is superior to the other two channels.>
We consider the problem where a group of n nodes, connected to the same broadcast channel (e.g., a wireless network), want to generate a common secret bitstream, in the presence of an adversary Eve, who tries to obtain information on the bitstream. We assume that the nodes initially share a (small) piece of information, but do not have access to any out-of-band channel. We ask the question: can this problem be solved without relying on Eve's computational limitations, i.e., without using any form of public-key cryptography? We propose a secret-agreement protocol, where the n nodes of the group keep exchanging bits until they have all agreed on a bit sequence that Eve cannot reconstruct with very high probability. In this task, the nodes are assisted by a small number of interferers, whose role is to create channel noise in a way that bounds the amount of information Eve can overhear. Our protocol has polynomial-time complexity and requires no changes to the physical or MAC layer of network devices. First, we formally show that, under standard theoretical assumptions, our protocol is information-theoretically secure, achieves optimal secret-generation rate for n = 2 nodes, and scales well to an arbitrary number of nodes. Second, we adapt our protocol to a small wireless 14-square-meter testbed; we experimentally show that, if Eve uses a standard wireless physical layer and is not too close to any of the nodes, 8 nodes can achieve a secret-generation rate of 38 Kbps. To the best of our knowledge, ours is the first experimental demonstration of information-theoretic secret exchange on a wireless network at a rate beyond a few tens of bits per second.
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 β 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/β 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≥ (42.8) ⋅ (1/$\beta)\sp{2.71}$(n + 0.07), then the capacity of a source in which each team player receives βd cards is at least 2$\sp{n}$. (Abstract shortened by UMI.)