[Resource Topic] 2023/1167: Constructive $t$-secure Homomorphic Secret Sharing for Low Degree Polynomials

Welcome to the resource topic for 2023/1167

Constructive t-secure Homomorphic Secret Sharing for Low Degree Polynomials

Authors: Kittiphop Phalakarn, Vorapong Suppakitpaisarn, Nuttapong Attrapadung, Kanta Matsuura


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.

ePrint: https://eprint.iacr.org/2023/1167

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .