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

Kittiphop Phalakarn; Vorapong Suppakitpaisarn; Nuttapong Attrapadung; Kanta Matsuura

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

Abstract

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.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Indocrypt 2020
DOI: 10.1007/978-3-030-65277-7_34
Keywords: Homomorphic secret sharing Homomorphic encryption Threshold non-access structure
Contact author(s): kittiphop phalakarn @ gmail com
History: 2023-08-03: revised; 2023-07-29: received; See all versions
Short URL: https://ia.cr/2023/1167
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1167,
      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},
      url = {https://eprint.iacr.org/2023/1167}
}