DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2022.71

On the Download Rate of Homomorphic Secret Sharing

Authors: Ingerid Fosli, Yuval Ishai, Victor I. Kolobov, and Mary Wootters

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

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 𝓁 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 𝓁 (polynomial in all problem parameters), the optimal rate can be realized using Shamir’s scheme, even with secrets over 𝔽₂. - 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^{-Ω(𝓁)} error probability.

Cite as

Ingerid Fosli, Yuval Ishai, Victor I. Kolobov, and Mary Wootters. On the Download Rate of Homomorphic Secret Sharing. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 71:1-71:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fosli_et_al:LIPIcs.ITCS.2022.71,
  author =	{Fosli, Ingerid and Ishai, Yuval and Kolobov, Victor I. and Wootters, Mary},
  title =	{{On the Download Rate of Homomorphic Secret Sharing}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{71:1--71:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.71},
  URN =		{urn:nbn:de:0030-drops-156675},
  doi =		{10.4230/LIPIcs.ITCS.2022.71},
  annote =	{Keywords: Information-theoretic cryptography, homomorphic secret sharing, private information retrieval, secure multiparty computation, regenerating codes}
}

Search Results

Documents authored by Fosli, Ingerid

On the Download Rate of Homomorphic Secret Sharing

Abstract

Cite as

Thanks for your feedback!

Could not send message