A non-interactive \((t, n)\)-publicly verifiable multi-secret sharing scheme (Q2161420)

The introduced non-interactive publicly verifiable multi-secret sharing scheme is such that the participants may recover a list of secrets when just one share is provided by each participant in such a way that the shares may be authenticated by each participant when sharing and by the distributing dealer when created. Multi secret sharing is granted using homogeneous linear recurrences: a number sequence \(\left(u_i\right)_{i\in\mathbb{N}}\) is built by an initial case, \(u_i=c_i\), \(i=0,1,\ldots,t-1\), with \(c_i\in\mathbb{Z}\), and a recursive case stated as \(a_i + \sum_{j=1}^ta_ju_{i-j}=0\) for \(i\geq t\), with \(a_j\in\mathbb{Z}\). In a ``forward approach'' any current term is calculated using \(t\) precedent terms. In a ``backward approach'' given \(t\) last terms, the precedent terms can be recovered by a simple iteration. In any threshold secret sharing scheme (SSS), there is a space of secrets, a dealer, and a set of participants. Given a secret, the dealer builds corresponding shares for participants and distributes a share for each participant. When as many participants as the threshold provide their shares, they are able to recover the corresponding secret. In a verifiable SSS, the threshold gives a kind of message authentication code (MAC) for his built shares so that any verifier may check its authenticity, and each participant may provide also a MAC to each submission of his share to guarantee its authenticity. In any such SSS, there is a generation procedure producing the scheme parameters and pairs of public and private keys for the dealer and each participant, a secret distribution procedure, to build shares and the MAC produced by the dealer of the whole collection of shares, and the corresponding MAC, produced by the receiving participant, for each share, and finally a secret recovery procedure that recovers the multi secret when at least as many shares as the threshold are provided together with their verified MACs. The scheme should be correct, i.e. the verification of the dealer production is successful with probability 1, it should be consistent, i.e. any two recovering sets of participants should recover the same multi secret, and secure, i.e. there is a formal proof that any attempt to cheat the scheme has a negligible probability of success. In the built scheme, the space of secrets is a cyclic group of order a big prime such that the discrete logarithm problem or variants of the Diffie-Hellman problem are computationally intractable. However, for the given scheme it is mandatory that the dealer knows a priori the discrete logarithms of the secrets, concerning an initially chosen group generator since these logarithms are the parameters of the used homogeneous linear recurrence. There are proposed as well effective constructions of MACs entailing verification procedures using just public information. The recovery proceeds through operations in the cyclic group and produces the multi-secret effectively, although the discrete logarithms of the secrets to being recovered remain unknown to the participants. Certainly, the proposed method is new, correct, and efficient. A comparison of performance with other such SSS shows experimentally that the method is potentially useful in applications.