일방향 함수

x 에서 f(x) 를 구하기는 다항 시간에 되지만, 무작위로 고른 x 의 f(x) 를 받아 그 값이 나오는 입력을 찾는 일은 어떤 효율적 알고리즘으로도 거의 언제나 실패하는 함수다. 큰 소수 두 개를 곱하는 함수가 후보다. 일방향 함수가 존재하는지는 증명되지 않았다. 존재한다면 P ≠ NP 이지만, P ≠ NP 라고 해서 일방향 함수가 존재한다는 보장은 없다. 최악의 경우가 아니라 평균적인 어려움이 필요하기 때문이다. 현대 암호의 거의 전부가 일방향 함수의 존재를 최소한의 가정으로 삼는다.