Trapdoor function とは

トラップドア関数は、一方向に計算するのは簡単ですが、トラップドアと呼ばれる特別な情報なしに反対方向に計算することは難しい(その逆行列を求める)関数です。トラップドア機能は、暗号化に広く使用されています。
数学的には、fがトラップドア関数である場合、与えられたf(x)とyのようないくつかの秘密情報yが存在し、xを計算することは容易である。南京錠とその鍵を考えてみましょう。シャックルをロック機構に押し込むことで、キーを使わずにパドロックをオープンからクローズに変更することは自明です。しかし、錠前を簡単に開くには、キーを使用する必要があります。ここで鍵はトラップドアであり、パドロックはトラップドア機能です。
単純な数学的なトラップドアの例は、「6895601は2つの素数の積であり、その数字は何ですか?典型的な解決方法は、答えを見つけるまで6895601をいくつかの素数で割ってみることです。しかし、1931が数字の1つであると言われれば、 "6895601÷1931"を任意の電卓に入力することで答えを見つけることができます。この例は、頑丈なトラップドア機能ではありません。現代のコンピュータは、すべての可能な回答を1秒以内に推測することができますが、このサンプルの問題は、2つの大きな素数の積を使用することによって改善できます。
1970年代半ば、Diffie、Hellman、Merkleによる非対称(または公開鍵)暗号化技術の公開により、トラップドアの機能が暗号の目立つようになりました。確かに、Diffie&Hellman(1976)はこの言葉を作った。いくつかの機能クラスが提案されており、当初考えられていたよりもトラップドア機能が見つけにくいことがすぐ明らかになりました。例えば、初期の提案は、部分集合和問題に基づくスキームを使用することでした。これは不適切であることが判明しました。
2004年現在で最もよく知られているトラップドア機能(家族)の候補は、RSAとRabinファミリーの機能です。どちらも複合数を法とする累乗として書かれており、どちらも素因数分解の問題に関連しています。
効率的な計算を可能にするグループについて知られていない「トラップドア」情報がないので、離散対数問題(楕円曲線上で定義された、または素数を剰余として扱う)の硬度に関連する関数はトラップドア関数では知られていない離散対数の
暗号のトラップドアは、前述した非常に具体的な意味を持ち、バックドアと混同してはいけません(これらは頻繁に入れ替えて使用されますが、間違っています)。バックドアとは、例えば、1つまたは複数の権限のない当事者がセキュリティを迂回または破壊することを可能にする、暗号アルゴリズム(たとえば、鍵ペア生成アルゴリズム、デジタル署名アルゴリズムなど)またはオペレーティングシステムに追加される意図的なメカニズムです。いくつかの方法でシステム。