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

A Secure Vector Space Secret Sharing Scheme

Chunxiao Xu

Published Jan 1, 2002• 8 citations
OpenAlex

Abstract

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.

Related papers

Construction of Cheating Immune Secret Sharing

Jie Zhang

Cheating immune secret sharing in the unconditionally secure case was investigated. Secret sharing is a k-cheating immune if any k cheaters are not better off than a participant which follows the protocol honestly. k-cheating immune secret sharing scheme under the unconditionally secure would be given. The obtained function of the secret sharing scheme is k-resilient and satisfies k-strengthened propagation criterion. Furthermore, its degree is high. So it has better cryptographic properties than that of the known results.

Beijing Youdian Xueyuan xuebao•Jan 1, 2005•0 citations

The Detection of Cheaters in Thershold Schemes

Ernest F. Brickell, Douglas R. Stinson

Informally, a $( t,w )$-threshold scheme is a way of distributing partial information (shadows) to w participants, so that any t of them can easily calculate a key (or secret), but no subset of fewer than t participants can determine the key. Presented in this paper is an unconditionally secure threshold scheme in which any cheating participant can be detected and identified with high probability by any honest participant, even if the cheater is in coalition with other participants. Also given is a construction that will detect with high probability a dealer who distributes inconsistent shadows (shares) to the honest participants. The scheme is not perfect; a set of $t - 1$ participants can rule out at most $1 + \begin{pmatrix} {w - t + 1} \\ {t - 1} \end{pmatrix}$ possible keys, given the information they have. In this scheme, the key will be an element of GF$( q )$ for some prime power q. Hence q can be chosen large enough so that the amount of information obtained by any $t - 1$ participants is negligible.

SIAM Journal on Discrete Mathematics•Nov 1, 1991•43 citations

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

Mitsugu Iwamoto, H. Yamamoto, Hiroki Koga

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.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2009•3 citations

On Cheating Immune Secret Sharing

Josef Pieprzyk, Xian-Mo Zhang

The paper addresses the cheating prevention in secret sharing. We consider secret sharing with binary shares. The secret also is binary. This model allows us to use results and constructions from the well developed theory of cryptographically strong boolean functions. In particular, we prove that for given secret sharing, the average cheating probability over all cheating vectors and all original vectors, i.e., 1/n 2^n ∑ _c=1...n ∑ _α ∈V n ρ _c,α , denoted by øverlineρ , satisfies øverlineρ ≥ \frac12 , and the equality holds if and only if ρ _c,α satisfies ρ _c,α = \frac12 for every cheating vector δ _c and every original vector α . In this case the secret sharing is said to be cheating immune. We further establish a relationship between cheating-immune secret sharing and cryptographic criteria of boolean functions.This enables us to construct cheating-immune secret sharing.

Discrete Mathematics & Theoretical Computer Science•Jan 1, 2004•16 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
Cheating immune secret sharing in the unconditionally secure case was investigated. Secret sharing is a k-cheating immune if any k cheaters are not better off than a participant which follows the protocol honestly. k-cheating immune secret sharing scheme under the unconditionally secure would be given. The obtained function of the secret sharing scheme is k-resilient and satisfies k-strengthened propagation criterion. Furthermore, its degree is high. So it has better cryptographic properties than that of the known results.
Informally, a (t,w)( t,w )(t,w)-threshold scheme is a way of distributing partial information (shadows) to w participants, so that any t of them can easily calculate a key (or secret), but no subset of fewer than t participants can determine the key. Presented in this paper is an unconditionally secure threshold scheme in which any cheating participant can be detected and identified with high probability by any honest participant, even if the cheater is in coalition with other participants. Also given is a construction that will detect with high probability a dealer who distributes inconsistent shadows (shares) to the honest participants. The scheme is not perfect; a set of t−1t - 1t−1 participants can rule out at most 1+(w−t+1t−1)1 + \begin{pmatrix} {w - t + 1} \\ {t - 1} \end{pmatrix}1+(w−t+1t−1​) possible keys, given the information they have. In this scheme, the key will be an element of GF(q)( q )(q) for some prime power q. Hence q can be chosen large enough so that the amount of information obtained by any t−1t - 1t−1 participants is negligible.
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.
The paper addresses the cheating prevention in secret sharing. We consider secret sharing with binary shares. The secret also is binary. This model allows us to use results and constructions from the well developed theory of cryptographically strong boolean functions. In particular, we prove that for given secret sharing, the average cheating probability over all cheating vectors and all original vectors, i.e., 1/n 2^n ∑ _c=1...n ∑ _α ∈V n ρ _c,α , denoted by øverlineρ , satisfies øverlineρ ≥ \frac12 , and the equality holds if and only if ρ _c,α satisfies ρ _c,α = \frac12 for every cheating vector δ _c and every original vector α . In this case the secret sharing is said to be cheating immune. We further establish a relationship between cheating-immune secret sharing and cryptographic criteria of boolean functions.This enables us to construct cheating-immune secret sharing.
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).