無視可能函数
数学における無視可能函数（むしかのうかんすう、英: negligible function）は、極限においていかなる多項式よりも非常に緩やかな増加をするような函数である。
定義
編集実数列 μ: N → R は、任意の正整数 c に対して適当な整数 Nc を選べば、x > Nc なる全ての x について
が成り立つようにできるとき、「無視できる」という。あるいは同じことだが、次のように定義してもよい。すなわち、実数列 μ: N → R が「無視できる」とは、任意の正値多項式 poly(•) に対して適当な自然数 Npoly を選べば、x > Npoly なる全ての x に対して
が成り立つようにできることをいう。
歴史
編集「無視可能」という概念は sound models of analysis にまで遡ることができる。 ニュートンやライプニッツの時代（1680年代）には連続性や無限小の概念が重要な意味を持つようになっていたが、これらの概念は後の1810年代になるまではきちんと定義されたものではなかった。解析学において「連続性」の意味のある厳密な定義が初めて成されるのは、ベルナルト・ボルツァーノが1817年に著した『連続性の現代的定義』においてである。その後、コーシー、ワイエルシュトラスおよびハイネらも以下のような定義を与えている。ここでは数は全て実数全体の成す集合 R に属するものとする。
- 連続函数
- 函数 f: R → R が点 x = x0 において連続であるとは、いかなる正の数 ε > 0 に対しても正の数 δ > 0 を適当に選べば、|x − x0| < δ ならば |f(x) − f(x0)| < ε とできることをいう。
この古典的な連続性の定義を適当に書き換えれば、無視可能性の定義に書き直すことができる。まず、x0 = ∞ において f(x0) = 0 となる場合を考える。ここで「無限小」の概念を定義する必要が生じる。
- 無限小函数
- 連続函数 μ: R → R が（x を無限大に飛ばす極限で）無限小であるとは、あらゆる ε > 0 に対して適当な Nε を選べば、x > Nε なるとき常に |μ(x)| < ε とできることをいう。
引き続き、定義における ε > 0 を函数 1/xc (c > 0) あるいは 1/poly(x)（poly(x) は正値多項式）に取り替えれば、先の無視可能函数の定義を得る。定数 ε > 0 も適当な定数多項式に対する 1/poly(x) として書けるから、無視可能函数のクラスは（無限遠における）無限小函数のクラスの部分集合になっていることがわかる。
暗号理論
編集計算量に基づく現代暗号理論では、セキュリティ方式が証明可能な安全性を持つとは、入力項 x を長さ n の暗号鍵とするとき、セキュリティ失敗（例えば一方向函数が覆されたり、暗号論的強擬似乱数ビットが真のビットと峻別されたり）の可能性が「無視できる」ことをいう。これを適用するためには、鍵長 n は自然数でないといけないので、冒頭の定義における x は自然数としている。
もちろん、無視可能函数の一般概念では系の入力変数 x は何も鍵長 n である必要はないのであって、実際 x は事前に与えられた系の任意の計量としてよく、無視可能函数についての解析学は、こういった系のある種の隠れた解析学的振る舞いを記述するものになる。
多項式の逆数による定式化は、計算論的有界性が多項式時間に従って定義されるのと同じ理由で利用される。これは閉包性質を持つから漸近的な設定において御しやすい。例えば仮に、無視できる可能性しかないセキュリティ条件に反して攻撃が成功したとして、攻撃回数が多項式オーダーで繰り返されたならば、攻撃が全般にわたって成功する可能性はそれでもまだ無視できる。実用上はもっと具体的な函数が求められ、それによって相手の成功可能性を低く抑えたり、その可能性が適当な閾値（2−128 など）を超えない程度に十分に長いセキュリティー変数を選んだりする。
参考文献
編集- Goldreich, Oded (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press. ISBN 0-521-79172-3. Fragments available at the author's web site.
- Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X Section 10.6.3: One-way functions, pp.374–376.
- Christos Papadimitriou (1993). Computational Complexity (1st edition ed.). Addison Wesley. ISBN 0-201-53082-1 Section 12.1: One-way functions, pp.279–298.
- Jean François Colombeau (1984). New Generalized Functions and Multiplication of Distributions. Mathematics Studies 84, North Holland. ISBN 0-444-86830-5