일방향함수

Template:미해결 일방향함수(一方向函數, one-way function)는 계산하기는 쉽지만 역을 구하는 것은 어려운 함수이다. 다시 말해서, 결과값이 주어졌을 때 입력값을 구하는 것이 어려운 함수이다. 물론 '쉽다', '어렵다'는 의미도 수학적으로 엄밀히 정의해야 한다. 공개 키 암호 방식은 극히 일부의 예외를 제외하면 모두 일방향함수가 존재한다는 가정 위에 연구되어 왔다.

엄밀한 정의

엄밀하게 정의하자면, 일방향함수에는 두 가지 종류가 있는데 각각 강한 일방향함수(strong one-way function)와 약한 일방향함수(weak one-way function)이다.

강한 일방향함수

함수 <math>f : \{0,1\}^* \rightarrow \{0,1\}^*</math>가 다음 두 가지 조건을 만족할 때 (강한) 일방향함수라고 정의한다.

순방향은 쉽다: 입력 <math>x</math>에 대해 출력 <math>f(x)</math>를 구할 수 있는 (결정론적) 다항시간 알고리즘 <math>A</math>가 존재한다. (즉, <math>A(x)=f(x)</math>이다.)
역방향은 어렵다: 모든 확률적 다항시간 알고리즘 <math>A^'</math>과 모든 다항식 <math>p(\cdot)</math>, 충분히 큰 모든 <math>n</math>에 대하여 다음 식이 성립한다.

<math>U_n</math>은 <math>\{0,1\}^n</math>에 균등하게 분포한 확률변수이다. 그러므로 두 번째 조건에서는 <math>U_n</math>에 할당된 모든 값과 <math>A^'</math>가 실행되면서 진행되는 모든 상태에 대해서 확률을 계산해야 한다. 또한 함수 <math>f</math>의 치역 이외에도 원하는 출력의 길이를 unary notation으로 나타낸 1^n도 역방향 알고리즘에 입력으로 제공해야 한다. 이렇게 쓰는 이유는 입력의 길이를 급격히 줄이기 때문에 역을 구하는데 다항식 시간으로 부족한 경우를 제외하기 위해서이다.

약한 일방향함수

위에서 정의한 일방향함수의 조건은 '모든 효율적인 역방향 알고리즘은 역을 구하는데 있어서 무시할 수 있는 확률로만 성공한다'는 것이다. 이 조건을 '모든 효율적인 역방향 알고리즘은 역을 구하는데 있어서 무시할 수 없는 확률로 실패한다'라고 완화한 것이 아래에서 정의할 약한 일방향함수의 핵심이다.

함수 <math>f : \{0,1\}^* \rightarrow \{0,1\}^*</math>가 다음 두 가지 조건을 만족할 때 약한 일방향함수라고 한다.

순방향은 쉽다: 강한 일방향함수와 동일함
역방향은 약간 어렵다: 모든 다항시간 확률적 알고리즘 <math>A^'</math>와 충분히 큰 <math>n</math>에 대하여 다음 조건을 만족하는 다항식 <math>p(\cdot)</math>가 존재한다.