一方向性関数の存在
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/07/25 09:14 UTC 版)
「計算機科学の未解決問題」の記事における「一方向性関数の存在」の解説
一方向性関数とは順方向への計算は容易だが、逆方向への計算が困難な関数のこと。つまり「一方向性関数が存在するかどうか？」とは「暗号化は容易だが、復号は困難であるような暗号化方法は存在するのか？」という問題を一般化したもの。容易、困難という言葉の定義は数学的に厳密に与えられている。現在、一部の研究者達は離散対数とinverting RSA暗号の計算アルゴリズムは一方向性関数だろうと予測している。 もし一方向性関数が存在しない場合、公開鍵暗号は不可能である。逆に一方向性関数が存在するならば、その存在は多くの複雑性のクラスの問題がlearnableではないこと、またP≠NPであることを示す。現在、存在するだろうとは予想されているが、証明されていない。
※この「一方向性関数の存在」の解説は、「計算機科学の未解決問題」の解説の一部です。
「一方向性関数の存在」を含む「計算機科学の未解決問題」の記事については、「計算機科学の未解決問題」の概要を参照ください。
ウィキペディア小見出し辞書の「一方向性関数の存在」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 一方向性関数の存在のページへのリンク
