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

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

Published May 1, 2001• 0 citations
OpenAlex

Abstract

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.

Related papers

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

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

Sharing secret keys along a Eulerian circuit

Takaaki Mizuki, Hiroki Shizuya, Takao Nishizeki

A method for sharing secret keys that is information-theoretically secure is an important problem in the area of cryptography. By randomly distributing cards to players, it is possible to provide random information with which information-theoretically secure secret keys can be shared by players. This paper formulates sharing secret keys along a Eulerian circuit for information transmission for which the receipt can be confirmed and provides a protocol for its realization. The conditions for the success of the protocol for sharing secret keys along a Eulerian circuit are identified. Further, under the natural assumption that the same numbers of cards are distributed to each player, it is shown that the number of cards distributed is a minimum. © 1999 Scripta Technica, Electron Comm Jpn Pt 3, 83(4): 33–42, 2000

Electronics and Communications in Japan (Part III Fundamental Electronic Science)•Apr 1, 2000•0 citations

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

Necessary and Sufficient Numbers of Cards for Sharing Secret Keys on Hierarchical Groups

Takaaki Mizuki, Takao Nishizeki

Lecture notes in computer science•Jan 1, 2001•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
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.
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 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.
A method for sharing secret keys that is information-theoretically secure is an important problem in the area of cryptography. By randomly distributing cards to players, it is possible to provide random information with which information-theoretically secure secret keys can be shared by players. This paper formulates sharing secret keys along a Eulerian circuit for information transmission for which the receipt can be confirmed and provides a protocol for its realization. The conditions for the success of the protocol for sharing secret keys along a Eulerian circuit are identified. Further, under the natural assumption that the same numbers of cards are distributed to each player, it is shown that the number of cards distributed is a minimum. © 1999 Scripta Technica, Electron Comm Jpn Pt 3, 83(4): 33–42, 2000
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 ...
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.