Paper 2023/1167

Constructive $t$-secure Homomorphic Secret Sharing for Low Degree Polynomials

Kittiphop Phalakarn, The University of Tokyo, Tokyo, Japan
Vorapong Suppakitpaisarn, The University of Tokyo, Tokyo, Japan
Nuttapong Attrapadung, National Institute of Advanced Industrial Science and Technology, Tokyo, Japan
Kanta Matsuura, The University of Tokyo, Tokyo, Japan

This paper proposes $t$-secure homomorphic secret sharing schemes for low degree polynomials. Homomorphic secret sharing is a cryptographic technique to outsource the computation to a set of servers while restricting some subsets of servers from learning the secret inputs. Prior to our work, at Asiacrypt 2018, Lai, Malavolta, and Schröder proposed a $1$-secure scheme for computing polynomial functions. They also alluded to $t$-secure schemes without giving explicit constructions; constructing such schemes would require solving set cover problems, which are generally NP-hard. Moreover, the resulting implicit schemes would require a large number of servers. In this paper, we provide a constructive solution for threshold-$t$ structures by combining homomorphic encryption with the classic secret sharing scheme for general access structure by Ito, Saito, and Nishizeki. Our scheme also quantitatively improves the number of required servers from $O(t^2)$ to $O(t)$, compared to the implicit scheme of Lai et al. We also suggest several ideas for future research directions.

Available format(s)
Publication info
Published elsewhere. Indocrypt 2020
Homomorphic secret sharingHomomorphic encryptionThreshold non-access structure
Contact author(s)
kittiphop phalakarn @ gmail com
2023-08-03: revised
2023-07-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kittiphop Phalakarn and Vorapong Suppakitpaisarn and Nuttapong Attrapadung and Kanta Matsuura},
      title = {Constructive $t$-secure Homomorphic Secret Sharing for Low Degree Polynomials},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1167},
      year = {2023},
      doi = {10.1007/978-3-030-65277-7_34},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.