REVIEW
양자 알고리즘,
가까워진 양자내성암호 공략
ETRI가 양자내성암호를 공략할 수 있는 세계 최고 성능 수준의 양자 알고리즘을 개발했다.
양자내성암호(Post-Quantum Cryptography)는 양자컴퓨팅 환경에서
안전하게 암호기술을 이용할 수 있는 새로운 공개키암호로, 양자컴퓨터의 모든 공격에 내성이 있다.
이런 양자내성암호를 풀 수 있는 양자 알고리즘은 양자컴퓨터뿐 아니라 수학, 암호학 등 관련 산업 분야의 전환점이 될 전망이다.
양자내성암호 공략, 가능성을 보다
ETRI는 KIST, 서울대학교, 한양대학교, KIAS, 영국 임페리얼 대학교 등 국내외 연구진들과 함께 양자내성암호의 주요 기반 문제 중 하나인 선형잡음문제를 효과적으로 공략할 수 있는 양자 알고리즘을 개발했다. 선형잡음문제는 에러가 있는 선형일차방적식의 해를 구하는 문제로, 무작위로 추출된 입력과 에러가 포함된 출력으로 이루어진 샘플을 얼마나 적게 사용해 해당 문제를 해결할 수 있는지로 난이도가 결정된다.
양자컴퓨팅 연구 초기, 양자 소인수 분해 알고리즘이 등장했을 때 암호화뿐만 아니라 전자서명이 가능한 최초의 알고리즘인 공개키암호시스템(RSA)과 같은 기존 암호체계는 양자컴퓨터가 실용화될 경우 보안성 유지가 어려울 것으로 예상되었다.
이에 양자컴퓨터를 이용한 해킹에서도 안전한 것으로 기대되는 새로운 암호체계, ‘양자내성암호(PQC)’ 암호체계가 등장했다. 양자내성암호는 양자컴퓨터조차도 해결하기 어려운 수학적 난제를 활용한 차세대 암호체계다. 이를 풀기 위해서는 문제의 규모에 대비해 지수함수적으로 증가하는 큐비트(Qubit)1) 자원이 필요하다. 이로써 사실상 양자컴퓨터조차도 공략이 어려운 상황이었다.
1) 큐비트(Qubit) 양자 컴퓨터로 계산할 때의 기본 단위로, 일반 컴퓨터는 정보를 0과 1의 비트 단위 처리하고 저장하는 반면 양자 컴퓨터는 정보를 0과 1의 상태를 동시에 갖는 큐비트 단위로 처리하고 저장한다.
‘분할-정복 전략’의 양자 알고리즘
연구진은 이에 세계 최초로 ‘분할-정복(divide-and-conquer) 전략’을 활용해 비교적 소규모 수준의 양자컴퓨터로도 양자내성암호를 공략할 수 있는 양자 알고리즘을 개발했다. 분할-정복 전략은 차원이 높은 구조로 이루어진 입력-출력쌍 샘플을 여러 개의 입력-출력쌍 샘플들로 분해해, 분해된 각각을 보다 소규모의 양자시스템으로 각개 공략하고자 하는 전략이다.
이처럼 전체 구조를 하부 구조들로 작게 나누고 개별 공략하는 방법은 적정한 수준의 양자 연산 능력만으로도 ‘지수함수적 양자이득’이 가능함을 증명한 것이다. 이는 해결하고자 하는 문제의 계산에 필요한 자원의 증가량 양상이 어려운 문제에서 쉬운 문제로 줄어들었다는 뜻이다.
이로써 연구진은 이번 기술 공개로 양자 내성이 무효화되는 조건을 보다 구체적으로 특정할 수 있게 되었다. 이에 따라 양자기술을 활용하는 기업, 연구기관, 공공기관의 차세대 암호 연구의 활용영역을 명확하게 할 수 있을 것으로 전망된다.
양자내성암호 공략을 위한 발걸음
이번 연구는 양자내성암호 양자공략이 원리적으로 가능하다는 점에서 의미가 크다. 양자내성암호를 실제 효과적으로 공략하기 위해서는 양자컴퓨터의 연산 능력을 더 확보해야 하며, 양자내성암호 공략 및 수호 관점에서 앞으로도 지속적인 연구가 더 필요하다.
연구진은 향후 양자샘플을 생성하고 준비하는 단계부터 주요 알고리즘의 동작에 이르기까지 문제해결 전체 과정의 계산 지원량을 ‘결함허용 양자컴퓨팅’2) 관점에서 최적화하는 연구를 추가적으로 수행할 계획이다. 이를 통해 보다 현실적인 측면에서 양자내성암호 양자공략 가능성을 검증할 것으로 기대된다.
이번 성과는 양자정보과학기술 전문 학술지인 퀀텀 사이언스&테크놀로지에 게재되었으며, 과학기술정보통신부의 양자컴퓨팅 기술개발 사업과 정보통신 기획평가원 양자암호통신 집적화 및 전송기술 고도화 사업 등의 지원을 통해 개발됐다.
2) 결함허용 양자컴퓨팅 양자컴퓨터에 일정 수준의 오류가 존재하더라도 신뢰도 있는 양자컴퓨팅을 수행하기 위한 방법을 제시하기 위한 것으로서, 양자오류정정 부호 기법을 활용한다.
