The quest for quantum-proof encryption just made a leap forward

양자 컴퓨팅이 뚫지 못 하는 암호를 만들라

양자 컴퓨터의 발전은 암호화 기술을 무용지물로 만들 수 있다. 양자 컴퓨팅으로부터 당신의 데이터를 보호할 수 있다고 주장하는 15개 팀이 경쟁하고 있다.

당신이 온라인에서 하는 활동은 다른 사람이 엿볼 수 없도록 암호화된다. 정부 기밀이 암호화되듯, 온라인 뱅킹이나 메시지 송수신도 암호화되어 처리된다. 그런데 이 같은 보호 장치가 양자 컴퓨터의 발전으로 무용지물이 될 위기에 처했다.

양자 컴퓨터는 현재 우리가 사용하는 고전적 컴퓨터와 작동 방식이 근본적으로 다르다. 전통적 컴퓨터는 정보 처리에 0과 1의 이진법을 사용하지만, 양자 컴퓨터는 큐비트(qubit) 즉, 양자비트(quantum bit)를 사용한다. 큐비트가 가진 특이한 성질 덕분에 양자 컴퓨터는 현대 암호화 기술의 토대가 된 수학적 난제를 비롯하여 몇 가지 종류의 연산에서 압도적인 우위를 보여준다.

미국 표준연구소(National Institute of Standards and Technology, 이하 NIST)의 수학자 더스틴 무디(Dustin Moody)는 “과학자들은 수십 년 전부터 거대한 양자 컴퓨터를 만들 수 있다면 상당히 복잡한 연산들도 해결할 수 있다고 주장했다. 그것은 오늘날 우리가 사용하는 보안 암호 시스템에 위협이 될 것이다”라고 말한다.

양자 컴퓨터가 현대 암호화 기술을 무력화하는 수준에 도달하기 위해서는 아직 가야할 길이 멀다. 그럼에도 불구하고 NIST는 ‘양자 내성(quantum-proof)’이 높은 암호화 표준 구축을 목표로 2016년 공모전을 시작했다. 최종 우승팀은 2022년 발표될 예정이며, 지난 주 최초 69개 팀에서 15개 팀으로 우승 후보가 좁혀졌다는 중간 결과가 발표되었다.

중간 결과를 보면 우승 후보 대부분이 ‘양자 후 암호화(post-quantum cryptography)’에 대해 동일한 접근법을 취하고 있음을 알 수 있다. 바로 격자 기반 암호화(lattice-based cryptography)가 그것이다.

어떻게 작동하나?

전통 수학 기법으로 데이터를 암호화하는 기존 공개키(public-key) 암호 방식의 경우, 암호를 풀기 위해서는 키를 이미 알거나, 알아낼 수 있어야 한다. 반면 격자 기반 암호화는 수천 개의 차원을 관통하는 수십억 개의 포인트로 이루어진 그리드(격자)가 사용된다. 격자 기반 암호의 코드를 해독한다는 것은 이 같은 그리드에 놓인 어느 한 포인트에서 다른 한 포인트로 이동한다는 것을 의미한다. 즉, 처음부터 경로를 알고 있지 않으면 불가능한 일인 것이다.

양자 컴퓨터의 위협에 경계의 목소리를 높이던 미국 국가안보국(National Security Agency)조차 격자 기반 접근법에 대해서는 신뢰감을 표시했을 정도다.

그렇지만 중요한 것은 단순히 얼마나 어렵고 복잡한 수학을 사용했는지가 아니다. 양자 후 접근법이 효과를 발휘하기 위해서는 강력한 암호화가 필요한 곳이면 어디든 적용될 수 있어야 한다. 예를 들어, 데이터 해독에 필요한 키의 크기에 대해 생각해보자. 의료 장비가 있는데, 메모리가 극히 작고 대역폭도 극히 제한적이라면 이 의료 장비에 과연 얼마나 큰 키를 사용할 수 있을까? 만약 암호화에 사용된 수학이 지나치게 복잡해서 암호 해독에 필요한 키도 지나치게 커져야 한다면 실용성은 제로가 될 것이다.

지난 주 발표된 최종 후보 15개 팀 중 다섯 개 팀은 지금까지 알려진 양자 해답이 없는 격자 접근법을 사용한다. NIST의 최신 현황 보고에 따르면, 현재 후보에 오른 알고리즘 중 이 접근법이 ‘가장 유망한 범용 알고리즘’이다.

후보 중에는 격자 시스템의 보안성이 불충분할 경우 다른 획기적인 돌파구의 단초가 될 수 있는 대안도 포함되어 있다. 그렇지만 이들은 전반적으로 초기 단계로, 아직 연구가 부족하고 무엇보다 현실화되기까지 가야 할 길이 격자 접근법에 비해 훨씬 더 멀다. 그래서 대부분의 전문가들은 2022년 최종 우승을 차지할 두 개 팀이 사용하는 알고리즘은 결국 격자 시스템이 될 것이라고 입

이 기사는 유료 구독자 전용 콘텐츠입니다.

유료 멤버십 플랜 보기