Paper 2018/1010

Space Efficient Computational Multi-Secret Sharing and Its Applications

Aggelos Kiayias, Murat Osmanoglu, Alexander Russell, and Qiang Tang

Abstract

In a (t_1,...,t_l)-multi-secret sharing scheme (MSSS), l independent secrets s_1,...,s_l are shared with n parties in such a way that at least t_i parties are required to recover the secret s_i (while s_i remains hidden with fewer shares). We consider the problem of minimizing the share size of MSSS in the challenging setting when there are many secrets to be shared among many parties. To circumvent the information-theoretic lower bound (e.g., Blundo [4]), we focus on the computational setting. A simple generalization of computational secret sharing (Krawczyk [17]) to multi-secret sharing yields a scheme with share size/overhead scaling linearly in l, the total number of secrets. To beat this linear scaling, we consider constructing MSSS based on a related notion of encryption|dynamic threshold public key encryption (DTPKE)|that enables a sender to dynamically specify a threshold for each ciphertext. None of the existing DTPKE is well-suited for our purpose. Thus, we propose a new construction of a dynamic threshold public key encryption scheme with improved efficiency characteristics. We then give a recursive application of our construction that yields an efficient MSSS with share size only logarithmic in the number of secrets (thus effectively O(log l) as in the common cases, where l and n are polynomially related). Finally, we describe an application of our space efficient (1,2,...,n-1)-MSSS to a special tool called gradual verifiable secret sharing which is the fundamental building block for general multiparty computation (MPC) with n players that provides fairness without honest majority.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
multi-secret sharingfair MPCdynamic threshold
Contact author(s)
mosmanoglu @ ankara edu tr
History
2018-10-24: revised
2018-10-24: received
See all versions
Short URL
https://ia.cr/2018/1010
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1010,
      author = {Aggelos Kiayias and Murat Osmanoglu and Alexander Russell and Qiang Tang},
      title = {Space Efficient Computational Multi-Secret Sharing and Its  Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1010},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1010}},
      url = {https://eprint.iacr.org/2018/1010}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.