Fugu-MT 論文翻訳(概要): Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection

論文の概要: Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection

arxiv url: http://arxiv.org/abs/2610.12357v1
Date: Thu, 08 Oct 2026 17:23:04 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-10 02:36:54.21955
Title: Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection
Title（参考訳）: Shamir Secret Sharing と Worst-Case Optimal Polynomial Intersection の局所リーク抵抗性の改善
Abstract要約: Shamirシークレット共有のための局所漏洩抵抗性とOPI(Optimal Polynomial Intersection)の2つの問題我々は、これらの2つの問題(Sun、Wooters 2026)の間の最近の接続を使って、両方の問題の最先端を改善します。 LLR に対して、ある定数 $> 0$ が存在して、$R := k/n geq 1/2 - $ である限り、シャミールの秘密共有は局所的に1ビットレジリエントである。これがいわゆる「一」を破る最初の結果である
参考スコア（独自算出の注目度）: 10.37026246853005
License: http://creativecommons.org/licenses/by/4.0/
Abstract: 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(α_1), \ldots, Q(α_n)$, for distinct non-zero evaluation points $α_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(α_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 $δ> 0$ so that, as long as $R := k/n \geq 1/2 - δ$, 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}_ρ(R)-\varepsilon$ fraction of the lists in expectation, for every fixed $\varepsilon>0$, where $\mathsf{SCL}_ρ$ 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.
Abstract（参考訳）: そこで本研究では,Shamir秘密共有のためのLLR(Local Leakage Resilience)と,OPI(Fast-case Optimal Polynomial Intersection)の2つの問題について検討する。どちらの問題も、素順序有限体 $\mathbb{F}_p$ 上の多項式 $Q(X)$ は$k$ 以下である。シャミールの秘密共有のための LLR では、異なるゼロでない評価点 $α_i \in \mathbb{F}_p$ に対して、Q(α_1), \ldots, Q(α_n)$ の各ビットから漏れた数ビットに対して、$Q(0)$ についてどのくらい学べるかを問う。 OPI では、入力リスト $S_1, \ldots, S_n \subset \mathbb{F}_p$ が与えられ、$k$ 以下の多項式 $Q(X)$ を求めるので、$Q(α_i) \in S_i$ をできるだけ多くの$i$ に対して求める。これらの2つの問題(Sun, Wootters 2026)間の最近の接続を活用して、両問題の最先端を改善します。 LLR に対して、ある定数 $δ> 0$ が存在して、$R := k/n \geq 1/2 - δ$ である限り、シャミールの秘密共有は局所的に1ビットのリーク耐性を持つ(つまり、$Q(0)$)。これは、LLRのいわゆる「一半障壁」を破る最初の結果であり、R \geq 0.668$ (Kasser, 2025) を必要とする以前の最もよく知られた結果よりも改善されている。 OPI に対して、少なくとも$\mathsf{SCL}_ρ(R)-\varepsilon$ を期待するリストの分数に一致する多項式 $Q(X)$ を求める量子アルゴリズムを与え、ここで $\mathsf{SCL}_ρ$ は (Jordan et al , 2025) の \emph{semicircle law} である。これにより (Jo, 2026) と (Horinaga, Yamakawa, 2026) のアルゴリズムによる以前の結果が向上する。また、さらに改良された実測結果も提供します。我々はまた、(山川, Zhandry, 2024) の硬度結果を OPI に適用し(折りたたみ版ではなく)、大体上は、会員オラクルに対して OPI の量子的硬度と古典的硬度を無条件に分離する。

論文の概要: Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection

関連論文リスト