2026-07-28T13:32:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20515 2024-08-06T05:20:07Z ddc:004 open_access

Improved Trade-Offs Between Amortization and Download Bandwidth for Linear HSS Blackwell, Keller Wootters, Mary Error Correcting Codes Homomorphic Secret Sharing 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Keller Blackwell and Mary Wootters 2024 Is Part Of LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2024.7 urn:nbn:de:0030-drops-205156 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.7 eng https://creativecommons.org/licenses/by/4.0/legalcode