일방향함수

컴퓨터 과학의 미해결 문제

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

엄밀한 정의

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

강한 일방향함수

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

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

\Pr[A^{'}(f(U_{n}),1^{n})\in f^{-1}f(U_{n})]<{1 \over p(n)}

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

약한 일방향함수

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

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

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

\Pr[A^{'}(f(U_{n}),1^{n})\not \in f^{-1}f(U_{n})]>{1 \over p(n)}

일방향함수의 존재

일방향함수가 존재하는지 여부는 아직도 증명하지 못했다. 사실, 일방향함수가 존재한다는 것이 증명된다면 P≠NP임을 증명하는 셈이며 이것으로 컴퓨터 과학 최대의 이론적 문제를 해결할 수 있다. 그러나, P≠NP라고 일방향함수가 반드시 존재하는 것은 아니다. 약한 일방향함수의 존재와 강한 일방향함수의 존재는 서로 필요충분관계라는 것이 증명되어 있으므로, 일방향함수가 존재한다는 것을 증명한다면 약한 일방향함수나 강한 일방향함수 모두 존재한다.

일방향함수가 존재한다면 여러 가지 유용한 암호요소 만들 수 있다. 예를 들어 일방향함수를 이용하여 의사난수발생기, 의사난수함수, (선택평문공격에 대해 안전한) 전자서명 등을 포함한 많은 암호요소를 만들 수 있다.

일방향함수라고 생각하는 함수에는 몇 가지가 있다.

소인수 분해의 어려움에 기반하여 두 개의 큰 소수를 곱하는 함수.
이산 대수의 어려움에 기반하여 특수한 군에서 정의된 거듭제곱 함수.
두개의 소수를 곱한 값 n을 이용한 모듈로 n 제곱함수.

같이 보기

트랩도어 일방향함수 혹은 트랩도어 치환(- 置換, trapdoor permutation)은 특수한 종류의 일방향함수이다. 일방향함수처럼 일반적으로 역을 구하는 것은 어렵지만, 트랩도어(trapdoor)라고 하는 비밀정보를 얻으면 역을 쉽게 구할 수 있다. 대표적인 예로 RSA가 있다.
비슷한 주제로 암호학적 해쉬 함수가 있다.

참고 문헌

Goldreich, Oded (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press. ISBN 0-521-79172-3. Fragments available at the author's web site.
Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 10.6.3: One-way functions, pp.374–376.
Christos Papadimitriou (1993) Computational Complexity. Addison Wesley (1st edition) ISBN 0-201-53082-1. Section 12.1: One-way functions, pp.279–298.