Search Results

Documents authored by Blackwell, Keller

Document
DOI: 10.4230/LIPIcs.ITCS.2026.19
Limitations to Computing Quadratic Functions on Reed-Solomon Encoded Data

Authors: Keller Blackwell and Mary Wootters

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We study the problem of low-bandwidth non-linear computation on Reed-Solomon encoded data. Given an [n,k] Reed-Solomon encoding of a message vector 𝐟 ∈ 𝔽_q^k, and a polynomial g ∈ 𝔽_q[X₁, X₂, …, X_k], a user wishing to evaluate g(𝐟) is given local query access to each codeword symbol. The query response is allowed to be the output of an arbitrary function evaluated locally on the codeword symbol, and the user’s aim is to minimize the total information downloaded in order to compute g(𝐟). This problem has been studied before for linear functions g; in this work we initiate the study of non-linear functions by starting with quadratic monomials. For q = p^e and distinct i,j ∈ [k], we show that any scheme evaluating the quadratic monomial g_{i,j} := X_i X_j must download at least 2 log₂(q-1) - 3 bits of information when p is an odd prime, and at least 2log₂(q-2) -4 bits when p = 2. When k = 2, our result shows that one cannot do significantly better than the naive bound of k log₂(q) bits, which is enough to recover all of 𝐟. This contrasts sharply with prior work for low-bandwidth evaluation of linear functions g(𝐟) over Reed-Solomon encoded data, for which it is possible to substantially improve upon this bound [Venkatesan Guruswami and Mary Wootters, 2016; Tamo et al., 2018; Shutty and Wootters, 2021; Kiah et al., 2024; Con and Tamo, 2022]. Some proofs have been omitted from this extended abstract; the full version can be found at [Keller Blackwell and Mary Wootters, 2025].
Cite as

Keller Blackwell and Mary Wootters. Limitations to Computing Quadratic Functions on Reed-Solomon Encoded Data. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 19:1-19:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{blackwell_et_al:LIPIcs.ITCS.2026.19,
  author =	{Blackwell, Keller and Wootters, Mary},
  title =	{{Limitations to Computing Quadratic Functions on Reed-Solomon Encoded Data}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{19:1--19:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.19},
  URN =		{urn:nbn:de:0030-drops-253064},
  doi =		{10.4230/LIPIcs.ITCS.2026.19},
  annote =	{Keywords: Distributed computation, Reed-Solomon codes}
}
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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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