In modern cryptography, a secret sharing scheme is an important cryptographic primitive. In particular, Krawczyk proposed a computational secret sharing (CSS) scheme, which is a practical, simple secret sharing scheme. In this paper, we focus on a CSS scheme with timed-release functionality, which we call a timed-release computational secret sharing (TR-CSS) scheme. In TR-CSS, participants more than or equal to a threshold number can reconstruct a secret by using their shares only when the time specified by a dealer has come. Our main purpose is to realize a TR-CSS scheme in a generic and efficient way in terms of the share size. Specifically, we first introduce a model and formalization of security of TR-CSS. In addition, we propose two kinds of constructions of TR-CSS: the first one is a simple and generic construction starting from an identity-based key encapsulation mechanism (IB-KEM); the second one, which is a more efficient construction than the first one, is built using a specific IB-KEM as the underlying IB-KEM. As a result, we can regard TR-CSS as a natural extension of Krawczyk’s CSS in terms of both a model and constructions, and we finally succeed to add timed-release functionality to Krawczyk’s CSS with small overhead, which is almost optimal. Moreover, our proposal of TR-CSS is important for constructing threshold encryption and multiple encryption with timed-release functionality in a generic and efficient way. Dodis and Katz showed (i) a simple and generic construction of threshold encryption from multiple encryption; and (ii) a simple, elegant and generic construction of multiple encryption. By using TR-CSS, we can effectively apply the Dodis–Katz paradigm even in the context of timed-release security.

1. The ciphertext size in the underlying IB-KEM leads directly to the share size of the resulting TR-CSS scheme.

2. SS schemes with the (k, n)-threshold access structure is traditionally called (k, n)-threshold SS schemes.

3. The notion ofFTG-CPA will be described in Sect.2.5.

4. For the rest of this paper, in each scheme, we omit a security parameter\(1^{\kappa }\) from all algorithms except for a setup (or key generation) algorithm as input, if it is clear from the context.

5. In this game, we consider\({\mathcal {W}}={\mathcal {P}}\) (not a proper subset of\({\mathcal {P}}\)), since we want to focus on the strongest security.

6. For formal definitions of ME, PKE, and OTS, see Appendix 1.

7. Our goal is to keep confidentiality until the specified time comes. Therefore, we do not consider replacing OTS schemes.

8. To be precise, anIND-CCA secure tag-KEM [1] and a DEM. However, we simplify our description here for the easy-to-understand explanation since an IND-CCA secure PKE scheme can be constructed from these primitives.

9. As mentioned in [22], it is only necessary to consider a notion of “CPA” for insider security, since an adversary has all secret keys and hence he can decrypt ciphertexts by access to a time-signals generation oracle.

10. In timed-release cryptography, it is usually assumed that the time-server always generates and broadcasts time-signals correctly, however tries to get some information on the underlying plaintexts from transmitted ciphertexts. Such an adversary is often called the curious one.

We would like to thank Goichiro Hanaoka and Keita Emura for helpful suggestions to improve the preliminary version of this paper, and Michel Abdalla for his valuable comment for the conference version of this paper. We would also like to than anonymous reviewers for their constructive feedbacks. The first author is supported by JSPS Research Fellowships for Young Scientists. This work (Yohei Watanabe) was supported by Grant-in-Aid for JSPS Fellows Grant Number 25\(\cdot \)3998, This work (Junji Shikata) was conducted under the auspices of the MEXT Program for Promoting the Reform of National Universities.

1. Yohei Watanabe

   Present address: Graduate School of Informatics and Engineering, The University of Electro-Communications, 1-5-1 Chofugaoka, Chofu, 182-8585, Japan

Authors and Affiliations

1. Graduate School of Environment and Information Sciences, Yokohama National University, 79-7 Tokiwadai, Hodogaya-ku, Yokohama, 240-8501, Japan

   Yohei Watanabe & Junji Shikata

2. Information Technology Research Institute (ITRI), National Institute of Advanced Industrial Science and Technology (AIST), 2-4-7 Aomi, Koto-ku, Tokyo, 135-0064, Japan

   Yohei Watanabe

3. Institute of Advanced Sciences, Yokohama National University, 79-7 Tokiwadai, Hodogaya-ku, Yokohama, 240-8501, Japan

   Junji Shikata

Corresponding author

Correspondence toYohei Watanabe.

Communicated by C. Blundo.

A shorter version appeared in the Proceedings of the 8th International Conference on Provable Security (ProvSec 2014), Hong Kong, October, 2014 [45]. This is the full version.

Appendix 1: Definitions

We give several formal definitions.

1.1Bilinear groups

A (symmetric) bilinear group generator\({\mathcal {G}}\) is an algorithm that takes a security parameter\(\kappa \) as input and outputs a bilinear group\((p, {\mathbb {G}}, {\mathbb {G}}_T, g, e)\), wherep is a prime,\({\mathbb {G}}\) and\({\mathbb {G}}_T\) are multiplicative cyclic groups of orderp,g is a (random) generator of\({\mathbb {G}}\), ande is an efficiently computable and non-degenerate bilinear map\(e: {\mathbb {G}}\times {\mathbb {G}}\rightarrow {\mathbb {G}}_T\) with the following bilinear property: For any\(u, u',v, v' \in {\mathbb {G}}\),\(e(uu',v)=e(u,v)e(u',v)\) and\(e(u,vv')=e(u,v)e(u,v')\), and for any\(u,v\in {\mathbb {G}}\) and any\(a\in {\mathbb {Z}}_p\),\(e(u^a,v)=e(u,v^a)=e(u,v)^a\).

1.2Decisional bilinear Diffie–Hellman (DBDH) assumption

Let\({\mathcal {A}}\) be a PPT adversary and we consider\({\mathcal {A}}\)’s advantage against the DBDH problem as follows.

Definition 13

For\({}^{\exists }\kappa _0 \in {\mathbb {N}}\) and\({}^{\forall }\kappa \ge \kappa _0\), the DBDH assumption relative to a generator\({\mathcal {G}}\) holds if there exists a negligible\(\epsilon \) in\(\kappa \) such that\(Adv^{\textsf {DBDH}}_{{\mathcal {G}},{\mathcal {A}}}(\kappa )<\epsilon \) holds for any PPT adversary\({\mathcal {A}}\).

1.3Multiple encryption

In ME, a plaintext is encrypted by using independent secret keys or distinct PKE schemes based on different computational assumptions. An ME scheme provides better security than a PKE scheme, since even if underlying assumptions of some component PKE schemes are broken or some of secret keys are leaked, the confidentiality can still be maintained by the remaining PKE schemes (for details, see [23,35,49]).

We adopt the model of ME shown by Dodis and Katz [23]. An ME scheme\({\varPi }_{\textsc {me}}\) consists of five-tuple algorithms (M.Gen, M.Enc, Split, M.Dec, M.Combine) defined as follows, where\({\mathcal {M}}_{\textsc {me}}\) is a set of plaintexts determined by a security parameter\(\kappa \).

• \((EK,{{\varvec{D}}}{{\varvec{K}}})\leftarrow \textsf {M.Gen}(1^{\kappa })\): A probabilistic algorithm for key generation. It takes a security parameter\(\kappa \) as input, and outputs a public keyEK and secret keys\({{\varvec{D}}}{{\varvec{K}}}:=(DK_1,\ldots ,DK_n)\).

• \(C\leftarrow \textsf {M.Enc}_L(EK,M)\): A probabilistic algorithm for encryption. It takes a public keyEK, a labelL, and a plaintext\(M\in {\mathcal {M}}_{\textsc {me}}\) as input, and then outputs a ciphertextC.

• \({\varvec{C}}\leftarrow \textsf {Split}_L(EK,C)\): A deterministic algorithm for splitting a ciphertext. It takes a public keyEK, a labelL, and a ciphertextC as input, and outputsn ciphertext shares\({\varvec{C}}:=(C_1,\ldots ,C_n)\).

• \(M_i\) or\(\bot \leftarrow \textsf {M.Dec}(DK_{i},C_i)\): A deterministic algorithm for decryption. It takes a secret key\(DK_i\) and a ciphertext share\(C_i\) as inputs, and outputs a decryption share\(M_i\) or\(\bot \).

• M or\(\bot \leftarrow \textsf {M.Combine}({\varvec{M}})\): A deterministic algorithm for combining decryption shares. It takes all decryption shares\({\varvec{M}}:=(M_1,\ldots ,M_n)\) as input, and outputs the plaintext\(M\in {\mathcal {M}}_{\textsc {me}}\) or\(\bot \notin {\mathcal {M}}_{\textsc {me}}\).

In the above model, we assume that\({\varPi }_{\textsc {me}}\) meets the followingcorrectness property: For all\(\kappa \in {\mathbb {N}}\), all labelsL, all\((EK,{{\varvec{D}}}{{\varvec{K}}})\leftarrow \textsf {M.Gen}(1^{\kappa })\) and all\(M\in {\mathcal {M}}_{\textsc {me}}\), it holds that

where\(\varvec{DEC}({\varvec{C}}):=(\textsf {M.Dec}(DK_{1},C_1),\ldots ,\textsf {M.Dec}(DK_{n},C_n))\) for\((C_1,\ldots ,C_n)\leftarrow \textsf {Split}_L(EK,\)\(\textsf {M.Enc}_L(EK,M))\).

We describe notions of indistinguishability against the following four attacks defined by Dodis and Katz [23]: multiple chosen plaintext attack (IND-MCPA), weak multiple chosen ciphertext attack (IND-wMCCA), multiple chosen ciphertext attack (IND-MCCA), and strong multiple chosen ciphertext attack (IND-sMCCA). Let\({\mathcal {A}}\) be a PPT adversary, and letX\(\in \){MCPA,wMCCA,MCCA,sMCCA}. Let\({\mathcal {A}}\) be a PPT adversary, and\({\mathcal {A}}\)’s advantage against theIND-X security is defined by

Here, we require\(|M_{0}^*|=|M_{1}^*|\), andst is state information.\(\textit{Corrupt}(\cdot )\) is acorrupt oracle which takes an IDi as input, and then\({\mathcal {W}}\leftarrow {\mathcal {W}}\cup \{P_i\}\) and returns\(DK_i\).\({\mathcal {A}}\) can query to\(\textit{Corrupt}(\cdot )\) until\(|{\mathcal {W}}|=d\). In addition,\({\mathcal {O}}\) is an oracle corresponding to attacks (see Table1).\({\mathcal {A}}\) is allowed to access the above oracle at most\(q_{c}\) times at any time, however it cannot submit the target ciphertext\(C^*\) to\({\mathcal {O}}\). In addition to this, we need to add two restrictions in theIND-sMCCA game. First,\({\mathcal {A}}\) cannot submit\((i, C_i^*)\), where\(C^*_i\in \varvec{C^*}\) and\(({\varvec{C}}^*,aux)\leftarrow \textsf {Split}_{L^*}(EK,C^*)\). Second, we need the weakly collision-resistant property, which means that any PPT adversary\({\mathcal {A}}\) cannot find\(C'\) such that\(\textsf {Split}_{L}^{(i)}(EK,C)=\textsf {Split}_{L}^{(i)}(EK,C')\) and\(C'\ne C\), where\(\textsf {Split}_{L}^{(i)}(EK,C)\) denotes thei-th output of\(\textsf {Split}_L(EK,C)\) (see [23] for the formal definition).

Definition 14

(Security of ME [23]) For\({}^{\exists }\kappa _0 \in {\mathbb {N}}\) and\({}^{\forall }\kappa \ge \kappa _0\), an ME scheme\({\varPi }_{\textsc {me}}\) is said to be\((d, q_{c}, \epsilon )\)-IND-X secure if there exists a negligible\(\epsilon \) in\(\kappa \) such that\(Adv^{\textsf {IND-X}}_{{\varPi }_{\textsc {me}},{\mathcal {A}}}(\kappa )<\epsilon \) holds for any PPT adversary\({\mathcal {A}}\), whered is the maximum number of secret keys that\({\mathcal {A}}\) can obtain and\(q_{c}\) is the number of queries that\({\mathcal {A}}\) can issue to the oracle\({\mathcal {O}}\) in theIND-X game.

1.4Public key encryption

We consider public key encryption (PKE) with labels as in [42]. Let\({\mathcal {M}}_{\textsc {pke}}\) be a set of plaintexts determined by a security parameter\(\kappa \). A PKE scheme\({\varPi }_{\textsc {pke}}\) consists of three-tuple algorithms (Gen, Enc, Dec) defined as follows.

• \((pk,sk)\leftarrow \textsf {Gen}(1^{\kappa })\): A probabilistic algorithm for key generation. It takes a security parameter\(\kappa \) as input and outputs a pair of a public key and a secret key (pk, sk).

• \(c\leftarrow \textsf {Enc}_L(pk,m)\): An algorithm for encryption. It takes the public keypk, a labelL, and a plaintext\(m\in {\mathcal {M}}_{\textsc {pke}}\) as input, and outputs a ciphertextc.

• m or\(\bot \leftarrow \textsf {Dec}_L(sk,c)\): A deterministic algorithm for decryption. It takes the secret keysk, a labelL, and a ciphertextC, and outputs a plaintext\(m\in {\mathcal {M}}_{\textsc {pke}}\) or\(\bot \notin {\mathcal {M}}_{\textsc {pke}}\).

We assume that\({\varPi }_{\textsc {pke}}\) meets the followingcorrectness property: For all\(\kappa \in {\mathbb {N}}\), all labelsL, all\((pk,sk)\leftarrow \textsf {Gen}(1^\kappa )\), and all\(m\in {\mathcal {M}}_{\textsc {pke}}\), it holds that\(m\leftarrow \textsf {Dec}_L(sk,\textsf {Enc}_L(pk,m))\).

We describe the notion of indistinguishability against chosen plaintext attack (IND-CPA). Let\({\mathcal {A}}\) be a PPT adversary, and\({\mathcal {A}}\)’s advantage against theIND-CPA security is defined by

Here, we require\(|m_{0}^*|=|m_{1}^*|\), andst is state information.

Definition 15

(IND-CPA) For\({}^{\exists }\kappa _0 \in {\mathbb {N}}\) and\({}^{\forall }\kappa \ge \kappa _0\), a PKE scheme\({\varPi }_{\textsc {pke}}\) is said to be\(\epsilon \)-IND-CPA secure if there exists a negligible\(\epsilon \) in\(\kappa \) such that\(Adv^{\mathsf {IND\textsf {-}CPA}}_{{\varPi }_{\textsc {pke}},{\mathcal {A}}}(\kappa )<\epsilon \) holds for any PPT adversary\({\mathcal {A}}\).

Moreover, by taking adecryption oracle into account we can also consider the notion of indistinguishability against chosen ciphertext attack (IND-CCA). Let\({\mathcal {A}}\) be a PPT adversary, and\({\mathcal {A}}\)’s advantage against theIND-CCA security is defined by

Here, we require\(|m_{0}^*|=|m_{1}^*|\), andst is state information. In addition,\(\textit{Dec}(\cdot ,\cdot )\) is adecryption oracle which takes a pair of a ciphertext and a labelc as input, and then returns\(\textsf {Dec}_{L}(sk,c)\).\({\mathcal {A}}\) is allowed to issue arbitrary queries to the above oracle in thechal stage, however,\({\mathcal {A}}\) cannot submit\(c^*\) to the oracle in theguess stage.

Definition 16

(IND-CCA) For\({}^{\exists }\kappa _0 \in {\mathbb {N}}\) and\({}^{\forall }\kappa \ge \kappa _0\), a PKE scheme\({\varPi }_{\textsc {pke}}\) is said to be\((q_{c}, \epsilon )\)-IND-CCA secure if there exists a negligible\(\epsilon \) in\(\kappa \) such that\(Adv^{\mathsf {IND\textsf {-}CCA}}_{{\varPi }_{\textsc {pke}},{\mathcal {A}}}(\kappa )<\epsilon \) holds for any PPT adversary\({\mathcal {A}}\), where\(q_{c}\) is the number of queries that\({\mathcal {A}}\) can issue to the oracle in theIND-CCA game.

1.5One-time signature

Let\({\mathcal {M}}_{\textsc {ots}}\) be a set of messages determined by a security parameter\(\kappa \). A DS scheme\({\varPi }_{\textsc {ots}}\) consists of three-tuple algorithms (KG, Sign, Vrfy) defined as follows.

• \((vk,sigk)\leftarrow \textsf {KG}(1^{\kappa })\): It takes a security parameter\(\kappa \) and outputs a pair of a verification key and a signing key (vk, sigk).

• \(\sigma \leftarrow \textsf {Sign}(sigk,m)\): It takes the signing keysigk and a message\(m\in {\mathcal {M}}_{\textsc {ots}}\) and outputs a signature\(\sigma \).

• 1 or\(0\leftarrow \textsf {Vrfy}(vk,m,\sigma )\): It takes the verification keyvk and a pair of a message and a signature\((m,\sigma )\), and then outputs 1 if it accepts them, otherwise it outputs 0.

We assume that\({\varPi }_{\textsc {ds}}\) meets the followingcorrectness property: For all\(\kappa \in {\mathbb {N}}\), all\((vk,sigk)\leftarrow \textsf {KG}(1^\kappa )\), and all\(m\in {\mathcal {M}}_{\textsc {ds}}\), it holds that\(1\leftarrow \textsf {Vrfy}(vk,m,\textsf {Sign}(sigk,m))\).

We describe the notion of strong unforgeability against a one-time attack (sUF-OT). Let\({\mathcal {A}}\) be a PPT adversary, and\({\mathcal {A}}\)’s advantage against theUF-CMA security is defined by

where\(\textit{Sign}\) is asigning oracle which takes a message\(m\in {\mathcal {M}}_{\textsc {ots}}\) as input and returns\(\textsf {Sign}(sigk,m)\).\({\mathcal {A}}\) is allowed to accessSign only once. Formally, the OTS scheme is defined as follows.

Definition 17

(sUF-OT) If a DS scheme\({\varPi }_{\textsc {ds}}\) is\((1, \epsilon )\)-sUF-CMA secure, then it is also\(\epsilon \)-sUF-OT secure.

Appendix 2: Generic construction of (k, n)-TR-CSS from TR-PKE

We show a generic construction of a (k, n)-CSS scheme from a TR-PKE scheme. Before that, we describe a formal definition of TR-PKE.\({\mathcal {T}}\) is a set of time and\({\mathcal {M}}_{\textsc {tre}}\) is a set of plaintexts determined by a security parameter\(\kappa \). A TR-PKE scheme\({\varPi }_{\textsc {tpke}}\) consists of five-tuple algorithms (TR.Init, TRKeyGen, TR.Release, TR.Enc, TR.Dec) defined as follows:

• \((params,tsk)\leftarrow \textsf {TR.Init}(1^{\kappa })\): A probabilistic algorithm for setup. It takes a security parameter\(\kappa \) as input and outputs a public parameterparams and time-server’s master secret keytsk.

• \((upk,usk)\leftarrow \textsf {TR.KeyGen}(params)\): An algorithm for key generation. It takes the public parameterparams as input and outputs a pair of public keyupk and a secret keyusk.

• \(s_{t}\leftarrow \textsf {TR.Release}(tsk,t)\): An algorithm for time-signal generation. It takes the master secret keytsk and time\(t\in {\mathcal {T}}\) as input and outputs a time-signal\(s_{t}\) at timet.

• \(ct_{t}\leftarrow \textsf {TR.Enc}(params,upk,m,t)\): A probabilistic algorithm for encryption. It takes the public parameterparams, a public keyupk, timet, and a plaintext\(m\in {\mathcal {M}}_{\textsc {tre}}\) as input and then outputs a ciphertext\(ct_{t}\).

• m or\(\bot \leftarrow \textsf {TR.Dec}(params, usk, s_{t},ct_{t}, t)\): A deterministic algorithm for decryption. It takes the public parameterparams, a secret keyusk, a time-signal\(s_t\) at the specified timet, a ciphertext\(ct_{t}\), and the specified timet as input, and then outputs a plaintext\(m\in {\mathcal {M}}_{\textsc {tre}}\) or\(\bot \notin {\mathcal {M}}_{\textsc {tre}}\).

In the above model, we assume that\({\varPi }_{\textsc {tpke}}\) meets the followingcorrectness property: For all\(\kappa \in {\mathbb {N}}\), all\((params,tsk)\leftarrow \textsf {TR.Init}(1^{\kappa })\), all\((upk,usk)\leftarrow \textsf {TR.KeyGen}(params)\), all\(t\in {\mathcal {T}}\), and all\(m\in {\mathcal {M}}_{\textsc {tre}}\), it holds that\(m\leftarrow \textsf {TR.Dec}(params, usk, \textsf {TR.Release}(tsk,t),\textsf {TR.Enc}(params,\)upk, m, t), t).

We describe two security notions: Indistinguishability against chosen plaintext attack (IND-CPA) and indistinguishability against chosen time and plaintext attack (IND-CTPA). The former is a security notion against acurious time-server.^Footnote10 In fact, formalization of this notion is almost the same as theIND-CPA security of PKE. In the latter, we consider malicious receivers attempting to obtain information on the plaintext before its specified time. Let\({\mathcal {A}}\) be a PPT adversary, and\({\mathcal {A}}\)’s advantage against theIND-CPA security is defined by

Here, we require\(|m_{0}^*|=|m_{1}^*|\), andst is state information.

Definition 18

(IND-CPA) For\({}^{\exists }\kappa _0 \in {\mathbb {N}}\) and\({}^{\forall }\kappa \ge \kappa _0\), a TR-PKE scheme\({\varPi }_{\textsf {tre}}\) is said to be\(\epsilon \)-IND-CPA secure if there exists a negligible\(\epsilon \) in\(\kappa \) such that\(Adv^{\textsf {IND-CPA}}_{{\varPi }_{\textsf {tre}},{\mathcal {A}}}(\kappa )<\epsilon \) holds for any PPT adversary\({\mathcal {A}}\).

Next, we define theIND-CTPA security. Let\({\mathcal {A}}\) be a PPT adversary, and\({\mathcal {A}}\)’s advantage against theIND-CTPA security is defined by

Here, we require\(|m_{0}^*|=|m_{1}^*|\), andst is state information. In addition,\({\mathcal {R}}(\cdot )\) is atime-signal generation oracle which takes timet as input, and then returns\(\textsf {TR.Release}(tsk,t)\).\({\mathcal {A}}\) is allowed to issue arbitrary queries to the above oracle in thechal stage, however,\({\mathcal {A}}\) cannot submit\(t^*\) to the oracle after deciding\(t^*\).

Definition 19

(IND-CTPA) For\({}^{\exists }\kappa _0 \in {\mathbb {N}}\) and\({}^{\forall }\kappa \ge \kappa _0\), a TR-PKE scheme\({\varPi }_{\textsc {tpke}}\) is said to be\((q_{ts}, \epsilon )\)-IND-CTPA secure if there exists a negligible\(\epsilon \) in\(\kappa \) such that\(Adv^{\textsf {IND-CTPA}}_{{\varPi }_{\textsc {tpke}},{\mathcal {A}}}(\kappa )<\epsilon \) holds for any PPT adversary\({\mathcal {A}}\), where\(q_{ts}\) is the number of queries that\({\mathcal {A}}\) can issue to the oracle in theIND-CTPA game.

We construct a (k, n)-TR-CSS scheme by using a TR-PKE scheme as follows. Let\({\varPi }_{\textsc {ss}}\)=(SS.Share, SS.Recon) be a (k, n)-SS scheme,\({\varPi }_{\textsc {ida}}\)=(IDA.Share, IDA.Recon) be a (k, n)-IDA,\({\varPi }_{\textsc {tpke}}\)=(TR.Init, TRKeyGen, TR.Release, TR.Enc, TR.Dec) be a TR-PKE scheme, and let\({\varPi }_{\textsc {dem}}\)=(E, D) be a DEM. Suppose that\({\mathcal {T}}\subset \hat{{\mathcal {T}}}\). Then, a (k, n)-TR-CSS scheme\({\varPi }_{\textsc {tcss}}\)=(Setup, Ext, Share, Recon) is constructed as follows.

• \((mpk,msk)\leftarrow \textsf {Setup}(1^{\kappa })\): Output\((mpk, msk ) := (params, tsk) \leftarrow \textsf {TR.Init} ( 1^{\kappa } ) \).

• \(ts^{(t)}\leftarrow \textsf {Ext}(msk, t)\): Output\(ts^{(t)}\leftarrow \textsf {TR.Release}(tsk,t)\).

• \((u_1^{(t)},\ldots ,u_n^{(t)})\leftarrow \textsf {Share}({\varGamma },mpk,s,t)\): Choose\(K\overset{\$}{\leftarrow }{\mathcal {K}}\) and\(C\leftarrow \textsf {E}(K,s)\). Compute\((upk,usk)\leftarrow \textsf {TRKeyGen}(params)\) and\(ct_t\leftarrow \textsf {TR.Enc}(params,upk,K,t)\). Generate\(({\tilde{u}}_{1},\)\(\ldots ,{\tilde{u}}_{n})\leftarrow \textsf {IDA.Share}(1^{\kappa },{\varGamma },C)\),\(({\hat{u}}_{1},\ldots ,{\hat{u}}_{n})\leftarrow \textsf {SS.Share}(1^{\kappa },{\varGamma },ct_t)\), and\((\acute{u}_{1},\ldots ,\acute{u}_{n})\leftarrow \textsf {SS.Share}(1^{\kappa },{\varGamma },usk)\). Output\(u_i^{(t)}:=({\tilde{u}}_{i},{\hat{u}}_{i},\acute{u}_i) \ (1 \le i \le n)\).

• \(s\leftarrow \textsf {Recon}({\hat{u}}_{{\mathcal {Q}}},ts^{(t)})\): Compute\(ct_t\leftarrow \textsf {SS.Recon}(1^{\kappa },{\hat{u}}_{{\mathcal {Q}}})\),\(usk\leftarrow \textsf {SS.Recon}(1^{\kappa },\acute{u}_{{\mathcal {Q}}})\), and\(C\leftarrow \textsf {IDA.Recon}(1^{\kappa },{\tilde{u}}_{{\mathcal {Q}}})\). Then compute\(K\leftarrow \textsf {TR.Dec}(params,usk,ts^{(t)},ct_t,t)\). Output\(s\leftarrow \textsf {D}(K,C)\).

The resulting (k, n)-TR-CSS scheme in the above construction is secure, if a given (k, n)-SS scheme is a (k, n)-PSS scheme, a given TR-PKE scheme meetsIND-CTPA, and a given DEM meetsFTG-CPA, as follows.

Proposition 6

If\({\varPi }_{\textsc {dem}}\) is\(\epsilon _1\)-FTG-CPA secure,\({\varPi }_{\textsc {ss}}\) is (k, n)-PSS, and\({\varPi }_{\textsc {tpke}}\) is\((q_{ts},\epsilon _2)\)-IND-CTPA secure, then the resulting (k, n)-TR-CSS scheme\({\varPi }_{\textsc {tcss}}\) in the above construction is a\((q_t,\delta _1,\delta _2)\)-(k, n)-TR-CSS scheme, where\(q_t=q_{ts}\),\(\delta _1\le \epsilon _1\) and\(\delta _2\le \epsilon _1+2\epsilon _2\).

We omit the proof of Proposition6 since we can prove it in a similar way to the proof of Theorem1.

Reprints and permissions