쓰다가 날아가서 의욕이 좀 없어져서 약간 대충 씀



0. 인트로덕션


앞선 고닉의 글에서 2^-128으로 일어나는 확률이 "거의" 일어나지 않고, 이걸 안전성의 척도로 잡는다는 말을 했다.

뭐 말은 된다. 지구 어쩌구저쩌구 우주 어쩌구저쩌구.. 근데, 좀 만족스럽지가 않다. 굉장히 작위적이고 인위적이잖아?

다른 우주에서는 이걸 다르게 정의해야하냐?


현실적인 관점에서는 그럴듯하긴 하고, 맞다. 불만족스럽지만, 실제로 그렇게 생각한다.

보통 안전성은 다음과 같이 생각함.


[우리가 잘 아는 제일 좋은 공격]이 T번의 bit operation을 통해 p의 확률로 암호시스템을 깨면 log (T/p) = λ의 안전성을 갖는다.


여기서 λ를 security parameter라고 안전성의 척도로 재고 λ-bit security를 갖는다고 간단하게 씀. 이런 관점을 concrete security라고 함.

고닉의 글에서는 λ=128, 256, 80등인 경우를 말했고 실제로 제일 많이 쓰는 파라미터들임.

(상황따라 p가 1정도일때 log T이나 그냥 log T/p^2을 λ로 잡을때가 있는데, 이건 암호시스템의 안전성의 정의에 의존함.)



근데 이 정의(?)가 만족스럽냐? 이딴 정의를 들고 대체 어떻게 암호가 안전하다고 말할수있냐/암호를 푸는게 [어려운 문제]라는걸 말할수 있을까?

공격이 조금씩 좋아질때마다 안전한 암호가 바뀐다고, 그냥 어려운 문제라는걸 사회적 합의로 하고 넘어가야할까?





당연히 아니지. 저런 관점은 현실적으로 다루는 방식을 잘 설명한거고, 이론적으로는 좀 더 잘 정의되어 있음.

이 글의 목표는 "어려운 문제"가 뭔지 약간 formal하게, 덜 인위적이게 정의하는거임. 혹은 CS사람들이 신봉하는 complexity theory와 비슷한 관점으로 정의하는것.



음.. 간단하게 한줄 요약하면, [어려운 문제]는 임의의 [현실적인 알고리즘]을 돌려도 올바른 답을 낼 확률이 [무시할만한] 문제를 말함.


말은 참 쉬운데, 수학하는 사람은 저 문장의 단어들의 의미를 잘 아는 경우가 별로 없더라. 그래서 그 단어들을 먼저 설명하고자 함.




1. "현실적인 알고리즘"의 정의


현실적인 알고리즘이 뭘까? 사실 CS계열에 관심있는사람은 언뜻 들어본적 있을텐데,

그 유명한 P vs NP의 P를 현실적인 시간에 돌릴수있는 알고리즘의 집합으로 자주 정의하곤 함.


근데 P가 뭐냐? 다들 [다항식시간에 풀 수 있는 문제]라고 하는건 한번씩 들어봤을텐데, 사실 거의 모든 단어가 모호하다.

문제는 뭐고, 푸는건 뭐고, 다항식시간은 뭐냐?


모든걸 다 정의하면 참 좋겠지만, 너무나 귀찮고 오래 걸린다. 문제와 푸는게 뭔지는 대충 상상이 되잖아?

엄밀하게 정의하려면 튜링머신과 랭귀지에 대해 말을 해야하는데, 슬쩍 넘어가자.


우리에게 필요한건 "문제를 푸는것"은 알고리즘을 말하는거고, 그 알고리즘의 실행시간은 알고리즘을 하는 과정에서 행하는 operation횟수라는 것임.

이게 다항식시간이길 요구하고 있는거고.





그럼 [다항식시간]이 뭘까?

교양 등에서 썰풀때는 다들 슬쩍 넘어가는데, 다항식을 말할때는 어떤 파라미터에 다항식인지가 굉장히 중요하다.

여기 들어갈 파라미터가 바로 위에서 얘기한 security parameter와 비슷한 역할을 함. (물론 아직 security는 고려하지 않지만..)


즉, 사실 우리가 알고리즘을 말할때는 사실 알고리즘(=튜링머신)들의 열 A={A(λ):λ는 자연수}을 말하는거고,

이 알고리즘이 P에 속한다는건 [어떤 고정된 다항식 q가 있어서 A(λ)를 실행하는데 q(λ)이하의 시간이 걸려야한다]는거다.

이런 알고리즘이 P에 속하는 "현실적인 알고리즘" 인거지.





2. "무시할만한것=negligible"의 정의


그럼 무시할만한것이 뭘까? 공부 안하고 구석에서 게임하다 이거 쓰고있는 나? 쉬불..

인트로에서는 2^-λ를 말했는데, 이건 너무 특정한 수다. 이거 대신 다음과 같은 함수를 생각한다.

(P에 속하는 알고리즘처럼 λ에 parametrized 되어야한다는걸 명심하자)


[정의1] 함수 f:N->R+가 negligible function이라고 하는 것은 임의의 양수 c에 대해 적당한 상수 Nc가 존재해서 λ>Nc이면 f(λ)λ^c를 만족하는것을 말한다.


Asymptotic하게 말하면, f가 커지는 속도가 임의의 다항식의 역수보다도 작다는거다.

여기서 concrete security에서 고려했던 2^-λ같은 수열은 negligible인 수열의 한 예시에 불과한거지. 뭐 아직은 괴상해보인다.

굳이 장점이라고 하면 negligible function들이 덧셈 등등에 닫혀있고, 아무 다항식을 곱해도 여전히 negligible인거지.





3. "어려운 문제"의 정의

그러면 이 괴상한 negligible의 정의가 어디에 도움이 될까? 바로 "어려운 문제"를 robust(?)하게 정의하는데 도움이 된다.

계속 모든것을 λ에 의존해서 정의하고 있으니, 문제도 문제들의 열 X={X(λ)}가 된다는걸 일러두겠음.


[정의2] 문제 X={X(λ)}가 "어려운 문제"라는 것은 임의의 P에 속하는 알고리즘 A={A(λ):λ는 자연수}에 대해

A(λ)가 X(λ)를 풀 확률 r(λ)로 정의되는 함수 r가 negligible function인 것을 말한다.


엥~ 아주 복잡하고 이해도 안된다. 왜 이따위로 정의할까? 조금만 더 의미를 살펴보자면, 음...

약간 뭉개서 말하면, 다항식 시간 알고리즘으로는 성공확률 1/다항식을 달성할수 없다는 거지.

이 정의가 뭐가 좋냐... 뭐 엄밀한게 하나의 장점이고 (여기서는 이것저것 다 생략했지만..),

알고리즘의 "조그만 진보"가 있어도 "어려움"에 변화가 없거든 (위에서 말한 robust).




다음과 같은 구체적인 예시를 통해 "소인수분해가 어렵다"는 말이 암호학적으로 무엇을 말하는지 생각해보고 넘어가자.


[문제3] Factoring(λ): a,b를 [2^(λ-1),2^λ)에서 뽑은 두 소수라고 하자. N=ab에서 a,b를 구하여라.


[가정4] Factoring(λ)는 어려운 문제이다. 즉, 임의의 λ-bit 두 소수를 뽑아서 곱한 수를 보고 (λ에 대한)다항식시간에 소수를 찾는 확률은 negligible이다.


이 가정은, 맨 처음 고려했던 작위적인 문제들은 없어짐.

지금까지의 모든 알고리즘에 대해 어려웠으면, 그것보다 100000000000배 빠른 알고리즘을 찾아도 여전히 어렵거든.




================Remark. 이건 넘어가도 됨==================

그리고 또다른 장점도 있는데, 슬쩍 뭉개고 넘어갔던 P부분을 조금 더 넓게 잡아야함. 보통은 결정론적인 알고리즘 P보다 확률적인 알고리즘을 고려하거든.

이 때 어떤 일이 벌어지냐면, 소인수분해는 한번 하고나면 성공했는지 확인은 쉽잖아? 그래서 다음과 같은 알고리즘의 반복을 통한 성공확률 증폭이 가능함.

우선 알고리즘 A가 실행시간 q(λ)이고, 성공확률이 r(λ)라고 하자.


[알고리즘 B] B(λ)는 A(λ)를 서로 다른 random에 대해 100/r(λ)번 반복해서 돌리고, 그 답들을 확인해서 맞는 답이 있으면 그걸 내뱉는 알고리즘임.


이런 알고리즘은 실행시간 q(λ)/r(λ)이고, 성공확률이 0.99보다 높음. 이런 B가 [가정4]를 조금 더 강한 가정으로 바꾸게도 해줌.


만약 [가정4]가 틀렸으면 그 다항식시간에 1/다항식으로 성공하는 A를 잡을수 있고, 또 그 A를 통해 B를 만들수 있잖아?

이 B는 다항식시간에 0.99 성공확률을 갖는애임. 따라서 [가정4]가 거짓이면 아래 훨씬 약한 가정인 [가정4']도 거짓임. (즉, 두 가정이 동치임!)


[가정4'] 임의의 λ-bit 두 소수를 뽑아서 곱한 수를 보고 (λ에 대한)다항식시간에 거의 무조건(99%확률로) 소인수를 찾는 알고리즘은 없다.


처음 가정은 소인수분해가 성공할확률이 거의 없을정도로 어려워야한다는 거고, 두번째 가정은 정말 가끔씩만 못찾아도 된다는거니까 꽤나 약한 가정이지.

이 논증은 concrete security를 T/p에 대해 정의하는것과 관련이 있기도 함.

====================================================




4. "어려운 문제"가 그래서 정말 어렵냐?


솔직히 이건 믿음이다. 여러가지 이유가 있는데, 내 느낌으로는 P가 NP가 아니라고 믿는 이유랑 비슷함.

여러가지 이유로 사람들이 "어려운 문제"를 풀려고 굉장히 노력했지만, 다항식시간에 1/다항식 확률로 성공하는 알고리즘을 못찾았거든.

우리는 보통 "어려움"을 증명하는것보다 알고리즘을 찾는걸 훨씬 잘하니까 (혹은 그렇다고 믿으니까), 그냥 믿어버리는거지.


그러면 어려운문제가 정말 어렵다고 증명할수 있을까? 사실상 못한다고 보면 됨.

왜냐면 웬만한 암호학적 가정이 참이면, P가 NP가 아님을 보일수 있음.


그러니까.. 암호가 정말 안전하다는것을 아무것도 없이 보이는건 불가능하고,

대부분의 경우 [암호시스템 X는 문제 Y가 어려우면 안전하다] 와 같은 류의 논증을 거치지.

여기서 문제 Y의 선택은....결국은 사회적 합의일수밖에 없긴 함.



0편이라고 쓰긴 했는데 1편이상이 나올지는 잘 모르겠다.