Paper 2021/1532

On the Download Rate of Homomorphic Secret Sharing

Ingerid Fosli
Yuval Ishai
Victor I. Kolobov
Mary Wootters
Abstract

A homomorphic secret sharing (HSS) scheme is a secret sharing scheme that supports evaluating functions on shared secrets by means of a local mapping from input shares to output shares. We initiate the study of the download rate of HSS, namely, the achievable ratio between the length of the output shares and the output length when amortized over $\ell$ function evaluations. We obtain the following results. * In the case of linear information-theoretic HSS schemes for degree-$d$ multivariate polynomials, we characterize the optimal download rate in terms of the optimal minimal distance of a linear code with related parameters. We further show that for sufficiently large $\ell$ (polynomial in all problem parameters), the optimal rate can be realized using Shamir's scheme, even with secrets over $\mathbb{F}_2$. * We present a general rate-amplification technique for HSS that improves the download rate at the cost of requiring more shares. As a corollary, we get high-rate variants of computationally secure HSS schemes and efficient private information retrieval protocols from the literature. * We show that, in some cases, one can beat the best download rate of linear HSS by allowing nonlinear output reconstruction and $2^{-\Omega(\ell)}$ error probability.

Note: Minor corrections.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. ITCS 2022
Keywords
Information theoretic cryptography homomorphic secret sharing private information retrieval secure multiparty computation
Contact author(s)
ifosli @ gmail com
yuval ishai @ gmail com
kolobov victor @ gmail com
marykw @ stanford edu
History
2022-05-30: revised
2021-11-22: received
See all versions
Short URL
https://ia.cr/2021/1532
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1532,
      author = {Ingerid Fosli and Yuval Ishai and Victor I.  Kolobov and Mary Wootters},
      title = {On the Download Rate of Homomorphic Secret Sharing},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1532},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1532}},
      url = {https://eprint.iacr.org/2021/1532}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.