Publicly Verifiable Secret Sharing Scheme with Provable Security against Chosen Secret Attacks

Abstract

Secret sharing is an important aspect of key management in wireless ad hoc and sensor networks. In this paper, we define a new secure model of secret sharing, use the Lagrange interpolation and the bilinear cyclic groups to construct an efficient publicly verifiable secret sharing scheme on the basis of this model, and show that this scheme is provably secure against adaptively chosen secret attacks (CSAs) based on the decisional bilinear Diffie-Hellman (DBDH) problem. We find that this scheme has the following properties: (a) point-to-point secure channels are not required in both the secret distribution phase and the secret reconstruction phase; (b) it is a noninteractive secret sharing system in that the participants need not communicate with each other during subshadow verification; and (c) each participant is able to share many secrets with other participants despite holding only one shadow.

1. Introduction

A secret sharing scheme [1–8] allows the splitting of a secret into different pieces, called shares or shadows, which are given to a group of participants (or shareholders). Only a certain specified subset of the participants can reconstruct the secret easily by providing their shadows, while any unqualified subsets cannot obtain any knowledge about the secret. Secret sharing is useful for any important action whose initiation requires the collective decision of several designated participants, such as the launch of a missile, opening of a bank vault, or opening of a safety deposit box. Research on secret sharing is important for the key distribution of wireless ad hoc and sensor networks [9], both in theory and in practice.

In 1979, two basic secret sharing schemes were independently proposed by Shamir [1] and Blakley [10]. They used two different methods to construct threshold secret sharing schemes. In Shamir's scheme, a secret s is divided into n shadows by a dealer and shared among n participants in such a way that it is possible to reconstruct the secret with any t or more shadows but impossible to reconstruct the secret with fewer than t shadows. This scheme is called a $(t,n)$ threshold secret sharing scheme. Early secret sharing schemes [1, 10] did not include the verification of the correctness of shadows; hence, if one or more participants are dishonest, the secret cannot be recovered correctly.

Verifiable secret sharing (VSS) was proposed in [11] to solve the problem of dishonest participants who want to deceive other honest participants or the problem of a dishonest dealer who distributes incorrect shadows to some participants. VSS has been an important area of cryptography research for the last two decades [5, 7, 8, 12–15]. Feldman [12] proposed a very practical VSS scheme in which the security is based on a discrete logarithm problem. In this scheme, a deterministic function of the secret is published; hence, it achieves only one-way security. Pedersen [13] proposed a VSS scheme that can withstand an unbounded passive adversary.

Stadler [16] proposed a publicly verifiable secret sharing (PVSS) scheme in which the validity of the shadows can be verified by anyone without knowledge of the shadows. In some PVSS schemes [5, 14], the verification procedure involves interactive proofs of knowledge. If these proofs are made noninteractive by means of the Fiat-Shamir technique [17], the security of the verification process would only be carried out in the random oracle model (ROM) [18]. Transferring security analysis of cryptographical primitives from the random oracle model to the standard model (SM) [19] has always been a theoretically important task.

1.1. Related Work

In 2005, Ruiz and Villar [15] proposed a new PVSS scheme that has a higher level of secrecy, called indistinguishability (IND) of secrets based on the decisional composite residuosity assumption. In 2009, Heidarvand and Villar [3] gave two new secure definitions of publicly verifiable secret sharing, which capture the notion of indistinguishability of shared secrets. Then they proposed a non-interactive PVSS scheme against the attacks of indistinguishability of secrets in the standard model based on the decisional bilinear square assumption (DBS) which is a natural variant of the standard decisional bilinear Diffie-Hellman (DBDH) assumption. In 2010, Jhanwar [20] proposed a PVSS scheme whose level of security is called semantic security based on the $(t,n)$ -multi-sequence of exponents Diffie-Hellman problem. In 2011, Wu and Tseng [2] proposed a pairing-based PVSS scheme. For deducing the computational cost, they used the batch verification technique. They also showed that their scheme is a secure PVSS scheme under the bilinear Diffie-Hellman (BDH) assumption in the random oracle model. In fact, semantic security does not guarantee any level of secrecy if an adversary mounts an active attack. Therefore, it is very important to design a PVSS scheme against adaptively chosen secret attacks (CSAs) in the standard model.

Another important aspect of secret sharing is the problem of making the size of shadows of each participant as small as of making the size of shadows of each. A secret sharing scheme is ideal if the length of every shadow is the same as the length of the secret. This is the best possible situation. However, we would like to emphasize that it is also very important to reduce the number of secure channels used in a secret sharing scheme, especially in wireless ad hoc and sensor networks.

A secret sharing scheme contains at least two essential phases: a share distribution phase and a secret reconstruction phase. In the share distribution phase, a dealer chooses a secret, executes a secret distribution algorithm to generate shadows, and then sends the generated shadows to the participants through point-to-point secure channels. In the secret reconstruction phase, the participants belonging to a qualified subset of participants exchange shadows amongst themselves through point-to-point secure channels to reconstruct the secret. In a $(t,n)$ threshold secret scheme, there are n secure channels in the share distribution phase and at least $O(t^{\mathrm{2}})$ secure channels in the secret reconstruction phase. To reduce the number of secure channels to $O(t)$ , Huaxiong and wong [21] constructed a $(t,n)$ threshold secret sharing scheme using partial broadcast channels.

1.2. Our Contributions

In this paper, we use the Lagrange interpolation and bilinear cyclic groups to construct a $(t,n)$ threshold PVSS scheme with IND-CSA security. Our scheme has the following features.

• (i)

Public Verifiability: a dishonest dealer or participant is detected unconditionally.

(ii)

Security: the scheme has provable security against an IND-CSA (see the security model present in this paper) adversary in the standard model. The security relies on the hardness of the decisional bilinear Diffie-Hellman (DBDH) problem.

(iii)

Needless security channels: in both the setup and share distribution phases, these are no secure point-to-point communication channels between the dealer and the participants. Moreover, no secure point-to-point communication channels are used in the reconstruction phase of the extended scheme.

(iv)

Noninteractivity: the participants need not talk to each other during the secret reconstruction phase.

An overview comparison of the major technique differences and the corresponding security level those of WT11's [2] and HV09's [3] PVSS schemes is given in Table 1.

Table 1

Major technique differences and corresponding security level.

	WT11 [2]	HV09 [3]	Ours
Needless secure channels	No	No	Yes
Verify subshare in reconstruction	No	Yes	Yes
Assumption	BDH	DBS	DBDH
Security model	ROM	SM	SM
Security level	IND	IND	IND-CSA

1.3. Paper Organization

This paper is organized as follows. In Section 2, we describe the definition of bilinear maps and the decisional bilinear Diffie-Hellman problem. In Section 3, we describe the model of our PVSS scheme and the security model. In Section 4, we present our pairing-based PVSS scheme, and in Section 5, we prove its security. In Section 6, we analyze the performance of our scheme. In Section 7, we present an extended scheme that allows reconstruction of the secret through publicle channels. Finally, we give a conclusion in Section 8.

2. Preliminaries

If S is a set, $|S|$ denotes its size. The symbol “⊥” denotes failure.

2.1. Bilinear Map

Let 𝔾 and ${𝔾}_{\mathrm{1}}$ be two cyclic groups of prime order p. Here, we assume that 𝔾 is an additive cyclic group, and ${𝔾}_{\mathrm{1}}$ is a multiplicative cyclic group. A bilinear map $e(\cdots )$ is a map $𝔾\times 𝔾\to {𝔾}_{\mathrm{1}}$ such that for $P\ne \mathrm{0}\in 𝔾$ and $\alpha ,\beta \in {\mathbb{Z}}_p\setminus \{\mathrm{0}\}$ , it satisfies the following properties [22, 23].

• (i)

Bilinearity: $e(\alpha P,\beta P)=e(P,P{)}^{\alpha \beta }$ .

(ii)

Nondegeneracy: $e(P,P)\ne {\mathrm{1}}_{{𝔾}_{\mathrm{1}}}$ unless $P={\mathrm{1}}_{𝔾}$ .

(iii)

Computability: there is an efficient algorithm to compute $e(P,Q)\hspace{0.17em}\hspace{0.17em}\text{for}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{all}\hspace{0.17em}\hspace{0.17em}P,Q\in 𝔾$ .

The algorithm $𝒢𝒢(\lambda )$ is a bilinear group generator that takes a secure parameter $\lambda \in \mathbb{Z}$ as input and outputs the descriptions of the groups 𝔾, ${𝔾}_{\mathrm{1}}$ , and a bilinear map $e:𝔾\times 𝔾\to {𝔾}_{\mathrm{1}}$ , where all group operations in 𝔾 and ${𝔾}_{\mathrm{1}}$ as well as map e can be computed in polynomial time with λ. We posit that $B=(p,P,𝔾,{𝔾}_{\mathrm{1}},e(\cdots )$ ) is the output of $𝒢𝒢(\lambda )$ .

2.2. Decisional Bilinear Diffie-Hellman Assumption

Given a tuple $P,aP,bP,cP\in 𝔾$ for some uniformly chosen $a,b,c\in {\mathbb{Z}}_p\setminus \{\mathrm{0}\}$ and $T\in {𝔾}_{\mathrm{1}}$ as input to decide whether or not $T=e(P,P{)}^{abc}$ . The advantage of an algorithm 𝒜 solving the DBDH problem is defined as

$$\begin{array}{ll}& |\text{Pr}[𝒜(P,aP,bP,cP,e{\left(P,P\right)}^{abc}=\mathrm{1}]\mathrm{\hspace{0.17em}\hspace{0.17em}}\\ \hspace{1em}-\text{Pr}\left[𝒜\left(P,aP,bP,cP,T\right)=\mathrm{1}\right]\phantom{{\left(P,P\right)}^{\text{abc}}}|.\end{array}$$

(1)

The DBDH problem is said to be $(t,ϵ)$ -hard if there is no algorithm that can solve the DBDH problem within time t with an advantage equal to at least ϵ.

2.3. Lagrange Interpolation

Let $f(x)={\sum }_{j=\mathrm{0}}^{t-\mathrm{1}}‍{\alpha }_j{x}^j$ be a polynomial over ${\mathbb{Z}}_p$ with degree $t-\mathrm{1}$ , and let $(x_{\mathrm{1}},f(x_{\mathrm{1}})),(x_{\mathrm{2}},f(x_{\mathrm{2}})),\dots ,(x_t,f(x_t))$ be t distinct points of $f(x)$ . Then, given $(x_{\mathrm{1}},f(x_{\mathrm{1}}))$ , $(x_{\mathrm{2}},f(x_{\mathrm{2}})),\dots ,(x_t,f(x_t))$ , one can reconstruct $f(x)$ as

$$\begin{array}{cc}& f\left(x\right)=f\left(x_{\mathrm{1}}\right){\lambda }_{x_{\mathrm{1}}}^x+f\left(x_{\mathrm{2}}\right){\lambda }_{x_{\mathrm{2}}}^x+\cdots +f\left(x_t\right){\lambda }_{x_t}^x,\end{array}$$

(2)

where

$$\begin{array}{cc}& {\lambda }_{x_j}^x=\frac{(x-x_{\mathrm{1}})\cdots (x-x_{j-\mathrm{1}})(x-x_{j+\mathrm{1}})\cdots (x-x_t)}{(x_j-x_{\mathrm{1}})\cdots (x_j-x_{j-\mathrm{1}})(x_j-x_{j+\mathrm{1}})\cdots (x_j-x_t)},\end{array}$$

(3)

for any $\mathrm{1}\le j\le t$ .

3. Definitions

This section is dedicated to the definition of a $(t,n)$ threshold PVSS scheme and its security model.

3.1. Threshold PVSS Scheme without Secure Channels

Let $𝒰=(U_{\mathrm{1}},\dots ,U_n)$ be a set of n participants. A dealer wants to share a secret 𝒮 among the participants of 𝒰 in such a way that any t or more participants can recover the secret, while no $t-\mathrm{1}$ participants can obtain any information about the secret.

A PVSS scheme is described by the following algorithms.

• (1)

Setup $(\lambda )$ : takes as input a secure parameter λ.

• (i)

The dealer generates all public parameters of the scheme.

(ii)

Furthermore, every participant selects its channel protection key $d_i$ and publishes the corresponding public key $D_i$ .

(iii)

The dealer randomly picks a number as the main secret of the system and uses $D_i\hspace{0.17em}\hspace{0.17em}(i=\mathrm{1,2},\dots ,n)$ and the main secret to generate a main shadow $Y_i\mathrm{\hspace{0.17em}\hspace{0.17em}}(i=\mathrm{1,2},\dots ,n)$ for every participant and the system shadow verification key (SVK).

(iv)

For each $U_i$ , the dealer sends $U_i$ 's main shadow $Y_i$ to $U_i$ through public channels.

(2)

Secret distribution: the dealer randomly selects a secret S that will be distributed to the participants. It calculates and publishes the secret commitment value (SCV) $s_{\mathrm{1}}$ and the secret deriving value (SDV) $s_{\mathrm{2}}$ of the secret S. It then outputs $(s_{\mathrm{1}},s_{\mathrm{2}})$ . A participant can use $s_{\mathrm{1}}$ and its main-shadow $Y_i$ to obtain its subshadow of the secret S by itself.

(3)

Verification $\mathbf{(}{s}_{\mathrm{1}},s_{\mathrm{2}}\mathbf{)}$ : takes as inputs $s_{\mathrm{1}}$ and $s_{\mathrm{2}}$ of a secret. It is required that $s_{\mathrm{1}}$ be publicle verifiable. Knowing only the publicly parameter, anyone may verify that $s_{\mathrm{2}}$ is consistent with $s_{\mathrm{1}}$ . If the verification fails, the verifier broadcasts a complaint about the dealer.

(4)

Reconstruction: this algorithm is composed of three subalgorithms.

• (a)

Subshadow generation $(s_{\mathrm{1}},s_{\mathrm{2}},U_i,Y_i,d_i)$ : takes as inputs $s_{\mathrm{1}}$ and $s_{\mathrm{2}}$ of a secret, a participant $U_i$ , $U_i$ 's main shadow $Y_i$ , and $U_i$ 's channel protection key $d_i$ . To generate its sub-shadow, $U_i$ executes verification ( $s_{\mathrm{1}},s_{\mathrm{2}}$ ). If the verification fails, $(i,\perp )$ is output. Otherwise, $U_i$ generates the sub-shadow $S_i$ from $s_{\mathrm{1}}$ and $s_{\mathrm{2}}$ using its main shadow $Y_i$ and channel protection key $d_i$ . $(i,S_i)$ is then output.

(b)

Sub-shadow verification   $(s_{\mathrm{1}},U_i,\text{SV}{\text{K}}_i,S_i)$ : takes as inputs $s_{\mathrm{1}}$ of a secret, a participant $U_i$ and $U_i$ 's verification key $\text{SV}{\text{K}}_i$ , and $U_i$ 's sub-shadow $S_i$ . This algorithm checks whether $S_i$ is a valid sub-shadow with respect to $\text{SV}{\text{K}}_i$ and $s_{\mathrm{1}}$ . If the verification fails, a complaint about the participant $U_i$ is broadcast.

(c)

Combine $(s_{\mathrm{1}},s_{\mathrm{2}},\mathrm{\Gamma },\mathrm{\Omega })$ : takes as inputs $s_{\mathrm{1}}$ and $s_{\mathrm{2}}$ of a secret, a qualified set $\mathrm{\Gamma }\subseteq 𝒰$ of t participants, and a list $\mathrm{\Omega }=(S_{\mathrm{1}},\dots ,S_t)$ of t valid sub-shadows. Outputs a secret S.

3.2. Security Model

The PVSS scheme described above must satisfy the following properties.

• (i)

Correctness: if the dealer and the participants act honestly, any t or more participants can reconstruct the secret correctly during the execution of the reconstruction algorithm.

(ii)

Verifiability: a successful verification of the SCV and SDV of a secret implies that the SCV and SDV are consistent.

(iii)

Privacy: the basic requirement is that it is impossible for any collusion of less than t participants to obtain any information about a secret.

Hereafter, we will use the notion of a CSA to define the security of the PVSS scheme. We mostly follow the notation from [19, 23], using a game between an adversary 𝒜 and a challenger 𝒞.

• (i)

  Init. 𝒞 executes Setup  (λ) to obtain the public parameters and sends the public parameters to 𝒜 along with all of the shadow verification keys SVK.

• (ii)

  Phase 1. The adversary adaptively selects a secret and generates $(s_{\mathrm{1}},s_{\mathrm{2}})$ about the secret using the public parameters just as the dealer does. Moreover, the adversary 𝒜 is permitted to query a sub-shadow of a participant using $(s_{\mathrm{1}},s_{\mathrm{2}})$ .

• (iii)

  Sub-shadow query. On being input a participant $U_i$ , as well as $s_{\mathrm{1}}$ and $s_{\mathrm{2}}$ , 𝒞 executes the Sub-shadow generation sub-algorithm using $(s_{\mathrm{1}},s_{\mathrm{2}}),Y_i$ and $d_i$ then forwards the resulting $(i,S_i)$ or $(i,\perp )$ to the adversary 𝒜.

• (iv)

  Challenge. The adversary 𝒜 outputs a target set of participants ${𝕌}^{*}$ , where $|{𝕌}^{*}|<t$ . The challenger 𝒞 picks two random secrets $T_{\mathrm{0}}$ and $T_{\mathrm{1}}$ as well as a random bit $\delta \in \{\mathrm{0,1}\}$ . Then, 𝒞 executes the secret distribution algorithm to obtain $(s_{\mathrm{1}}^{*},s_{\mathrm{2}}^{*})$ for the secret $T_{\delta }$ and sends $(s_{\mathrm{1}}^{*},s_{\mathrm{2}}^{*})$ and all the sub-shadows of each $U_i^{*}\in {𝕌}^{*}$ to 𝒜 along with $T_{\mathrm{0}}$ and $T_{\mathrm{1}}$ .

• (v)

  Phase 2. The adversary continues to adaptively issue the subshadow query as in phase 1, but with the constraint that $(s_{\mathrm{1}},s_{\mathrm{2}})\ne (s_{\mathrm{1}}^{*},s_{\mathrm{2}}^{*})$ , and challenger 𝒞 responds similarly in phase 1.

• (vi)

  Guess. Finally, the adversary 𝒜 outputs a guess ${\delta }^{\prime }\in \{\mathrm{0,1}\}$ and wins the game if $\delta ={\delta }^{\prime }$ .

Definition 1 (IND-CSA security).

A $(t,n)$ PVSS scheme has indistinguishability against adaptive CSA if, for any probabilistic polynomial-time (PPT) adversary 𝒜, the advantage

$$\begin{array}{cc}& \text{AD}{\text{V}}_{𝒜,t,n}^{\text{IND-CSA}}\left(\lambda \right)=\text{Pr}[\delta ={\delta }^{\prime }]-\frac{\mathrm{1}}{\mathrm{2}}\end{array}$$

(4)

is negligible with respect to λ.

4. Construction

In this section, we present a concrete $(t,n)$ PVSS scheme and prove its security against CSA in the next section.

Setup

The dealer obtains the group parameters $(p,P,𝔾,{𝔾}_{\mathrm{1}},e(\cdots ))$ by executing the group generator algorithm $𝒢𝒢(\lambda )$ . It then selects a random integer $\gamma \in {\mathbb{Z}}_p\setminus \{\mathrm{0}\}$ and publishes $(p,𝔾,{𝔾}_{\mathrm{1}},e(\cdots )$ , $P,P_{\mathrm{2}}=\gamma P)$ on the system bulletin board (BB). Supposing that $𝒰=\{U_{\mathrm{1}},\dots ,U_n\}$ is the set of participants of the system, each participant may be uniquely identified by means of an index $i\in \{\mathrm{1},\dots ,n\}$ . After the dealer has announced the public parameters, each participant $U_i$ randomly selects an integer $d_i\in {\mathbb{Z}}_p\setminus \{\mathrm{0}\}$ ( $d_i$ is $U_i$ 's channel protection key) and calculates $D_i=d_i{P}_{\mathrm{2}}$ . Each participant keeps $d_i$ confidentially and sends $D_i$ to the dealer over public channels.

Having received all the $D_i$ , the dealer performs the following operations.

• (1)

The dealer selects a random number $\alpha \in {\mathbb{Z}}_p\setminus \{\mathrm{0}\}$ and a random polynomial $f(x)=\alpha +{\sum }_{j=\mathrm{1}}^{t-\mathrm{1}}‍{\alpha }_j{x}^j$ with degree $t-\mathrm{1}$ , where t is the threshold value and, for $j=\mathrm{1},\dots ,t-\mathrm{1}$ , ${\alpha }_j\in {\mathbb{Z}}_p\setminus \{\mathrm{0}\}$ .

(2)

The dealer computes $P_{\mathrm{1}}=\alpha P$ and $Y_i=f(i)D_i\mathrm{\hspace{0.17em}\hspace{0.17em}}(\text{for}\hspace{0.17em}\hspace{0.17em}i=\mathrm{1},\dots ,n)$ , where $Y_i$ is the main shadow of the participant $U_i$ .

(3)

The dealer selects a collision-resistant hash function $H:𝔾\to \{\mathrm{0,1}{\}}^l$ , where l is the output length of H.

(4)

The dealer sets the $\text{SVK}=(f(\mathrm{1})P,f(\mathrm{2})P,\dots ,f(n)P)$ as the shadow verification key.

(5)

The dealer randomly selects $u^{\prime },u_{\mathrm{1}},u_{\mathrm{2}},\dots ,u_l\in 𝔾$ .

Finally, the dealer sends $Y_i$ to the participant $U_i\mathrm{\hspace{0.17em}\hspace{0.17em}}(i=\mathrm{1},\dots ,n)$ through public channels and publishes $(P_{\mathrm{1}},H,u^{\prime },u_{\mathrm{1}},u_{\mathrm{2}},\dots ,u_l,\text{SVK})$ on the bulletin board.

Secret Distribution

The dealer wants to share a secret, which is a random element in ${𝔾}_{\mathrm{1}}$ . The form of the secret is $𝒮=e(P_{\mathrm{1}},P_{\mathrm{2}}{)}^k$ , where k is selected randomly from ${\mathbb{Z}}_p\setminus \{\mathrm{0}\}$ . Let v be a bit string of length l, let $v_i$ denote the ith bit of v, and let $𝒱\subseteq \{\mathrm{1},\dots ,l\}$ be the set of all i for which $v_i=\mathrm{1}$ . The dealer calculates and publishes the SCV $s_{\mathrm{1}}$ and SDV $s_{\mathrm{2}}$ as follows:

$$\begin{array}{cc}& s_{\mathrm{1}}=kP,\\ v=H\left(s_{\mathrm{1}}\right),\\ s_{\mathrm{2}}=k\left(u^{\prime }+\sum _{i\in 𝒱}{u}_i\right).\end{array}$$

(5)

The dealer either broadcasts $(s_{\mathrm{1}},s_{\mathrm{2}})$ to all participants or publishes $(s_{\mathrm{1}},s_{\mathrm{2}})$ on the BB. ( $U_i$ 's real sub-shadow $S_i$ for the secret 𝒮 is $e(s_{\mathrm{1}},-d_{i}f(i)D_i)$ . In order to achieve CSA security, in the reconstruction algorithm, no participant $U_i$ directly sends $S_i$ to other participants.) If the dealer wants to share a new secret, it just executes the secret distribution algorithm again and publishes appropriate information on the BB. However, the main shadow $Y_i$ of $U_i$ need not be changed.

Verification

Given $(s_{\mathrm{1}},s_{\mathrm{2}})$ , this algorithm first computes $v=H(s_{\mathrm{1}})$ and outputs “valid” or “invalid” according to the following:

$$\begin{array}{cc}& e\left(s_{\mathrm{2}},P\right)=e\left(u^{\prime }+\sum _{i\in 𝒱}{u}_i,s_{\mathrm{1}}\right).\end{array}$$

(6)

Reconstruction

Without loss of generality, let us assume that $\mathrm{\Gamma }=\{\mathrm{1},\dots ,t\}$ is a qualified subset of the set of participants, that is, it consists of at least t participants who want to collectively reconstruct the secret 𝒮. Each participant in Γ executes the following algorithms:

• (1)

Sub-shadow generation $(s_{\mathrm{1}},s_{\mathrm{2}},U_i,Y_i,d_i)$ : takes as inputs $s_{\mathrm{1}}$ and $s_{\mathrm{2}}$ a participant $U_i$ , $U_i$ 's main shadow $Y_i$ , and $U_i$ 's channel protection key $d_i$ . To generate its sub-shadow, $U_i$ executes the verification ( $s_{\mathrm{1}},s_{\mathrm{2}}$ ) algorithm. If the verification fails, $U_i$ outputs ( $i,\perp$ ) and exits. Otherwise, $U_i$ randomly selects ${\beta }_i\in {\mathbb{Z}}_p\setminus \{\mathrm{0}\}$ and performs the following calculations:

$$\begin{array}{cc}& v=H\left(s_{\mathrm{1}}\right),\\ {\mu }_{i\mathrm{1}}=(-d_i)Y_i+{\beta }_i(u^{\prime }+\sum _{j\in 𝒱}{u}_j),\\ {\mu }_{i\mathrm{2}}={\beta }_{i}P.\end{array}$$

(7)

At this point, $U_i$ sends $S_i=\{{\mu }_{i\mathrm{1}},{\mu }_{i\mathrm{2}}\}$ to the other participants in Γ through secure channels. ( $U_i$ may use the method described in Section 7 to send $S_i=\{{\mu }_{i\mathrm{1}},{\mu }_{i\mathrm{2}}\}$ through public channels.)

(2)

Sub-shadow verification $(s_{\mathrm{1}},U_i,\text{SV}{\text{K}}_i,S_i)$ : takes as inputs $s_{\mathrm{1}}$ for a secret, a participant $U_i$ , and $U_i$ 's verification key $\text{SV}{\text{K}}_i$ , $U_i$ 's sub-shadow $S_i=\{{\mu }_{i\mathrm{1}},{\mu }_{i\mathrm{2}}\}$ . Another participant $U_j\in \mathrm{\Gamma }$ computes $v=H(s_{\mathrm{1}})$ and then checks

$$\begin{array}{cc}& e({\mu }_{i\mathrm{1}},P)=e(P_{\mathrm{2}},\text{SV}{\text{K}}_i)e\left(u^{\prime }+\sum _{j\in 𝒱}{u}_j,{\mu }_{i\mathrm{2}}\right).\end{array}$$

(8)

If the checked equality does not hold, $U_j$ demands that $U_i$ sends $({\mu }_{i\mathrm{1}},{\mu }_{i\mathrm{2}})$ again or declares that $U_i$ is a cheater.

(3)

Combine $(s_{\mathrm{1}},s_{\mathrm{2}},\mathrm{\Gamma },\mathrm{\Omega })$ : takes as input $s_{\mathrm{1}}$ and $s_{\mathrm{2}}$ for a secret, a qualified subset $\mathrm{\Gamma }\subseteq 𝒰$ of the set of participants that contains at least t participants, and a list $\mathrm{\Omega }=(S_{\mathrm{1}},\dots ,S_t)$ (where $S_i=\{{\mu }_{i\mathrm{1}},{\mu }_{i\mathrm{2}}\}$ ) of t valid subshadows. Each participant $U_i\in \mathrm{\Gamma }$ first computes the Lagrange coefficients ${\lambda }_{\mathrm{1}}^{\mathrm{0}},{\lambda }_{\mathrm{2}}^{\mathrm{0}},\dots ,{\lambda }_n^{\mathrm{0}}\in {\mathbb{Z}}_p$ , where ${\lambda }_i^{\mathrm{0}}={\prod }_{j\ne i,j\in \{\mathrm{1},\dots ,t\}}((\mathrm{0}-j)/(i-j))$ , then calculates

$$\begin{array}{cc}& {\mu }_{\mathrm{1}}=\sum _{i=\mathrm{1}}^t‍{\lambda }_i^{\mathrm{0}}{\mu }_{i\mathrm{1}},\\ {\mu }_{\mathrm{2}}=\sum _{i=\mathrm{1}}^t‍{\lambda }_i^{\mathrm{0}}{\mu }_{i\mathrm{2}}.\end{array}$$

(9)

At this point, every participant in Γ uses $(s_{\mathrm{1}},s_{\mathrm{2}},{\mu }_{\mathrm{1}},{\mu }_{\mathrm{2}}$ ) to reconstruct the secret 𝒮 as follows:

$$\begin{array}{cc}& 𝒮=\frac{e(s_{\mathrm{1}},{\mu }_{\mathrm{1}})}{e(s_{\mathrm{2}},{\mu }_{\mathrm{2}})}.\end{array}$$

(10)

5. Security and Correctness

5.1. Correctness

If the dealer and the participants are honest, any t or more participants can reconstruct the secret during the execution of the reconstruction algorithm. The correctness of equalities (6), (9), and (10) is as follows.

$$\begin{array}{lll}e({\mu }_{i1},P)\hfill & =\hfill & e\left(-d_i{Y}_i+{\beta }_i\left(u^{\text{'}}+\sum _{j\in 𝒱}{u}_j\right),P\right)\hfill \\ \hfill & =\hfill & e(P_2,f(i)P)e\left(u^{\text{'}}\sum _{j\in 𝒱}{u}_j,{\beta }_{i}P\right)\hfill \\ \hfill & =\hfill & e(P_2,{\text{SVK}}_i)e\left(u^{\text{'}}+\sum _{j\in 𝒱}{u}_j,{\mu }_{i2}\right),\hfill \end{array}$$

(11)

$$\begin{array}{lll}{\mu }_1\hfill & =\hfill & \sum _{i=1}^t{\lambda }_i^0{\mu }_{i1}\hfill \\ \hfill & =\hfill & \sum _{i=1}^t\left({\lambda }_i^0(-d_i)Y_i+{\lambda }_i^0{\beta }_i\left(u^{\text{'}}+\sum _{j\in 𝒱}{u}_j\right)\right)\hfill \\ \hfill & =\hfill & \sum _{i=1}^t{\lambda }_i^{0}f(i)P_2+\sum _{i=1}^t{\beta }_i{\lambda }_i^0\left(u^{\text{'}}+\sum _{j\in 𝒱}{u}_j\right)\hfill \\ \hfill & =\hfill & \alpha P_2+\sum _{i=1}^t{\beta }_i{\lambda }_i^0\left(u^{\text{'}}\sum _{j\in 𝒱}{u}_j\right),\hfill \end{array}$$

(12)

$$\begin{array}{lll}{\mu }_2\hfill & =\hfill & \sum _{i=1}^t{\lambda }_i^0{\mu }_{i2}\hfill \\ \hfill & =\hfill & \sum _{i=1}^t\left({\beta }_i{\lambda }_i^0\right)P\hfill \end{array}$$

(13)

$$\begin{array}{lll}\delta \hfill & =\hfill & \frac{e(s_1,{\mu }_1)}{e(s_2,{\mu }_2)}\hfill \\ \hfill & =\hfill & \frac{e(kP,\alpha P_2+{\sum }_{i=1}^t{\beta }_i{\lambda }_i^0(u^{\text{'}}+{\sum }_{j\in 𝒱}{u}_j))}{e(k{u}^{\text{'}}+k{\sum }_{i\in 𝒱}{u}_i,{\sum }_{i=1}^t({\beta }_i{\lambda }_i^0)P)}\hfill \\ \hfill & =\hfill & \frac{e(kP,\alpha P_2)e(kP,{\sum }_{i=1}^t{\beta }_i{\lambda }_i^0(u^{\text{'}}+{\sum }_{j\in 𝒱}{u}_j))}{e(kP,\sum _{i=1}^t{\beta }_i{\lambda }_i^0(u^{\text{'}}+{\sum }_{j\in 𝒱}{u}_j))}\hfill \\ \hfill & =\hfill & e{(P_1,P_2)}^k.\hfill \end{array}$$

(14)

5.2. Security

Theorem 2 (IND-CSA of PVSS).

Suppose the hash function H is a universal collision-resistant one-way family. Then, the proposed PVSS scheme is secure against adaptive CSA under the intractability assumption of the DBDH problem. More specifically, if there is an adversary that can break the PVSS scheme within time 𝒯 with probability at least ϵ, then there exists an algorithm that can solve the DBDH problem within time ${𝒯}^{\prime }$ with probability at least ${ϵ}^{\prime }$ , where

$$\begin{array}{cc}& {𝒯}^{\prime }=𝒯+{𝒯}_Q,\hspace{1em}\hspace{1em}{ϵ}^{\prime }\ge \frac{\mathrm{3}}{\mathrm{4}}ϵ.\end{array}$$

(15)

Here, ${𝒯}_Q$ denotes the time taken to answer all queries.

Proof.

Suppose an adversary 𝒜 breaks the PVSS scheme with advantage $\text{AD}{\text{V}}_{𝒜,t,n,q}^{\text{IND-CSA}}>ϵ$ . Then we can devise an algorithm ℛ that solves a random DBDH problem instance with advantage ${ϵ}^{\prime }\ge (\mathrm{3}/\mathrm{4})ϵ$ . Algorithm ℛ is given as input a group parameter $B=(p,P,𝔾,{𝔾}_{\mathrm{1}},e(\cdots ))$ and a random tuple $(𝔾,P,aP,bP,cP,T)$ , where T is a random element of ${𝔾}_{\mathrm{1}}$ or $T=e(P,P{)}^{abc}$ . The goal of algorithm ℛ is to output 1 (“true”) if $T=e(P,P{)}^{abc}$ and 0 (“false”) otherwise. Set $P_{\mathrm{1}}=aP,P_{\mathrm{2}}=bP,P_{\mathrm{3}}=cP$ . Algorithm ℛ works by interacting with 𝒜 in a game as follows:

Init. Algorithm ℛ does the following.

• (1)

Algorithm ℛ chooses a set 𝕌 containing $t-\mathrm{1}$ participants. Without loss of generality, let $𝕌=\{U_{\mathrm{1}},\dots ,U_{t-\mathrm{1}}\}\subset 𝒰=\{U_{\mathrm{1}},\dots ,U_n\}$ .

(2)

Algorithm ℛ selects a collision-resistant hash function $H:𝔾\to \{\mathrm{0,1}{\}}^l$ and computes the public keys for all participants in 𝒰 as follows: $D_i=d_i{P}_{\mathrm{2}},$ for all  $i\in 𝒫$ and $d_i\stackrel{R}{\leftarrow }{\mathbb{Z}}_p\setminus \{\mathrm{0}\}$ , where $d_i$ is the channel protection key of $U_i$ .

(3)

Algorithm ℛ selects $t-\mathrm{1}$ random integers ${\alpha }_i\in {\mathbb{Z}}_p$ , where $i=\mathrm{1},\dots ,t-\mathrm{1},$ and   ${\alpha }_{t-\mathrm{1}}\ne \mathrm{0}$ . There exists a polynomial $f(x)\in {\mathbb{Z}}_p[X]$ of degree $t-\mathrm{1}$ such that for all   $U_i\in 𝕌,f(\mathrm{0})=a$ and $f(i)={\alpha }_i$ . However, ℛ does not know the polynomial f, because it does not know a.

(4)

Algorithm ℛ constructs the shadow verification key SVK as follows.

• (i)

If $U_i\in 𝕌$ , since ℛ knows $f(i)={\alpha }_i$ , he can compute the shadow verification key $\text{SV}{\text{K}}_i=f(i)P={\alpha }_{i}P$ .

(ii)

If $U_i\notin 𝕌$ , ℛ computes the Lagrange coefficients ${\lambda }_{\mathrm{0}}^i,{\lambda }_{\mathrm{1}}^i,{\lambda }_{\mathrm{2}}^i,\dots ,{\lambda }_{k-\mathrm{1}}^i\in {\mathbb{Z}}_p$ , such that $f(i)={\lambda }_{\mathrm{0}}^{i}f(\mathrm{0})+{\sum }_{j=\mathrm{1}}^{t-\mathrm{1}}‍{\lambda }_j^{i}f(j)$ . Algorithm ℛ then sets

$$\begin{array}{cc}& \text{SV}{\text{K}}_i={\lambda }_{\mathrm{0}}^{i}aP+{\lambda }_{\mathrm{1}}^i{\alpha }_{\mathrm{1}}P\cdots +{\lambda }_{t-\mathrm{1}}^i{\alpha }_{t-\mathrm{1}}P,\end{array}$$

(16)

which entails that $\text{SV}{\text{K}}_i=f(i)P$ , as required.

(5)

Algorithm ℛ follows Waters' [24] method to simulate it as follows.

• (i)

For v, it lets $𝒱\subseteq \{\mathrm{1},\dots ,l\}$ be the set of all i for which $v_i=\mathrm{1}$ .

(ii)

It sets an integer $m=\mathrm{4}q$ (where q is the maximum number of sub-shadow queries) and randomly chooses an integer k between 0 and l.

(iii)

It chooses a random vector $\overrightarrow{x}=(x_i)$ of length l, where $x_i\in \{\mathrm{0},m-\mathrm{1}\}$ .

(iv)

It lets $v^{\prime }=H(cP)$ , and computes $x^{\prime }=km-{\sum }_{i\in v^{\prime }}‍x_i$ .

(v)

It chooses a random integer $h^{\prime }\in {\mathbb{Z}}_p$ and a vector $\overrightarrow{h}=(h_i)$ of length l, where $h_i\in {\mathbb{Z}}_p$ .

(vi)

It sets $u^{\prime }=(p-km+x^{\prime })P_{\mathrm{2}}+h^{\prime }P$ , $u_i=x_i{P}_{\mathrm{2}}+h_{i}P$ .

(vii)

It defines $F(v)=(p-mk)+x^{\prime }+{\sum }_{i\in 𝒱}{x}_i$ , $J(v)=h^{\prime }+{\sum }_{i\in 𝒱}‍h_i$ and

$$\begin{array}{cc}& K\left(v\right)=\{\begin{array}{cc}\mathrm{0},\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}{x}^{\prime }+\sum _{i\in 𝒱}{x}_i\equiv \mathrm{0}\left(\mathrm{mod}\hspace{0.17em}m\right),\hfill \\ \mathrm{1},\hfill & \text{otherwise}.\hfill \end{array}\end{array}$$

(17)

(6)

Algorithm ℛ sends $(B,P,P_{\mathrm{1}},P_{\mathrm{2}},H,e(\cdots ),\hspace{0.17em}\text{SV}{\text{K}}_i\hspace{0.17em}\hspace{0.17em}(i=\mathrm{1,2},\dots ,n),u^{\prime },u_i\mathrm{\hspace{0.17em}\hspace{0.17em}}(i=$ $\mathrm{1},\dots ,l))$ to the adversary 𝒜.

Phase 1. The adversary 𝒜 adaptively selects a secret ${𝒮}^{\prime }=e(P_{\mathrm{1}},P_{\mathrm{2}}{)}^{k^{\prime }}$ and generates $(s_{\mathrm{1}},s_{\mathrm{2}})$ for the secret ${𝒮}^{\prime }$ using the public parameters $\{P_{\mathrm{1}},P_{\mathrm{2}},e(\cdots )\}$ just as the dealer does. Then, 𝒜 adaptively issues a sub-shadow query of the form $\{i,(s_{\mathrm{1}},s_{\mathrm{2}})\}$ , where $i\in \{\mathrm{1},\dots ,n\}$ . For each such sub-shadow query the following applies.

• (1)

The algorithm ℛ computes $v=H(s_{\mathrm{1}})$ and checks $e(s_{\mathrm{2}},P)=e(u^{\prime }+{\sum }_{i\in 𝒱}‍u_i,s_{\mathrm{1}})$ . If the equality does not hold, ℛ responds to 𝒜's query with $(i,\perp )$ .

(2)

Otherwise, ℛ continues to check whether $K(𝒱)=\mathrm{0}$ holds. If it does hold, ℛ aborts the game and randomly selects a bit as the answer to the DBDH problem.

(3)

Otherwise, there are two different cases as follows.

• (i)

If $i\in \{\mathrm{1},\dots ,t-\mathrm{1}\}$ , computing ${\mu }_{i\mathrm{1}},\hspace{0.17em}{\mu }_{i\mathrm{2}}$ is easy, because $f(i)$ is equal to one of the ${\alpha }_{\mathrm{1}},\dots ,{\alpha }_{t-\mathrm{1}}$ , which are known to ℛ. Thus, ℛ randomly selects ${\beta }_i\in {\mathbb{Z}}_p\setminus \{\mathrm{0}\}$ and performs the following calculations:

$$\begin{array}{ll}& {\mu }_{i\mathrm{1}}=\left(-d_i\right)Y_i+{\beta }_i\left(u^{\prime }+\sum _{j\in 𝒱}{u}_j\right)\\ ={\alpha }_i{P}_{\mathrm{2}}+{\beta }_i\left(u^{\prime }+\sum _{j\in 𝒱}{u}_j\right),\\ {\mu }_{i\mathrm{2}}={\beta }_{i}P.\end{array}$$

(18)

ℛ sends the sub-shadow $S_i=({\mu }_{i\mathrm{1}},{\mu }_{i\mathrm{2}})$ of $U_i$ to 𝒜.

(ii)

If $i\notin \{\mathrm{1},\dots ,t-\mathrm{1}\}$ , ℛ randomly selects ${\beta }_i\in {\mathbb{Z}}_p\setminus \{\mathrm{0}\}$ and performs the following calculations:

$$\begin{array}{cc}& {\mu }_{i\mathrm{1}}=\frac{-J\left(𝒱\right){\lambda }_{\mathrm{0}}^i}{F\left(𝒱\right)}{P}_{\mathrm{1}}+{\beta }_i\left(u^{\prime }+\sum _{j\in 𝒱}{u}_j\right)+\chi ,\\ {\mu }_{i\mathrm{2}}={\beta }_{i}P+\frac{-{\lambda }_{\mathrm{0}}^i}{F\left(𝒱\right)}{P}_{\mathrm{1}},\end{array}$$

(19)

where $\chi ={\sum }_{j=\mathrm{1}}^{t-\mathrm{1}}‍{\lambda }_j^i{\alpha }_j{P}_{\mathrm{2}}$ .

We claim that $S_i=\{{\mu }_{i\mathrm{1}},{\mu }_{i\mathrm{2}}\}$ is a valid sub-shadow for $\{i,(s_{\mathrm{1}},s_{\mathrm{2}})\}$ . To see this, let ${\tilde{\beta }}_i={\beta }_i-(a{\lambda }_{\mathrm{0}}^i/F(𝒱)$ ). Then we have

$$\begin{array}{lll}{\mu }_{i1}\hfill & =\hfill & \frac{-J(𝒱){\lambda }_0^i}{F(𝒱)}{P}_1+{\beta }_i\left(u^{\text{'}}+\sum _{j\in 𝒱}{u}_j\right)+\chi \hfill \\ \hfill & =\hfill & \frac{-j(𝒱){\lambda }_0^i}{F(𝒱)}{P}_1+{\beta }_{i}F(𝒱)P_2+{\beta }_{i}J(𝒱)P+\chi \hfill \\ \hfill & =\hfill & \alpha {\lambda }_0^i{P}_2+\frac{-\alpha F(𝒱){\lambda }_0^i}{F(𝒱)}{P}_2+\frac{-J(𝒱){\lambda }_0^i}{F(𝒱)}{P}_1\hfill \\ \hfill & =\hfill & +{\beta }_{i}F(𝒱)P_2+{\beta }_{i}J(𝒱)P+\chi \hfill \\ \hfill & =\hfill & \alpha {\lambda }_0^i{P}_2+\frac{-\alpha {\lambda }_0^i}{F(𝒱)}(F(𝒱)P_2+J(𝒱)P)\hfill \\ \hfill & =\hfill & +{\beta }_{i}F(𝒱)P_2+{\beta }_{i}J(𝒱)P+\chi \hfill \\ \hfill & =\hfill & \alpha {\lambda }_0^i{P}_2+\sum _{j=1}^{t-1}{\lambda }_j^i{\alpha }_j{P}_2+\left({\beta }_i-\frac{\alpha {\lambda }_0^i}{(𝒱)}\right)\hfill \\ \hfill & =\hfill & \times (F(𝒱)P_2+J(𝒱)P)\hfill \\ \hfill & =\hfill & f(i)P_2+\left({\beta }_i-\frac{\alpha {\lambda }_0^i}{F(𝒱)}\right)\left(u^{\text{'}}+\sum _{j\in 𝒱}{u}_j\right)\hfill \\ \hfill & =\hfill & f(i)(-d_i)D_i{\tilde{\beta }}_i\left(u^{\text{'}}+\sum _{j\in 𝒱}{u}_j\right),\hfill \\ {\mu }_{i2}\hfill & =\hfill & {\beta }_{i}P+\frac{-{\lambda }_0^i}{F(𝒱)}{P}_1\hfill \\ \hfill & =\hfill & {\beta }_{i}P+\frac{-a{\lambda }_0^i}{F(𝒱)}P={\tilde{\beta }}_{i}P.\hfill \end{array}$$

(20)

Since ${\tilde{\beta }}_i$ is uniform in ${\mathbb{Z}}_p$ , the sub-shadow $S_i=({\mu }_{i\mathrm{1}},{\mu }_{i\mathrm{2}})$ of the participant $U_i$ is a valid response to 𝒜.

Challenge. Once the adversary 𝒜 has completed phase 1, and sent a challenge set ${𝕌}^{*}$ , where $|{𝕌}^{*}|<t$ , the algorithm ℛ can form the following challenge information. Let $v^{*}=H(P_{\mathrm{3}})$ , so that there is $F(v^{*})\equiv \mathrm{0}(\mathrm{mod}p)$ . Then, algorithm ℛ selects T as the secret and computes $(s_{\mathrm{1}}^{*},s_{\mathrm{2}}^{*})$ as follows.

$$\begin{array}{cc}& s_{\mathrm{1}}^{*}=P_{\mathrm{3}},\\ s_{\mathrm{2}}^{*}=cJ\left(v^{*}\right)P=c\left(u^{\prime }+\sum _{i\in {𝒱}^{*}}{u}_i\right).\end{array}$$

(21)

Thus, the secret T is of the required form as described in the scheme, whenever $T=e(P,P{)}^{abc}=e(P_{\mathrm{1}},P_{\mathrm{2}}{)}^c$ .

Algorithm ℛ computes the sub-shadow of each $U_i^{*}\in {𝕌}^{*}$ as follows:

• (i)

If $U_i^{*}\in 𝕌$ , the sub-shadow of $U_i^{*}$ is $({\mu }_{i\mathrm{1}}^{*},{\mu }_{i\mathrm{2}}^{*})=$ $({\beta }_i{a}_i(u^{\prime }+{\sum }_{j\in 𝒱}‍u_j)P_{\mathrm{2}},{\beta }_{i}P)$ , where $v=H(s_{\mathrm{1}}^{*})$ .

(ii)

If $U_i^{*}\notin 𝕌$ , the sub-shadow of $U_i^{*}$ is

$$\begin{array}{cc}& {\mu }_{i\mathrm{1}}^{*}=\frac{-J\left(𝒱\right){\lambda }_{\mathrm{0}}^i}{F\left(𝒱\right)}{P}_{\mathrm{1}}+{\beta }_i\left(u^{\prime }+\sum _{j\in 𝒱}{u}_j\right)+\sum _{j=\mathrm{1}}^{t-\mathrm{1}}{\lambda }_j^i{\alpha }_j{P}_{\mathrm{2}},\end{array}$$

(22)

$$\begin{array}{cc}& {\mu }_{i\mathrm{2}}^{*}={\beta }_{i}P+\frac{-{\lambda }_{\mathrm{0}}^i}{F\left(𝒱\right)}{P}_{\mathrm{1}},\end{array}$$

(23)

where $v=H(s_{\mathrm{1}}^{*})$ .

At this point, algorithm ℛ randomly selects a bit $\delta \in \{\mathrm{0,1}\}$ , sets $T_{\delta }=T$ , and assigns a random value in the secret space ${𝔾}_{\mathrm{1}}$ to $T_{\mathrm{1}-\delta }$ . ℛ then sends $(s_{\mathrm{1}}^{*},s_{\mathrm{2}}^{*},T_{\mathrm{0}},T_{\mathrm{1}},S_i^{*}=({\mu }_{i\mathrm{1}}^{*},{\mu }_{i\mathrm{2}}^{*}))$ to the adversary 𝒜, where $i\in {𝕌}^{*}$ .

Claim 1. Our simulation does not abort with probability greater than 3/4.

Proof. Without loss of generality, let us assume that the adversary 𝒜 makes the maximum number q of sub-shadow queries. For any sub-shadow query of a participant and the $v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_q(\ne v^{*})$ , we have

$$\begin{array}{lll}Pr[\overline{\text{abort}}]\hfill & =\hfill & \text{Pr}\left[\underset{i=\mathrm{1}}{\overset{q}{\bigwedge }}K((v_i))=1\right]\hfill \\ \hfill & =\hfill & 1-Pr\left[\underset{i=\mathrm{1}}{\overset{q}{\bigvee }}K((v_i))=0\right]\hfill \\ \hfill & \ge \hfill & 1-\sum _{i=1}^{q}Pr[K((v_i))=0]\hfill \\ \hfill & =\hfill & 1-\frac{q}{m}\hfill \\ \hfill & =\hfill & \frac{3}{4}\hspace{0.17em}\hspace{0.17em}(\text{for}\hspace{0.17em}m=4q).\hfill \end{array}$$

(24)

This completes the proof of Claim 1.

Phase 2. The adversary 𝒜 continues to issue queries about a sub-shadow of the form $\{i,(s_{\mathrm{1}},s_{\mathrm{2}})\}$ , where $i\in \{\mathrm{1},\dots ,n\}$ and $(s_{\mathrm{1}},s_{\mathrm{2}})\ne (s_{\mathrm{1}}^{*},s_{\mathrm{2}}^{*})$ . Algorithm ℛ responds as in phase 1.

Guess. Eventually, 𝒜 outputs a guess bit ${\delta }^{\prime }\in \{\mathrm{0,1}\}$ for δ. Based on the value of ${\delta }^{\prime }$ , ℛ concludes its own game by outputting a guess as follows.

• (i)

If ${\delta }^{\prime }=\delta$ , ℛ answers 1, meaning that $T=e(P,P{)}^{abc}$ .

(ii)

Otherwise, ℛ answers 0, meaning that T is a random element of ${𝔾}_{\mathrm{1}}$ .

If the input $(P,aP,bP,cP,T)$ satisfies $T=e(P,P{)}^{abc}$ , then 𝒜's view is identical to its view in a real attack game, and therefore 𝒜 must satisfy $|\text{Pr}\mathrm{\hspace{0.17em}\hspace{0.17em}}[\delta ={\delta }^{\prime }]-\mathrm{1}/\mathrm{2}|>ϵ$ . On the other hand, if the input of $(P,aP,bP,cP,T)$ satisfies $T\ne e(P,P{)}^{abc}$ (where T is uniform in ${𝔾}_{\mathrm{1}}$ ), then $\text{Pr}\mathrm{\hspace{0.17em}\hspace{0.17em}}[\delta ={\delta }^{\prime }]=\mathrm{1}/\mathrm{2}$ . Therefore, with $P\stackrel{R}{\leftarrow }𝔾,a,b,c\stackrel{R}{\leftarrow }{\mathbb{Z}}_p$ and $T\stackrel{R}{\leftarrow }{𝔾}_{\mathrm{1}}$ , we have

$$\begin{array}{ll}& |\text{Pr}\left[ℛ\left(𝔾,P,aP,bP,cP,e{\left(P,P\right)}^{abc}\right)=\mathrm{1}\right]\\ \hspace{1em}\hspace{1em}-\text{Pr}\left[ℛ\left(𝔾,P,aP,bP,cP,T\right)=\mathrm{1}\right]\phantom{{\left(P,P\right)}^{\text{abc}}}|\\ \hspace{1em}\ge \left|(\frac{\mathrm{1}}{\mathrm{2}}\pm ϵ)-\frac{\mathrm{1}}{\mathrm{2}}\right|=ϵ.\end{array}$$

(25)

According to Claim 1, we have that ${ϵ}^{\prime }\ge (\mathrm{3}/\mathrm{4})ϵ$ . This completes the proof of Theorem 2.

6. Comparison

Now, let us compare our scheme to $\text{WT}\mathrm{11}$ [2] and $\text{HV}\mathrm{09}$ [3] in terms of computational cost and security. We firstly define the following notations.

• (i)

$T_p$ : The time taken to execute a bilinear pairing operation $e(·,·)$ .

(ii)

$T_m$ : The time taken to execute a scalar multiplication operation of point in 𝔾.

(iii)

$T_e$ : The time taken to execute a modular exponent operation in ${𝔾}_{\mathrm{1}}$ .

(iv)

$|p|$ : The binary length of order p.

(v)

$|H|$ : The output length of the hash function H.

As is well known, the time taken to execute $T_p$ , $T_m$ , and $T_e$ is much greater than the other operations, so we will ignore the time consumption of the other operations, such as executing an addition operation of points in 𝔾. The details of the comparison are given in Table 2. In Table 3, we compare the communication cost of the dealer distributing a secret to the participants, and a participant sends its subshare to other participants.

Table 2

Computational cost and security.

	WT11 [2]	HV09 [3]	Our scheme
Setup	0	0	$\left(2n+1\right)T_m$
Secret distribution	$\left(4n+t\right)T_p+n{T}_m$	$\left(n+t\right)T_m$	$2T_m$
Verification	$\left(n+3\right)T_p+n\left(t+1\right)T_m$	$t{T}_m+2t{T}_p$	$2T_p$
Subshadow generation	$T_e$	$T_m$	$3T_m$
Sub-shadow verification	/	$2\left(t-1\right)T_p$	$3\left(t-1\right)T_p$
Combine	$t{T}_e$	$t{T}_m+T_p$	$2T_p+2t{T}_m$
Secure level	IND	IND	IND-CSA

Table 3

Communication cost.

	WT11 [2]	HV09 [3]	Our scheme
Dealer distribution of a secret	$n(t+4)\left|p\right|$	$n(t+n)\left|p\right|$	$n(2\left|p\right|+\left|H\right|)$
Reconstruction of a secret	$t\left|p\right|$	$t\left|p\right|$	$2t\left|p\right|$

From the comparison in Tables 2 and 3, one can see that our scheme achieves a higher level of security without significantly increasing the overall computational complexity and the communication cost.

7. Extension Scheme

In the basic scheme described previously, the secret reconstruction requires the presence of point-to-point secure channels among the participants. In this section, we remove this limitation without sacrificing any good property of the scheme.

Suppose that a participant $U_i$ wants to send its sub-shadow through a public channel to a participant $U_j$ . For this purpose, $U_i$ randomly selects ${\beta }_i,r\in {\mathbb{Z}}_p\setminus \{\mathrm{0}\}$ , uses $U_j$ 's public key $D_j$ , and the following calculations are performed:

$$\begin{array}{cc}& v=H\left({𝒮}_{\mathrm{1}}\right),\\ {\upsilon }_{i\mathrm{1}}=(-d_i)Y_i+{\beta }_i\left(u^{\prime }+\sum _{i\in 𝒱}{u}_i\right)+r{D}_j,\\ {\upsilon }_{i\mathrm{2}}={\beta }_{i}P,\\ {\upsilon }_{i\mathrm{3}}=r{P}_{\mathrm{2}}.\end{array}$$

(26)

Then, $U_i$ sends $\{{\upsilon }_{i\mathrm{1}},{\upsilon }_{i\mathrm{2}},{\upsilon }_{i\mathrm{3}}\}$ to $U_j$ .

$U_j$ computes

$$\begin{array}{cc}& {\mu }_{i\mathrm{1}}={\upsilon }_{i\mathrm{1}}-d_j{\upsilon }_{i\mathrm{3}},\end{array}$$

(27)

sets

$$\begin{array}{cc}& {\mu }_{i\mathrm{2}}={\upsilon }_{i\mathrm{2}},\end{array}$$

(28)

and then checks whether or not

$$\begin{array}{cc}& e\left({\mu }_{i\mathrm{1}},P\right)=e\left(P_{\mathrm{2}},\text{SV}{\text{K}}_i\right)e\left(u^{\prime }+\sum _{i\in 𝒱}{u}_i,{\mu }_{i\mathrm{2}}\right).\end{array}$$

(29)

Having collected t valid sub-shadows, $U_i$ first computes ${\mu }_{\mathrm{1}}={\sum }_{i=\mathrm{1}}^t‍{\lambda }_i^{\mathrm{0}}{\mu }_{i\mathrm{0}},\hspace{0.17em}\hspace{0.17em}{\mu }_{\mathrm{2}}={\sum }_{i=\mathrm{1}}^t‍{\lambda }_i^{\mathrm{0}}{\mu }_{i\mathrm{1}}$ and then reconstructs the secret 𝒮 by computing $e(s_{\mathrm{1}},{\mu }_{\mathrm{1}})/e(s_{\mathrm{2}},{\mu }_{\mathrm{2}})$ just as it does in the basic scheme.

8. Conclusion

In this paper, we proposed a $(t,n)$ threshold PVSS scheme. Under the decisional bilinear Diffie-Hellman assumption, we proved that our scheme has indistinguishability against adaptively chosen secret attacks in the standard model. In the secret distribution phase, the dealer can send the main shadow to a participant through public channels. When the participants exchange their sub-shadows in the secret reconstruction phase, point-to-point secure channels need not be established in the extended scheme. This scheme is fairly interesting for practical applications.