無視可能函数とは何か — 暗号学での定義・性質・応用を深掘り

2025年12月12日 最終更新日時 : 2025年12月12日 エバープレイ編集部

はじめに

無視可能函数（無視可能関数、negligible function）は、現代の暗号学における基礎概念の一つです。暗号学的な安全性は「ある攻撃成功確率が無視可能である」と表現されることが多く、この直感的な「無視してよいほど小さい」という概念を厳密化したものが無視可能函数です。本稿では定義・具体例・基本性質・証明スケッチ・暗号応用での扱い方・注意点まで幅広く、かつ厳密に解説します。

形式的定義

正整数 n を安全性パラメータとするとき、函数 ν: N → R は「無視可能（negligible）」であるとは、任意の正の整数 c に対して、ある N 0 が存在して、すべての n ≥ N 0 について

ν(n) < 1 / n^c

が成り立つことをいいます。直感的には、ν(n) は任意の多項式の逆数よりも最終的に小さくなる、すなわち n→∞ において任意の逆多項式よりも速く 0 に収束する函数です。

代表的な例と非例

  • 有利な例（無視可能）: 2-n, 2-n/2, exp(-n), exp(-nα) (α>0), 1/2log^2 n など。これらは任意の多項式の逆数よりも速く 0 になる。

  • 非例（無視できない）: 1/n, 1/n^2, 1/log n, 1/sqrt(n) など。これらは多項式の逆数のクラスに留まり、定義を満たさない。

  • 注意すべき境界: 1/exp(log n) = 1/n は非無視可能。したがって「指数関数的に小さい」と「多項式的に小さい」は明確に区別される。

基本的性質とその証明スケッチ

無視可能函数は暗号学的議論で便利な代数的性質を持っています。主要な性質を挙げ、簡単な証明スケッチを示します。

  • （1）有界和: もし ν1(n), …, νk(n) がいずれも無視可能であれば、その和 ν(n)=∑i=1k νi(n) も無視可能である。

    証明スケッチ: 任意の c に対し、各 νi について十分大きな Ni を取れば νi(n)<1/(k n^c) となる。n≥max Ni とすれば和は < k·(1/(k n^c))=1/n^c。よって定義を満たす。

  • （2）多項式倍: 任意の多項式 p(n) と無視可能 ν(n) について、p(n)·ν(n) も無視可能である。

    証明スケッチ: ν は任意の正整数 c に対し n として大きければ ν(n)<1/n^{c+deg p} とできる。よって p(n)·ν(n) < poly(n)/n^{c+deg p} ≦ 1/n^c となる。

  • （3）多項式個の和: 多項式個の無視可能函数の和は無視可能である（上の和の拡張）。一方、指数個（例えば 2^n 個）の和は一般に無視可能とは限らない。

応用 — 暗号学での使われ方

暗号学では「攻撃者の成功確率の優位（advantage）」や「失敗確率」を無視可能と表現することで、実用的に安全であることを示します。主な応用場面を挙げます。

  • 安全性の定義: 例えば「ある暗号化スキームは任意の多項式時間攻撃者に対して、租弁（distinguishing）優位が無視可能である」と言うとき、その意味は攻撃者の区別成功確率が 1/2 に対して無視可能にしか上回らない、ということです。つまり成功確率は 1/2 + ν(n) で ν は無視可能。

  • 結合と還元: 安全性還元では、ある攻撃の成功確率をいくつかの事象の和として上界しがちです。上で述べた性質により、（多項式個の）事象それぞれが無視可能ならば、その和も無視可能であり、全体として無視可能な優位に収まることが保証されます。ハイブリッド法で多くのハイブリッドケースを線形和で扱えるのはまさにこれが理由です。

  • パラメータ選択: 実装では「2-λ 程度の小ささ」を目標に安全性パラメータ λ を選ぶことが多いです。これは無視可能であるだけでなく、実用的に十分に小さい値を与えるためでもあります。

注意点・誤解しやすい点

  • 無視可能は「ゼロではない」: 無視可能函数は厳密に 0 である必要はなく、むしろ 0 に収束する速度の概念です。実運用では「十分小さい」ことと「理論上無視可能」には差がある点に注意してください。

  • 非一様（non-uniform）モデル: 非一様攻撃者（アドバイサリに助言列を与える事前情報を許すモデル）では、優位の扱いが変わる場合があります。非一様モデルでも同様に無視可能性を使いますが、証明では回路サイズや助言の長さに応じた議論が必要です。

  • 確率と期待値: 無視可能函数は確率や期待値の上界としてしばしば現れますが、「平均的には無視可能」か「ほとんど確実に無視可能か」を区別する必要があります（例えば期待値が無視可能でも高い確率で大きな値を取る分布は問題）。

数学的観点からの類似概念

計算複雑性や解析学には類似の漸近概念がいくつかありますが、無視可能は特に「任意の多項式の逆数より小さい」という性質に特化しています。たとえば「超多項式的に小さい」と言う場合は、任意の多項式 p(n) に対して ν(n)<1/p(n) と表現され、無視可能の定義と一致します。数学的には、無視可能函数は o(1/poly(n)) 全体の集合です。

証明: 多項式倍が無視可能を保つことの詳細

ここでは性質（2）のもう少し詳細な証明を示します。仮定として ν は無視可能であり p(n) は多項式で次数を d とします。任意の c>0 を取ると、無視可能性より、ある N について n≥N のとき ν(n) < 1/n^{c+d} が成り立ちます。したがって n≥N に対して

p(n)·ν(n) < p(n)·(1/n^{c+d}) ≦ C·n^{d}·(1/n^{c+d}) = C·(1/n^{c})

ここで p(n) ≤ C·n^{d} を満たす定数 C を使いました。ゆえに任意の c に対して十分大きな N が存在して p(n)·ν(n) < 1/n^{c} が成り立つため、p(n)·ν(n) は無視可能です。

実務でのパラメータ例と解釈

例えば RSA や ECC の安全性パラメータ λ を 128 や 256 に取る場合、攻撃の成功確率は理想的には 2-λ 程度になることを期待します。2-128 は無視可能であり、実際的には爆発的に小さいため「現実世界での攻撃は実質的にあり得ない」と判断されます。しかし注意点として、実装の脆弱性やサイドチャネル攻撃は理論上の無視可能な優位を無効化する可能性があり、単に理論的に無視可能であることだけでは不十分です。

よくある応用例：ハイブリッド引数

ハイブリッド引数は暗号学で非常に多用される手法です。典型的には多段階でゲームを切り替え、それぞれのステップで生じる差を無視可能な項で上界します。各ステップの差が無視可能であり、ステップ数が多項式であるならば全体の差は和の性質により無視可能に保たれます。これが「安全性証明が多段階で分解できる」強力な理由です。

まとめ

無視可能函数は暗号の安全性を厳密に議論するための基本ツールで、任意の多項式の逆数より速く 0 に収束する概率や優位を表現します。和や多項式倍に関して閉じているため、還元証明やハイブリッド法と非常に親和性があります。実務では理論的な無視可能性と実装上の安全性を区別して扱うことが重要です。

参考文献

カテゴリー
IT
前の記事
ピーター・ローレの生涯と演技史：代表作・タイプキャスト・遺産を徹底解剖New!!
2025年12月12日
次の記事
『天気の子』徹底解説：新海誠が描く気候・青春・都市の寓話と映像美の秘密New!!
2025年12月12日