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

Electronics and Communications in Japan (Part III Fundamental Electronic Science)

Sharing secret keys along a Eulerian circuit

Takaaki Mizuki, Hiroki Shizuya, Takao Nishizeki

Published Apr 1, 2000• 0 citations
Publisher

Abstract

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

DOI
10.1002/(sici)1520-6440(200004)83:4<33::aid-ecjc4>3.0.co;2-d

Related papers

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

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

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

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

A single shuffle is enough for secure card-based computation of any Boolean circuit

Kazumasa Shinagawa, Koji Nuida

Secure computation enables a number of players each holding a secret input value to compute a function of the inputs without revealing the inputs. It is known that secure computation is possible physically when the inputs are given as a sequence of physical cards. This research area is called card-based cryptography. One of the important problems in card-based cryptography is to minimize the number of cards and shuffles, where a shuffle is the most important (and somewhat heavy) operation in card-based protocols. In this paper, we determine the minimum number of shuffles for achieving general secure computation. Somewhat surprisingly, the answer is just one, i.e., we design a protocol which securely computes any Boolean circuit with only a single shuffle. The number of cards required for our protocol is proportional to the size of the circuit to be computed.

Discrete Applied Mathematics•Nov 2, 2020•42 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
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 ...
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.
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.
Secure computation enables a number of players each holding a secret input value to compute a function of the inputs without revealing the inputs. It is known that secure computation is possible physically when the inputs are given as a sequence of physical cards. This research area is called card-based cryptography. One of the important problems in card-based cryptography is to minimize the number of cards and shuffles, where a shuffle is the most important (and somewhat heavy) operation in card-based protocols. In this paper, we determine the minimum number of shuffles for achieving general secure computation. Somewhat surprisingly, the answer is just one, i.e., we design a protocol which securely computes any Boolean circuit with only a single shuffle. The number of cards required for our protocol is proportional to the size of the circuit to be computed.
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)