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

IEEE International Symposium on Information Theory (ISIT)

A coding theorem for cheating-detectable (2, 2)-threshold blockwise secret sharing schemes

Mitsugu Iwamoto, H. Yamamoto, Hiroki Koga

Published Jun 1, 2009• 3 citations
Publisher

Abstract

It is known that a secret sharing scheme (SSS) with perfect cheating detection cannot be realized because such a SSS requires infinite share rates. However, this impossibility comes from the fact that block coding is not used and any decoding error is not allowed in the SSS. Hence, in this paper, we consider a SSS constructed by block coding with an arbitrarily small decoding error probability. It is shown that the perfect cheating detection with finite rates is possible for the 2-out-of-2 SSS in a certain asymptotic sense. Furthermore, the supremum of the achievable exponent in the maximum success probability of impersonation attack turns out to be the mutual information between the two shares.

DOI
10.1109/isit.2009.5205941

Related papers

A Secure Vector Space Secret Sharing Scheme

Chunxiao Xu

A secure vector space secret sharing scheme with the secret k∈GF(q) is presented.This scheme can detect the cheaters more effectively,with the probability of cheating 1/ q 2 and asymptotically optimal information rate 1/3.Meanwhile,a robust threshold scheme is studied and the expression of its probability of cheating is given.

•Jan 1, 2002•8 citations

Error Decodable Secret Sharing and One-Round Perfectly Secure Message Transmission for General Adversary Structures.

Keith M. Martin, Maura B. Paterson, Douglas R. Stinson

An error decodable secret-sharing scheme is a secret-sharing scheme with the additional property that the secret can be recovered from the set of all shares, even after a coalition of participants corrupts the shares they possess. In this paper, schemes that can tolerate corruption by sets of participants belonging to a monotone coalition structure are considered. This coalition structure may be unrelated to the authorised sets of the secret-sharing scheme. This is generalisation of both a related notion studied in the context of multiparty computation, and the well-known error-correction properties of threshold schemes based on Reed-Solomon codes. Necessary and sufficient conditions for the existence of such schemes are deduced, and methods for reducing the storage requirements of a technique of Kurosawa for constructing error-decodable secret-sharing schemes with efficient decoding algorithms are demonstrated. In addition, the connection between one-round perfectly secure message transmission (PSMT) schemes with general adversary structures and secret-sharing schemes is explored. We prove a theorem that explicitly shows the relation between these structures. In particular, an error decodable secret-sharing scheme yields a one-round PSMT, but the converse does not hold. Furthermore, we are able to show that some well-known results concerning one-round PSMT follow from known results on secret-sharing schemes. These connections are exploited to investigate factors affecting the performance of one-round PSMT schemes such as the number of channels required, the communication overhead, and the efficiency of message recovery.

•Jan 1, 2009•0 citations

General Error Decodable Secret Sharing Scheme and Its Application

Kaoru Kurosawa

Consider a model of secret sharing schemes with cheaters. We say that a secret sharing scheme is error decodable if we can still recover the secretscorrectly from a noisy share vector (share1', ..., sharen'). In this paper, we first prove that a perfect secret sharing scheme is error decodable if and only if the adversary structure Γ satisfies a certain condition calledQ3. Next, for such Γ , we show a scheme such that the decoding algorithm runs in polynomial-time in |S| and the size of a linear secret sharing scheme which realizes Γ. We finally show an application to 1-round perfectly secure message transmission schemes (PSMT).

IEEE Transactions on Information Theory•Sep 1, 2011•8 citations

General Error Decodable Secret Sharing Scheme and Its Application.

Kaoru Kurosawa

Consider a model of secret sharing schemes with cheaters. We say that a secret sharing scheme is error decodable if we can still recover the secret s correctly from a noisy share vector (share1', ..., sharen'). In this paper, we first prove that a perfect secret sharing scheme is error decodable if and only if the adversary structure Γ satisfies a certain condition called Q3. Next, for such Γ , we show a scheme such that the decoding algorithm runs in polynomial-time in |S | and the size of a linear secret sharing scheme which realizes Γ. We finally show an application to 1-round perfectly secure message transmission schemes (PSMT).

•Jan 1, 2009•8 citations

Coding Theorems on the Threshold Scheme for a General Source

Hiroki Koga

In this paper, coding theorems on the (t, m) -threshold scheme for a general source are discussed, where m means the number of the shares and t means a threshold. The (t,m) -threshold scheme treated in this paper encrypts n source outputs Xnto m shares at once and is required to satisfy the two conditions that 1) Xnis reproduced from arbitrary t shares, and 2) almost no information of Xnis revealed from any t - 1 shares. It is shown that the (t,m) -threshold scheme must satisfy certain inequalities including the limit inferiors in probability. One of the inequalities is closely related to the minimum length of the fair random bits needed to a dealer for realizing the (t, m) -threshold scheme. In addition, it is shown that a certain variation of Shamir's threshold scheme meets the two conditions. The same approach can be taken to the problems of Shannon's cipher system with the perfect secrecy and fixed-length source coding with vanishing decoding error probability. It is shown that the same kind of inequalities, which indicate the converse coding theorems, hold in both two cases.

IEEE Transactions on Information Theory•May 29, 2008•9 citations

A simple secret sharing scheme using a key and its security against substitution of shares

Hiroki Koga

Secret sharing schemes which are secure under the presence of malicious participants who forge their shares have been investigated by many researchers so far. In this paper we consider a secret sharing scheme with a key at an encoder and a decoder and analyze its security against the substitution attack by malicious participants. We first give conditions that the secret sharing scheme with a key must satisfy. Next, we construct a simple secret sharing scheme with a key that generates n shares and detects forged shares with high probability. We can prove that, if at most n - 1 malicious participants collude and try to deceive the other participants by forged shares optimally, the success probability of such an attack is upper-bounded by |S|-1/|X|-1, where |S| and |X| denote the sizes of the secret and the n shares, respectively. In addition, we investigate basic properties of the scheme especially for the case of n = 2.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•1 citation
It is known that a secret sharing scheme (SSS) with perfect cheating detection cannot be realized because such a SSS requires infinite share rates. However, this impossibility comes from the fact that block coding is not used and any decoding error is not allowed in the SSS. Hence, in this paper, we consider a SSS constructed by block coding with an arbitrarily small decoding error probability. It is shown that the perfect cheating detection with finite rates is possible for the 2-out-of-2 SSS in a certain asymptotic sense. Furthermore, the supremum of the achievable exponent in the maximum success probability of impersonation attack turns out to be the mutual information between the two shares.
An error decodable secret-sharing scheme is a secret-sharing scheme with the additional property that the secret can be recovered from the set of all shares, even after a coalition of participants corrupts the shares they possess. In this paper, schemes that can tolerate corruption by sets of participants belonging to a monotone coalition structure are considered. This coalition structure may be unrelated to the authorised sets of the secret-sharing scheme. This is generalisation of both a related notion studied in the context of multiparty computation, and the well-known error-correction properties of threshold schemes based on Reed-Solomon codes. Necessary and sufficient conditions for the existence of such schemes are deduced, and methods for reducing the storage requirements of a technique of Kurosawa for constructing error-decodable secret-sharing schemes with efficient decoding algorithms are demonstrated. In addition, the connection between one-round perfectly secure message transmission (PSMT) schemes with general adversary structures and secret-sharing schemes is explored. We prove a theorem that explicitly shows the relation between these structures. In particular, an error decodable secret-sharing scheme yields a one-round PSMT, but the converse does not hold. Furthermore, we are able to show that some well-known results concerning one-round PSMT follow from known results on secret-sharing schemes. These connections are exploited to investigate factors affecting the performance of one-round PSMT schemes such as the number of channels required, the communication overhead, and the efficiency of message recovery.
Consider a model of secret sharing schemes with cheaters. We say that a secret sharing scheme is error decodable if we can still recover the secretscorrectly from a noisy share vector (share1', ..., sharen'). In this paper, we first prove that a perfect secret sharing scheme is error decodable if and only if the adversary structure Γ satisfies a certain condition calledQ3. Next, for such Γ , we show a scheme such that the decoding algorithm runs in polynomial-time in |S| and the size of a linear secret sharing scheme which realizes Γ. We finally show an application to 1-round perfectly secure message transmission schemes (PSMT).
Consider a model of secret sharing schemes with cheaters. We say that a secret sharing scheme is error decodable if we can still recover the secret s correctly from a noisy share vector (share1', ..., sharen'). In this paper, we first prove that a perfect secret sharing scheme is error decodable if and only if the adversary structure Γ satisfies a certain condition called Q3. Next, for such Γ , we show a scheme such that the decoding algorithm runs in polynomial-time in |S | and the size of a linear secret sharing scheme which realizes Γ. We finally show an application to 1-round perfectly secure message transmission schemes (PSMT).
In this paper, coding theorems on the (t, m) -threshold scheme for a general source are discussed, where m means the number of the shares and t means a threshold. The (t,m) -threshold scheme treated in this paper encrypts n source outputs Xnto m shares at once and is required to satisfy the two conditions that 1) Xnis reproduced from arbitrary t shares, and 2) almost no information of Xnis revealed from any t - 1 shares. It is shown that the (t,m) -threshold scheme must satisfy certain inequalities including the limit inferiors in probability. One of the inequalities is closely related to the minimum length of the fair random bits needed to a dealer for realizing the (t, m) -threshold scheme. In addition, it is shown that a certain variation of Shamir's threshold scheme meets the two conditions. The same approach can be taken to the problems of Shannon's cipher system with the perfect secrecy and fixed-length source coding with vanishing decoding error probability. It is shown that the same kind of inequalities, which indicate the converse coding theorems, hold in both two cases.
Secret sharing schemes which are secure under the presence of malicious participants who forge their shares have been investigated by many researchers so far. In this paper we consider a secret sharing scheme with a key at an encoder and a decoder and analyze its security against the substitution attack by malicious participants. We first give conditions that the secret sharing scheme with a key must satisfy. Next, we construct a simple secret sharing scheme with a key that generates n shares and detects forged shares with high probability. We can prove that, if at most n - 1 malicious participants collude and try to deceive the other participants by forged shares optimally, the success probability of such an attack is upper-bounded by |S|-1/|X|-1, where |S| and |X| denote the sizes of the secret and the n shares, respectively. In addition, we investigate basic properties of the scheme especially for the case of n = 2.