'양자내성암호는 완전한가' 관련 대표문제 공략 전 과정 증명 이뤄져

ETRI 연구진이 양자중첩샘플 생성 및 메인 계산 알고리즘 전반의 최적화에 대해 논의하고 있다.
ETRI 연구진이 양자중첩샘플 생성 및 메인 계산 알고리즘 전반의 최적화에 대해 논의하고 있다.

'양자컴퓨터로도 풀 수 없는 완전한 암호체계'라는 양자내성암호 이미지를 퇴색시키는 연구 결과가 재차 나왔다. 양자내성암호 대표 문제 공략 가능성을 다시 한번 현실적인 관점에서 입증했다. 양자컴퓨터를 이용, 양자내성암호를 공략할 수 있는 조건이 존재함을 밝혔다.

한국전자통신연구원(ETRI)은 한국과학기술연구원(KIST), 서울대, 한양대, 고등과학원(KIAS), 서울대, 한양대, 영국 임페리얼대 연구진과 함께 격자 기반 양자내성암호 기반 문제인 '2진 선형잡음문제' 공략 가능성을 증명하고 이를 물리학 전문 학술지인 '뉴 저널 오브 피직스'에 게재했다고 16일 밝혔다.

선형잡음문제는 에러가 있는 선형 일차방정식 해(문제 풀이)를 구하는 것이다. 무작위 추출된 입력, 에러가 포함된 출력으로 이뤄진 샘플을 얼마나 적게 사용해 문제를 해결하느냐에 따라 난이도가 갈린다. 주요 양자내성암호 기반 문제다.

연구진은 올해 초 세계 최초로 '분할-정복 전략'을 활용한 알고리즘을 기반으로 비교적 소규모 양자컴퓨터로 양자내성암호를 공략할 가능성을 보였다.

이번 연구에서는 알고리즘 계산에 필요한 양자샘플(양자컴퓨팅에 필수인 양자중첩 형태 입력 소스) 구성부터 주된 알고리즘 계산에 이르기까지 전 과정을 '결함허용 양자컴퓨팅' 관점에서 최적화했다. 결함허용 양자컴퓨팅은 일정 수준 오류가 발생해도 이를 수정·정정하는 양자컴퓨팅을 뜻한다. 양자컴퓨팅 기술 지향점이다.

연구진은 이번 연구가 '가정'이 담겨있던 이전 연구를 보다 '현실적'으로 발전시킨 것이라고 설명한다. 일례로 이전 연구에서는 양자샘플 생성과 활용을 단순히 가정했는데, 이번에는 다수의 0, 한 개의 1 값으로 데이터를 구분하는 '원-핫 인코딩' 방법을 활용해 실제 양자샘플을 구성하는 설계를 마련했다.

양자중첩샘플 준비 및 액세스를 위한 양자회로
양자중첩샘플 준비 및 액세스를 위한 양자회로

연구진은 또 2진 인코딩을 주된 알고리즘 계산에 활용하고 양자컴퓨팅 구동 자원을 최적화해 2진 선형잡음문제를 '다항 시간' 내 공략할 수 있음을 증명했다. 다항 시간은 해결하고자 하는 문제 양 대비 계산 필요 자원 증가가 다항함수보다 크지 않은 것을 뜻한다. 즉 이른 시일 안에 공략할 수 있다는 것이다.

방정호 ETRI 양자컴퓨팅연구실장은 “이번 연구는 분명히 선형잡음문제 양자 공략 가능성에 한 걸음 더 전진한 연구 결과”라고 밝혔다. 김명식 영국 임페리얼대 교수도 “기존 연구에서는 양자샘플이 이미 준비돼 있거나 효율적으로 만들 수 있다고 가정해 문제를 다뤘는데, 이번 연구에서는 양자샘플 생성을 비롯한 모든 계산과정을 분석해 양자 공략 가능성을 보였다”고 전했다.

연구진은 연속된 연구를 토대로 양자내성암호 안전성에 대한 너무 과도한 신뢰는 지양돼야 한다는 의견을 밝혔다. 박성수 ETRI 양자기술연구단장은 “양자내성암호 안전성에 대한 과도한 신뢰는 학술적으로 옳지 않다”며 “양자컴퓨팅, 암호학 발전을 위해서는 수학, 물리학, 암호학 등 연구자의 끊임없는 논의와 상호협력이 필요하다”고 설명했다.

한편 연구진은 향후 양자 데이터 검색 알고리즘의 계산 자원량을 결함허용 관점에서 정밀 분석하는 연구를 수행할 예정이다. ETRI는 양자컴퓨팅 연구를 꾸준히 수행 중으로, 수년 내 10여 개 큐비트급 규모 연산제어 기능을 갖춘 양자컴퓨팅 기술 확보를 위해 연구 중이다.

이번 논문 공동 1저 자는 송우영 KIST 박사, 임영롱 KIAS 박사, 정갑균 서울대 박사다. 참여 저자는 이진형 한양대 교수, 박정준 KIAS 박사, 김재완 KIAS 교수다. 공동 교신저자는 김명식 임페리얼대 교수, 방정호 ETRI 실장이다.

이번 연구는 과학기술정보통신부 '양자컴퓨팅 기술 개발 사업', 정보통신기획평가원(IITP) '양자암호통신 집적화 및 전송기술 고도화 사업' '양자인터넷 유선 양자 중계기 개발사업' 등을 통해 이뤄졌다.

김영준기자 kyj85@etnews.com