Quantum Stamp 

개발 과정 소개


Quantum Stamp(양자 우표)는 수학의 7대 난제 중의 하나인 P대NP문제를 증명하는 과정에서 나온 결과물이다.

P대NP 문제를 처음 들어본 사람이 P가 무엇이고 NP가 무엇인지를 정확히 이해하기는 어렵다.
그냥 1+2는 3이 맞아요? 틀려요? 라고 묻는 문제와 같이 YES또는 NO로 대답을 요구하는 컴퓨터를 이용해서 풀리는 문제들의 집합들인데 P는 일반컴퓨터로도 풀 수 있고 NP는 네트웍으로 연결된 수많은 컴퓨터 또는 병렬컴퓨터가 동시에 풀어야지만 풀리는 문제라고만 생각하자.
물론 이것은 명확한 표현이 아니고 사실상 맞는 표현도 아니다. 그러나 일반인이 어느정도 그 차이점을 이해할 수 있는 표현이라고 생각된다.
양자 우표에 대한 기술적인 내용을 서술할때 좀 더 명확하게 설명하겠다.
P대NP문제는 P와 NP가 같은지 다른지를 수학적으로 증명하라는 것이다.

나는 박사과정 중에 P대NP문제를 처음 접하고 P와 NP가 같을 것이라고 생각하고 그것을 증명할 방법을 찾았었다.
다행스럽게 단순히 수학에 관심을 가지는 것 이상으로 나에게는 평범한 사람보다는 훨씬 더 쉽게 내 생각을 실험적으로 증명할 수 있는 소프트웨어 코딩 능력을 가지고 있었다.
그래서 SAT solver라는 프로그램을 짜서 며칠동안 계속 돌리는데 오랜 시간동안 P=NP일 것이라는 예측을 뒷받침할 만한 결과들이 나왔다.
실험을 멈추고 한달 가까이 논문을 쓰고 탑저널 (흔히 사이언스와 네이처를 탑저널이라고 부른다) 에 클릭만 하면 투고하는 상황까지 만들었다. 
그런데 문득 그래도 탑저널인데 실험 기간이 너무 짧지 않은가? 라는 생각이 들어서 일주일만 더 돌려보자고 하고 다시 소프트웨어를 돌리다가 특정 현상을 발견하게 되었다.
그 현상으로 거꾸로 P와 NP가 같지 않다는 확신을 가지게 되었고 그 이후로 꾸준히 P와 NP가 같지않다(명확한 표현으로는 P는 NP의 진부분집합이다)는 것을 증명하기 위해서 노력해왔다.
4년 가까운 연구 끝에 P는 NP가 아니라는 완전한 증명은 아니지만 내가 발견한 특성들이 큰 가치가 있는 것이라고 판단하고 탑저널에 몇번 투고 했다가 모두 reject되고 아카이브에 올린 것이 아래의 논문이다. 
THE NUMBER SYSTEM HIDDEN...
첫번째는 scope가 다르고(수학저널에 냈어야 했는데 욕심을 부렸다) 두번째는 완전한 증명이 아니고  세번째는 영어 표현 능력이 낮아서 reject되었다고 판단하고 있지만 위의 논문은  틀린 논문이 아니다. 
10년 가까이 지난 현재까지도 나는 위의 논문에 쓰인 내용은 가치 있는 내용들이라고 생각하고 있다.
그러나 논문에서도 쓰여있는 것처럼 P가 NP가 아닐것이라는 확신을 서게 하는 단초를 제공하지만 그것만으로 P가 NP가 아니라는 것을 증명하지는 못했다.

계속적인 관심을 가지고 연구한 끝에 두번째 논문은 4년이 지난 2018년에 아카이브에 등록했다.
--
논문을 올리고 며칠 지나서 위의 논문에 중대한 결함이 있음을 발견했다.
그러나 위의 논문에서 소개하는 비구분성이항트리(indistinguishable binomial tree)의 개념이 발전해서 양자 우표의 핵심이 되는 원환형 이항트리(troidal binomial tree)가 탄생된다. 
양자우표는 원환형 이항트리와 modular random encapsulation이라는 새로운 두 개념에 의해서 만들어진다.

최근들어서 암호화폐가 뜨고 몇몇 사람들은 수조원을 쉽게 버는 세상이 되었다.
암호화폐의 근간을 이루는 비트코인이나 이더리움은 ECC알고리즘(타원곡선암호알고리즘:Elliptic Curve Cryptography)을 사용한다. 
ECC알고리즘이라는 것이 수학적으로는 이것보다 더 간단할 수 없다.
a,b값을 알려주고 a를 몇번 더하면 b가 되니?라도 묻는 것이다. 그 더한 횟수가 여러분 지갑의 패스워드인 비밀키가 된다.
그 횟수를 찾을 수 만 있다면 그당시에 몇천조가 되는 샤토시 계좌에 있는 돈을 내계좌로 옮길 수도 있다는 환상을 가지고  ECC 알고리즘의 취약성을 분석했다.
그러는 와중에 결국은 과거에 끝내지 못했던 P대NP 문제의 증명까지 오게 되고 완성한 논문이 이것이다.
SATbased ..

어떤면에서는 무지가 낳은 보석으로 볼 수 있다.
ECC알고리즘이 단순 덧셈으로 위에서 표현했으나 실수를 더할때와 복소수를 더할때 매트릭스를 더할때 덧셈의 개념이 다르듯이 ECC알고리즘에서의 덧셈의 개념이 다르다. 그뿐만아니라
우리는 보통 직선형 도메인을 사용하지만 즉 -무한대 에서 + 무한대인 수를 하나의 직선 위에 옮길수 있지만 대부분의 암호알고리즘에서는 환형 도메인인 갈루아필드를 사용한다.
더욱 더 패스워드를 찾기 어려운 이유는 공개키를 그대로 쓰지 않고 해시코드를 만들어서 사용하므로 공개키로부터 개인키를 구하는 과정이 수학적으로 하나의 function의 inverse를 구하는 과정으로 매핑될 수 없다는 것이다.
공개키를 만들때 해시를 써서 만든다는 것을 나중에 알게 되고 "적어도 양자컴퓨터 도움을 받기 전에는 불가능하네"라고 생각하게 되었을때 이미 발동이 걸려서 예전의 논문을 들여다 보고 있던 때라서 최종논문을 완성할 수 있는 기회를 가지게 되었다.

논문을 완성하고 그것을 구현하는 소프트웨어도 짜고 검증까지 마친 후에  몇달간 그냥 방치하자는 생각을 했다.
두번째 논문을 내고 조금 지나서 틀렸다는 사실을 알게된 선례가 있어서 혹시라도 시간이 지나면 생각하지 못했던 어떤 것이 나올 수 도 있지 않을까 하는 생각에서였다.

어떤 사람은 아주 중요한 데이터를 여러개 카피해서 따로 보관하기도 하지만 나는 정말로 중요하는 것은 카피본을 도난 당할 수도 있다는 생각에 한곳에만 보관하려 한다.
그래서 백업을 하지않고 노트북 하나에만 모든 소프트웨어와 논문 자료를 보관했다. (이것이 게으름에 대한 구차한 변명일 수도 있다)
그러는 가운데 어느날 랜섬웨어에 걸렸다.
하드디스크가 완전히 포맷된 것과 동일한 상황이 되었다.

그 어느것보다도 강력한 암호화 알고리즘을 완성했는데 암호학의 기초적인 알고리즘을 사용하는 랜섬웨어(대칭키 알고리즘을 사용하고 양자우표와 어떻게 다른지는 후에 설명한다)에 걸려서 모든 데이터가 날아갔다는 사실이 참으로 한심하면서도 
신께서 계획하신 아이러니가 아닌가 하는 생각이 들었다.
"내가 준 선물을 네가 열어서 다른 사람에게 보여주지 않는다면 나는 다시 빼앗을 수 도 다른 사람에게 줄 수 도 있다."라고 경고하시는 것 같아서 정신을 바짝 차리고 다시 소프트웨어를 짜고 논문을 다시 써서 지금의 상태에 이르렀다.
특허를 출원하기 위해서 변리사에게 준 자료가 다행히 남아 있어서 오랜 시간이 걸리지는 않았다. 또한 했던 것을 한번 더 하면서 알고리즘의 완결성을 다시 한번 확인하는 기회도 되었다.
 
내게는 하나의 생각에 집중하면 생각하고 먹고 자는 것 외에는 어떤 다른 것도 할 수 없는 고질 적인 병이 있다.
첫번째 논문을 완성하는 시점에 결혼까지도 생각하는 한 사람이 있었는데 논문을 쓰기 위해서 핸드폰을 꺼 놓고 3개월간 잠수를 탔다. 그래서 자의반 타의반으로 헤어지게 되었다. 계속 교편을 잡지 못한 이유이기도 하다. 
대학교 다닐때는 페르마의 정리 증명에 매달리고 있었는데 한가지 방법이 떠올라서 2달간 기숙사에서 안나오고 그 생각에만 몰두했다.
그결과 F학점을 받은 과목이 수두룩하고 다음 학기에 재수강하려고 무려 30학점을 신청한 예가 있다. (지금은 오프라인 수업에서 한학기에 30학점을 신청하는 것이 불가능할텐데 그 당시에 나의 모교에서는 토요일 오전에도 수업을 했다.)
두번째 논문을 쓰다가 이번에는 좋은 친구를 잃었다.
그 친구에게 소프트웨어를 개발하는 프로젝트를 받아서 끝내주기로 해놓고 2개월간 잠수를 탔다. 한마디로 돈만 받고 먹튀한 꼴이 됐다. 
그 이후로 마무리는 해 주었지만 2개월간 잠수를 탄 이유를 말해줄 기회가 없어서인지 아직까지도 서먹서먹한 상태다. 

내가 이러한 어쩌면 좀.. 꼰대들이 쓸법한 글을 쓰는 이유는 양자 우표(SAT기반의 양자내성 암호화 알고리즘)은 가벼운 생각들이 모아져서 얻어진 결과가 아니라 인생의 긴 시간동안 정상적인 삶을 포기하는 희생과 때론 눈물들이 모아져서 만들어 졌다는 것을 알리기 위함이다.
10살부터 30살까지는 페르마의 문제 증명에 매달려서 인생을 소비하고 40살부터 50살까지는 수학의 7대 난제인 P대NP 문제에 매달려서 인생을 소비하다가 최근들어서 화룡점정을 했다고 나는 생각한다.
물론  내인생의 지하실 안에는  평생을 거쳐서 조금씩 조금씩 완성해나가는그리다 만 수채화만 있는 것이 아니라 이제 막  화룡점정을 하려는 유화도 있긴 하다.
SAT기반의 양자내성 암호화 알고리즘의 근간을 이루는 원환형 이항트리는 어렸을때 페르마의 정리를 증명한다고 수만페이지를 손으로 써 왔던 이항 계수와도 관련이 있다. 이것까지 고려한다면 하나를 완성하기 위해서 정말로 인생의 긴 시간이 소비되었다.