一方向性関数 【OWF】 One-Way Function / トラップドア関数 / trapdoor function / 落とし戸関数

概要

一方向性関数（OWF）とは、値の算出は簡単にできるが、逆関数の計算は極めて困難であるような関数。公開鍵暗号などに応用されている。

ある値xについて何らかの計算を行う関数 y=f（x） があるとき、yの値から逆方向の計算を行いxを求める x=g（y） という関数を逆関数という。例えば、一次関数 y=2x+4 の逆関数は x=0.5y-2 となり、関数の計算も逆関数の計算も同じように容易に行うことができる。

一方向性関数は関数値の算出は簡単にできる（多項式時間で計算できる）が、逆関数の計算は非常に困難で極めて時間がかかるような関数を指す。「簡単に計算できる逆関数が存在しない」ことの証明は非常に困難であるため、数学的には一方向性関数の存在は未だ証明されていない。

とは言え、現在知られている計算法の中には効率的な算出手順が知られていない関数はいくつかあるため、これを一方向性関数とみなして暗号の算出手順の一部に組み込むことがある。例えば、同じ桁数の巨大な素数pとqを掛け合わせて巨大な整数pqを算出するのは容易だが、与えられた巨大な整数pqからpとqを特定する効率的な方法は知られていない。この原理を応用した公開鍵暗号方式を「RSA暗号」という。

(2024.5.9更新)

他の辞典による解説 （外部サイト）

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。
ホーム画面への追加方法
1.ブラウザの 共有ボタンのアイコン 共有ボタンをタップ
2.メニューの「ホーム画面に追加」をタップ
閉じる