一方向性関数は存在するか？

多項式時間で計算できるが、どの多項式時間アルゴリズムも無視できない確率では逆算できない関数が存在するかを決定せよ。

Decide whether there is a polynomial-time computable function that no polynomial-time algorithm can invert with non-negligible probability on random inputs.

The existence of one-way functions is equivalent to the existence of most of modern cryptography (pseudorandom generators, symmetric encryption, digital signatures). Liu and Pass showed it is also equivalent to mild average-case hardness of time-bounded Kolmogorov complexity, turning an assumption into a question about a concrete problem.

解決したかどうかは、問いではなくアプローチごとに決まります。Atlas は判定しません。外部の判定者が何をしたかを記録します。

• Construction from a concrete hard problem

  査読付きの証明

  到達状況

  進行中

  判定者

  the cryptography community, through journal peer review · 査読

  定式化

  Exhibit an explicit candidate and prove it one-way, or prove one-wayness follows from average-case hardness of a natural problem such as time-bounded Kolmogorov complexity.問いと同値

  保たれているもの

  • A proof either way settles the question

  加えられた仮定・条件

  • All candidates in use today are assumptions, not theorems

  閉じた道

  • One-way functions cannot exist if P = NP, so any proof that they exist also separates P from NP and inherits every barrier attached to that question.無条件
    • standardhttps://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdfS. Cook, The P versus NP problem, Clay Mathematics Institute official problem description

  証拠

  • preprintarXiv:2009.11514Y. Liu, R. Pass, On one-way functions and Kolmogorov complexity (2020): one-way functions exist iff time-bounded Kolmogorov complexity is mildly hard on average

• Black-box reductions

  閉じた道（障壁）

  到達状況

  この道では到達できないと証明済み

  判定者

  none: the obstruction is a published theorem · 引用

  差分（このアプローチが問いの何を保ち、何を弱めるか）はまだ書かれていません。人類審査で書きます。

  閉じた道

  • Impagliazzo and Rudich show no relativizing construction can build key agreement from one-way functions, which rules out the black-box style of argument for a large part of the surrounding theory.無条件
    • paperdoi:10.1145/73007.73012R. Impagliazzo, S. Rudich, Limits on the provable consequences of one-way functions, STOC 1989, 44-61: no relativizing construction of key agreement from one-way functions

• paperdoi:10.1145/73007.73012R. Impagliazzo, S. Rudich, Limits on the provable consequences of one-way functions, STOC 1989, 44-61: no relativizing construction of key agreement from one-way functions
• preprintarXiv:2009.11514Y. Liu, R. Pass, On one-way functions and Kolmogorov complexity (2020): one-way functions exist iff time-bounded Kolmogorov complexity is mildly hard on average

URI

https://atlasalt.com/q/a6fd02bb-ae01-4f35-bd14-ada6e9c1780d

登録

2026-09-17

最終レビュー

2026-09-19

次回レビュー期限

2026-12-18

版

a030299f439f

ライセンス

CC-BY-4.0

立場

record_only（Atlas は判定しない）