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 simple secret sharing scheme using a key and its security against substitution of shares

Hiroki Koga

Published Jun 1, 2010• 1 citation
Publisher

Abstract

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.

DOI
10.1109/isit.2010.5513434

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

Analysis of a kind of quantum cryptographic schemes based on secret sharing

Zhang Xing

Recently, Yang et al. proposed a kind of quantum cryptographic schemes based on secret sharing. The main idea is drawn from the case, where any n participants who share a secret K can co-operate as K does. This process can be applied to encryption, authentication, signature and so on. Unfortunately, since there is no identity authentication of the share’s holder, these schemes inherit the limitation of secret sharing in practice. If some participants do not follow the protocol, the protocol would be a failure at last. Moreover, these schemes encounter another serious attack. Any two participants can co-operate to defeat the schemes by sending different shares to the parties unknown to the distributor of the secret K, such that these parties can execute the protocol as well. The attack proves that it is not enough for quantum cryptographic schemes that only the secret key is secure.

Science in China. Series G, Physics, mechanics & astronomy/Science in China. Series G, Physics, Mechanics & Astronomy•Jan 1, 2009•0 citations

Collusion-Secure Semi-Quantum Secret Sharing Scheme using a Quantum Third Party

Santanu Majhi, Nirupam Basak

The security of a secret sharing protocol is compromised if one or more dishonest participants can reconstruct the secret by deviating from the prescribed protocol, particularly when such malicious behavior remains undetected. Semi-Quantum Secret Sharing (SQSS) is a variant of secret sharing in which the participants possess only classical capabilities, such as preparing and measuring qubits in the computational ($Z$) basis, while a quantum-capable third party assists the dealer in generating and distributing quantum shares of a classical secret. The limited quantum capabilities of the participants in SQSS protocols may introduce vulnerabilities to collusion attacks, enabling an assisting quantum third party, in collaboration with a dishonest classical participant, to jointly recover the secret even without detection. In this work, we propose a novel SQSS protocol that eliminates this vulnerability and achieves information-theoretic security against collusion attacks. We further prove that the proposed protocol is secure against a broad class of external and internal attacks. Finally, a comparative analysis demonstrates that our construction advances existing SQSS protocols by simultaneously optimizing qubit efficiency, involves a classical dealer, and resilience against DCNA attacks using basic Bell states.

cs.CRCross-listedarXiv:2610.10176•Oct 8, 2026•0 citations

New bounds on the information rate of secret sharing schemes

Carlo Blundo, Alfredo De Santis, Antonio Giorgio Gaggia +1 more

/spl acute/A secret sharing scheme permits a secret to be shared among participants in such a way that only qualified subsets of participants can recover the secret, but any nonqualified subset has absolutely no information on the secret. We derive new limitations on the information rate of secret sharing schemes, that measures how much information is being distributed as shares as compared to the size of the secret key, and the average information rate, that is the ratio between the secret size and the arithmetic mean of the size of the shares. By applying the substitution technique, we are able to construct many new examples of access structures where the information rate is bounded away from 1. The substitution technique is a method used to obtain a new access structure by replacing a participant in a previous structure with a new access structure.>

IEEE Transactions on Information Theory•Mar 1, 1995•30 citations

On Secret Reconstruction in Secret Sharing Schemes

Huaxiong Wang, Duncan S. Wong

A secret sharing scheme typically requires secure communications in each of two distribution phases: (1) a dealer distributes shares to participants (share distribution phase); and later (2) the participants in some authorised subset send their share information to a combiner (secret reconstruction phase). While problems on storage required for participants, for example, the size of shares, have been well studied, problems regarding the communication complexity of the two distribution phases seem to have been mostly neglected in the literature so far. In this correspondence, we deal with several communication related problems in the secret reconstruction phase. Firstly, we show that there is a tradeoff between the communication costs and the number of participants involved in the secret reconstruction. We introduce the communication rate as the ratio of the secret size and the total number of communication bits transmitted from the participants to the combiner in the secret reconstruction phase. We derive a lower bound on the communication rate and give constructions that meet the bound. Secondly, we show that the point-to-point secure communication channels for participants to send share information to the combiner can be replaced with partial broadcast channels. We formulate partial broadcast channels as set systems and show that they are equivalent to the well-known combinatorial objects of cover-free family. Surprisingly, we find that the number of partial broadcast channels can be significantly reduced from the number of point-to-point secure channels. Precisely, in its optimal form, the number of channels can be reduced from n to O(log n), where is the number of participants in a secret sharing scheme. We also study the communication rates of partial broadcast channels for the secret reconstruction.

IEEE Transactions on Information Theory•Jan 1, 2008•53 citations
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.
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).
Recently, Yang et al. proposed a kind of quantum cryptographic schemes based on secret sharing. The main idea is drawn from the case, where any n participants who share a secret K can co-operate as K does. This process can be applied to encryption, authentication, signature and so on. Unfortunately, since there is no identity authentication of the share’s holder, these schemes inherit the limitation of secret sharing in practice. If some participants do not follow the protocol, the protocol would be a failure at last. Moreover, these schemes encounter another serious attack. Any two participants can co-operate to defeat the schemes by sending different shares to the parties unknown to the distributor of the secret K, such that these parties can execute the protocol as well. The attack proves that it is not enough for quantum cryptographic schemes that only the secret key is secure.
The security of a secret sharing protocol is compromised if one or more dishonest participants can reconstruct the secret by deviating from the prescribed protocol, particularly when such malicious behavior remains undetected. Semi-Quantum Secret Sharing (SQSS) is a variant of secret sharing in which the participants possess only classical capabilities, such as preparing and measuring qubits in the computational (ZZZ) basis, while a quantum-capable third party assists the dealer in generating and distributing quantum shares of a classical secret. The limited quantum capabilities of the participants in SQSS protocols may introduce vulnerabilities to collusion attacks, enabling an assisting quantum third party, in collaboration with a dishonest classical participant, to jointly recover the secret even without detection. In this work, we propose a novel SQSS protocol that eliminates this vulnerability and achieves information-theoretic security against collusion attacks. We further prove that the proposed protocol is secure against a broad class of external and internal attacks. Finally, a comparative analysis demonstrates that our construction advances existing SQSS protocols by simultaneously optimizing qubit efficiency, involves a classical dealer, and resilience against DCNA attacks using basic Bell states.
/spl acute/A secret sharing scheme permits a secret to be shared among participants in such a way that only qualified subsets of participants can recover the secret, but any nonqualified subset has absolutely no information on the secret. We derive new limitations on the information rate of secret sharing schemes, that measures how much information is being distributed as shares as compared to the size of the secret key, and the average information rate, that is the ratio between the secret size and the arithmetic mean of the size of the shares. By applying the substitution technique, we are able to construct many new examples of access structures where the information rate is bounded away from 1. The substitution technique is a method used to obtain a new access structure by replacing a participant in a previous structure with a new access structure.>
A secret sharing scheme typically requires secure communications in each of two distribution phases: (1) a dealer distributes shares to participants (share distribution phase); and later (2) the participants in some authorised subset send their share information to a combiner (secret reconstruction phase). While problems on storage required for participants, for example, the size of shares, have been well studied, problems regarding the communication complexity of the two distribution phases seem to have been mostly neglected in the literature so far. In this correspondence, we deal with several communication related problems in the secret reconstruction phase. Firstly, we show that there is a tradeoff between the communication costs and the number of participants involved in the secret reconstruction. We introduce the communication rate as the ratio of the secret size and the total number of communication bits transmitted from the participants to the combiner in the secret reconstruction phase. We derive a lower bound on the communication rate and give constructions that meet the bound. Secondly, we show that the point-to-point secure communication channels for participants to send share information to the combiner can be replaced with partial broadcast channels. We formulate partial broadcast channels as set systems and show that they are equivalent to the well-known combinatorial objects of cover-free family. Surprisingly, we find that the number of partial broadcast channels can be significantly reduced from the number of point-to-point secure channels. Precisely, in its optimal form, the number of channels can be reduced from n to O(log n), where is the number of participants in a secret sharing scheme. We also study the communication rates of partial broadcast channels for the secret reconstruction.