[암호학] 18. NP-Complete

지난시간에 의하면 $P = NP$인지 모르기 때문에 암호가 불완전할 수 있다고 했다.

그래서 차라리 $NP$문제를 선택하고 Bob에게 힌트를 줘서 $P$로 만드는게 나을 수 있다.

그렇다면 $NP$문제중에 어려운걸 선택하면 될 것이다.

그런 문제셋을 $NP$-Complete라고 소개를 했었다.

 

$NP$-Complete

Class를 시간제한으로 봤을 때 위와 같이 나온다. ($D$, $E$와 유사하다. co-$NP$는 생각하지 말자)

$NP$-Complete의 예시로 SAT가 있는데 이 문제가 핵심 역할을 할 것이다.

 

Reduction

Problem $A$의 입력 $a$를 $b$로 변환할 수 있다면 Problem $B$로 reduce할 수 있다.

우리가 알고리즘이나 수학문제를 풀 때 해당 문제를 변형해서 풀면 더 쉽게 풀리는 경우가 많은 것과 유사하다.

다만 transform 하는 시간이 직접 문제를 해결하는 시간보다 오래걸리면 의미가 사라질 것이다.

이 내용의 핵심은 문제를 다른 문제로 변환할 수 있다는 것이다!

 

SAT

SAT(Satisfiability)은 $n$개의 bool 변수가 참일 조합이 있는지 찾는 문제이다.

예를들어 $p_1 \land (p_2 \lor \lnot p_3)$라고 하면 $p_1 = T, p_2 = T, p_3 = F$가 정답중 하나가 될 것이다.

직관적으로 모든 경우를 확인하는 $O(2^n)$ 알고리즘이 있기 때문에 $EXP$에는 포함된다는 것을 알 수 있다.

https://www.acmicpc.net/problem/11281

특히 2-SAT이면 SCC로 풀 수 있지만 3-SAT만 하더라도 휴리스틱이 필요한 굉장히 어려운 문제이다.

 

SAT의 특징

1. SAT은 $NP$에 있다.
2. SAT은 $NP$-Complete임이 최초로 증명된 문제이다.
3. $NP$에 있는 모든 Problem은 SAT으로 reduce할 수 있다.

핵심은 3번이다.

$NP$에 있는 모든 문제는 $NP$-Complete인 SAT으로 바뀔 수 있다는 것이다.

정말 신기한 증명이 있지만 지금은 다루지 않는다.

SAT이 $P$에 존재함을 증명한다면 이는 곧 $P = NP$임을 증명하는 것과 같아진다

SAT의 특징에 의해 $P \neq NP$라면 모든 $NP$-Complete 문제로 암호를 만들 수 있다.

---

요즘 암호는 그림의 위치에 있는 Problem을 사용한다. (RSA가 소인수분해를 사용한다.)

소수판정은 $P$일 수도 있다고 하는데 만약 $P$에 들어간다면 $P$-Complete가 된다고 한다.

이는 $P \neq NP$라는 것을 가정했기 때문에 아직은 믿고 사용할 수 있다.

 

앞으로 RSA같은 구체적인 암호화 기법을 알아볼 것이다.