技術要約：一般化ルカス行列に基づく新しい公開鍵暗号

問題提起

本論文は、より大きな鍵空間、減少した伝送複雑性、そして数論と線形代数に基づいた堅牢なセキュリティを提供する、強化された公開鍵暗号スキームの必要性に取り組んでいる。行列理論や再帰数列（フィボナッチ数列やルカス数列など）は、暗号学（例：ヒル暗号、ElGamal）において利用されてきたが、既存の手法は、大きな鍵行列の交換を伴うか、標準的な数列の特性に依存していることが多い。著者らは、一般化された再帰行列を用いることで、交換されるデータを最小限に抑えつつ、暗号化鍵の複雑性を最大化するシステムを提案している。

手法

1. 数学的基礎

提案されたスキームの核となるのは、一般化フィボナッチ行列 (GFM) から導出される 一般化ルカス行列 (GLM) の構築である。

• 一般化フィボナッチ行列 (GFM): 著者らは、$k$ 次の一般化フィボナッチ数列 $\{f_{k,n}\}$ と、それに対応する行列表現 $Q^k_n$ を利用している。これらの行列は、$Q^n_k Q^l_k = Q^{n+l}_k$ という標準的な性質や、次数 $k$ に基づく特定の行列式規則を満たす。
• 一般化ルカス数列: 初項が最初の $k$ 個の GFM 行列のトレースから導かれる新しい数列 $\{l_{k,n}\}$ を定義する（$l_{k,r} = \text{trace}(Q^r_k)$）。漸化関係は一般化フィボナッチ数列と同様である：$l_{k,k+n} = \sum_{i=0}^{k-1} l_{k,k+n-1-i}$。
• 一般化ルカス行列 (GLM): 一般化ルカス数列の項の線形結合を用いて、再帰的な行列 $L^{(n)}_k$ を構築する。著者らは、GLM と GFM の間の基本的な関係を以下のように確立している：
  $$L^{(n)}_k = Q^n_k L^{(0)}_k = L^{(0)}_k Q^n_k$$
  ここで、$L^{(0)}_k$ は初期のルカス行列である。

2. 暗号スキーム

提案されたシステムは、これらの行列を、修正された アフィン・ヒル暗号 (Affine-Hill Cipher) と ElGamal 公開鍵インフラストラクチャと統合したものである。

• 鍵交換 (ElGamal ベース):

  • 受信者 (Bob): 素数 $p$、原始根 $\alpha$、および秘密整数 $D$ を選択する。彼は $E_1 = \alpha$ および $E_2 = \alpha^D \pmod p$ を公開する。
  • 送信者 (Alice): ランダムな整数 $e$ を選択する。彼女は署名 $s = E_1^e \pmod p$ と共有秘密 $\lambda = E_2^e \pmod p$ を計算する。
  • 伝送: Alice は暗号文と署名 $s$ を Bob に送る。彼女は完全な鍵行列や秘密 $\lambda$ を送ることはしない。

• 暗号化 (GLM を用いたアフィン・ヒル):

  • 共有秘密 $\lambda$（行列の次数）と署名 $s$（指数）を使用して、Alice は暗号化鍵行列 $K = L^{(s)}_\lambda \pmod p$ を構築する。
  • シフトベクトル $B$ は、ルカス数列の項を用いて生成される：$B = [l_{\lambda,\lambda}, l_{\lambda,\lambda+1}, \dots, l_{\lambda,2\lambda-1}]$。
  • 平文ブロック $P$ は、$C = (P \cdot K + B) \pmod p$ として暗号化される。

• 復号:

  • Bob は自身の秘密鍵を用いて $\lambda$ を復元する：$\lambda = s^D \pmod p$。
  • 彼は逆行列 $K^* = L^{(-s)}_\lambda H^{-1} \pmod p$ を構築する。ここで $H = (L^{(0)}_\lambda)^2$ である。論文では、$L^{(s)}_\lambda L^{(-s)}_\lambda = H$ であることを証明しており、逆行列の存在を保証している。
  • 復号は $P = (C - B) \cdot K^* \pmod p$ として行われる。

主な貢献

1. 一般化ルカス行列の定義: 本論文は、次数 $k$ の GLM を正式に定義し、その行列式公式、積の規則 ($L^{(m)}_k L^{(n)}_k = L^{(m+n)}_k L^{(0)}_k$)、およびその逆行列の明示的な構成を含む代数的性質を確立している。
2. パラメータに基づく鍵生成: 大きなシードから生成または共有される従来の行列ベースの暗号とは異なり、このスキームでは、2つのパラメータ（離散対数問題から導出される $\lambda$ と、署名 $s$）のみを使用して、両者が鍵行列を再構築できる。
3. アフィン・ヒルと ElGamal の統合: 著者らは、ElGamal 設定に固有の離散対数問題によって保護された、アフィン・ヒル暗号（シフトベクトルを用いたブロック暗号）の効率性を利用したハイブリッドスキームを提案している。
4. 逆行列の構成: 論文では、標準的なガウス消去法に頼ることなく、関係式 $Inv(L^{(n)}_k) = L^{(-n)}_k H^{-1}$ を利用して、GLM の逆行列を計算する特定の方法を提供している。

結果と分析

• 実装例: 著者らは、$p=37$、次数 $k=3$、および特定の整数値 $D$ と $e$ を用いてスキームを実証している。彼らは平文 "NOBLE2022" を暗号文ブロックへと正常に暗号化し、元のメッセージを復元しており、行列演算と剰余演算の数学的正当性を検証している。
• 複雑性の低減: このスキームは、鍵伝送の実行時間と空間の複雑性を低減すると主張している。$n \times n$ 行列を送信する代わりに、ペア $(\lambda, s)$ のみが交換される。
• セキュリティ分析:
  • 離散対数: $s$ から $\lambda$ を復元するには、離散対数問題を解く必要があるが、これは大きな素数の場合、計算量的に実行不可能である。
  • 鍵空間: 総当たり攻撃に対するセキュリティは、一般線型群 $|GL(\lambda)|$ の大きさに依存する。著者らは、$p=37$ かつ $\lambda=50$ の場合、鍵空間が約 $3.105 \times 10^{3920}$ であると計算している。これは指数関数的に巨大である。
  • 署名の独立性: 分析によれば、署名 $s$ が既知であっても、セキュリティは主に $\lambda$ を決定することの困難さと、定義された行列空間の広大さに依存するため、セキュリティを損なうことはない。

重要性と主張

本論文は、提案された手法が、正当な当事者には数学的に単純でありながら、侵入者に対しては強力な障壁を提示すると結論付けている。その重要性は以下の点にある：

• 拡大された鍵空間: 一般化ルカス行列の使用により、標準的な実装と比較して利用可能な鍵空間が大幅に拡大される。
• 効率性: 鍵の伝送を数値のペアに削減することで、帯域幅とストレージの面で効率を向上させている。
• 堅牢性: 鍵合意のための離散対数問題と、暗号化のための行列構造の複雑さを組み合わせることで、多層的な防御を実現している。

著者らは、この手法が「正当な当事者にとっては数学的に単純であり、侵入者にとっては非常に困難である」と断言しており、それは離散対数問題の確立された困難さと、一般化ルカス行列の膨大な組合せ空間に基づいている。