💻 computer science

From Bits to Mixed-Radix Keys: Horner Decomposition, Uniform Sampling, and the Information-Theoretic QKD Interface of the MR-OTP

本論文は、ホーナー法によるマッピング、バイアスを除去するための棄却サンプリング、および安全性と効率性の厳密な証明を利用することで、量子鍵配送ソースからの生のバイナリエントロピーを混合基数ワンタイムパッド用の一様混合基数鍵へと変換するための、実用的かつ情報理論的に安全なフレームワークを確立するものである。

原著者： Fabio F. G. Buono

公開日 2026-06-19

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

CC BY 4.0

原著者： Fabio F. G. Buono

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

全体像：新しい種類の「破れない」鍵

あなたが送りたい秘密のメッセージがあると想像してください。究ディールの秘匿性の基準は「ワンタイムパッド（OTP）」です。これは、鍵がメッセージと同じ長さのランダムな数字の列であるようなロックだと考えてください。もし鍵が真にランダムで、一度も再利用されないのであれば、そのメッセージを解読しようとするコンピュータがいかに強力であっても、数学的に解読は不可能です。

しかし、従来のOTPには欠点があります。それは、それらが「バイナリ（2進数）」（0と1）しか話せないことです。例えば「A」という文字（これは自然な記号であり、0や1ではありません）を送りたい場合、まずそれをバイナリに翻訳しなければなりません。この翻訳作業はスペースを無駄にし、非効率的です。

本論文は、「混合基数ワンタイムパッド（MR-OTP）」を紹介しています。これは、データの「母国語」を話すロックだと考えてください。

DNA（4つの文字）を送る場合は、4面体のサイコロを使用します。
英語のテキスト（26文字）を送る場合は、26面体のサイコロを使用します。
数字（10進数）を送る場合は、10面体のサイコロを使用します。

本論文は、0と1のストリームしか生成できない「量子鍵配送（QKD）」マシンを使用して、このロックを構築する方法という実用的な問題を解決します。

コアとなる問題：「ランダム性の粗い切り出し」

比喩：
完璧に公平な6面体のサイコロの目（0〜5）を吐き出すマシンがあるとします。しかし、あなたのロックには7面体のサイコロ（0〜6）が必要です。

素朴な間違い： 「6面体の出目を取って、1を足して、もし7になったら0にラップアラウンド（循環）させればいい」と考えるかもしれません。
問題点： これでは「偏り（バイアス）」が生じます。特定の数字（例えば0や1）が、他の数字（例えば6）よりも頻繁に現れることになります。完全な秘匿性を求める世界では、たとえ微小な偏りであっても、ドアの隙間を空けているようなものです。それは「破れない」という保証を台無しにします。

論文による解決策：
著者らは、厳格な「棄却サンプリング（Rejection Sampling）」ルールを提案しています。

マシンが数字を生成します。
その数字があなたの7面体の範囲内に収まっている場合は、それを保持します。
もし大きすぎる場合（例：7や8が出た場合）は、それを捨てて、やり直します。
有効な数字が得られるまでこれを繰り返します。

これにより、すべての数字（0から6まで）が選ばれる確率が正確に等しくなることが保証されます。論文では、この方法が非常に効率的であり、量子ストリームのビットをほとんど無駄にしないことを証明しています。

秘伝のレシピ：「ホーナー法」

長いバイナリビットの列（量子マシンからの出力）を、どのようにして特定の混合基数のサイコロの目（例：1つの7面体、1つの13面体、1つの5面体）に変換するのでしょうか？

比喩：
入れ子になったロシアのマトリョーシカ、あるいは塔を建てるための指示書を想像してください。

順方向（構築）： 最初の桁から始め、次のサイコロのサイズを掛け、次の桁を足し、次のサイコロのサイズを掛ける……という作業を繰り返します。これはホーナー法と呼ばれます。これは、異なるサイズの数字を一つの大きな整数の中に詰め込むための巧妙な数学的トリックです。
逆方向（展開）： 鍵を取り出すときは、その逆を行います。大きな数を取り、最後のサイコロのサイズで割って余りを得る（これが最後の鍵になります）、次にその結果を次のサイコロのサイズで割る……という手順を踏みます。

論文は、この「パッキング（詰め込み）とアンパッキング（展開）」が、完全な一対一の対応であることを証明しています。これは、0と1のストリームを、偏りのない完璧な混合基数の鍵へと変換するための代数的な架け橋となります。

セキュリティの保証：「二層の盾」

本論文は、恐ろしい問いに対処しています。「もしハッカーが、私たちが使っているサイコロの『形（基数のシーケンス）』を突き止めてしまったらどうなるのか？」

著者らは「二層の盾」を証明しています。

第1層：形は隠されている（計算量的困難性）。
もしハッカーが、私たちが7面体のサイコロや13面体のサイコロを使っていることを知らない場合、彼らは推測するしかありません。論文は、元のテキストなしに暗号文（シファーテキスト）だけを見た場合、サイコロのサイズのシーケンスを推測することは極めて困難であることを示しています。実際、暗号文のみを見ている場合、サイコロのサイズを知ることは数学的に不可能です。
第2層：鍵は破れない（情報理論的安全性）。
たとえハッカーがサイコロのサイズ（「形」）を突き止めたとしても、メッセージを読み取ることはできません。なぜでしょうか？なぜなら、実際の鍵（それらのサイコロで振られたランダムな数）は、メッセージごとに新しく生成されるからです。
- 比喩： ハッカーが、あなたが26面体のサイコロを使っていることを突き止めたとしましょう。それは彼らにとって素晴らしいことですが、それでもなお、今回のメッセージのために「どの」数字（A〜Z）が振られたのかは分かりません。その振られた目は真にランダムであり、二度と再利用されないため、サイコロのサイズを知ったところで、文字に関する情報は何も得られないのです。

結論： メッセージのセキュリティは、ハッカーがサイコロのサイズを推測する速度に依存しません。たとえハッカーが瞬時にサイコロのサイズを推測できたとしても、鍵が新鮮かつランダムであるため、メッセージは完全に秘密のまま保たれます。

効率性：スペースの節約

論文はまた、素晴らしい副次的効果についても指摘しています。

従来の方法（バイナリOTP）： 文字「A」（26個のうちの1つ）を送るために、5ビット（ $2^5 = 32$ なので）を使用しなければなりません。32は26よりも大きいため、6ビット分のスペースが無駄になります。
新しい方法（MR-OTP）： 26の選択肢に対して、必要なスペースを正確に使用します。
結果： 何百万ものメッセージを通じて、これは「鍵材料（量子マシンから必要なランダムなビット）」の膨大な量を節約します。これは荷造りに似ています。従来の方法は小さなシャツに対して巨大な箱を強制していましたが、新しい方法はシャツにぴったりフィットする箱を使用します。

主な主張の要約

変換方法： 「棄却および再試行」法と「ホーナー分解」と呼ばれる数学的トリックを組み合わせることで、量子ランダムビットを混合基数の鍵に変換できる。
偏りなし： この方法は、完璧な秘匿性の保証に必要な、完全に一様な鍵を作成する。
エンドツーエンドのセキュリティ： 量子マシン $\to$ 変換 $\to$ 暗号化というプロセス全体が、数学的に破れないことが証明されている。
将来への備え： 将来のスーパーコンピュータが、サイコロのサイズ（基数のシーケンス）を瞬時に推測できるようになったとしても、鍵が新鮮でランダムであるため、メッセージは安全に保たれる。
効率性： 特に自然言語や生物学的データにおいて、従来のバイナリ手法と比較してスペースを節約できる。

この論文は、これが今日販売可能な商業製品であると主張しているわけでも、すべての暗号学的問題を解決すると主張しているわけでもありません。これは、この特定のタイプの「完全な秘匿性」を現実世界の量子ハードウェアで機能させるために必要な、数学的基礎とアルゴリズムを厳密に証明するものです。

技術要約：ビットから混合基数鍵へ

問題提起
先行研究 [1] で導入された混合基数ワンタイムパッド（MR-OTP）は、古典的なバイナリ・ワンタイムパッドを、非一様基数を持つ桁空間へと一般化したものである。これにより、中間的なバイナリ変換を行うことなく、ヘテロジニアスなデータアルファベット（例：DNA配列、ラテン文字）をネイティブにエンコードしつつ、シャノンの完全秘密性を保持することが可能となる。しかし、実用的な展開には、量子鍵配送（QKD）ソースからの生のバイナリ・エントロピー出力を、混合基数鍵空間上で一様に分布する鍵タプルへと変換するメカニズムが必要である。

素朴なアプローチとして、 $k = \lceil \log_2 P \rceil$ ビット（ここで $P$ は基数の積）を読み取り、得られた整数を $P$ で剰余演算する手法は、「剰余バイアス」として知られる統計的歪みを導入する。情報理論的な設定において、鍵分布におけるいかなる非一様性も完全秘密性の定理の仮定を破るものであり、そのバイアスの大きさに関わらず、システムを脆弱にする。本論文は、このバイアスを導入することなく、一様なバイナリ・ストリームを一様な混合基数鍵タプルへと変換するためのアルゴリズム的課題に対処している。

手法
本論文は、混合基数の位置重みと多項式評価の入れ子構造との間の構造的等価性を確立している。

代数的対応： 著者らは、この変換における標準的な代数的双対として、**ホーナー法（Horner's method）**とその逆操作を特定している。順方向写像（ホーナー評価）は、桁タプルを単一の整数へと合成し、逆方向写像（逆ホーナー分解）は、逐次的な剰余演算を通じて整数から桁を復元する。これにより、鍵空間 $\mathcal{K}$ と整数区間 $\{0, \dots, P-1\}$ の間に全単射関係が確立される。
棄却サンプリング： 剰余バイアスを排除するために、本論文は棄却サンプリング・アルゴリズム（アルゴリズム1）を提案している。このアルゴリズムは、 $k$ ビットを抽出して整数 $V$ を形成する。もし $V \ge P$ であれば、そのサンプルは破棄され、プロセスが繰り返される。もし $V < P$ であれば、逆ホーナー分解が適用されて鍵タプルが生成される。
セキュリティ分析フレームワーク： 本論文は、単一および複数セッションにおけるフルパイプライン（QKD $\to$ 鍵抽出 $\to$ MR-OTP 暗号化）を分析している。ここでは、各セッションの鍵と基数シーケンスに対して、QKDストリームの互いに素なブロックを使用するパーティション・キーローリング・スキームを採用している。
敵対者分類： セキュリティ分析では、4つの敵対者クラス（テスト型、代数的、無制限、および暗号文のみ）を区別している。また、「計算論的秘密」（基数シーケンス $B$ ）と「情報理論的秘密」（パド $K$ ）を分離している。

主要な貢献と結果

一様な鍵サンプリング： 本論文は、素朴な剰余演算が完全秘密性を損なうことを証明している（命題 3.1）。棄却サンプリングと逆ホーナー分解を組み合わせることで、鍵空間上の一様な分布が回復されることを示している（定理 3.4）。このプロセスの期待ビットコストは $2\lceil \log_2 P \rceil$ によって抑えられ、棄却ラウンドの期待回数は最大で2回である（命題 3.5）。
エンドツーエンドのセキュリティ： 理想的なQKDソース、棄却サンプリング・アルゴリズム、およびMR-OTPの合成は、単一セッション（定理 4.2）およびパーティション・キーローリング・スキームの下での $N$ セッション（定理 6.2）において、シャノンの完全秘密性を達成する。これは計算論的な仮定なしに成立する。
表現効率： 本論文は、自然なアルファベットに対するMR-OTPのバイナリOTPに対する効率性の向上を定量化している。ネイティブなシンボル空間で動作することにより、MR-OTPはバイナリ符号化に固有の「バイナリ・オーバーヘッド」（ $\lceil \log_2 b \rceil - \log_2 b$ ）を排除する。例えば、十進数字に対しては約 $16.9\%$ 、ラテン文字に対しては約 $6.0\%$ の鍵材料の削減を実現する（命題 5.3）。
基数回復問題（BRP）：
- 暗号文のみ： 本論文は、暗号文のみから基数シーケンス $B$ を復元することは情報理論的に不可能であることを証明している（系 8.2）。暗号文は、 $b_i > c_i$ という制約を除いて、 $B$ に関する情報を一切提供しない。
- 既知平文： 既知平文の設定において、本論文はテスト型敵対者に対するクエリ複雑性の無条件の下限を確立しており、識別には少なくとも $|F_T| - 1$ 回のクエリが必要であることを示している。ここで、 $T$ が小さい場合、 $|F_T|$ はメッセージ長 $L$ に対して指数関数的に残る（定理 8.10）。
- セキュリティの不変性： 中心的な結果（定理 8.15）は、たとえ敵対者（有界または無界）が既知平文データから基数シーケンス $B$ を正常に復元したとしても、新しい鍵を用いて暗号化された将来のメッセージに関する情報を一切得られないことを証明している。パドの情報理論的セキュリティは、基数回復問題の計算論的ステータスに関わらず保持される。
バッチ抽出： 本論文は、単一の大きな整数を抽出して $N$ 個の鍵桁を同時に生成するバッチ鍵抽出アルゴリズム（セクション 9）を導入している。これにより、逐次的なサンプリングと比較して棄却オーバーヘッドが軽減され、 $N \to \infty$ において理論的なエントロピー限界である $\log_2 b$ ビット/シンボルに近づく（定理 9.2）。
非理想的なソース： 本論文は、全変動距離において一様分布に $\epsilon$ -近い非理想的なQKDソースへのセキュリティ保証を拡張している。エンドツーエンドのセキュリティの劣化は、 $N$ セッションにおいて $2N\epsilon$ によって抑えられることを示している（定理 10.3）。

意義と主張
本論文は、厳格な情報理論的セキュリティを維持しながら、QKDソースを用いたMR-OTPを展開するための完全なアルゴリズム的基礎を提供すると主張している。その主な意義は以下の通りである：

バイアス問題の解決： 完全秘密性の一様性要件を破ることなく、バイナリ・エントロピーを混合基数鍵に変換するための、証明可能な正しい手法（棄却サンプリング＋ホーナー逆変換）を提供している。
無条件の時間的セキュリティ： 基数シーケンスの復元の困難さが、将来のメッセージのセキュリティに影響を与えないことを確立している。たとえ基数シーケンスが復元されたとしても、システムは新しい暗号化に対して完全秘密性を保持する。これにより、計算論的レイヤー（基数を隠す）と情報理論的レイヤー（メッセージを隠す）が独立した、「二層」のセキュリティ構造が構築される。
効率性： MR-OTPは理論的に健全であるだけでなく、2の累乗ではないアルファベットに対してバイナリOTPよりも実用的に効率的であり、セキュリティを犠牲にすることなく鍵消費を削減できることを示している。
敵対者分類： 敵対者の能力を厳密に分離し、既知平文の設定における（テスト型 vs 代数的）特定のサブセットに対しては計算論的困難性が適用される一方で、情報理論的保証はすべての敵対者クラスに対して無条件に成立することを証明している。

本論文は、動的なキーローリング・バリアント（基数シーケンスが前の暗号文に依存する場合）および代数的敵対者に対する基数回復問題の平均的な計算論的困難性に関する未解決問題を特定することで締めくくられている。