Search Results

Documents authored by Blackwell, Keller

Document
DOI: 10.4230/LIPIcs.ITC.2024.7
Improved Trade-Offs Between Amortization and Download Bandwidth for Linear HSS

Authors: Keller Blackwell and Mary Wootters

Published in: LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024)

Abstract
A Homomorphic Secret Sharing (HSS) scheme is a secret-sharing scheme that shares a secret x among s servers, and additionally allows an output client to reconstruct some function f(x) using information that can be locally computed by each server. A key parameter in HSS schemes is download rate, which quantifies how much information the output client needs to download from the servers. Often, download rate is improved by amortizing over 𝓁 instances of the problem, making 𝓁 also a key parameter of interest. Recent work [Fosli et al., 2022] established a limit on the download rate of linear HSS schemes for computing low-degree polynomials and constructed schemes that achieve this optimal download rate; their schemes required amortization over 𝓁 = Ω(s log(s)) instances of the problem. Subsequent work [Blackwell and Wootters, 2023] completely characterized linear HSS schemes that achieve optimal download rate in terms of a coding-theoretic notion termed optimal labelweight codes. A consequence of this characterization was that 𝓁 = Ω(s log(s)) is in fact necessary to achieve optimal download rate. In this paper, we characterize all linear HSS schemes, showing that schemes of any download rate are equivalent to a generalization of optimal labelweight codes. This equivalence is constructive and provides a way to obtain an explicit linear HSS scheme from any linear code. Using this characterization, we present explicit linear HSS schemes with slightly sub-optimal rate but with much improved amortization 𝓁 = O(s). Our constructions are based on algebraic geometry codes (specifically Hermitian codes and Goppa codes).
Cite as

Keller Blackwell and Mary Wootters. Improved Trade-Offs Between Amortization and Download Bandwidth for Linear HSS. In 5th Conference on Information-Theoretic Cryptography (ITC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 304, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{blackwell_et_al:LIPIcs.ITC.2024.7,
  author =	{Blackwell, Keller and Wootters, Mary},
  title =	{{Improved Trade-Offs Between Amortization and Download Bandwidth for Linear HSS}},
  booktitle =	{5th Conference on Information-Theoretic Cryptography (ITC 2024)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-333-1},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{304},
  editor =	{Aggarwal, Divesh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.7},
  URN =		{urn:nbn:de:0030-drops-205156},
  doi =		{10.4230/LIPIcs.ITC.2024.7},
  annote =	{Keywords: Error Correcting Codes, Homomorphic Secret Sharing}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.16
A Characterization of Optimal-Rate Linear Homomorphic Secret Sharing Schemes, and Applications

Authors: Keller Blackwell and Mary Wootters

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
A Homomorphic Secret Sharing (HSS) scheme is a secret-sharing scheme that shares a secret x among s servers, and additionally allows an output client to reconstruct some function f(x), using information that can be locally computed by each server. A key parameter in HSS schemes is download rate, which quantifies how much information the output client needs to download from each server. Recent work (Fosli, Ishai, Kolobov, and Wootters, ITCS 2022) established a fundamental limitation on the download rate of linear HSS schemes for computing low-degree polynomials, and gave an example of HSS schemes that meet this limit. In this paper, we further explore optimal-rate linear HSS schemes for polynomials. Our main result is a complete characterization of such schemes, in terms of a coding-theoretic notion that we introduce, termed optimal labelweight codes. We use this characterization to answer open questions about the amortization required by HSS schemes that achieve optimal download rate. In more detail, the construction of Fosli et al. required amortization over 𝓁 instances of the problem, and only worked for particular values of 𝓁. We show that - perhaps surprisingly - the set of 𝓁’s for which their construction works is in fact nearly optimal, possibly leaving out only one additional value of 𝓁. We show this by using our coding-theoretic characterization to prove a necessary condition on the 𝓁’s admitting optimal-rate linear HSS schemes. We then provide a slightly improved construction of optimal-rate linear HSS schemes, where the set of allowable 𝓁’s is optimal in even more parameter settings. Moreover, based on a connection to the MDS conjecture, we conjecture that our construction is optimal for all parameter regimes.
Cite as

Keller Blackwell and Mary Wootters. A Characterization of Optimal-Rate Linear Homomorphic Secret Sharing Schemes, and Applications. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{blackwell_et_al:LIPIcs.ITCS.2024.16,
  author =	{Blackwell, Keller and Wootters, Mary},
  title =	{{A Characterization of Optimal-Rate Linear Homomorphic Secret Sharing Schemes, and Applications}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{16:1--16:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.16},
  URN =		{urn:nbn:de:0030-drops-195447},
  doi =		{10.4230/LIPIcs.ITCS.2024.16},
  annote =	{Keywords: Error Correcting Codes, Homomorphic Secret Sharing}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact