トラップドア機能

理論計算機科学と暗号学において、トラップドア関数とは、一方向の計算は容易であるが、特別な情報（「トラップドア」と呼ばれる）がなければ逆方向の計算（逆関数の探索）は困難な関数である。トラップドア関数は一方向関数の特殊なケースであり、公開鍵暗号で広く使用されている。^[2]

数学的に言えば、f がトラップドア関数である場合、何らかの秘密情報t が存在し、 f ( x ) とtが与えられればx を簡単に計算できます。南京錠とその鍵を考えてみましょう。鍵を使わずに、シャックルをロック機構に押し込むことで、南京錠を開いた状態から閉じた状態にするのは簡単です。しかし、南京錠を簡単に開けるには、鍵を使用する必要があります。ここで、鍵tはトラップドアであり、南京錠はトラップドア関数です。

単純な数学的な落とし穴の例は、「6895601 は 2 つの素数の積です。その数はいくつですか?」です。典型的な「総当たり」の解決法は、答えが見つかるまで 6895601 を多数の素数で割ることです。しかし、1931 が数の 1 つであると伝えられた場合、どの計算機にも「6895601 ÷ 1931」と入力することで答えを見つけることができます。この例は堅牢な落とし穴関数ではありません (現代のコンピューターは 1 秒以内にすべての可能な答えを推測できます) が、このサンプル問題は2 つのはるかに大きな素数の積を使用することで改善できます。

トラップドア関数は、1970 年代半ばにDiffie、Hellman、Merkleによる非対称 (または公開鍵) 暗号化技術の発表とともに、暗号学で注目されるようになりました。実際、この用語は Diffie & Hellman (1976) によって造られました。いくつかの関数クラスが提案されていましたが、トラップドア関数は当初考えられていたよりも見つけにくいことがすぐに明らかになりました。たとえば、初期の提案は、部分集合和問題に基づくスキームを使用するというものでした。これはすぐに不適切であることが判明しました。

2004 年現在^{[アップデート]}、最もよく知られているトラップドア関数 (ファミリー) の候補は、RSA関数ファミリーとRabin関数ファミリーです。どちらも合成数を法とする累乗として記述され、どちらも素因数分解の問題に関連しています。

離散対数問題の困難性に関連する関数（素数を法とするか、楕円曲線上で定義された群内のいずれか）は、離散対数の効率的な計算を可能にする群に関する「落とし戸」情報が知られていないため、落とし戸関数であるとは知られていない 。

暗号化におけるトラップドアは、前述のように非常に具体的な意味を持ち、バックドアと混同しないでください(これらは頻繁に同じ意味で使用されますが、これは誤りです)。バックドアは、暗号化アルゴリズム (キー ペア生成アルゴリズム、デジタル署名アルゴリズムなど) またはオペレーティング システムに追加される意図的なメカニズムであり、これにより、1 人以上の権限のない当事者が何らかの方法でシステムのセキュリティを回避または破壊できるようになります。

トラップドア関数は、一方向関数{ f _k  : D _k → R _k } ( k ∈ K )の集合であり、 K、D _k、R _kはすべてバイナリ文字列 {0, 1} ^*のサブセットであり、次の条件を満たします。

• 確率的多項式時間 (PPT)サンプリングアルゴリズム Gen st Gen(1 ⁿ ) = ( k , t _k )が存在します。ここで、 k ∈ K ∩ {0, 1} ⁿかつt _k ∈ {0, 1} ^*は| t _k | < p ( n ) を満たします (ここでp は何らかの多項式です)。各t _kはkに対応するトラップドアと呼ばれます。各トラップドアは効率的にサンプリングできます。
• 入力kが与えられると、 x ∈ D _{k を}出力する PPT アルゴリズムも存在します。つまり、各D _{k を}効率的にサンプリングできます。
• 任意のk ∈ Kに対して、 f _{k を}正しく計算する PPT アルゴリズムが存在します。
• 任意のk ∈ Kに対して、任意のx ∈ D _kに対してPPT アルゴリズムA st が存在し、y = A ( k , f _k ( x ), t _k ) とすると、f _k ( y ) = f _k ( x ) が成り立ちます。つまり、トラップドアが与えられれば、簡単に反転できます。
• 任意のk ∈ Kに対して、トラップドアt _kがない場合、任意の PPT アルゴリズムでf _{k を}正しく反転する確率（つまり、f _k ( x ) が与えられたときに、 f _k ( x' ) = f _k ( x )となるような原像x'を見つける確率）は無視できるほど小さい。^{[3] [4] [5]}

上記の集合内の各関数が一方向の順列である場合、その集合はトラップドア順列とも呼ばれます。^[6]

次の 2 つの例では、常に大きな合成数を因数分解することは困難であると想定しています ( 「整数因数分解」を参照)。

この例では、を法とするの逆関数(のオイラーのトーティエント関数) がトラップドアです。 ${\displaystyle d}$${\displaystyle e}$${\displaystyle \phi (n)}$${\displaystyle n}$

${\displaystyle f(x)=x^{e}\mod n.}$

の因数分解が分かっている場合、を計算できます。これによりの逆数を計算でき、 が与えられればを見つけることができます。その困難性は RSA 仮定から導かれます。^[7]${\displaystyle n=pq}$${\displaystyle \phi (n)=(p-1)(q-1)}$${\displaystyle d}$${\displaystyle e}$${\displaystyle d=e^{-1}\mod {\phi (n)}}$${\displaystyle y=f(x)}$${\displaystyle x=y^{d}\mod n=x^{ed}\mod n=x\mod n}$

を となる大きな合成数とします。ここで、と はとなる大きな素数であり、敵対者に秘密にしておきます。問題は、となるようにを計算することです。トラップドアは の因数分解です。トラップドアを使用すると、zの解は（ただし ）として与えられます。詳細については、中国剰余定理を参照してください。素数と が与えられると、と を見つけることができることに注意してください。ここで、条件と は、解とが適切に定義できることを保証します。^[8]${\displaystyle n}$${\displaystyle n=pq}$${\displaystyle p}$${\displaystyle q}$${\displaystyle p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}}$${\displaystyle z}$${\displaystyle a}$${\displaystyle a\equiv z^{2}{\pmod {n}}}$${\displaystyle n}$${\displaystyle cx+dy,cx-dy,-cx+dy,-cx-dy}$${\displaystyle a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}}$${\displaystyle p}$${\displaystyle q}$${\displaystyle x\equiv a^{\frac {p+1}{4}}{\pmod {p}}}$${\displaystyle y\equiv a^{\frac {q+1}{4}}{\pmod {q}}}$${\displaystyle p\equiv 3{\pmod {4}}}$${\displaystyle q\equiv 3{\pmod {4}}}$${\displaystyle x}$${\displaystyle y}$

• 一方向関数

• Diffie, W. ; Hellman, M. (1976)、「暗号化の新しい方向性」(PDF)、IEEE Transactions on Information Theory、22 (6): 644–654、CiteSeerX  10.1.1.37.9720、doi :10.1109/TIT.1976.1055638
• パス、ラファエル、暗号化講座(PDF) 、 2015 年11 月 27 日取得
• Goldwasser, Shafi、「暗号に関する講義ノート」(PDF) 、 2015 年11 月 25 日取得
• オストロフスキー、ラファイル、暗号の基礎(PDF) 、2015 年11 月 27 日閲覧
• Dodis, Yevgeniy、「暗号入門講義ノート (2008 年秋)」 、 2015 年12 月 17 日閲覧
• リンデル、イェフダ、暗号の基礎(PDF) 、2015 年12 月 17 日閲覧