국내 연구진이 양자컴퓨터 시대의 새로운 암호체계인 양자내성암호(PQC)를 공략할 수 있는 양자 알고리즘을 개발했다. 양자컴퓨터뿐 아니라 수학, 암호학 등 관련 산업 분야의 전환점이 될 수 있다는 평가가 나온다.

ETRI 연구진이 PQC를 공략하고자 사용한 분할-정복 알고리즘 개요도 / ETRI
ETRI 연구진이 PQC를 공략하고자 사용한 분할-정복 알고리즘 개요도 / ETRI
한국전자통신연구원(ETRI)은 한국과학기술연구원(KIST)과 서울대, 한양대, 고등과학원(KIAS), 영국 임페리얼 대학 등 국내·외 연구진과 PQC 주요 기반 문제인 선형 잡음 문제를 효과적으로 공략할 수 있는 양자 알고리즘을 개발했다고 3일 밝혔다.

PQC는 양자컴퓨터 조차 해결하기 어려운 수학 난제를 활용한 차세대 암호 체계다. 양자컴퓨팅 연구 초기 양자 소인수 분해 알고리즘이 등장하며 공개키 암호시스템(RSA)과 같은 기존 암호 체계가 양자컴퓨터 실용화로 보안성을 유지하기 어려울 것으로 전망되는 상황에서 대체재로 나왔다.

PQC를 풀려면 문제의 규모 대비 지수함수적으로 증가하는 큐비트(Qubit) 자원이 필요하다. 그간 양자컴퓨터도 공략이 불가능한 것으로 알려졌다.

하지만 연구진은 분할-정복(divide-and-conquer) 전략을 활용해 비교적 소규모 수준의 양자컴퓨터로 PQC를 공략할 수 있는 양자 알고리즘을 개발했다. 분할-정복 전략은 전체 구조를 하부 구조로 작게 나눈 뒤 개별 공략하는 방법이다.

ETRI는 이번 연구가 적정한 수준의 양자 연산능력만으로 지수함수적 양자이득이 가능함을 증명한 사례라고 강조했다. 본 기술 공개로 양자 내성이 무효화되는 조건을 구체적으로 특정할 수 있게 됐다는 설명도 더했다. 양자 기술을 활용하는 기업과 연구기관, 공공기관이 차세대 암호를 연구하는 과정에서 활용 영역을 명확하게 할 수 있을 것이라는 게 ETRI 설명이다.

김명수 영국 임페리얼대 교수는 "잡음을 동반한 선형 문제에 양자컴퓨터를 쓰면 고전 컴퓨터보다 빨리 풀 수 있다는 점을 증명했다"며 "분할-정복 전략을 양자알고리즘에 사용한 첫 사례이다 보니 새로운 암호 체계의 신뢰도 계산에 직접적으로 연관돼 좋은 파급 효과가 있을 것으로 기대한다"고 말했다.

ETRI는 다만 이번 연구 성과가 양자컴퓨터가 양자 내성을 완전히 정복했다는 뜻은 아니라는 입장을 밝혔다. PQC 공략과 수호 관점에서 지속적인 연구가 더 필요하다는 설명이다.

연구진은 향후 양자 샘플을 생성‧준비하는 단계부터 주요 알고리즘의 동작에 이르기까지 문제 해결 전 과정의 계산 자원량을 결함 허용 양자컴퓨팅 관점에서 최적화하는 연구를 추가로 수행한다. 이를 통해 보다 현실적인 측면에서 PQC 양자 공략 가능성을 검증할 계획이다.

박성수 ETRI 양자기술연구단장은 "그동안 불가능하다고 생각하던 PQC 양자 공략이 원리적으로 가능하다는 점에서 해당 연구결과는 그 의미가 크다"며 다만 "PQC를 실제 효과적으로 공략하기 위해서는 양자컴퓨터의 연산능력을 더 확보해야 한다"고 말했다.

이번 연구 논문의 공동 제1저자는 송우영 KIST 박사, 임영롱 고등과학원 박사, 정갑균 서울대 박사다. 참여 저자는 지윤성 서울대 박사, 이진형 한양대 교수, 김재완 KIAS 교수다. 공동 교신 저자는 김명식 영국 임페리얼대 교수와 방정호 ETRI 박사다. 이번 연구 성과는 양자정보과학기술 전문 학술지인 퀀텀 사이언스&테크놀로지에 실렸다.

김평화 기자 peaceit@chosunbiz.com