💻 computer science

Partial Derandomization for Leakage-Resilient Shamir's Secret Sharing over Composite Order Fields

本論文は、 $n$ 個の独立した乱数点を固定された有理関数の反復に置き換えることにより、評価点の決定における合成位数体上の漏洩耐性を持つシャミールの秘密分散の部分的脱ランダム化を提示し、特定のパラメータ領域において単一ブロックの漏洩に対する完全な安全性を達成しつつ、必要な乱数量を $nd \log p$ ビットから $d \log p$ ビットへと削減するものである。

原著者： S. Venkitesh

公開日 2026-08-03

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： S. Venkitesh

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

想像してみてください。あなたは宝の地図やパスワードのような秘密を守ろうとしていますが、その秘密をバラバラに分割して、それぞれの断片を友人たちに渡さなければなりません。これが「秘密分散（Secret Sharing）」の世界です。数学者シャミールによって発明された古典的な手法は、まるで魔法のパズルのようです。例えば、5人の友人のうち3人が断片を持ち寄れば、パズルは自動的に解けて宝が姿を現します。しかし、集まった人数が足りなければ、断片はただのデタラメな文字列に見え、秘密は守られたままとなります。

しかし、現実の世界は混沌としています。ずる賢い泥棒は、パズルの断片そのものを盗み取ることはできなくても、同時にすべての友人の断片から、ごくわずかな情報を、少しずつ覗き見ることができるかもしれません。例えば、コンピュータチップ上の特定のライトが点灯しているか消えているかを見たり、微かな電気的なハム音を聞いたりすることです。これは「物理的ビット漏洩（physical bit leakage）」と呼ばれます。それは、鍵の束から鍵そのものを盗むことはできなくても、すべての鍵の歯の形を、一度に一つの小さな凹凸として感じ取ってしまうようなものです。もしパズルの断片が不注意に配置されていれば、これらの微細な覗き見が積み重なり、秘密全体を暴いてしまう可能性があります。

長い間、この泥棒を防ぐための最善の方法は、パズルの断片を完全にランダムに選ぶことでした。これは、隠し場所を決めるためにサイコロを振るようなものです。これは非常に効果的ですが、問題があります。それは、セットアップを行うたびに、信頼できる「サイコロの振る人（完全な乱数の供給源）」が必要になることです。もしサイコロの目が操作されていたり、泥棒がその出目に影響を与えられたりすれば、システム全体が崩壊してしまうかもしれません。科学者たちは、毎回サイコロを振る代わりに、単純で固定されたルールを使って隠し場所を選ぶ方法を見つけ出したいと考えていました。そうすれば、誰が見ていようとも、システムは常に安全になります。

この論文は、まさにその問題に取り組んでいます。著者は、こうした微細な覗き見に対して、秘密分散は「完全に安全」か「完全に破綻」かのどちらかであるという最近の発見に基づき、隠し場所を選ぶ新しい方法を提示しています。一人ひとりの友人のために毎回サイコロを振る代わりに、巧妙で繰り返される数学的なパターンを使用します。一つの開始数を選び、そこから単純な数式を繰り返し適用することで、連鎖反応のようにすべての隠し場所を生成していくのです。

著者は、この方法が驚くほど優れていることを証明しています。彼らは、特定のグループ規模の範囲において、この構造化されたパターンが秘密分散スキームを「完全に安全（perfectly secure）」にすることを明らかにしました。これは、漏洩した情報の統計的な距離が正確にゼロであることを意味します。つまり、泥棒はたとえ微かな優位性さえも得られず、情報を一切学ぶことができないのです。また、著者は、開始数が「良い（安全な）」ものか「悪い（安全でない）」ものかを判定するテストを提供し、良い開始数を見つけることは容易であることを証明しています。この方法は、ランダムなサイコロを使う方法よりも扱える友人の数はわずかに少なくなりますが、信頼できるサイコロの振る人を必要としなくなるため、より実用的で、操作に対しても強固なシステムとなります。また、本論文では、より単純で明白なパターン（単に数値を掛け合わせるだけのもの）を使用することは、彼らの新しい数式に含まれる特定の数学的な「ひねり」を欠いているためにセキュリティを提供できないとして、明確に否定しています。

技術要約：合成次数体における漏洩耐性を持つシャミアの秘密分散法の部分的決定論化

1. 問題設定

本論文は、合成次数体（ $d \ge 2$ である $\mathbb{F}_{p^d}$ ）における物理ビット漏洩（physical-bit leakage）に対して耐性を持つ、シャミアの秘密分散法（SSS）のための明示的な評価点（evaluation places）の構成について取り組んでいる。

標準的なSSSでは、秘密が $n$ 個のパーティ間で共有され、任意の $k$ 個が集まればそれを復元できる。ランダム化された構成（評価点を一様にランダムに選択するもの）は、局所的な漏洩に対して統計的に安全であることが知られているが、これには信頼できる公開乱数が必要となる。実際には、攻撃者が乱数シードに影響を与え、スキームを脆弱な評価点へと誘導する可能性がある。

先行研究では以下のことが確立されている：

素数体（ $\mathbb{F}_p$ ）上では、ランダムな評価点は高い確率で漏洩耐性を実現する。
合成次数体（ $\mathbb{F}_{p^d}$ ）上では、Nguyen（EUROCRYPT 2025）が完全な二分法（perfect dichotomy）を確立した。すなわち、任意の線形符号ベースの秘密分散法は、物理ビット漏洩に対して「完全に安全（統計的距離 0）」であるか、「完全に無防備」であるかのいずれかである。
しかし、合成次数体においては、 $k > 2$ または一般的なブロック漏洩レジームに対して、明示的かつ決定論的な評価点の族はこれまで知られていなかった。素数体における既存の明示的な構成は、合成体の線形座標写像には適用できない非線形なビット抽出特性に依存していた。

核心となる課題は、合成体設定において物理ビット漏洩に対する完全な安全性を維持しつつ、評価点の選択を部分的決定論化（エントロピーの削減）することである。

2. 手法および構成

著者は部分的決定論化戦略を提案している。 $n$ 個の独立したランダムな評価点を選択する代わりに、ランダムに選ばれた基点 $x_0$ に有理関数 $\Phi$ を繰り返し適用することで、評価点を構成する。

構成の詳細:

体のセットアップ: $\mathbb{F} = \mathbb{F}_{p^d}$ とし、原始元を $\alpha$ とする。
ステップ演算子: モービス変換 $\Phi(x) = \frac{\alpha x}{x + 1}$ を定義する。
評価点: $n$ 個の評価点は、 $x_j = \Phi^j(x_0)$ （ただし $j = 0, \dots, n-1$ ）として定義される。ここで $x_0 \in \mathbb{F}^*$ はランダムに選ばれた基点である。
エントロピーの削減: このスキームの指定に必要なのは $d \log p$ ビット（ $x_0$ を選ぶため）であり、 $n$ 個の独立したランダムな点が必要な場合の $nd \log p$ ビットから大幅に削減されている。

鍵となる構造的洞察:
セキュリティ分析は、 $\Phi$ の反復による**異なる極（distinct poles）**に基づいている。

$\Phi^0(x) = x$ は $\infty$ に極を持つ。
$j \ge 1$ の場合、 $\Phi^j(x)$ は $\mathbb{F}^*$ 内の異なる有限の点に極を持つ。
この「極の相違性（pole-distinctness）」が極めて重要である。著者は、候補となる $\Psi(x) = \alpha x$ （純粋な拡大）との対比を示している。 $\Psi(x)$ では、すべての反復が $\infty$ という同一の極を共有するため、セキュリティの議論が崩壊してしまう。

3. 技術的アプローチ

証明は、Nguyen (2025) によって確立された完全な二分法を利用して、以下の3つのフェーズで進行する。

完全な二分法 (フェーズ1):
$\mathbb{F}_{p^d}$ における座標抽出は $\mathbb{F}_p$ 線形であるという事実を利用する。その結果、漏洩マップは線形となる。これは、異なる秘密に対する漏洩分布の統計的距離が 0 または 1 であることを意味する。完全な安全性は、テスト行列 $\Theta_{\vec{i}}$ （評価点と漏洩パターンから導出される）が $\mathbb{F}_p$ 上でフル列ランクを持つことと同値である。
部分分数分解の非退化性 (フェーズ2):
テスト行列がフルランクであることを証明するために、著者は評価点の累乗の非自明な線形結合が消滅しないことを示さなければならない。彼らは有理関数 $G_\ell(x) = \sum c_j \eta(i_j) (\Phi^j(x))^\ell$ を定義する。部分分数分解を用いることで、 $\Phi^j$ の異なる極を利用する。極が互いに異なるため、 $G_\ell$ の特定の極における留数（residue）は、和の中の単一の項によって決定される。もし $G_\ell$ が恒等的にゼロであれば、すべての係数がゼロにならなければならない。この「非退化性」の議論により、ランク条件が失敗する「悪い」基点 $x_0$ の数を制限できる。
マルチブロックへの拡張 (フェーズ3):
この議論をマルチブロック漏洩（各シェアあたりの複数の座標が漏洩する場合）に拡張する。シェア内の線形結合から生じる体の係数を処理し、漏洩パターンが「許容可能（admissible）」（シェアごとに異なるブロック位置を持つ）である限り、部分分数分解の議論が有効であることを示す。

4. 主要な結果

定理 1.1 (シングルブロック漏洩に対する完全な安全性):
パラメータ $n = O(d / \log_p d)$ および任意の閾値 $k \ge 2$ に対して、サイズ $|Bad| \le n + n(dp)^n$ である「悪い」基点の集合 $Bad \subset \mathbb{F}^*$ が存在する。 $x_0 \notin Bad$ である任意の $x_0$ について、評価点 $x_j = \Phi^j(x_0)$ を用いたスキームは、あらゆるシングルブロック漏洩パターンに対して完全な安全性（統計的距離は正確に 0）を持つ。

これは、任意の素数 $p$ に対して、シェアあたりのシングル物理ビット漏洩に対する完全な安全性を示唆している。
$d > n(1 + \log_p d) + \log_p(2n)$ であるとき、良好な $x_0$ の存在が保証される。

定理 1.2 (マルチブロック漏洩):
$M$ 個の合計ブロックが漏洩する固定された許容可能な漏洩パターンに対して、悪い集合のサイズは $n + n \cdot p^M$ で抑えられる。 $M < d - \log_p(2n)$ であるとき、良好な $x_0$ が存在する。

$\le M$ 個のブロックを持つすべてのパターンに対する普遍的な安全性については、 $|Bad| \le n + n(dpe)^M$ となり、 $d > M(\frac{5}{2} + \log_p d) + \log_p(2n)$ のときに存在が保証される。

分類器:
本論文は、候補となる $x_0$ が与えられたとき、すべての漏洩パターンに対してフルランク条件を検証する明示的な分類器（アルゴリズム 1）を提供している。これは、構造化された構成の安全性を証明するための健全なテストとして機能する。

5. 意義と比較

本論文は、以下の貢献と区別を主張している：

完全な安全性 vs 統計的安全性: 合成体上の従来のランダム化された構成が統計的安全性（ $\epsilon = 2^{-\Omega(d)}$ ）を提供していたのに対し、本構成は特定のパラメータ領域において完全な安全性（統計的距離 0）を達成する。
決定論化: 評価点を（ $\Phi$ の軌道という）一パラメータ族に制限することで、スキームを指定するために必要な乱数を $nd \log p$ ビットから $d \log p$ ビットへと削減している。
明示的な構成: 物理ビット漏洩に耐える、合成体上の $k > 2$ 用の初の明示的な評価点の族を提供し、「ランダムな評価点」のパラダイムを超えた。
限界とトレードオフ:
- パーティ数 $n$ は $O(d / \log_p d)$ に制限されている。これは、ランダム化された構成が $O(dk / \log_p d)$ をサポートしているのと対照的である。著者は、この因子 $k$ の損失は一パラメータ構成に固有のものであると推測している。
- マルチブロックの普遍性は、現在、パターン列挙のボトルネックによって制限されており、 $M$ に関する指数関数的な悪い集合の境界が存在する。
- 本構成は、モービス変換 $\Phi(x) = \alpha x / (x+1)$ の特定の代数的構造に依存している。代替案である拡大 $\alpha x$ は、セキュリティを提供できない。

本研究は、すべてのパラメータ領域に対して決定論化問題を解決すると主張しているわけではなく、マルチブロックの普遍性における多項式サイズの悪い集合の境界などの未解決問題も特定しており、単一パラメータ構成による「因子 $k$ の損失」が固有の性質である可能性を示唆している。主要な貢献は、異なる極の反復を利用することで、実用的に関連のある特定の領域において完全な安全性を達成する、厳密な部分的決定論化である。