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

Rational secret sharing

Yun Zhang

Published Jan 1, 2012• 0 citations
Publisher

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

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•25 citations

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

Ventzislav Nikov, Svetla Nikova⋆, Bart Preneel

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

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

Span Programs and General Secure Multi-Party Computation

Ronald Cramer, Ivan Damgård, Ueli M. Maurer

The contributions of this paper are three-fold. First, as an abstraction of previously proposed cryptographic protocols we propose two cryptographic primitives: homomorphic shared commitments and linear secret sharing schemes with an additional multiplication property. We describe new constructions for general secure multi-party computation protocols, both in the cryptographic and the information-theoretic (or secure channels) setting, based on any realizations of these primitives. Second, span programs, a model of computation introduced by Karchmer and Wigderson, are used as the basis for constructing new linear secret sharing schemes, from which the two above-mentioned primitives as well as a novel verifiable secret sharing scheme can efficiently be realized. Third, note that linear secret sharing schemes can have arbitrary (as opposed to threshold) access structures. If used in our construction, this yields multi-party protocols secure against general sets of active adversaries, as long as in the cryptographic (information-theoretic) model no two (no three) of these potentially misbehaving player sets cover the full player set. This is a strict generalization of the threshold-type adversaries and results previously considered in the literature. While this result is new for the cryptographic model, the result for the information-theoretic model was previously proved by Hirt and Maurer. However, in addition to providing an independent proof, our protocols are not recursive and have the potential of being more efficient.

BRICS Report Series•Jan 28, 1997•17 citations

Unconditionally Secure Cryptographic Protocols from Coding-Theoretic Primitives

Gabriele Spini

Protocoles avec Sécurité Inconditionnelle issus de Techniques de la Théorie des Codes Le sujet de cette thèse est la cryptographie et son interconnexions avec la théorie des codes. En particulier, on utilise des techniques issues de la théorie des codes pour construire et analyser des protocoles cryptographiques avec des propriétés nouvelles ou plus avancées. On se concentre d'abord sur le partage de secret ou secret sharing, un sujet important avec de nombreuses applications pour la Cryptographie actuelle. Dans la variante à laquelle on s'intéresse, un schéma de partage de secret reçoit en entrée un élément secret, et renvoie en sortie n parts de telle façon que chaque ensemble de parts de taille suffisamment petite ne donne aucune information sur le secret (confidentialité), tandis que chaque ensemble de taille suffisamment grande permet de reconstituer le secret (reconstruction). Un schéma de partage de secret peut donc être vu comme une solution à un problème de communication où un émetteur Alice est connectée avec un destinataire Bob par n canaux distincts, dont certains sont contrôlés par un adversaire Ève. Alice peut utiliser un schéma de partage de secret pour communiquer un message secret a Bob de telle façon qu'Ève n'apprenne aucune information sur le secret en lisant les données transmises sur les canaux qu'elle contrôle, tandis que Bob peut recevoir le message même si Ève bloque ces dits canaux. Notre contributions au partage de secret concernent ses liens avec la théorie des codes ; comme les deux domaines partagent un même but (récupérer des données à partir d'informations partielles), ce n'est pas surprenant qu'ils aient connu une interaction longue et fertile. Plus précisément, Massey commença une analyse fructueuse à propos de la construction et de l'étude d'un schéma de partage de secret à partir d'un code correcteur. L'inconvénient de cette analyse est que la confidentialité d'un schéma de partage de secret est estimé grâce au dual du code sous-jacent ; cela peut être problématique vu qu'il pourrait ne pas être possible d'obtenir des codes avec des propriétés souhaitables qui aient aussi un bon code dual. On contourne ce problème en établissant une connexion nouvelle entre les deux domaines, telle que la confidentialité d'un schéma de partage de secrets n'est plus contrôlée par le dual du code sous-jacent. Cela nous permet d'exploiter complètement le potentiel de certaines constructions récentes de codes pour obtenir des meilleurs schémas; on illustre ceci avec deux applications. Premièrement, en utilisant des codes avec codage et décodage en temps linéaire on obtient une famille de schémas de partage de secret où le partage (calcul des parts issues du secret) tout comme la reconstruction peuvent s'effectuer en temps linéaire ; pour des seuils de confidentialité et de reconstruction croissants, ceci restait jusqu'à présent un problème ouvert. Deuxièmement, on utilise des codes avec décodage en liste pour construire des schémas de partage de secret robustes, c'est-à-dire des schémas qui peuvent reconstituer le secret même si certaines parts sont incorrectes, sauf avec une petite probabilité d'erreur. etc...

•Dec 6, 2017•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
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.
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
The contributions of this paper are three-fold. First, as an abstraction of previously proposed cryptographic protocols we propose two cryptographic primitives: homomorphic shared commitments and linear secret sharing schemes with an additional multiplication property. We describe new constructions for general secure multi-party computation protocols, both in the cryptographic and the information-theoretic (or secure channels) setting, based on any realizations of these primitives. Second, span programs, a model of computation introduced by Karchmer and Wigderson, are used as the basis for constructing new linear secret sharing schemes, from which the two above-mentioned primitives as well as a novel verifiable secret sharing scheme can efficiently be realized. Third, note that linear secret sharing schemes can have arbitrary (as opposed to threshold) access structures. If used in our construction, this yields multi-party protocols secure against general sets of active adversaries, as long as in the cryptographic (information-theoretic) model no two (no three) of these potentially misbehaving player sets cover the full player set. This is a strict generalization of the threshold-type adversaries and results previously considered in the literature. While this result is new for the cryptographic model, the result for the information-theoretic model was previously proved by Hirt and Maurer. However, in addition to providing an independent proof, our protocols are not recursive and have the potential of being more efficient.
Protocoles avec Sécurité Inconditionnelle issus de Techniques de la Théorie des Codes Le sujet de cette thèse est la cryptographie et son interconnexions avec la théorie des codes. En particulier, on utilise des techniques issues de la théorie des codes pour construire et analyser des protocoles cryptographiques avec des propriétés nouvelles ou plus avancées. On se concentre d'abord sur le partage de secret ou secret sharing, un sujet important avec de nombreuses applications pour la Cryptographie actuelle. Dans la variante à laquelle on s'intéresse, un schéma de partage de secret reçoit en entrée un élément secret, et renvoie en sortie n parts de telle façon que chaque ensemble de parts de taille suffisamment petite ne donne aucune information sur le secret (confidentialité), tandis que chaque ensemble de taille suffisamment grande permet de reconstituer le secret (reconstruction). Un schéma de partage de secret peut donc être vu comme une solution à un problème de communication où un émetteur Alice est connectée avec un destinataire Bob par n canaux distincts, dont certains sont contrôlés par un adversaire Ève. Alice peut utiliser un schéma de partage de secret pour communiquer un message secret a Bob de telle façon qu'Ève n'apprenne aucune information sur le secret en lisant les données transmises sur les canaux qu'elle contrôle, tandis que Bob peut recevoir le message même si Ève bloque ces dits canaux. Notre contributions au partage de secret concernent ses liens avec la théorie des codes ; comme les deux domaines partagent un même but (récupérer des données à partir d'informations partielles), ce n'est pas surprenant qu'ils aient connu une interaction longue et fertile. Plus précisément, Massey commença une analyse fructueuse à propos de la construction et de l'étude d'un schéma de partage de secret à partir d'un code correcteur. L'inconvénient de cette analyse est que la confidentialité d'un schéma de partage de secret est estimé grâce au dual du code sous-jacent ; cela peut être problématique vu qu'il pourrait ne pas être possible d'obtenir des codes avec des propriétés souhaitables qui aient aussi un bon code dual. On contourne ce problème en établissant une connexion nouvelle entre les deux domaines, telle que la confidentialité d'un schéma de partage de secrets n'est plus contrôlée par le dual du code sous-jacent. Cela nous permet d'exploiter complètement le potentiel de certaines constructions récentes de codes pour obtenir des meilleurs schémas; on illustre ceci avec deux applications. Premièrement, en utilisant des codes avec codage et décodage en temps linéaire on obtient une famille de schémas de partage de secret où le partage (calcul des parts issues du secret) tout comme la reconstruction peuvent s'effectuer en temps linéaire ; pour des seuils de confidentialité et de reconstruction croissants, ceci restait jusqu'à présent un problème ouvert. Deuxièmement, on utilise des codes avec décodage en liste pour construire des schémas de partage de secret robustes, c'est-à-dire des schémas qui peuvent reconstituer le secret même si certaines parts sont incorrectes, sauf avec une petite probabilité d'erreur. etc...