일방향함수

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 엄밀한 정의
3. 이론적 함의
4. 일방향 함수의 후보
5. 일방향 함수의 존재성
6. 비균일 일방향 함수
참조

1. 개요

일방향 함수는 쉽게 계산할 수 있지만, 그 역함수를 계산하기는 어려운 함수를 의미한다. 강한 일방향 함수와 약한 일방향 함수로 구분되며, 약한 일방향 함수의 존재는 일방향 함수의 존재와 필요충분조건이다. 일방향 함수의 존재는 P≠NP를 함의하지만, P≠NP가 일방향 함수의 존재를 의미하지는 않는다. 일방향 함수가 존재한다면 의사난수발생기, 전자서명 등 다양한 암호학적 요소를 만들 수 있다. 소인수 분해, 이산 대수 문제, 암호화 해시 함수 등이 일방향 함수 후보로 거론되며, 비균일 일방향 함수는 다항 시간 내에 계산 가능하고 특정 회로족에 대해 역함수 계산이 어려운 함수이다. 일방향 함수의 존재 여부는 아직 증명되지 않았다.

더 읽어볼만한 페이지

컴퓨터 과학의 미해결 문제 - 인공지능
인공지능은 인간의 지능적 행동을 모방하는 컴퓨터 시스템으로, 인간 수준의 일반 지능을 가진 강인공지능과 특정 문제 해결에 특화된 약인공지능으로 나뉘며, 딥러닝 기술 발전으로 다양한 분야에서 성과를 거두고 있지만 윤리적, 사회적 문제에 대한 고려가 필요하다.
컴퓨터 과학의 미해결 문제 - 이산 로그
이산 로그는 유한군에서 이산 거듭제곱의 지수를 찾는 역함수로, 소수 p를 법으로 하는 정수 모듈러 곱셈 그룹에서 계산적으로 풀기 어려운 문제이며, 현대 암호 시스템의 안전성 기반이지만 양자 알고리즘으로 효율적 해결이 가능하여 양자 내성 암호 연구가 필요하다.
암호학 - 양자 컴퓨터
양자 컴퓨터는 양자역학적 현상을 이용하여 정보를 처리하는 컴퓨터로, 큐비트를 통해 0과 1을 동시에 표현하여 특정 연산에서 기존 컴퓨터보다 빠른 속도를 보이며 암호 해독, 신약 개발 등 다양한 분야에 혁신을 가져올 것으로 기대된다.
암호학 - 암호화
암호화는 정보를 보호하기 위해 사용되는 기술로서, 단순한 문자 치환 방식에서 시작하여 현대에는 강력한 암호화 표준과 다양한 종류로 발전했으며, IT 시스템 전반에 적용되지만, 사이버 공격과 양자 컴퓨팅의 발전에 대한 대응이 필요한 기술이다.

일방향함수
컴퓨터 과학
분야	암호학, 계산 복잡도 이론
속성	계산의 용이성 (순방향), 계산의 어려움 (역방향)
중요성	암호학적 프로토콜, 디지털 서명, 의사 난수 생성기
관련 개념	단방향 치환, 트랩도어 함수, 해시 함수, 계산 복잡도 종류

2. 엄밀한 정의

일방향 함수는 강한 일방향 함수와 약한 일방향 함수 두 가지로 나뉜다.^[3]

함수 $f : \Sigma^* \to \Sigma^*$ 가 다음 조건을 만족할 때, 함수 $f$ 는 '''일방향 함수'''라고 한다.

1. $f$ 는 다항 시간에 계산 가능하다. 즉, 어떤 다항 시간 알고리즘 ''C''가 존재하여 ''C''(''x'') = ''f''(''x'')이다.

2. 임의의 다항 시간 알고리즘 ''A''에 대해, 어떤 무시 가능한 함수 $\nu$ 와 어떤 $k_0 \in {\mathbb N}$ 이 존재하여, 모든 ''k'' > ''k''_''0''에 대해,

: $Pr\left[x \gets_R \Sigma^k, y \gets f\left(x\right),x' \gets A\left(1^k, y\right) : y=f\left(x'\right)\right] \le \nu\left(l\right) .$

여기서,

${\mathbb N}$ 은 자연수의 집합을 나타낸다.
Σ = {0, 1}이고, $\Sigma^* = \cup_{k\in{\mathbb N}}\Sigma^k$ 이다.

일방향 함수가 존재한다는 것은 일방향 함수족이 존재한다는 것과 필요충분조건이다.

2. 1. 강한 일방향 함수

함수

f : \{0,1\}^* \rightarrow \{0,1\}^*

가 다음 두 가지 조건을 만족할 때 '''(강한) 일방향함수'''라고 정의한다.

1. 순방향은 쉽다: 입력

x

에 대해 출력

f(x)

를 구할 수 있는 (결정론적) 다항시간 알고리즘

A

가 존재한다. (즉,

A(x)=f(x)

이다.)

2. 역방향은 어렵다: 모든 확률적 다항시간 알고리즘

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''도 역방향 알고리즘에 입력으로 제공해야 한다. 이렇게 쓰는 이유는 입력의 길이를 급격히 줄이기 때문에 역을 구하는데 다항식 시간으로 부족한 경우를 제외하기 위해서이다.^[3]

2. 2. 약한 일방향 함수

함수

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)}

다르게 정의하면 함수

f

: Σ^* → Σ^* 가 다음을 만족할 때, 함수

f

는 '''약한 일방향 함수'''라고 한다.

#

f

는 다항 시간에 계산 가능하다.

# 어떤 다항식

P

가 존재하여, 임의의 다항 시간 알고리즘

A

에 대해, 어떤

k

₀ 가 존재하고, 모든

k

>

k

₀ 에 대해, Pr[

z

≠

f

(

x

) |

x

←_''R'' Σ^''k'',

y

←

f

(

x

),

z

←

A

(1^''k'',

y

)] > 1/

P

(

k

)

'''정리:''' 일방향 함수가 존재할 필요충분 조건은 약한 일방향 함수가 존재하는 것이다.

'''증명 개요:'''

(→) 자명하다.
(←) $f$ 를 약한 일방향 함수로 한다. $g$ 를 $g$ ( $x$ ₁ || … || $x$ _''N'') = $f$ ( $x$ ₁) || … || $f$ ( $x$ _''N'') 로 정의한다. 단 여기서 "||"는 비트 열의 연결, $N$ = 2 $kP$ ( $k$ ) ( $P$ 는 약한 일방향 함수의 정의 조건 2에 있는 것).

이 때

g

^-1 를 구하려면,

f

^-1 를

N

번 계산해야 한다.

어떤 알고리즘을 사용해도

f

^-1 를 계산하는 데 1/

P

(

k

) 단계가 걸리므로,

f

^-1 를

N

번 계산하는 것은 다항 시간 내에 할 수 없다.

2. 3. 관련 개념

'''일방향 순열'''은 일방향 함수이면서 전단사 함수인 경우를 말한다. 전사 함수인 일방향 함수라고도 한다. 일방향 순열은 중요한 암호화 기본 요소이며, 일방향 함수의 존재가 일방향 순열의 존재를 함축하는지는 알려져 있지 않다.

'''트랩도어 일방향 함수'''는 특수한 종류의 일방향 함수이다. '트랩도어'라고 하는 비밀 정보를 알아야만 역함수를 쉽게 구할 수 있다.

'''충돌 회피 해시 함수''' ''f''는 일방향 함수이면서 '충돌 저항성'을 갖는 함수를 말한다. 즉, 확률적 다항 시간 알고리즘으로 ''f''(''x'') = ''f''(''y'')를 만족하는 서로 다른 값 ''x'', ''y''( 해시 충돌)을 찾기 어렵다.^[4]

3. 이론적 함의

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

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

만약 ''f''가 일방향 함수라면, ''f''의 역함수는 출력을 계산하기는 어렵지만, ''f''를 계산함으로써 확인하기는 쉬운 문제가 된다. 따라서 일방향 함수의 존재는 FP ≠ FNP를 함의하며, 이는 다시 P ≠ NP를 함의한다. 그러나 P ≠ NP는 일방향 함수의 존재를 함의하지 않는다.

일방향 함수의 존재는 다음과 같은 개념들의 존재를 함의한다.

의사 난수 생성기
의사 난수 함수 패밀리
비트 약속
적응적 선택 암호문 공격에 안전한 비밀 키 암호화 방식
메시지 인증 코드
디지털 서명 방식(적응적 선택 메시지 공격에 안전)

현재까지 일방향 함수의 존재는 증명되지 않았지만, 암호 이론에서는 일방향 함수의 존재를 가정하고 논의를 진행한다. 다음은 모두 동치이다.

# 일방향 함수가 존재한다.

# 약한 일방향 함수가 존재한다.

# 일방향 함수족이 존재한다.

# 암호론적 의사 난수 생성기가 존재한다.

# 의사 랜덤 함수족이 존재한다.

# 전자 서명 방식이 존재한다.

4. 일방향 함수의 후보

현재까지 일방향 함수의 존재는 증명되지 않았지만, 다음은 일방향 함수일 것으로 추정되는 후보들이다.^[1]

곱셈과 인수분해: 두 소수 ''p''와 ''q''를 곱하는 것은 쉽지만, 곱해진 결과 ''N'' (= ''pq'')을 다시 소인수분해하는 것은 어렵다.
'''래빈 함수'''^[1]: 주어진 수 ''N''에 대해 제곱을 한 후 ''N''으로 나눈 나머지를 구하는 함수이다. 이 함수는 ''N''을 소인수분해하는 것만큼 어렵다고 알려져 있다. 래빈 암호 시스템은 이 함수가 일방향이라는 가정에 기반한다.
'''모듈러 지수와 이산 로그''': 모듈러 지수는 다항 시간 내에 계산 가능하지만, 역함수인 이산 로그를 다항 시간 내에 계산하는 알고리즘은 아직 발견되지 않았다. 엘가말 암호화, 디피-헬만 키 교환, 디지털 서명 알고리즘 등이 이산 로그 문제의 어려움에 기반한다.
'''타원 곡선 연산''': 타원 곡선 위의 점 덧셈 연산은 빠르지만, 역연산은 어렵다고 알려져 있다. 타원 곡선 암호화는 이 성질을 이용한다.
'''암호화 해시 함수''': SHA-256과 같이 널리 사용되는 암호화 해시 함수들은 일방향성을 가질 것으로 추정된다.
'''기타''': 무작위 선형 부호의 해독, 특정 격자 문제, 부분 집합 합 문제 (나카시-스턴 냅색 암호 시스템) 등도 일방향 함수의 후보로 거론된다.

5. 일방향 함수의 존재성

일방향 함수의 존재 여부는 아직 증명되지 않았다.^[5] 만약 일방향 함수가 존재한다면 P≠NP가 증명되는 것이며, 이는 컴퓨터 과학의 최대 이론적 문제를 해결하는 셈이 된다.^[5] 그러나 P≠NP라고 해서 일방향 함수가 반드시 존재하는 것은 아니다.

약한 일방향 함수의 존재와 강한 일방향 함수의 존재는 서로 필요충분조건임이 증명되었다.^[5] 따라서 일방향 함수가 존재한다면 약한 일방향 함수나 강한 일방향 함수 모두 존재한다.

일방향 함수족의 존재는 일방향 함수의 존재와 동치이다.
보편 일방향 함수(Universal one-way function): 일방향 함수가 존재할 때만 명시적인 함수 ''f''가 일방향 함수임이 증명된 함수이다.^[5] 어떤 함수라도 일방향 함수라면 ''f''도 일방향 함수이다. 이 함수는 최초로 증명된 조합론적 완전 일방향 함수이므로 "보편 일방향 함수"로 알려져 있다.^[5]

다항 시간으로 제한된 콜모고로프 복잡성이 평균적으로 다소 어려운 경우 일방향 함수가 되는 함수가 존재한다. 일방향 함수의 존재는 다항 시간으로 제한된 콜모고로프 복잡성이 평균적으로 다소 어렵다는 것을 의미하므로, 이 함수는 보편 일방향 함수이다.^[6]

다음은 모두 동치이다.

일방향 함수가 존재한다.
약한 일방향 함수가 존재한다.
일방향 함수족이 존재한다.
암호론적 의사 난수 생성기가 존재한다.
의사 랜덤 함수족이 존재한다.
전자 서명 방식이 존재한다.

6. 비균일 일방향 함수

함수 ''f'': Σ^* → Σ^*가 다음 조건을 만족할 때, ''f''는 '''비균일 일방향 함수'''라고 한다.

# ''f''는 다항 시간 내에 계산 가능하다.

# 임의의 다항 시간 크기의 회로족 ''A'' = {''A''_''k''}에 대해, 어떤 무시 가능한 함수 ν가 존재하여 Pr[''x'' ← ''A''_''k''(''y'') | ''x'' ←_''R'' Σ^''k'', ''y'' ← ''f''(''x'')] < ν(''l'')가 성립한다.

다항 시간 알고리즘은 다항 시간 크기의 회로족으로 나타낼 수 있으므로, 비균일 일방향 함수는 반드시 일방향 함수이다. 하지만 역은 아직 잘 알려져 있지 않다.

참조

_[1] 서적 Foundations of Cryptography: Volume 1, Basic Tools http://www.wisdom.we[...] Cambridge University Press 2001
_[2] 간행물 Lecture Notes on Cryptography http://cseweb.ucsd.e[...] MIT 1996-2001
_[3] 문서 Goldreich's Foundations of Cryptography, vol. 1, ch. 2.1–2.3
_[4] 논문 Necessary and Sufficient Conditions for Collision-Free Hashing 1995
_[5] 논문 The Tale of One-Way Functions 2003-01
_[6] arXiv On One-way Functions and Kolmogorov Complexity 2020-09-24

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com