Sharing many secrets with computational provable security

• Two new multi-secret sharing schemes, with computational provable security.
• The security proofs are in the standard model.
• The two schemes generalize schemes previously proposed in the literature.
• We compare the two schemes in terms of security, efficiency and extendability.
• The schemes work for general access structures.

We propose in this work two new multi-secret sharing schemes, that allow to distribute ℓ   different secrets among a set P={P1,…,Pn}P={P1,…,Pn} of players, each one according to a (possibly different) access structure. The two schemes are proved to enjoy computational security, by reduction to the semantic security of the underlying symmetric encryption scheme. The two security proofs are in the standard model and provide the exact relation between the security of the involved primitives. As far as we know, this is the first formal security analysis for a computational multi-secret sharing scheme in the literature.We compare the two new schemes, taking into account their efficiency properties, their security analysis and possible extensions. One of the schemes has very short secret shares (independently of the number ℓ of secrets) and can be easily extended to work without any trusted dealer. The other scheme has longer secret shares and the extension to work without a trusted dealer is much more complicated, but on the other hand it produces shorter public outputs and the security relation with the underlying symmetric encryption scheme is better, which may have consequences in the final efficiency of the scheme.