Keywords

1 Introduction

With the advent of big data era, massive information is collected, accessed and operated all the way. Nevertheless, large amounts of privacies relevant to these data are confronted with the peril of revelation since the communication channels are open and the storages are always consigned [1]. On the other hand, the reliability of stocked data is also prone to damages due to system failure, interference or tampering, which may severely jeopardize the availability of important data [2]. Though functionality and security seem like two contrary goals for information system, lots of cryptographic techs can be used to balance the requirements between them. Oriented to different applications such as secure multi-parity computation) [3], Byzantine agreement [4] and oblivious transfer [5], secret sharing schemes are extensively used as their building block to narrow the gaps of system performance and security [6].

Based on Lagrange polynomial and Chinese remainder theorem, Shamir [7] and Blakley [8] brought about the schemes of secret sharing for the first time. Following their work, a series of secret sharing schemes [9,10,11,12,13,14] are proposed focusing on specific access structures. Though Ito et al. [15] have devised an universal framework to realize secret sharing on general access structure, it is deemed as impractical since the share size is extraordinary large. However, once the access structure is equivalent to a small monotone span program, efficient secret sharing schemes can easily be achieved [16, 17].

Another research attraction is related to the communication burden and rounds of secret sharing. As proved by Csirmaz [18], to share a \( \ell \)-bits secret within a n-party network, the lower bound of share size is \( \varOmega \left( {\ell n/log_{2} n} \right) \). Though the share sizes of best known schemes [19, 20] are far more larger than such benchmark, the size of shared data can practically approach \( n^{{\varOmega \left( {log_{2} n} \right)}} \) by linear secret sharing. In order to conserve the confidentiality of shared secrets when compounded with each other, homomorphic computability is also considered as an important requirement for secret sharing [21]. Aiming at minimizing the traffic overhead, linear secret sharing schemes are always exploited in virtue of non-interactive addition and constant multiplication [22, 23]. However, when two shared secrets are multiplied, how to reduce or even eliminate unnecessary communications still remains an open problem [24]. The original homomorphic multiplication for linear secret sharing is presented by Gennaro et al. with \( \ell \left( {2k - 1} \right)^{2} \)-bits1-round communication [25], which may incur a severe delay when arithmetic circuits are deep. In fact, as proved by Ishai et al. [26, 27], once more that third of the participants are honest, any circuit can be cryptically evaluated via a 2-round secret sharing protocol. That is to say, refraining the communication from homomorphic multiplication is possible. In [28], Barkol et al. presented a multiplication scheme which enables all participants to secretly convert \( d \) distinct secrets into an additive sharing of their product. And its verifiable version was then proposed by Yoshida et al. [29]. However, since the circuit depth is strictly limited by the number of participants and security level, their schemes are incapable of fulfilling the property of fully homomorphism. In order to address such defect, Watanabe et al. [30] devised a FHE (Fully Homomorphic Encryption) scheme at the expense of \( 2n \) extra shares for each secret. Based on the recursive construction, Blackburn et al. [31] presented an efficient multiplicative sharing scheme where the share size will slightly expand along with the increasing of network scales. Thereafter, Wang et al. [32] pointed out that the forementioned scheme is infeasible within MTA (Mutually Trusted Authority)-free environment [33] and disposed the problem of redundantly operating on the same secret. Moreover, numerous secret sharing schemes are successively proposed utilizing different algebraic structures such as discrete logarithm [34], lattice [35] and Abelian codes [36].

Due to the linear nature and Q2 access structure of Shamir’s secret sharing, it is widely used as a building block for privacy-preserving implementation. Moreover, since Shamir’s scheme is ideal [9], the size of a shared secret is only \( \ell n \)-bits uniformly distributed on \( n \) participants, which is commendably close to its lower bound. For the sake of homomorphic computation, the trait of its linearity refrained the operations of addition and constant multiplication from interactions. Nevertheless, even if the best multiplicative secret sharing scheme is exploited, non-negligible delay occurs due to a series of communications.

Considering that the multiplicative circuits are inevitable for most practical applications and the characteristics of low communication along with computation overheads must be conserved for real-time implementation, a non-interactive multiplication scheme is proposed for Shamir’s secret sharing in this paper. The main idea is, once the identities of all participants are reasonably regulated, polynomial convolution can play a part in reducing the overflowed orders incurred by trivial multiplication. The rest of this paper is organized as below.

In Sect. 2, a formal definition regarding Shamir’s secret sharing is given, together with the defect analysis of some previous multiplicative secret sharing scheme. Then, a non-interactive multiplicative method and its correctness proof will be depicted in Sect. 3. Section 4 testified that our method is unconditionally secure and its performance is more preferable compared to related schemes. Finally, the paper will be concluded in Sect. 5.

2 Preliminary of Shamir’s Secret Sharing

Based on Q2 access structure, Shamir’s secret sharing is always recognized as a \( \left( {k, n} \right) \)-threshold scheme, where at least k shares amongst n pieces of a secret s should be gather to for information revealing. Since the essential idea of this threshold scheme is that any polynomial of degree \( k - 1 \) can be exclusively determined by k points in virtue of Lagrange interpolation [7], a secret s can be divided into a series of shares \( \left( {x_{i} , f\left( {x_{i} } \right)} \right) \), \( i = 1,2, \cdots ,n \), according to a stochastic polynomial

$$ f_{s} \left( x \right) = s + a_{1} x + a_{2} x^{2} + \cdots a_{k - 1} x^{k - 1} . $$
(1)

Without loss of generality, we assume that the coefficients \( a_{j} \), \( j = 1,2, \cdots ,k - 1 \), are independently and uniformly sampled from a finite field \( {\mathbb{F}}_{p} \), where \( p \) is an odd prime. For any secret \( s \in {\mathbb{F}}_{p} \), the scheme can be formally defined as follows.

Definition 1.

The Shamir’s secret sharing scheme is a triple function set \( \prod = \left( {{\text{DIT, EVL, REC}}} \right) \) works on Q2 access structure, where

  • a. The secret holder computes \( \left\{ {\left( {x_{i} , f_{s} \left( {x_{i} } \right)} \right)} \right\}\mathop \leftarrow \limits^{{{\rm \$ }}} {\rm{DIT}}\left( s \right) \) in terms of formula (1) and distributes them to their correspondent receivers via authenticated and private channels. Denoting \( {\text{A}} \) as the set of all adversary structures, if \( {\text{T}}\backslash {\text{C}} \notin {\text{A}} \) for any \( {\text{C}} \in {\text{A}} \) where \( {\text{T}} = \left\{ {1,2, \cdots ,n} \right\} \), then

    $$ \Pr \left[ {{\mathcal{A}}\left( {\left[ s \right]_{\text{C}} } \right) = s} \right] = 1/p , $$
    (2)

    where \( \left[ s \right]_{\text{C}} \) represents the set of shares corrupted by adversary \( {\mathcal{A}} \).

  • b. For any constants \( c_{1} , c_{2} \) and a pair of shares \( \left[ {s_{1} } \right]_{\text{T}} ,\left[ {s_{2} } \right]_{\text{T}} \), it is easy to non-interactively compute \( \left[ {c_{1} s_{1} + c_{2} s_{2} } \right]_{\text{T}} \leftarrow {\text{EVL}}\left( {\left[ {s_{1} } \right]_{\text{T}} ,\left[ {s_{2} } \right]_{\text{T}} ,c_{1} , c_{2} } \right) \) in terms of trivial addition and multiplication. In order to calculate \( \left[ {s_{1} s_{2} } \right]_{\text{T}} \leftarrow {\text{EVL}}\left( {\left[ {s_{1} } \right]_{\text{T}} ,\left[ {s_{2} } \right]_{\text{T}} } \right) \), interactive fully homomorphic schemes do also exist [25]. When executing the function of \( {\text{EVL}}\left( \cdot \right) \), it is obvious that the requirements

    $$ \Pr \left[ {{\mathcal{A}}\left( {\left[ \cdot \right]_{\text{C}} ,{\rm{Com}}_{\text{T}} } \right) = s,s \in {\text{S}}} \right] = 1/p $$
    (3)

    and

    $$ \Pr \left[ {{\mathcal{A}}\left( {\left[ \cdot \right]_{\text{C}} ,{\rm{Com}}_{\text{T}} } \right) = {\text{REC}}\left( {{\rm{EVL}}\left( {\left[ {\text{S}} \right]_{\rm{T}} } \right)} \right)} \right] = 1/p $$
    (4)

    must hold, where \( {\text{S}} \) stands for the set of original secrets and \( \left[ \cdot \right]_{\text{C}} ,{\rm{Com}}_{\text{T}} \) are all corrupted shares along with intercepted communications.

  • c. Within the Q2 structure, the recovery function \( {\text{REC}}\left( \cdot \right) \) is capable of revealing the shared secret by

    $$ { \Pr }\left[ {{\text{REC}}\left( {\left[ s \right]_{{{\bar{\text{c}}}}} } \right) = s} \right] = 1 $$
    (5)

    where \( {\bar{\text{C}}} \) is the complementary set of \( {\text{C}} \).

It is worth noting that the multiplicative secret sharing presented in [25] is feasible only if \( n \ge 2k - 1 \) with non-negligible communications. Though Barkol et al. [28] achieved a non-interactive scheme which can locally multiply \( d \) shared secrets, an auxiliary condition where \( n > dk \) should also be satisfied. As for Watanabe’s method [30], it is capable of performing multiplication even only \( k \) share holders are involved, the share size for each secret are 3 times than that of the primitive scheme and \( 4\ell k \)-bits messages must be collected for each participant to achieve a share of multiplication result. To sum up, no existing multiplicative secret sharing scheme is in a position to avoid both interaction and parameter limitation, and that is why our research cut in.

3 Multiplicative Secret Sharing Without Interaction

The main reason that two shares should not be trivially multiplied can be attributed to the remarkable increment of polynomial order. For instance, when two shares \( \left( {x_{i} , f_{a} \left( {x_{i} } \right)} \right) \) and \( \left( {x_{i} , f_{b} \left( {x_{i} } \right)} \right) \) are directly multiplied by participant \( i \), the result is \( \left( {x_{i} , f_{a} \left( {x_{i} } \right)f_{b} \left( {x_{i} } \right)} \right) \), where \( f_{a} \left( {x_{i} } \right)f_{b} \left( {x_{i} } \right) \) can be written as

$$ f_{a} \left( {x_{i} } \right)f_{b} \left( {x_{i} } \right) = ab + r_{1} x_{i} + r_{2} x_{i}^{2} + \cdots r_{2k - 2} x_{i}^{2k - 2} $$
(6)

which turns the original scheme into a \( \left( {2k - 1, n} \right) \)-threshold secret sharing. With the help of polynomial convolution, we caught a sight of how to reduce the multiplicative result back to a \( k - 1 \) order polynomial and maintain its raw threshold without interaction.

Assuming that the polynomials \( f_{a} \left( {x_{i} } \right) \) and \( f_{b} \left( {x_{i} } \right) \) is represented as

$$ f_{a} \left( {x_{i} } \right) = \left( {a, a_{1} , a_{2} , \cdots ,a_{k - 1} } \right)\left( {x_{i}^{0} , x_{i}^{1} ,x_{i}^{2} , \cdots ,x_{i}^{k - 1} } \right)^{T} $$
(7)

and

$$ f_{b} \left( {x_{i} } \right) = \left( {b, b_{1} , b_{2} , \cdots ,b_{k - 1} } \right)\left( {x_{i}^{0} , x_{i}^{1} ,x_{i}^{2} , \cdots ,x_{i}^{k - 1} } \right)^{T} $$
(8)

respectively. Then \( f_{a} \left( {x_{i} } \right)f_{b} \left( {x_{i} } \right) \) in formula (6) is equivalent to \( \alpha + \beta \), where

$$ \begin{array}{*{20}c} {\alpha = \left( {\left( {ab,ab_{1} + ba_{1} , \cdots ,\sum\nolimits_{{\upsigma + \tau = \mu }} {a_{\upsigma} b_{\tau } , \cdots ,} \,\sum\nolimits_{{\upsigma + \tau = k - 1}} {a_{\upsigma} b_{\tau } } } \right)\bmod \,p} \right) \cdot } \\ {\left( {x_{i}^{0} ,x_{i}^{1} , \cdots ,x_{i}^{\mu } , \cdots ,x_{i}^{k - 1} } \right)^{T} } \\ \end{array} $$
(9)

and

$$ \begin{aligned} & \beta = \left( {\left( {\sum\nolimits_{\sigma + \tau = k} {a_{\sigma } b_{\tau } , \cdots ,} \,\sum\nolimits_{\sigma + \tau = \omega } {a_{\sigma } b_{\tau } , \cdots ,a_{k - 2} b_{k - 1} + a_{k - 1} b_{k - 2} , a_{k - 1} b_{k - 1} } } \right)\bmod \,p} \right) \cdot \\ & \quad \left( {x_{i}^{k - 1} \left( {x_{i}^{1} , \cdots ,x_{i}^{\omega = k + 1} , \cdots x_{i}^{k - 2} ,x_{i}^{k - 1} } \right)} \right)^{T} , \\ \end{aligned} $$
(10)

where \( a_{0} = a \) and \( b_{0} = b \). Noting that the order of polynomial \( \alpha \) is \( k - 1 \) whose leading coefficient is exactly \( ab \), so if we can figure out \( \beta \) then the share of \( ab \) for participant \( i \) can be trivially achieved by subtract \( \beta \) from \( f_{a} \left( {x_{i} } \right)f_{b} \left( {x_{i} } \right) \). Based on forementioned observation, we construct a multiplicative secret sharing scheme as below.

Distribution \( \left\{ {\left( {x_{i} , f_{s} \left( {x_{i} } \right)} \right)} \right\}\mathop \leftarrow \limits^{{{\rm \$ }}} {\rm{DIT}}\left( s \right) \):

Define \( p < x_{i} < q \) as the identity of participate \( i \), where \( q > p + n \) is a positive integer and \( \gcd \left( {x_{i} ,p} \right) = \gcd \left( {\left( {x_{i}^{ - k} - 1} \right)^{ - 1} ,p} \right) = 1 \). Then calculate \( f_{s} \left( {x_{i} } \right) \) according to formula (1) modulo \( \left( {x_{i}^{k} - 1} \right) \), which will be distributed to \( i \) as her share of secret \( s \).

Multiplication \( \left[ {ab} \right]_{\text{T}} \leftarrow {\text{EVL}}\left( { \left[ a \right]_{\text{T}} ,\left[ b \right]_{\text{T}} } \right) \):

Participant \( i \) locally computes

$$ f_{ab} \left( {x_{i} } \right) = f_{a} \left( {x_{i} } \right)f_{b} \left( {x_{i} } \right) - \left( {x_{i}^{ - k} - 1} \right)^{ - 1} \left( {\left( {f_{a} \left( {x_{i} } \right)f_{b} \left( {x_{i} } \right)\,\bmod \left( {x_{i}^{k} - 1} \right)} \right) - f_{a} \left( {x_{i} } \right)f_{b} \left( {x_{i} } \right)} \right) $$
(11)

modulo \( \left( {x_{i}^{k} - 1} \right) \) as her share of \( ab \).

Since participant \( i \) is provided with all information about \( f_{a} \left( {x_{i} } \right), f_{b} \left( {x_{i} } \right) \) and \( x_{i} \), no interaction is necessary for her to calculate formula (11). In order to testify the correctness of our protocol, a Lemma is given in advance.

Lemma 1.

For \( \forall \, \theta \in \left\{ {0, 1, \cdots ,k - 1} \right\} \), if \( \left\| {\sum\nolimits_{\sigma + \tau = \theta \,\bmod \,k} {a_{\sigma } b_{\tau } } } \right\|_{\infty } < x_{i} - 1 \) then

$$ \alpha + x_{i}^{ - k} \beta < x_{i}^{k} - 1 . $$
(12)

Proof.

Since \( \alpha + x_{i}^{ - k} \beta \) is a \( k - 1 \) order polynomial, which can be written as \( \sum\nolimits_{\theta = 0}^{k - 1} {\left( {\sum\nolimits_{{\upsigma + \tau = \theta \,\bmod \,k}} {a_{\upsigma} b_{\tau } } } \right)x_{i}^{\theta } } \), we have

$$ 0 \le \alpha + x_{i}^{ - k} \beta \le \left\| {\sum\nolimits_{\sigma + \tau = \theta \,\bmod \,k} {a_{\sigma } b_{\tau } } } \right\|_{\infty } \left( {x_{i}^{0} + x_{i}^{1} + \cdots + x_{i}^{\theta } + \cdots + x_{i}^{k - 1} } \right). $$
(13)

Once \( \left\| {\sum\nolimits_{{\upsigma + \tau = \theta \,\bmod \,k}} {a_{\upsigma} b_{\tau } } } \right\|_{\infty } < x_{i} - 1 \), then

$$ \alpha + x_{i}^{ - k} \beta < \left( {x_{i} - 1} \right)\left( {x_{i}^{0} + x_{i}^{1} + \cdots + x_{i}^{\theta } + \cdots + x_{i}^{k - 1} } \right) $$
(14)

and the formula (12) holds.

Now, we are ready to claim the validity of our multiplicative secret sharing scheme in the following theorem.

Theorem 1.

If \( x_{i} > p \), any participant \( i \) is able to non-interactively multiply the shares of two secrets retaining the property of \( \left( {k, n} \right) \)-threshold.

Proof.

According to polynomial convolution, the formula \( f_{a} \left( {x_{i} } \right)f_{b} \left( {x_{i} } \right)\,\bmod \left( {x_{i}^{k} - 1} \right) \) can be represented as \( \alpha + x_{i}^{ - k} \beta + t\left( {x_{i}^{k} - 1} \right) \) for some non-positive integer \( t \). Once the condition \( \left\| {\sum\nolimits_{{\upsigma + \tau = \theta \,\bmod \,k}} {a_{\upsigma} b_{\tau } } } \right\|_{\infty } < x_{i} - 1 \) stands, then

$$ f_{a} \left( {x_{i} } \right)f_{b} \left( {x_{i} } \right)\,\bmod \left( {x_{i}^{k} - 1} \right) = \alpha + x_{i}^{ - k} \beta $$
(15)

in terms of Lemma 1. Denoting \( \varphi \left( {x_{i} } \right) \) as

$$ \begin{array}{*{20}l} {\varphi \left( {x_{i} } \right) = f_{a} \left( {x_{i} } \right)f_{b} \left( {x_{i} } \right) mod \left( {x_{i}^{k} - 1} \right) - f_{a} \left( {x_{i} } \right)f_{b} \left( {x_{i} } \right)} \hfill \\ { = \left( {r_{0}^{'} , r_{1}^{'} , \cdots , r_{k - 2}^{'} ,0, - r_{0}^{'} , - r_{1}^{'} , \cdots , - r_{k - 2}^{'} } \right) \cdot } \hfill \\ {\quad \left( {x_{i}^{0} ,x_{i}^{1} , \cdots ,x_{i}^{k - 2} ,x_{i}^{k - 1} ,x_{i}^{k} ,x_{i}^{k + 1} , \cdots ,x_{i}^{2k - 2} } \right)^{T} ,} \hfill \\ \end{array} $$
(16)

where \( r_{\delta }^{'} = \sum\nolimits_{\sigma = \delta + 1}^{k - 1} {a_{\sigma } b_{\tau = k - \sigma + \delta } } \) for \( \delta = \left\{ {0,1, \cdots , k - 2} \right\} \), it can be easily seem that

$$ \beta = \left( {x_{i}^{ - k} - 1} \right)^{ - 1} \varphi \left( {x_{i} } \right) $$
(17)

which is exactly the second term of \( \alpha + \beta \). Noting that \( \left\| {\sum\nolimits_{{\upsigma + \tau = \theta \,\bmod \,k}} {a_{\upsigma} b_{\tau } } } \right\|_{\infty } \equiv p - 1\,\bmod \,p \), thus our protocol is correct if \( x_{i} > p \).

4 Security and Performance Analysis

Since the coefficients of polynomial \( f_{s} \left( x \right) \) is independently and uniformly sampled from a finite field \( {\mathbb{F}}_{p} \), the secret \( s \) is unconditionally secure if less than \( k \) shares are compromised [7]. For clarity, we interpret this property as a formal description.

Lemma 2.

The Shamir’s secret sharing scheme is unconditionally secure, where the secret recovery advantage of any adversary \( {\mathcal{A}} \) is

$$ \begin{array}{*{20}l} {{\mathbf{Adv}}_{{f_{s} }}^{sr} \left( {\mathcal{A}} \right) = \Pr \left[ {{\mathcal{A}}\left( {\left[ s \right]_{\text{C}} } \right) = s,s \in {\mathbb{F}}_{p} } \right]} \hfill \\ {\quad \quad \quad \quad \;\, = 1/p,} \hfill \\ \end{array} $$
(18)

if \( {\text{T}}\backslash {\text{C}} \notin {\text{A}} \) for any \( {\text{C}} \in {\text{A}} \) where \( {\text{T}} = \left\{ {1,2, \cdots ,n} \right\} \).

It is obvious that because no information is exchanged when multiplying two shares \( f_{a} \left( {x_{i} } \right) \) and \( f_{b} \left( {x_{i} } \right) \) in our scheme, the secrets \( a \) and \( b \) are still unconditionally secure according to Lemma 2.

In order to prove the information-theory security of \( \left[ {ab} \right]_{\text{C}} \), we consider an experiment where the adversary runs \( {\mathcal{A}} \) as a subroutine to recover \( ab \).

$$ \begin{array}{*{20}l} {{{\rm Experiment}}\;{\mathbf{Exp}}_{{f_{ab} }}^{sr} \left( {\mathcal{B}} \right)} \hfill \\ {\left[ a \right]_{{\rm T}} \mathop \leftarrow \limits^{{{\rm \$ }}} {{\rm DIT}}\left( a \right), \left[ b \right]_{{\rm T}} \mathop \leftarrow \limits^{{{\rm \$ }}} {\rm{DIT}}\left( b \right)} \hfill \\ {\left[ {ab} \right]_{{\rm T}} \leftarrow {{\rm EVL}}\left( { \left[ a \right]_{{\rm T}} ,\left[ b \right]_{{\rm T}} } \right)} \hfill \\ {b \leftarrow {{\rm REC}}\left( {\left[ b \right]_{{\bar{c}}} } \right)} \hfill \\ {a^{{\prime }} \leftarrow {\mathcal{A}}\left( {\left[ a \right]_{{\rm C}} } \right)} \hfill \\ {s = a^{{\prime }} b} \hfill \\ {{{\rm If}}\;s = ab\;{{\rm return}}\;1,\;{{\rm else}}\;{{\rm return}}\;0} \hfill \\ \end{array} $$

By contrary, our scheme is also unconditionally secure as below.

Theorem 2.

The proposed multiplicative scheme is information-theoretically secure, where the advantage of any adversary \( {\mathcal{B}} \) who expect to reveal \( ab \) is

$$ \begin{array}{*{20}l} {{\mathbf{Adv}}_{{f_{ab} }}^{sr} \left( {\mathcal{B}} \right) = \Pr \left[ {{\mathcal{B}}\left( {\left[ {ab} \right]_{\text{C}} } \right) = ab,ab \in {\mathbb{F}}_{p} } \right]} \hfill \\ {\quad \quad \quad \quad \;\; = 1/p,} \hfill \\ \end{array} $$
(19)

if \( {\text{T}}\backslash {\text{C}} \notin {\text{A}} \) for any \( {\text{C}} \in {\text{A}} \) where \( {\text{T}} = \left\{ {1,2, \cdots ,n} \right\} \).

Proof.

The proof is straight-forward that if \( {\mathbf{Adv}}_{{f_{ab} }}^{sr} \left( {\mathcal{B}} \right) > 1/p \), the probability that \( {\mathcal{B}} \) recovers \( s \) where \( s = ab \) is greater than \( 1/p \). Since \( b \) is plain for him, it implies that \( {\mathcal{A}} \) can reveal \( a \) with an advantage \( {\mathbf{Adv}}_{{f_{s} }}^{sr} \left( {\mathcal{A}} \right) > 1/p \) as well, which is a contradiction against Lemma 2.

The multiplicative secret sharing scheme in Sect. 3 also suggests that it achieves preferable performance with regard to parameter constrain, share size and communication burden. Three linear secret sharing protocols [25, 28, 30] are investigated for comparison as illustrated in Table 1.

Table 1. Comparison amongst multiplicative secret sharing of [25, 28, 30] and the proposed
Full size table

As we can see from the above table, each piece of share is \( k\left\lceil {log_{2} q} \right\rceil \)-bits in our scheme to retain all information within \( \alpha \). Fortunately, the threshold parameters \( k \) and n are relatively inappreciable compared with \( p \) and q is only bounded with \( q > p + n \), meaning that the share size of our scheme, which is sub-linearly proportional to that of [25, 28, 30], is reasonable for practical application. Concerning the number of participants who are engaged in secret multiplication, at least \( 2k - 1 \) and \( dk \) members are necessary for the schemes of [25] and [28] to multiply \( d \) shares correctly. Though the scheme of [30] is capable of multiplying shared secrets only if \( k \) participants are involved, massive communications are inevitable since every participant has to collect \( 4k\left\lceil {log_{2} p} \right\rceil \) pieces of information for correct operation. As for our scheme, although the condition of \( n \ge k \) must be fulfilled to actualize Q2 access structure, no interaction will be necessary due to the locality of multiplication and the constrain on threshold parameters can be eliminate because each secret is only attached to one piece of shares for each participant.

The computational performance of our scheme is also commendable since the operation of formula (11) is trivial. Noting that, because every participant is provided with her unique identity \( x_{i} \), she can initially compute \( \left( {x_{i}^{k} - 1} \right) \) and \( \left( {x_{i}^{ - k} - 1} \right)^{ - 1} \) once for all. That is to say, when securely multiplying two pieces of shares, only two integer multiplications and subtractions along with one modular operation need to be executed.

5 Conclusion

In order to privately multiply shared secrets without interaction, a novel multiplicative scheme is presented based on \( \left( {k, n} \right) \)-threshold Shamir’s secret sharing. The main idea behind the proposed scheme is that we can subtly eliminate the overflowed terms of two plainly multiplied polynomials with the help of convolution. It is proved that our method is capable of correctly retaining the product of secrets as the first coefficient of a \( k - 1 \) order polynomial with unconditional security. Compared with relevant schemes, our method is preferable since no communication and system parameter constrain are necessary.