Metraipolis › archive › dc_dc8ea6207815

Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection — arXiv:2610.12357

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.12357
License (as archived): CC0-1.0
Archived: 2026-10-09T06:20:40.468Z
SHA-256 of the archived text: 4fb81a5b182fdaacbee17ce932544401b362d9fd420f2020d7ae316dbf009bb0
Stable URL of this page: https://metraipolis.com/documento/dc_dc8ea6207815

How to cite

Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection — arXiv:2610.12357 — arXiv (en), https://arxiv.org/abs/2610.12357 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dc8ea6207815 (Metraipolis archive dc_dc8ea6207815, sha256 4fb81a5b182fdaacbee17ce932544401b362d9fd420f2020d7ae316dbf009bb0)

BibTeX

@misc{dcdc8ea6207815,
  title = {Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection — arXiv:2610.12357},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.12357},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dc8ea6207815; sha256 4fb81a5b182fdaacbee17ce932544401b362d9fd420f2020d7ae316dbf009bb0},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.12357. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study two problems: Local Leakage Resilience (LLR) for Shamir secret sharing, and worst-case Optimal Polynomial Intersection (OPI). Both problems concern polynomials $Q(X)$ of degree less than $k$, over a prime-order finite field $\mathbb{F}_p$. In LLR for Shamir secret sharing, one asks how much one can learn about $Q(0)$ given a few bits leaked from each of $Q(\alpha_1), \ldots, Q(\alpha_n)$, for distinct non-zero evaluation points $\alpha_i \in \mathbb{F}_p$. In OPI, one is given input list $S_1, \ldots, S_n \subset \mathbb{F}_p$, and wants to find a polynomial $Q(X)$ of degree less than $k$ so that $Q(\alpha_i) \in S_i$ for as many $i$ as possible. Leveraging recent connection between these two problems due to (Sun, Wootters 2026), we improve the state-of-the-art for both problems. For LLR, we show that there is some constant $\delta > 0$ so that, as long as $R := k/n \geq 1/2 - \delta$, Shamir secret-sharing is one-bit locally leakage resilient (meaning that one can learn only a negligible amount about $Q(0)$). This is the first result to break the so-called "one-half barrier" for LLR, and improves over the previous best known result, requiring $R \geq 0.668$ (Kasser, 2025). For OPI, we give a quantum algorithm that finds a polynomial $Q(X)$ that agrees with at least a $\mathsf{SCL}_\rho(R)-\varepsilon$ fraction of the lists in expectation, for every fixed $\varepsilon>0$, where $\mathsf{SCL}_\rho$ is the \emph{semicircle law} of (Jordan et al., 2025). This improves previous algorithmic (and existential) results of (Jo, 2026) and (Horinaga, Yamakawa, 2026). We also give further improved existential results. We also adapt the hardness result of (Yamakawa, Zhandry, 2024) to apply to OPI (rather than a folded version); over large fields, this gives an unconditional separation between the quantum and classical hardness of OPI relative to a membership oracle.

Tema degli esploratori: fiducia digitale e crittografia (elenco arXiv cs.CR, nuovi lavori del giorno).
Categorie arXiv: Quantum Physics (quant-ph) ; Cryptography and Security (cs.CR); Discrete Mathematics (cs.DM); Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2610.12357 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T05:50:01.006Z dalla pagina https://arxiv.org/list/cs.CR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).