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 Transactions on Information Theory

General Error Decodable Secret Sharing Scheme and Its Application

Kaoru Kurosawa

Published Sep 1, 2011• 8 citations
Publisher

Abstract

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

DOI
10.1109/tit.2011.2161927

Related papers

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

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

Round-Efficient Perfectly Secure Message Transmission Scheme Against General Adversary.

Kaoru Kurosawa

In the model of Perfectly Secure Message Transmission Schemes (PSMTs), there are n channels between a sender and a receiver, and they share no key. An infinitely powerful adversary A can corrupt (observe and forge) the messages sent through some subset of n channels. For non-threshold adversaries called Q 2, Kumar et al. showed a many round PSMT (Ashwin Kumar et al. On perfectly secure communication over arbitrary networks. PODC 2002, pp. 193---202, 2002). In this paper, we show round efficient PSMTs against Q 2-adevrsaries. We first give a 3-round PSMT which runs in polynomial time in the size of the underlying linear secret sharing scheme. We next present a 2-round PSMT which is inefficient in general. (However, it is efficient for some special case.)

•Jan 1, 2010•3 citations

Ideal and perfect multi-secret sharing schemes whose access structure are Q 3

Lv yingli, Xiaojun Xu, Zhang Xiao-feng +1 more

The characterization of access structure is one of the main open problems in secret sharing schemes. We are particularly interested in determining which Q 3 access structures can be realized and the requirement should be achieved even in the presence of an adversary who is able to corrupt some players in an ideal secret sharing scheme. The problems are studied in our paper. Above all, we present a concrete scheme that can meet all above requirements. In our scheme, it is not only a dynamic multi-secret and multi-use sharing protocol, but participants from access structure can recover the secret using their shares, while the same number of participants from adversary structure can't recover the secret using their shares, which is different from general access structure schemes. Moreover, in the whole dynamic process, the coefficients of polynomial and private secret shares always stay the same. Therefore, it enjoys high practical value.

•Aug 1, 2012•0 citations

Unconditionally-secure ideal robust secret sharing schemes for threshold and multilevel access structure

Mahabir Prasad Jhanwar, Reihaneh Safavi–Naini

Abstract. An n -player -secure robust secret sharing scheme is a ( t , n )-threshold secret sharing scheme with the additional property that the secret can be recovered, with probability at least , from the set of all shares even if up to t players provide incorrect shares. The existing constructions of robust secret sharing schemes for the range have the share size larger than the secret size. An important goal in this area is to minimize the share size. In the paper, we propose a new unconditionally-secure robust secret sharing scheme for the case with share size equal to the secret size. This is the minimum possible size as dictated by the perfect secrecy of the scheme. We further extend our scheme to realize a class of multilevel access structures that satisfy a special condition. The property that the share size is equal to secret size is preserved in the extended scheme. The proposed scheme is the first known robust secret sharing scheme realizing multilevel access structure.

Journal of Mathematical Cryptology•Oct 8, 2013•2 citations

Computational Quantum Secret Sharing

Alper Çakan, Vipul Goyal, Chen-Da Liu-Zhang +1 more

Quantum secret sharing (QSS) allows a dealer to distribute a secret quantum state among a set of parties in such a way that certain authorized subsets can reconstruct the secret, while unauthorized subsets obtain no information about it. Previous works on QSS for general access structures focused solely on the existence of perfectly secure schemes, and the share size of the known schemes is necessarily exponential even in cases where the access structure is computed by polynomial size monotone circuits. This stands in stark contrast to the classical setting, where polynomial-time computationally-secure secret sharing schemes have been long known for all access structures computed by polynomial-size monotone circuits under standard hardness assumptions, and one can even obtain shares which are much shorter than the secret (which is impossible with perfect security). While QSS was introduced over twenty years ago, previous works only considered information-theoretic privacy. In this work, we initiate the study of computationally-secure QSS and show that computational assumptions help significantly in building QSS schemes, just as in the classical case. We present a simple compiler and use it to obtain a large variety results: We construct polynomial-time computationally-secure QSS schemes under standard hardness assumptions for a rich class of access structures. This includes many access structures for which previous results in QSS necessarily required exponential share size. In fact, we can go even further: We construct QSS schemes for which the size of the quantum shares is significantly smaller than the size of the secret. As in the classical setting, this is impossible with perfect security. We also apply our compiler to obtain results beyond computational QSS. In the information-theoretic setting, we improve the share size of perfect QSS schemes for a large class of n-party access structures to 1.5^{n+o(n)}, improving upon best known schemes and matching the best known result for general access structures in the classical setting. Finally, among other things, we study the class of access structures which can be efficiently implemented when the quantum secret sharing scheme has access to a given number of copies of the secret, including all such functions in 𝖯 and NP.

Leibniz international proceedings in informatics•Jan 1, 2023•0 citations
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).
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.
In the model of Perfectly Secure Message Transmission Schemes (PSMTs), there are n channels between a sender and a receiver, and they share no key. An infinitely powerful adversary A can corrupt (observe and forge) the messages sent through some subset of n channels. For non-threshold adversaries called Q 2, Kumar et al. showed a many round PSMT (Ashwin Kumar et al. On perfectly secure communication over arbitrary networks. PODC 2002, pp. 193---202, 2002). In this paper, we show round efficient PSMTs against Q 2-adevrsaries. We first give a 3-round PSMT which runs in polynomial time in the size of the underlying linear secret sharing scheme. We next present a 2-round PSMT which is inefficient in general. (However, it is efficient for some special case.)
The characterization of access structure is one of the main open problems in secret sharing schemes. We are particularly interested in determining which Q 3 access structures can be realized and the requirement should be achieved even in the presence of an adversary who is able to corrupt some players in an ideal secret sharing scheme. The problems are studied in our paper. Above all, we present a concrete scheme that can meet all above requirements. In our scheme, it is not only a dynamic multi-secret and multi-use sharing protocol, but participants from access structure can recover the secret using their shares, while the same number of participants from adversary structure can't recover the secret using their shares, which is different from general access structure schemes. Moreover, in the whole dynamic process, the coefficients of polynomial and private secret shares always stay the same. Therefore, it enjoys high practical value.
Abstract. An n -player -secure robust secret sharing scheme is a ( t , n )-threshold secret sharing scheme with the additional property that the secret can be recovered, with probability at least , from the set of all shares even if up to t players provide incorrect shares. The existing constructions of robust secret sharing schemes for the range have the share size larger than the secret size. An important goal in this area is to minimize the share size. In the paper, we propose a new unconditionally-secure robust secret sharing scheme for the case with share size equal to the secret size. This is the minimum possible size as dictated by the perfect secrecy of the scheme. We further extend our scheme to realize a class of multilevel access structures that satisfy a special condition. The property that the share size is equal to secret size is preserved in the extended scheme. The proposed scheme is the first known robust secret sharing scheme realizing multilevel access structure.
Quantum secret sharing (QSS) allows a dealer to distribute a secret quantum state among a set of parties in such a way that certain authorized subsets can reconstruct the secret, while unauthorized subsets obtain no information about it. Previous works on QSS for general access structures focused solely on the existence of perfectly secure schemes, and the share size of the known schemes is necessarily exponential even in cases where the access structure is computed by polynomial size monotone circuits. This stands in stark contrast to the classical setting, where polynomial-time computationally-secure secret sharing schemes have been long known for all access structures computed by polynomial-size monotone circuits under standard hardness assumptions, and one can even obtain shares which are much shorter than the secret (which is impossible with perfect security). While QSS was introduced over twenty years ago, previous works only considered information-theoretic privacy. In this work, we initiate the study of computationally-secure QSS and show that computational assumptions help significantly in building QSS schemes, just as in the classical case. We present a simple compiler and use it to obtain a large variety results: We construct polynomial-time computationally-secure QSS schemes under standard hardness assumptions for a rich class of access structures. This includes many access structures for which previous results in QSS necessarily required exponential share size. In fact, we can go even further: We construct QSS schemes for which the size of the quantum shares is significantly smaller than the size of the secret. As in the classical setting, this is impossible with perfect security. We also apply our compiler to obtain results beyond computational QSS. In the information-theoretic setting, we improve the share size of perfect QSS schemes for a large class of n-party access structures to 1.5^{n+o(n)}, improving upon best known schemes and matching the best known result for general access structures in the classical setting. Finally, among other things, we study the class of access structures which can be efficiently implemented when the quantum secret sharing scheme has access to a given number of copies of the secret, including all such functions in 𝖯 and NP.