© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Rational secret sharing

Yun Zhang

Published Jan 1, 2012• 0 citations

Abstract

The set of all real numbers Z -The set of all integers F -A finite field GF(q) -The finite field with q elements P i -The i th player n -The number of players P -The set contains n players P 1 , . . ., P n 2 P -The power set of P |A| -The size of the set A s -A secret in secret sharing schemes R -The domain of random strings S -The domain of the secrets in secret sharing schemesS i -The share domain of P i -The operation of bitwise XOR α, β -The inner product of α and β α[i] -The i th coordinate of α D -The dealer in secret sharing schemes Π -A secret sharing scheme Π(s, r) i -The share of P i generated with the secret s and a random string r in the secret sharing scheme Π Π(s, r) A -The shares of players in A generated with the secret s and a random string r in the secret sharing scheme Π A -An adversary structure Γ -An access structure A ⊥ -The dual adversary structure of A Γ ⊥ -The dual access structure of Γ M -A monotone span program M ⊥ -A dual monotone span program of M LSSS -Linear secret sharing scheme RSSS -Rational secret sharing scheme MSP -Monotone span program MPC -Multiparty computation C -A block code C ⊥ -The dual code of C Γ(C) -The admissible distance of a block code C ∆(C) -The forbidden distance of a block code C rank(M ) -The rank of a matrix M span(M ) -The vector space spanned by the row vectors in M M T -The transpose of the matrix M ker(M ) -The solution space of the linear equation system M • X = 0 (α|M ) -The matrix containing the columns of M along with an additional column α (a, β) -The vector containing the elements of β along with an additional element a t -The size of each minimal authorized set in a threshold access structure t * -The size of active players in the secret reconstruction process k -A security parameter G -A game

DOI: 10.32657/10356/48667

Related papers

Cutting-Edge Cryptography Through the Lens of Secret Sharing

Ilan Komargodski, Mark Zhandry

Secret sharing is a mechanism by which a trusted dealer holding a secret “splits ” the secret into many “shares ” and distributes the shares to a collection of parties. Associated with the sharing is a monotone access structure, that specifies which parties are “qualified ” and which are not: any qualified subset of parties can (efficiently) reconstruct the secret, but no unqualified subset can learn anything about the secret. In the most general form of secret sharing, the access structure can be any monotone NP language. In this work, we consider two very natural extensions of secret sharing. In the first, which we call distributed secret sharing, there is no trusted dealer at all, and instead the role of the dealer is distributed amongst the parties themselves. Distributed secret sharing can be thought of as combining the features of multiparty non-interactive key exchange and standard secret sharing, and may be useful in settings where the secret is so sensitive that no one individual dealer can be trusted with the secret. Our second notion is called functional secret sharing, which incorporates some of the features of functional encryption into secret sharing by providing more fine-grained access to the secret. Qualified subsets of parties do not learn the secret, but instead

•Feb 16, 2016•0 citations

Not all perfect extrinsic secret sharing schemes are ideal.

W. D. Wallis

Abstract. We construct a perfect extrinsic secret sharing scheme for any case in which a set of participants can gain access to the secret if and only if the set contains a pair of members from some given list of pairs. A secret sharing scheme is a way by which a dealer rnay distribute secret information to individuals (call participants). There is associated '-<U.lh'.lcH"""F- of subsets of a set of can if they constitute a member of the access structure. usual to demand that the access structure be monotone: If A contains a subset which to the structure, then A itself must also belong to the structure. A secret scheme is called perfect if a set of pa.rticipants can no information by their shares unless the set is member of the access structure. An structure is called extrinsic if each participant '8 share contains the same amount of information. Simmons [4] has pointed out the desirability of a scheme which is and the access structure of which extrinsic. Observe

Australas. J Comb.•Jan 1, 1990•0 citations

Socio-Rational Secret Sharing as a New Direction in Rational Cryptography

Mehrdad Nojoumian, Douglas R. Stinson

Lecture notes in computer science•Jan 1, 2012•26 citations

Multi-party computation from any linear secret sharing scheme secure against adaptive adversary : the zero-error case

Ventzislav Nikov, Svetla Nikova⋆, Bart Preneel A

We use a general treatment of both information-theoretic and cryptographic settings for Multi-Party Computation (MPC), based on the underlying linear secret sharing scheme. Our goal is to study the Monotone Span Program (MSP), which is the result of local multiplication of shares distributed by two given MSPs as well as the access structure that this resulting MSP computes. First, we expand the construction proposed by Cramer et al. multiplying two different general access structures and we prove some properties of the resulting MSP M. Next we expand the definition of multiplicative MSPs and we prove that when one uses dual MSPs only all players together can compute the product, i.e., the construction proposed by Cramer et al. gives only multiplicative MPC. Third, we propose a solution for the strongly multiplicative MPC (in presence of adversary). The knowledge of the resulting MSP and the access structure it computes allows us to build an analog of the algebraic simplification protocol of Gennaro et al. We show how to achieve in the computational model MPC secure against adaptive adversary in the zero-error case, through the application of homomorphic commitments. There is an open problem how efficiently we can determine Γ the access structure of the resulting MSP M. This open problem reflects negatively on the efficiency of the proposed solution.

•Jan 1, 2003•4 citations

On the Power of Nonlinear Secret-Sharing.

Amos Beimel, Yuval Ishai

A secret-sharing scheme enables a dealer to distribute a secret among n parties such that only some predefined authorized sets of parties will be able to reconstruct the secret from their shares. The (monotone) collection of authorized sets is called an access structure, and is freely identified with its characteristic monotone function f : 1}. A family of secret-sharing schemes is called efficient if the total length of the n shares is polynomial in n. Most previously known secret-sharing schemes belonged to a class of linear schemes, whose complexity coincides with the monotone span program size of their access structure. Prior to this work there was no evidence that nonlinear schemes can be significantly more efficient than linear schemes, and in particular there were no candidates for schemes efficiently realizing access structures which do not lie in NC.

•Jan 1, 2001•2 citations

Rational Secret Sharing, Revisited.

Steven Gordon, Jonathan I. Katz

We consider the problem of secret sharing among n rational players. This problem was introduced by Halpern and Teague (STOC 2004), who claim that a solution is impossible for n = 2 but show a solution for the case n >= 3. Contrary to their claim, we show a protocol for rational secret sharing among n = 2 players; our protocol extends to the case n 3, where it is simpler than the Halpern-Teague solution and also o#ers a number of other advantages. We also show how to avoid the continual involvement of the dealer, in either our own protocol or that of Halpern and Teague. Our

•Jan 1, 2006•0 citations

The set of all real numbers Z -The set of all integers F -A finite field GF(q) -The finite field with q elements P i -The i th player n -The number of players P -The set contains n players P 1 , . . ., P n 2 P -The power set of P |A| -The size of the set A s -A secret in secret sharing schemes R -The domain of random strings S -The domain of the secrets in secret sharing schemesS i -The share domain of P i -The operation of bitwise XOR α, β -The inner product of α and β α[i] -The i th coordinate of α D -The dealer in secret sharing schemes Π -A secret sharing scheme Π(s, r) i -The share of P i generated with the secret s and a random string r in the secret sharing scheme Π Π(s, r) A -The shares of players in A generated with the secret s and a random string r in the secret sharing scheme Π A -An adversary structure Γ -An access structure A ⊥ -The dual adversary structure of A Γ ⊥ -The dual access structure of Γ M -A monotone span program M ⊥ -A dual monotone span program of M LSSS -Linear secret sharing scheme RSSS -Rational secret sharing scheme MSP -Monotone span program MPC -Multiparty computation C -A block code C ⊥ -The dual code of C Γ(C) -The admissible distance of a block code C ∆(C) -The forbidden distance of a block code C rank(M ) -The rank of a matrix M span(M ) -The vector space spanned by the row vectors in M M T -The transpose of the matrix M ker(M ) -The solution space of the linear equation system M • X = 0 (α|M ) -The matrix containing the columns of M along with an additional column α (a, β) -The vector containing the elements of β along with an additional element a t -The size of each minimal authorized set in a threshold access structure t * -The size of active players in the secret reconstruction process k -A security parameter G -A game

Secret sharing is a mechanism by which a trusted dealer holding a secret “splits ” the secret into many “shares ” and distributes the shares to a collection of parties. Associated with the sharing is a monotone access structure, that specifies which parties are “qualified ” and which are not: any qualified subset of parties can (efficiently) reconstruct the secret, but no unqualified subset can learn anything about the secret. In the most general form of secret sharing, the access structure can be any monotone NP language. In this work, we consider two very natural extensions of secret sharing. In the first, which we call distributed secret sharing, there is no trusted dealer at all, and instead the role of the dealer is distributed amongst the parties themselves. Distributed secret sharing can be thought of as combining the features of multiparty non-interactive key exchange and standard secret sharing, and may be useful in settings where the secret is so sensitive that no one individual dealer can be trusted with the secret. Our second notion is called functional secret sharing, which incorporates some of the features of functional encryption into secret sharing by providing more fine-grained access to the secret. Qualified subsets of parties do not learn the secret, but instead

Abstract. We construct a perfect extrinsic secret sharing scheme for any case in which a set of participants can gain access to the secret if and only if the set contains a pair of members from some given list of pairs. A secret sharing scheme is a way by which a dealer rnay distribute secret information to individuals (call participants). There is associated '-<U.lh'.lcH"""F- of subsets of a set of can if they constitute a member of the access structure. usual to demand that the access structure be monotone: If A contains a subset which to the structure, then A itself must also belong to the structure. A secret scheme is called perfect if a set of pa.rticipants can no information by their shares unless the set is member of the access structure. An structure is called extrinsic if each participant '8 share contains the same amount of information. Simmons [4] has pointed out the desirability of a scheme which is and the access structure of which extrinsic. Observe

We use a general treatment of both information-theoretic and cryptographic settings for Multi-Party Computation (MPC), based on the underlying linear secret sharing scheme. Our goal is to study the Monotone Span Program (MSP), which is the result of local multiplication of shares distributed by two given MSPs as well as the access structure that this resulting MSP computes. First, we expand the construction proposed by Cramer et al. multiplying two different general access structures and we prove some properties of the resulting MSP M. Next we expand the definition of multiplicative MSPs and we prove that when one uses dual MSPs only all players together can compute the product, i.e., the construction proposed by Cramer et al. gives only multiplicative MPC. Third, we propose a solution for the strongly multiplicative MPC (in presence of adversary). The knowledge of the resulting MSP and the access structure it computes allows us to build an analog of the algebraic simplification protocol of Gennaro et al. We show how to achieve in the computational model MPC secure against adaptive adversary in the zero-error case, through the application of homomorphic commitments. There is an open problem how efficiently we can determine Γ the access structure of the resulting MSP M. This open problem reflects negatively on the efficiency of the proposed solution.

A secret-sharing scheme enables a dealer to distribute a secret among n parties such that only some predefined authorized sets of parties will be able to reconstruct the secret from their shares. The (monotone) collection of authorized sets is called an access structure, and is freely identified with its characteristic monotone function f : 1}. A family of secret-sharing schemes is called efficient if the total length of the n shares is polynomial in n. Most previously known secret-sharing schemes belonged to a class of linear schemes, whose complexity coincides with the monotone span program size of their access structure. Prior to this work there was no evidence that nonlinear schemes can be significantly more efficient than linear schemes, and in particular there were no candidates for schemes efficiently realizing access structures which do not lie in NC.

We consider the problem of secret sharing among n rational players. This problem was introduced by Halpern and Teague (STOC 2004), who claim that a solution is impossible for n = 2 but show a solution for the case n >= 3. Contrary to their claim, we show a protocol for rational secret sharing among n = 2 players; our protocol extends to the case n 3, where it is simpler than the Halpern-Teague solution and also o#ers a number of other advantages. We also show how to avoid the continual involvement of the dealer, in either our own protocol or that of Halpern and Teague. Our