Japan Advanced Institute of Science and Technology
https://dspace.jaist.ac.jp/
Title
Ideal Secret Sharing Schemes with Share
Selectability
Author(s)
Emura, Keita; Miyaji, Atsuko; Nomura, Akito;
Rahman, Mohammad Shahriar; Soshi, Masakazu
Citation
Lecture Notes in Computer Science, 7043/2011:
143-157
Issue Date
2011-11-01
Type
Journal Article
Text version
author
URL
http://hdl.handle.net/10119/10296
Rights
This is the author-created version of Springer,
Keita Emura, Atsuko Miyaji, Akito Nomura,
Mohammad Shahriar Rahman, and Masakazu Soshi,
Lecture Notes in Computer Science, 7043/2011,
2011, 143-157. The original publication is
available at www.springerlink.com,
http://dx.doi.org/10.1007/978-3-642-25243-3_12
Description
Selectability
Keita Emura1, Atsuko Miyaji2, Akito Nomura3,
Mohammad Shahriar Rahman2, and Masakazu Soshi4
1
Center for Highly Dependable Embedded Systems Technology, Japan Advanced Institute of Science and Technology (JAIST), Japan
2
School of Information Science, JAIST, Japan
3
Institute of Science and Engineering, Kanazawa University, Japan
4
Graduate School of Information Sciences, Hiroshima City University, Japan
{k-emura,miyaji,mohammad}@jaist.ac.jp,[email protected],
Abstract. In this paper, we investigate a new concept, called share
selectable secret sharing, where no unauthorized set can obtain
informa-tion of the secret (in the informainforma-tion-theoretic sense) even if shares are selectable as arbitrary values which are independent of the secret. We propose two totally selectable (i.e., all users’ shares are selectable) secret sharing schemes with unanimous structure. We also propose a quasi-selectable (i.e., a part of each user’s share is quasi-selectable) secret sharing scheme with certain hierarchical structures which contains special cases of the hierarchical threshold structures introduced by Tamir Tassa in TCC2004 (or its full version (J. Cryptology2007)). If all selectable shares are randomly chosen, then our schemes are perfect. Finally, we discuss the effect of the leakage information of the secret if a weak secret is indicated as a selectable share.
1
Introduction
1.1 Cryptography with Information-theoretic Security
In cryptography, security models are classified roughly according to computa-tional security and uncondicomputa-tional security (or information-theoretic security). An adversary is modeled as a probabilistic polynomial time algorithm in com-putational security, whereas it is defined as an infinitely powerful adversary in unconditional security. Nowadays, unconditional secure protocols have become more noticeable as one of the post-quantum cryptographic schemes. Many un-conditional secure protocols have been proposed so far. Secret sharing is one of the most popular schemes among such primitives. Briefly, the flow of secret shar-ing is described as follows. Each user is given a piece of the secret called share, and an authorized set of users can recover the secret value by using their shares. On the contrary, unauthorized set can obtain information of the secret. Until now, several kind of research issues of secret sharing have been proposed, e.g.,
realizing flexible access structures [9, 24, 25, 41, 42, 44], multi secret sharing [6], dynamic secret sharing [5], information rate (which indicates the lower bound of the share size in the case of corresponding access structure5) [10, 12, 31],
ra-tional secret sharing [18, 20, 23, 27, 32] (i.e., with game-theoretic analyses), and so on. In addition, for the purpose of establishing secret sharing with shorter share size, computational secure secret sharing also have been proposed [3, 28]. As one of such schemes, computational secure on-line secret sharing schemes have been proposed [11, 22, 35, 40], where an auxiliary public value is opened to abridge the secret and the shares. Secret sharing is used in other cryptographic primitive as a building tool, e.g., attribute-based encryption [2, 34, 45], thresh-old encryption [7, 14, 36], and so on. In this paper, we attempt to revisit secret sharing from a perspective different from previous works above.
1.2 Research Background
Recently, construction of cryptographic protocols from weak secrets (e.g., a short human selected password with low Shannon’s entropy) has been considered. Some examples are, password-based authenticated key exchange (where crypto-graphically strong key can be exchanged even user has a very weak secret) [16, 17, 26, 30, 38, 46], distributed public-key cryptography (where even if each group member holds a small secret password only, they can associate to a public-key cryptosystem) [1, 8], and symmetric-key cryptography from weak secrets (where two users share a secret key which might not be uniformly random) [15], and so on. However, to the best of our knowledge, there is no proposal of unconditional secret sharing with such attempt so far (here, we exclude computational secure secret sharing which can treat such weak secrets under the computational secu-rity). Moreover, no consideration has been made about the cases where a dealer can “select” shares independently with the secret. As a simple example, in the Shamir’s secret sharing scheme [37], a share is a random value on a randomly-chosen polynomial (with the condition that the constant value equals the secret value). That is, it is impossible to select the values of shares as particular values (for certain purposes) in the Shamir’s secret sharing scheme.
1.3 Our Contribution
In this paper, we innovate a new concept, called share selectable secret sharing, where
– Shares are selectable as arbitrary values.
• The word “arbitrary” means that shares are independent of the secret.
5
Note that unconditionally secure secret sharing requires that every qualified user should have a share at least as large as the secret itself. Secret sharing is said to be ideal if and only if the size of share is the same as that of the secret (i.e., the corresponding information rate is 1).
– No unauthorized set can obtain information of the secret even if shares are selectable.
Of course, it is impossible to reconstruct the secret only from shares which are independently selected of the secret. Therefore, we introduce an auxiliary public value which works as a bridge between the secret and the shares. That is, it is required that even if unauthorized set of users obtain the auxiliary public value, it is not possible to obtain any information on the secret.
Briefly, we investigate ρs-quasi selectable secret sharing, where ρs is the
se-lectability ratio estimating the number of users’ shares that are selectable (i.e.,
ρs=(|Share selectable users|/|All users|), and selectable secret sharing is said
to be totally selectable if and only if ρs = 1. In this paper, we propose two
(n, n)-threshold totally selectable secret sharing schemes, where n is the to-tal number of users. We also propose a (1−nℓ)-quasi selectable secret sharing scheme with certain hierarchical structures, where ℓ (0 ≤ ℓ ≤ n − 2, ℓ ̸= 1) is the number of users who have un-selectable shares. Briefly speaking, these hierarchical structures contain special cases of the hierarchical threshold struc-tures of Tassa [41] (or its full version [42]). Note that Tassa [41, 42] (and [43] also) applies polynomial derivatives and Birkhoff interpolation for achieving hierarchi-cal structures, whereas we apply the classihierarchi-cal Lagrange interpolation technique only. That is, our quasi scheme implements hierarchical threshold structures by different methodology from that of Tassa’s constructions.
Remark1: Trivial Non-ideal Share Selectable Secret Sharing with Flex-ible Access Structures: Ito, Saito, and Nishizeki [24] proposed a secret sharing
scheme with general access structure from any (n, n) secret sharing scheme. Since a (n, n)-threshold totally selectable secret sharing scheme can be constructed easily (e.g., protocol 1 in Section 2), we also realize a totally selectable secret sharing scheme with general access structure. However, this totally selectable scheme is not ideal (i.e., the size of share is larger than that of the secret). We make it clear that the main objective of this paper is to construct “ideal” secret sharing schemes (i.e., the size of share is the same as that of the secret) with share selectability, and we stick resolutely to such ideal schemes in this paper.
Remark2: The Csirmaz-Tardos On-line Secret Sharing: To the best of our
knowledge, the case that shares are independently selected with the secret to be distributed has not been considered except in the following scheme proposed by Csirmaz and Tardos. Very recently, Csirmaz and Tardos proposed on-line secret sharing [13] for graph based access structures (which is totally different from the computational on-line ones [11, 22, 35, 40]). In the Csirmaz-Tardos on-line secret sharing scheme, the dealer assigns shares in the order the participants show up knowing only those qualified subsets whose all members she have seen. Users form a queue in the on-line share distribution, and they receive their shares in the order they appear. The users receive their shares one by one and the assigned share cannot be changed later on. Csirmaz and Tardos insist that their on-line scheme is useful when the set of users is not fixed in advance. Since their purpose and construction method are totally different from ours, we do not discuss their on-line secret sharing anymore although there might be somewhat relationships
between share selectable secret sharing and the Csirmaz-Tardos on-line secret sharing. There is space for argument on this point.
1.4 Requirement of Shannon’s Entropy of Selected Shares
Here, we clarify the requirement of selectable shares, especially, the difference between selectable shares and weak secrets with low entropy. For achieving “per-fect” secret sharing (i.e., no information can revealed from any unauthorized set of users), we cannot assume that a low entropy value (e.g., a human selected password) is indicated as a share. That is, we can say that:
– If selectable shares are randomly chosen, then our schemes are perfect.
• I.e., we assume that the guessing probability of each share is smaller
than that of the secret itself, namely H(S)≤ H(Wi) holds, where H(·)
is the Shannon’s entropy, S and Wi are the random variables induced by
the secret s and a share ωi. We explain other notations in Section 2.
– If a weak secret is indicated as a selectable share, then users gain some information by guessing the share of uncorrupted users.
• This setting is essentially the same as that of ramp secret sharing [4, 29].
From the above considerations, first, we propose selectable secret sharing schemes. We also prove that these schemes are perfect if selectable shares are randomly chosen (Appendix). Finally, we discuss the effect of the leakage information of the secret if a weak secret is indicated as a selectable share (Section 4).
1.5 Another Significance of the Share Selectability
Although our research starts with mainly mathematical interests, cryptographic applications of share selectable secret sharing are also expected. For example, in cryptographic schemes, where secret sharing approach is used, secret keys are computed by using shares of the master key. That is, if a decryptor has legitimate secret keys, then she can decrypt the corresponding ciphertext by combining the secret keys in the secret sharing manner (e.g., applying Lagrange interpolations). In this case, each share is also changed if access structures are changed. Hence the secret keys of users need to be updated as well. For example, in access trees (e.g., [19]), first a secret value of the root node is chosen, and next a polynomial is defined with the condition that the constant value is equal to the root secret, and a secret value of a child node is set as a value on the polynomial. So, a secret value of the leaf node is computed at the end. Therefore, if the structure of the access tree is changed, these procedures must be executed again. On the contrary, each share can be independently selected under the share selectability. So, it is expected that access structures can be updated by applying share selectable secret sharing without changing secret keys of users. In an opposite manner, secret keys might be updated without changing access structures and the master key (which is the same motivation of proactive secret sharing [21, 33, 39]). Since we mainly focus on the share selectability, we do not argue on updating the access structures or shares anymore.
2
Preliminaries
Throughout this paper, we use the following notations. Let n∈ N be the number of participants, p be a prime number of p > n (and ID mod p̸= 0 for all public identity), H(X) be Shannon’s entropy of a random variable X, H(X|Y ) be conditional Shannon’s entropy of random variables X and Y ,|X | be the number of elements of a finite setX , and 2X be the family of all subsets ofX . Operations are done over the fieldFp.
2.1 Share Selectable Secret Sharing
Here, we define share selectable secret sharing (notations are referred by [29]). LetP = {P1, P2, . . . , Pn} be a set of participants, and D ̸∈ P be a dealer who
selects a secret s∈ S, computes the corresponding auxiliary public value u ∈ U, and gives a share ωi ∈ Wi to Pi ∈ P for i ∈ [1, n], where S denotes the set of
secrets,U denotes the set of auxiliary public values, and Wi denotes the set of
possible shares that Pi might receive. The access structure Γ ⊂ 2P is a family
of subsets ofP.
Definition 1 (Share selectable secret sharing). Let S, U , and Wi be the
random variables induced by s, u, and ωi, respectively, and VA ={Wi|Pi ∈ A}
be the set of random variable of shares given to every participant Pi ∈ A ⊂ P.
Let SSGen be a selectable-share generation algorithm, which takes as an input the description of the underlying groupG (in our schemes, G = Zp), and returns
a share ω ∈ G. A share selectable secret sharing scheme is said to be perfect if the following holds.
H(S|VA, U ) =
{
0 (A∈ Γ )
H(S) (A̸∈ Γ )
Our major argument is the secret s is not included in the input of the SSGen algorithm. That is, a share ω← SSGen(G) is totally independent with the secret
s, and is called selectable. Therefore, for a selectable share ω,
H(S|V) = H(S)
holds, where V ⊂ W :=∪ni=1Wi be a random variable of shares induced by ω.
As a remark, we definitely distinguish the equation H(S|V) = H(S) above and the case that H(S|VA) = H(S) for A ̸∈ Γ in conventional perfect secret
sharing manner. That is, in share selectable secret sharing, even if all selectable shares are collected (i.e., A might be in Γ ), there is no way to recover the secret. Therefore, if all shares are selectable, then some auxiliary public value u∈ U is indispensable for reconstructing the secret s. Note that if a part of shares are non-selectable, then there is room for reconstructing the secret s without using any auxiliary public value u∈ U.
Next, we define the selectability ratio which estimates the number of users’ shares that are selectable.
Definition 2 (The Selectability Ratio). Let 0 ≤ ns ≤ n be the number of
users who have a selectable share. The selectabilty ratio ρs is defined as ρs =
ns/n.
Definition 3 (Quasi Selectability and Total Selectability). A secret
shar-ing is said to be ρs-quasi selectable secret sharing if its selectability ratio ρs is
0 < ρs < 1. A secret sharing is said to be totally selectable if its selectability
ratio ρsis 1.
The case ρs = 0 represents the conventional secret sharing schemes. Note that
there have been secret sharing schemes having ρs> 0. For example, for a secret
s ∈ Zp, the dealer D selects ωi ∈ Zp for all i ∈ [1, n − 1] (so, these shares
are selectable, since these can be selected independently with s), sets ωn :=
s−∑ni=1−1ωi (so, ωn is unselectable), and gives ωi to Pi for all i∈ [1, n]. s can
be reconstructed by ∑ni=1ωi. Then, obviously this scheme is a (1− n1)-quasi
selectable (n, n)-threshold secret sharing scheme, and is perfect.
3
Proposed Schemes
In this section, we propose two totally selectable (n, n)-threshold secret sharing schemes, and a (1− nℓ)-quasi selectable secret sharing scheme with certain hi-erarchical structures (ℓ (0 ≤ ℓ ≤ n − 2, ℓ ̸= 1) is defined in the third scheme). The first construction (protocol 1) is somewhat trivial since it is a simple mod-ification of the (1− 1
n)-quasi selectable (n, n)-threshold secret sharing scheme
introduced in the previous section. However, this scheme is easy-to-understand due to its simple structure. In our all schemes, the SSGen(Zp) algorithm simply
returns ω∈ Zp.
Protocol 1 (The first scheme: A totally selectable (n,n)-threshold se-cret sharing scheme).
Distribution Phase :
1. The dealer D selects the secret s∈ Zp
2. D selects a share ωi∈ Zp for all i∈ [1, n] such that ωi ← SSGen(Zp).
3. D sets u := s−∑ni=1ωi.
4. D gives ωi to Pi for all i ∈ [1, n], and opens u as the auxiliary public
value.
Reconstruction Phase : Compute s = u +∑ni=1ωi.
Next, we propose a polynomial-based totally selectable (n, n)-threshold se-cret sharing scheme. This second scheme can be seen as a special case of our quasi one (protocol 3). Let IDi be the (public) identity of Pi ∈ P and Γ =
{P1, P2, . . . , Pn}, namely, Γ is a (n, n)-threshold structure. We require IDi ̸=
Protocol 2 (The second scheme: A polynomial-based totally selectable (n,n)-threshold secret sharing scheme).
Distribution Phase :
1. The dealer D selects the secret s∈ Zp.
2. D selects a share ωi∈ Zp for all i∈ [1, n] such that ωi ← SSGen(Zp).
3. Let f (x) be a polynomial of degree at most n such that f (IDi) = ωi(Pi∈
Γ ) and fj(0) = s. D chooses IDD∈ Zp such that IDD̸∈ {IDi}ni=1, and
computes u = f (IDD).
4. D gives ωi to Pi for all i ∈ [1, n], and opens u as the auxiliary public
value.
Reconstruction Phase : By using Lagrange interpolation, f (x) can be
recon-structed from (IDD, u) and all{(IDi, ωi)}ni=1, and s = f (0) can be computed.
Next, we propose a (1− nℓ)-quasi selectable secret sharing scheme, which is the most interesting construction in this paper. First, we define the access structures of this quasi scheme.
Definition 4 (Hierarchical access structures realized in our quasi scheme).
Let ℓ (0≤ ℓ ≤ n−2, ℓ ̸= 1) be the number of users who have an unselectable share, and setPℓ:={U
j1, Uj2, . . . , Ujℓ} as the set of such ℓ users. Let n′:= n−ℓ be the
number of user who have a selectable share, and set P′ := {Ui1, Ui2, . . . , Uin′}
as the set of such n′ users. We require P = Pℓ∪ P′ and Pℓ ∩ P′ = ∅. Let
Γ′ ⊂ 2P′ is a family of subsets of P′, and m =|Γ′|. For Aj ∈ Γ′ (j ∈ [1, m]),
set|Aj| = nj. Let Γℓ:={A ∈ 2P ℓ
:|A| ≥ k}, where k ∈ N be the threshold value
and 2≤ k ≤ ℓ. The actual access structure Γ is defined as follows. Γ :={A : A = Aℓ∪ A′ such that Aℓ∈ Γℓ∧ A′∈ Γ′}
As one exception, if ℓ = 0, then Γ′ is restricted as the (n, n)-threshold structure only.
Note that the restriction case (ℓ = 0) is exactly the second construction, and therefore the second scheme is a special case of the third scheme. In addition,
Γ contains special cases of the hierarchical threshold structures [41, 42]6. For example, let Γ′ be (n′, n′)-threshold structure, then Γ ={A ⊂ P : |A ∩ P′| =
n′∧ |A ∩ |P′∪ Pℓ|| ≥ n′+ k} holds. This is a special case of the hierarchical
threshold structures with k0= n′, k1= n′+k,P0=P′, andP1=Pℓ. In addition
to this hierarchical threshold structure, the above Γ can represent any kind of access structure for P′ (not P). More precisely, we can achieve general access structures [24, 25, 44] for P′ although our scheme is ideal. Note that our result does not contradict with certain impossible results (e.g., there exist families
6
In the hierarchical threshold structures, a set of usersP is divided as N hierarchy
P := ∪N
i=1Pisuch thatPi∩ Pj=∅ for 0 ≤ i < j ≤ N. Let k = (k0, k1, . . . , kN) be
monotonically increasing sequence of integers 0 < k0<· · · < kN. (k, n) hierarchical
threshold structure is defined as Γ ={A ⊂ P : |A ∩(∪Ni=0Pi
)
of special access structures with n participants where the size of some shares increases unboundedly as n → ∞, i.e., at least about n/ log n times the secret size [12]), since access structures are restricted as threshold ones forPℓ(that is,
forP = Pℓ∪ P′, our access structure is not general).
Here, we give our quasi scheme. We omit the case ℓ = 0 in the following scheme, since it has already been shown as the second scheme.
Protocol 3 (The third scheme : A (1-nℓ)-quasi selectable secret sharing scheme).
Distribution Phase :
1. The dealer D selects the secret s∈ Zp.
2. D selects a share ωi∈ Zp for all Pi∈ P′ such that ωi← SSGen(Zp).
3. D chooses IDAj ∈ Zp for all j ∈ [1, m] such that IDAj ̸∈ {IDi} n i=1 and
IDAi̸= IDAj (i̸= j).
4. For each Aj ∈ Γ′ (j ∈ [1, m]), let fj(x) be a polynomial of degree at
most nj such that fj(IDi) = ωi (Ui ∈ Aj) and fj(0) = s. Set Dj :=
(IDAj, fj(IDAj)).
5. Let g(x) be a polynomial of degree at most m− 1 such that g(IDAj) =
fj(IDAj) for all j∈ [1, m].
6. For all Pi∈ Pℓ, D computes ωi:= g(IDi) (we make it clear that this step
is NOT for users Pi ∈ P′, their shares {ωi}Pi∈P′ have been “selected”
in Step 2).
7. D randomly chooses (m− k) coordinates on the polynomial g(x), exclud-ing all Dj and (IDi, g(IDi)) for all Pi ∈ Pℓ, and sets these (m− k)
coordinates as u. If k≥ m, then u = ∅.
8. D gives ωi to Pi for all i ∈ [1, n], and opens u as the auxiliary public
value.
Reconstruction Phase :
1. As in the Shamir (k, ℓ)-threshold secret sharing, by using Lagrange inter-polation, g(x) is reconstructed from all ωi of Pi∈ Pℓ (and u if k < m).
2. By using Lagrange interpolation, fj(x) can be reconstructed from (IDAj,
g(IDAj)) and (IDi, ωi) for all Pi ∈ Aj ∈ Γ′, and s = fj(0) can be
computed.
The first and second schemes are totally selectable (n, n)-threshold secret sharing schemes, and the third scheme is a (1−nℓ)-quasi selectable secret sharing scheme realizing Γ defined in Definition 4. Security proofs are given in the Appendix.
4
Share selectable secret sharing with weak shares
In this Section, we discuss the effect of the leakage information of the secret when a weak secret (e.g., a short human selected password with low Shannon’s entropy) is indicated as a selectable share. To give the maximum information to an unauthorized set of users A, we consider the situation where (1) A will be an
authorized set if only one more user (who has a share ω) is added to A, (2) ω is a selectable share, and (3) ω is the weakest share in the underlying system (i.e., for the random variables W induced by ω, H(W ) = min{H(Wi) : H(Wi) < H(S)}
holds). Note that ω is a independent value of the secret s. Therefore, the mutual information between s and ω is 0 since I(S; W ) := H(S) + H(W )− H(S, W ) =
H(S)+H(W )−H(S)−H(W ) = 0. It is thus easy to conclude that H(S|VA, U ) =
H(W ) < H(S) holds.
5
Conclusion and Future Work
In this paper, we investigate the new concept share selectable secret sharing, where a dealer D can select shares independent of the secret. We propose two totally selectable (i.e., all users’ share are selectable) secret sharing schemes with unanimous structure, and a quasi-selectable (i.e., a part of users’ share are selectable) secret sharing scheme with certain hierarchical structures which contains special cases of the hierarchical threshold structures [41, 42]. Our quasi scheme can be seen as an ideal secret sharing with flexible hierarchical struc-tures which has not been done before to the best of our knowledge, and is of independent interest.
Although our research resorts mainly on the mathematical interest, applica-tions of share selectable secret sharing are also realizable (as discussed in Section 1.5). As future work, it might be interesting to update access structures (resp. shares) without changing shares (resp. access structures).
References
1. Michel Abdalla, Xavier Boyen, C´eline Chevalier, and David Pointcheval. Dis-tributed public-key cryptography from weak secrets. In Public Key Cryptography, pages 139–159, 2009.
2. Nuttapong Attrapadung, Benoˆıt Libert, and Elie de Panafieu. Expressive key-policy attribute-based encryption with constant-size ciphertexts. In Public Key
Cryptography, pages 90–108, 2011.
3. Philippe B´eguin and Antonella Cresti. General short computational secret sharing schemes. In EUROCRYPT, pages 194–208, 1995.
4. G. R. Blakley and Catherine Meadows. Security of ramp schemes. In CRYPTO, pages 242–268, 1984.
5. Carlo Blundo, Antonella Cresti, Alfredo De Santis, and Ugo Vaccaro. Fully dy-namic secret sharing schemes. Theor. Comput. Sci., 165(2):407–440, 1996. 6. Carlo Blundo, Alfredo De Santis, Giovanni Di Crescenzo, Antonio Giorgio Gaggia,
and Ugo Vaccaro. Multi-secret sharing schemes. In CRYPTO, pages 150–163, 1994.
7. Dan Boneh, Xavier Boyen, and Shai Halevi. Chosen ciphertext secure public key threshold encryption without random oracles. In CT-RSA, pages 226–243, 2006. 8. Xavier Boyen, C´eline Chevalier, Georg Fuchsbauer, and David Pointcheval. Strong
cryptography from weak secrets. In AFRICACRYPT, pages 297–315, 2010. 9. Ernest F. Brickell. Some ideal secret sharing schemes. In EUROCRYPT, pages
10. Ernest F. Brickell and Douglas R. Stinson. Some improved bounds on the infor-mation rate of perfect secret sharing schemes. J. Cryptology, 5(3):153–166, 1992. 11. Christian Cachin. On-line secret sharing. In IMA Conf., pages 190–198, 1995. 12. L´aszl´o Csirmaz. The size of a share must be large. J. Cryptology, 10(4):223–231,
1997.
13. Laszlo Csirmaz and Gabor Tardos. On-line secret sharing. Cryptology ePrint Archive, Report 2011/174, 2011. http://eprint.iacr.org/.
14. Yvo Desmedt and Yair Frankel. Threshold cryptosystems. In CRYPTO, pages 307–315, 1989.
15. Yevgeniy Dodis and Daniel Wichs. Non-malleable extractors and symmetric key cryptography from weak secrets. In STOC, pages 601–610, 2009.
16. Rosario Gennaro. Faster and shorter password-authenticated key exchange. In
TCC, pages 589–606, 2008.
17. Craig Gentry, Philip D. MacKenzie, and Zulfikar Ramzan. Password authenticated key exchange using hidden smooth subgroups. In ACM Conference on Computer
and Communications Security, pages 299–309, 2005.
18. S. Dov Gordon and Jonathan Katz. Rational secret sharing, revisited. In SCN, pages 229–241, 2006.
19. Vipul Goyal, Omkant Pandey, Amit Sahai, and Brent Waters. Attribute-based encryption for fine-grained access control of encrypted data. In ACM Conference
on Computer and Communications Security, pages 89–98, 2006.
20. Joseph Y. Halpern and Vanessa Teague. Rational secret sharing and multiparty computation: extended abstract. In STOC, pages 623–632, 2004.
21. Amir Herzberg, Stanislaw Jarecki, Hugo Krawczyk, and Moti Yung. Proactive secret sharing or: How to cope with perpetual leakage. In CRYPTO, pages 339– 352, 1995.
22. Ren-Junn Hwang and Chin-Chen Chang. An on-line secret sharing scheme for multi-secrets. Computer Communications, 21(13):1170–1176, 1998.
23. Toshiyuki Isshiki, Koichiro Wada, and Keisuke Tanaka. A rational secret-sharing scheme based on RSA-OAEP. IEICE Transactions, 93-A(1):42–49, 2010.
24. Mitsuru Ito, Akira Saito, and Takao Nishizeki. Secret sharing scheme realizing general access structure. In Proceedings IEEE Globecom ’87, pages 99–102, 1987. 25. Mitsugu Iwamoto, Hirosuke Yamamoto, and Hirohisa Ogawa. Optimal multiple
assignments based on integer programming in secret sharing schemes with general access structures. IEICE Transactions, 90-A(1):101–112, 2007.
26. Jonathan Katz, Rafail Ostrovsky, and Moti Yung. Efficient password-authenticated key exchange using human-memorable passwords. In EUROCRYPT, pages 475– 494, 2001.
27. Gillat Kol and Moni Naor. Games for exchanging information. In STOC, pages 423–432, 2008.
28. Hugo Krawczyk. Secret sharing made short. In CRYPTO, pages 136–146, 1993. 29. Jun Kurihara, Shinsaku Kiyomoto, Kazuhide Fukushima, and Toshiaki Tanaka.
A fast (k, L, n)-threshold ramp secret sharing scheme. IEICE Transactions, 92-A(8):1808–1821, 2009.
30. Philip D. MacKenzie, Thomas Shrimpton, and Markus Jakobsson. Threshold password-authenticated key exchange. J. Cryptology, 19(1):27–66, 2006.
31. Jaume Mart´ı-Farr´e and Carles Padr´o. Secret sharing schemes on access structures with intersection number equal to one. Discrete Applied Mathematics, 154(3):552– 563, 2006.
32. Silvio Micali and Abhi Shelat. Purely rational secret sharing (extended abstract). In TCC, pages 54–71, 2009.
33. Ventzislav Nikov and Svetla Nikova. On proactive secret sharing schemes. In
Selected Areas in Cryptography, pages 308–325, 2004.
34. Takashi Nishide, Kazuki Yoneyama, and Kazuo Ohta. Attribute-based encryp-tion with partially hidden ciphertext policies. IEICE Transacencryp-tions, 92-A(1):22–32, 2009.
35. Tatsumi Oba and Wakaha Ogata. Provably secure on-line secret sharing scheme.
IEICE Transactions, 94-A(1):139–149, 2011.
36. Bo Qin, Qianhong Wu, Lei Zhang 0009, and Josep Domingo-Ferrer. Threshold public-key encryption with adaptive security and short ciphertexts. In ICICS, pages 62–76, 2010.
37. Adi Shamir. How to share a secret. Commun. ACM, 22(11):612–613, 1979. 38. SeongHan Shin, Kazukuni Kobara, and Hideki Imai. Security analysis of two
augmented password-authenticated key exchange protocols. IEICE Transactions, 93-A(11):2092–2095, 2010.
39. Douglas R. Stinson and Ruizhong Wei. Unconditionally secure proactive secret sharing scheme with combinatorial structures. In Selected Areas in Cryptography, pages 200–214, 1999.
40. Hung-Min Sun. On-line multiple secret sharing based on a one-way function.
Computer Communications, 22(8):745–748, 1999.
41. Tamir Tassa. Hierarchical threshold secret sharing. In TCC, pages 473–490, 2004. 42. Tamir Tassa. Hierarchical threshold secret sharing. J. Cryptology, 20(2):237–264,
2007.
43. Tamir Tassa and Nira Dyn. Multipartite secret sharing by bivariate interpolation.
J. Cryptology, 22(2):227–258, 2009.
44. Kouya Tochikubo. Efficient secret sharing schemes realizing general access struc-tures. IEICE Transactions, 87-A(7):1788–1797, 2004.
45. Shota Yamada, Nuttapong Attrapadung, Goichiro Hanaoka, and Noboru Kunihiro. Generic constructions for chosen-ciphertext secure attribute based encryption. In
Public Key Cryptography, pages 71–89, 2011.
46. Kazuki Yoneyama. Does secure password-based authenticated key exchange against leakage of internal states exist? IEICE Transactions, 92-A(1):113–121, 2009.
Appendix: Security Proofs
Here, we give security proofs of our schemes. As a reminder, we do not assume that a weak share is indicated as a selectable share (such weak cases has been considered in Section 4).
Theorem 1. The first scheme is a totally selectable (n, n)-threshold secret
shar-ing scheme.
Proof. The condition H(S|VA, U ) = 0 is clear when A =P, since s can be
re-constructed by computing s = u +∑ni=1ωi. In addition, the condition H(S|V) =
H(S) holds since each ωi is independently chosen with the secret s. W.l.o.g., we
setVA:= (P1, . . . , Pn−1) as the unqualified set of users. Then, since the secret s
Theorem 2. The second scheme is a totally selectable (n, n)-threshold secret
sharing scheme.
Since the second scheme is a special case of the third scheme, we give the security proof of Theorem 2 with the proof of Theorem 3.
Theorem 3. The third scheme is a (1−nℓ)-quasi selectable secret sharing scheme
realizing Γ defined in Definition 4.
As in Theorem 1, the condition H(S|VA, U ) = 0 (A∈ Γ ) and H(S|V) = H(S)
hold, where V ⊂ W :=∪ni=1′ Wi be a random variable of shares of users in P′.
So, the remaining part is H(S|VA, U ) = H(S) if A̸∈ Γ . Before giving the proof,
we prove the following Proposition and Lemmas. Below in this proposition, the notation (M, N ) represents the numbers of rows and columns, respectively.
Proposition 1. Let A be an M× N matrix over a field, and the first column
of A is C = [c1, c2, . . . , cM]T, where A = [ C | B ]. Then the first component
of the solution for simultaneous equation Ax = s is not unique if and only if rank(A) = rank(B).
Proof. Let WA={x|Ax = 0}. Then dim WA= N− rank(A). We assume that
u is a solution for Ax = s. Then we can express the general solution for Ax = s as x = u + x′, where x′ satisfies Ax′ = 0. We further assume that x′′ satisfies
Bx′′= 0. Then,
The first component of x, which is the solution for Ax = s , is unique.
⇐⇒ x′= [0, x′′]T.
⇐⇒ dim WA= dim WB
⇐⇒ N − rank(A) = N − 1 − rank(B) ⇐⇒ rank(A) = rank(B) + 1
Since rank(A) is equal to rank(B) or rank(B) + 1, then the first component of the solution for simultaneous equation Ax = s is not unique if and only if
rank(A) = rank(B). ⊓⊔
Next, we prove the following Lemma. For simplicity, we assume that g(x) is a polynomial of degree at most m− 1 which passes through m coordinates (IDAj, fj(IDAj)). Let Ps be an “imaginary” participant who has g(x) as Ps’s
share, and P′ be the set of users. Note that, here Pℓ is not considered, since
Pscan be seen asPℓ by using the Shamir (k, ℓ)-threshold scheme for the secret
g(x). LetC be the set of malicious participants such that they know the shares
of one another.
Lemma 1. We assume that the number of malicious participants be t (n′+1≥ t)
in n′ participants and one imaginary participant Ps. We calculate simultaneous
equations for coefficient polynomial fj (j = 1, 2, . . . , m) and shares of n′+ 1− t
R(n′+1, m, t) be the number of simultaneous equations for malicious participants.
Then V (n′+ 1, m, t) and R(n′+ 1, m, t) satisfy the following:
V (n′+ 1, m, t) = {
R(n′+ 1, m, t) + (n′− t + 1) (Ps̸∈ C)
R(n′+ 1, m, t) + (n′− t − m + 2) (Ps∈ C)
Proof.
The case of Ps ̸∈ C : W.l.o.g., we assume that Pi (i = 1, 2, . . . , t) are
mali-cious participants. Let C = {P1, P2, . . . , Pt} ̸∈ Γ be the set of malicious
participants. A polynomial of degree at most nj is made for each qualified
set Aj. So, the number of coefficients of the polynomial (except the secret
value s) is nj. We add the share of n′− t honest participants, the share
of a special participant Ps (i.e., a polynomial g(x)) and the secret value s
to this, V (n′+ 1, m, t) = 1 + n′− t + m +∑mj=1nj. Now we assume that
Pi ∈ Akj (j = 1, 2, . . . , ri), i.e., ri is the number of qualified sets Pi
be-longs to. Then we can obtain ri simultaneous equations. More specifically,
ωi= fk1(IDi) = fk2(IDi) =· · · = fkri(IDi). Moreover, we add a condition
such that each polynomial fj passes through coordinate (IDAj, fj(IDAj)),
R(n′+ 1, m, t) = m +∑ni=1′ ri holds. Then
∑n′ i=1ri = ∑m j=1nj holds, and therefore∑ni=1′ ri= ∑m j=1nj= V (n′+ 1, m, t)− (m + n′− t + 1) = R(n′+ 1, m, t)− m holds.
The case of Ps ∈ C : W.l.o.g., we assume that Pi (i = 1, 2, . . . , t − 1) are
malicious participants. Let C = {Ps, P1, P2, . . . , Pt−1} ̸∈ Γ represents the
set of malicious participants. Similar to the case of Ps ̸∈ C, the number
of coefficients of the polynomial (except the secret value s) is nj. We add
the share of n′− (t − 1) honest participants and the secret value s to this,
V (n′+ 1, m, t) = 1 + n′−(t−1)+∑mj=1njholds. Moreover, R(n′+ 1, m, t) = m +∑ni=1′ ri holds. So ∑n′ i=1ri= ∑m j=1nj = V (n′+ 1, m, t)− (n′− t + 2) = R(n′+ 1, m, t)− m holds. ⊓⊔
Lemma 2. We assume that Ps̸∈ C. In this situation, the secret value s cannot
be determined with R(n′+ 1, m, n′) simultaneous equations.
Proof. Let Γ′′ ={A′ = A∪ {Us} : A ∈ Γ }. For any Bj ∈ Γ′′, let fj(x) = s +
aj1x+aj2x
2+· · ·+a
jnjxnj be the polynomial associated with Bj ={Ps, Pj1, Pj2, . . . , Pjnj}. Note that fj(IDAj) = g(IDAj). So, simultaneous equations for s, aj1, aj2, . . . , ajn, g(IDAj) are (1) Nj = 1 0 IDj1 IDj1 2 · · · ID j1 nj 1 0 IDj2 IDj2 2 · · · ID j2 nj .. . ... ... . .. ... ... 1 0 IDjnj IDjnj2· · · IDjnjnj 1−1 xd,j xd,j2 · · · xd,jnj and Nj s g(IDAj) aj1 aj2 .. . ajnj = ωj1 ωj2 .. . ωjnj 0 · · · (1)
Moreover, we define that C = [ 1+m+∑mj=1nj z }| { 1, 1, . . . , 1 ]T, Mj = 0 IDj1 IDj1 2 · · · ID j1 nj 0 IDj2 IDj2 2 · · · ID j2 nj .. . ... ... . .. ... 0 IDjnj IDjnj2· · · IDjnjnj −1 IDAj IDAj 2 · · · ID Aj nj and M′ = 0· · · 0 0 · · · 0 M1 ... . .. ... ... . .. ... 0· · · 0 0 · · · 0 0· · · 0 0 · · · 0 .. . . .. ... . .. 0 · · · 0 0· · · 0 0 · · · 0 0· · · 0 0 · · · 0 .. . . .. ... ... . .. ... Mm 0· · · 0 0 · · · 0 Then, all simultaneous equations are as follows:
[C | M′] s g(IDA1) a11 .. . a1n1 g(IDA2) a21 .. . .. . g(IDAm) am1 .. . amnm = ∗ ∗ ∗ .. . ∗ ∗ ∗
Here, we prove that matrices M1, M2, . . . , Mmare regular. Let ah(h = 1, 2, . . . , nj+
1) be column vectors and ch∈ Fp be scalars on Mj. Then c1a1+ c2a2+· · · +
cnj+1anj+1= 0 holds. Let Mj′be the matrix which is Mjexcept the first column
and the (nj+ 1)’th row. Then Mj′ is regular, since it is a Vandermonde matrix.
We can obtain that c2 = c3 = . . . = cnj+1 = 0 since a1 = [0, 0, . . . , 0,−1] T.
Therefore−c1= 0 holds (and so c1= 0). That is, Mj is regular.
Let Cj= [1, 1, . . . , 1]T (j = 1, . . . , m) which is the first column of Nj. Then,
there exist αi∈ Fpsuch that Cj=
∑nj+1
i=1 αiai. Since this condition is satisfied
for all j (j = 1, 2, . . . , m), rank([C | N]) = rank(N) holds. By Proposition 1, an unqualified set cannot compute any information about s. ⊓⊔ Similar to the above, we prove Corollary 1. The notion was defined in the proof of Lemma 2.
Corollary 1. We assume that Ps̸∈ C. In this situation, g(IDAj) (j = 1, 2, . . . , m)
Proof. Similar to Lemma 2, let Cj = [1, 1, . . . , 1]T which is the first column
of Nj. Then, there exist αi ∈ Fp such that Cj =
∑nj+1
i=1 αiai. Then also
[Cj | a2 a3 · · · anj+1] is a Vandermonde matrix. Then, there exist βi (i =
1, 2, . . . , nj+ 1) such that a1 = β1Cj+
∑nj+1
i=2, βiai. By Proposition 1, an
un-qualified set cannot compute any information about g(IDAj). We previously assumed that IDAi̸= IDAj. Therefore g(IDAj) only appear on Nj, and an
un-qualified set cannot compute any information about g(IDAj) (j = 1, 2, . . . , m).
⊓ ⊔
By Lemma 2 and Corollary 3, Theorem 3 is proven by regarding as the share of
Ps, g(x), is distributed by using the Shamir (k, ℓ)-threshold secret sharing.
Next, we assume that Ps∈ C, i.e., malicious participants can obtain a
poly-nomial g(x). We can obtain the corollary as follows:
Corollary 2. We assume that an access structure for n′ participants and one special participant Psis unanimous, i.e., (n′+1, n′+1) threshold structure. Then
V (n′+ 1, m, t) > R(n′+ 1, m, t).
Proof. The case Ps̸∈ C, obviously hold. We assume that Ps∈ C. Then the
num-ber of participants that can collude is n′ (n′− 1 participants and Ps). Therefore
V (n′+1, m, t) = R(n′+1, m, t)+(n′−t−m+2) > R(n′+1, m, t)+(n′−n′−1+2) =
R(n′+ 1, m, t) + 1 holds. ⊓⊔
Lemma 3. We assume that an access structure for n′ participants and one special participant Ps is unanimous, i.e., (n′+ 1, n′ + 1) threshold structure.
Then the secret value s cannot be determined from R(n′+ 1, m, n′) simultaneous
equations.
Proof. Let f (x) = s+a1x+a2x2+· · ·+an′xn ′
be the polynomial associated with
B ={Ps, P1, P2, . . . , Pn′}. W.l.o.g., we assume P1to be the honest participant.
So, malicious participants can obtain simultaneous equation as follows (2):
N′= 1−1 ID1 ID12 · · · ID n′ 1 1 0 ID2 ID22 · · · IDn ′ 2 .. . ... ... ... . .. ... 1 0 IDn′ ID2n′ · · · ID n′ n′ 1 0 IDD IDD2· · · IDDn ′ and N′ s ω1 a1 a2 .. . an′ = 0 ω2 ω3 .. . ωn′ g(IDD) · · · (2)
Similar to Lemma 2, the (n′+ 1)× (n′+ 1) matrix which is N′ except the first column is Vandermonde. Moreover, the (n′+ 1)× (n′+ 1) matrix which is N′ except the second column is also Vandermonde. By Proposition 1, the set of malicious participants cannot determine the secret value s and the shares of
honest participants. ⊓⊔
By Lemma 3, Theorem 2 is proven by regarding as the share of Ps, i.e., g(IDD) =
