미래기술/미래전망/첨단산업

NTT 기술저널_2023.5 특집 요약

양자컴퓨터 시대를 내다 본 암호 연구의 최전선

최근 암호 기술은 단순히 정보를 은닉하는 것이 아닌 속성 기반 암호와 같은 고기능 암호를 통해 데이터의 안전한 이용 및 활용을 가능하게 하는 기술로서의 역할도 담당하고 있다.

또한 지금까지의 양자 기술 발전에 의해 양자내성암호나 양자의 특성을 살린 암호 기술 연구도 추진되고 있다. 본 특집에서는 NTT 암호 기술 연구자들의 논문을 베이스로 이러한 최신 암호 기술들에 대해 소개한다.

목차

1. 현대 암호 기술의 발전과 양자컴퓨터 시대의 암호 연구를 향해
40년에 이르는 NTT의 암호 연구 역사를 현재 인터넷 등에서도 널리 이용되고 있는 ‘현대 암호’, 범용 양자컴퓨터의 등장에 대비하는 ‘양자내성암호’, 양자의 특성을 활용한 전혀 새로운 ‘양자 암호’를 단계별로 소개한다.

2. 비밀키를 안전하게 대여할 수 있는 함수형 암호
양자의 특성을 활용함으로써 ‘비밀 키를 제거한 것에 대한 증명’, ‘비밀키의 복제 방지’를 가능하게 하는 암호 기술의 개요와 구현될 경우, 기대할 수 있는 이노베이션에 대해 소개한다

3. 새로운 응용 분야를 개척하는 양자컴퓨터용 알고리즘
양자컴퓨터를 이용해 고속으로 풀 수 있는 문제의 영역을 넓힐 수 있는 새로운 양자컴퓨터용 알고리즘에 대한 논문 (Verifiable Quantum Advantage without Structure)의 개요에 대해 소개한다.

4. 양자컴퓨터를 이용한 사이버 공격에 대한 해시함수의 안전성을 더 깊이 이해하기 위해
세계적으로 폭넓게 이용되고 있는 암호학적 해시함수 ‘SHA-2’의 안전성이 양자컴퓨터의 등장으로 어떤 영향을 받게 되는지에 대해 소개한다.

5. 암호와 액세스 제어를 조합할 수 있는 혁신적인 속성 베이스 암호(ABE) 기술의 최신 동향
NTT Research, In.에서 추진되고 있는 암호 기술과 속성에 따른 액세스 제어를 조합한 속성 베이스 암호 ‘ABE’에 관한 연구에 대해 소개한다.

6. 주역 등장: 니시마키(西卷) (NTT사회정보연구소)
고전컴퓨터로는 불가능한 암호 기술을 실현하는 양자역학의 힘

현대 암호 기술의 발전과 양자컴퓨터 시대의 암호 연구를 향해

1976년부터 시작된 현대 암호 이론에서는 공격자를 다항식 시간 튜링머신으로 인식하고 안전성을 고려했다. 하지만 최근의 범용 양자컴퓨터 실현 가능성은 이러한 모델을 뒤집을 정도의 영향을 현대 암호 이론에 주었다.

NTT의 암호 연구는 현대 정보 시스템의 안전성을 확립하는 기술을 제공하고, 양자컴퓨터가 보급된 미래에서의 응용 창출도 테마 중 하나이다. 본 특집에서는 10년에 걸친 NTT의 암호 연구를 개관하고 현재의 연구활동에 대해 소개한다.

■ NTT의 암호 연구를 둘러싼 상황
1982년 일본전신전화공사 직원의 은행 카드 위조 사건을 계기로 시작된 NTT의 암호 연구는 올해 40주년을 맞이했다. 연구가 시작된 당시 겨우 3명으로 구성되었던 연구팀은 1992년, 정보통신망연구소 내에서 8명으로 구성된 정식 연구 그룹이 되었다.

이후, 웹 브라우저 Mosaic의 등장(1993년)과 함께 인터넷이 폭발적으로 보급되는 시기에 정보 보안의 중요성이 인식되면서 정보시큐리티프로젝트(1999년)로, 더 나아가 NTT시큐어플랫폼(2012년)으로 거듭나게 되었다.

정보 보안 기술이 코모디티화되어 일상생활을 뒷받침하고 있는 현재는 NTT사회정보연구소로서 폭넓게 암호 및 정보 보안 연구를 추진하고 있다.

네트워크의 고도화는 다양한 정보 유통 시스템을 가능하게 했고, 암호도 은닉이나 인증과 같은 기본적인 ‘방어’에서 암호 통화나 클라우드 컴퓨팅 등 새로운 응용을 창출하는 ‘공격’으로 적용 범위를 확대해왔다.

또한, 범용 양자컴퓨터의 실현 가능성이 높아지면서 현재 실용화된 공개키 암호가 급격하게 위태로워지는 것이 명백해짐으로써 ‘방어’의 이용에서도 새로운 대응이 필요하게 되었다. 또한 미래를 위해 범용 양자컴퓨터를 적극적으로 이용한 암호 응용 창출과 그것을 뒷받침하는 기초 이론 확립이 기대되고 있다.

이번 특집에서는 암호의 이용자와 공격자가 현재 이용할 수 있는 컴퓨터인 고전적 컴퓨터를 이용한 ‘현대 암호’, 공격자만이 양자컴퓨터를 이용하는 ‘양자내성암호’, 이용자와 공격자가 모두 양자컴퓨터를 이용하는 ‘양자암호’에 대해 공개키 암호 관련 주제를 중심으로 개관하고, NTT의 암호 이론 연구와의 연관성에 대해 소개한다. 또 하나의 중요한 연구 주제인 공통키 암호에 대해서도 양자내성암호의 관점에서 소개한다.

■ 현대 암호 이론의 발전
안전하고 효율적인 암호는 어떤 클라스의 문제를 확률적 튜링머신으로 푸는 것이 평균적으로 어렵다고 하는 계산량 관점의 가정에 기반해 구성되어 있다. 공격자가 이용할 수 있는 알고리즘이나 하드웨어가 진보하게 되면 문제는 이전보다 짧은 시간에 풀 수 있게 된다. 그렇게 된다면 그 문제의 클라스에 기반한 암호는 안전성 확보를 위해 보다 큰 공개키가 필요하게 되어 퍼포먼스가 저하된다.

공개키 암호의 선구적 위치에 있는 RSA암호(1977년), Robin암호(1978년), NTT가 개발한 디지털 서명 방식의 ESIGN(1990년)은 소인수분해 문제의 곤란성을 이용하고 있다. 개발 당시, RSA의 공개키는 512비트이면 안전하다고 생각되었지만, 현재는 3,072비트 이상이 추천되고 있다.

마찬가지로 선구적인 암호 기술인 Diffie-Hellman 키배송(1976년), El Gamal암호(1985년), DSA서명(1993년)은 당초, 승법군(乘法群)상의 이산대수 문제를 이용해 구성된 것이지만, 같은 보안 레벨에서 공개키를 보다 작게 할 수 있는 타원곡선상의 이산대수 문제에 기반한 구성(ECDSA서명 등, 2005년)으로 전환되었다.

네트워크의 고도화로 인해 클라우드 컴퓨팅과 같은 고도의 응용이 등장하면서 암호는 기본적인 은닉과 인증이라는 방어의 기술에서 고도의 정보 유통 서비스를 구축하기 위한 공격의 기술로 발전해왔다.

타원곡선상의 군(群)에 있어서의 쌍선형 사상(페어링)은 당초, B.S.Kalisky Jr.에 의해 안전한 키 생성에 이용되었고(1987년), NTT의 오카모초(岡本) 연구팀의 타원곡선 암호의 안전성 해석(MOV 귀착, 1991년)으로 널리 알려지게 되었다.

이후, 개인 ID를 공개키로 할 수 있는 ID 베이스 키 교환(2000년)과 ID 베이스 암호(2001년)을 통해 본격적으로 암호에 이용되는 등, 현재까지 수많은 실용적 응용이 창출되었다.

특히, 그 전까지 한정적이었던 비(非)대화 영지식증명의 이용 영역이 페어링의 도입으로 단번에 확대(2008년), NTT에서도 페어링군상에서 영지식증명과 서명 등을 자유롭게 조합해 고도의 기능을 실현하는 군(群)구조유지암호계(2009년) 연구가 진전되었다.

페어링은 복잡한 스테이트먼트를 짧은 증명서를 통해 효율적으로 검증할 수 있는 Computationally Sound Proof라고 하는 선진적인 개념(2000년)을 Zero-Knowledge Succinct Noninteractive Argument(zkSNARG, 2012년)로 실현하는데 크게 기여했다.

짧은 증명서는 블록체인에서의 응용에 크게 유효하기 때문에 zkSNARG는 웹3 시대의 기반 기술이 될 수 있을 것으로 기대되고 있으며, C++와 같은 고급 언어로 표현된 스테이트먼트를 zkSNARG가 처리하기 쉬운 NP-완전 중간 언어에 컨파일하는 프론트엔드 개발이 추진되면서 실용성이 급속도로 향상되고 있다.

암호가 다양한 응용을 통해 이용되고 있다는 것과 암호 자체의 고기능화로 인해 요구되는 안전성도 고도화되고 있다. 식별 불가능성 등 비교적 단순한 안전성에 관련해서는 이산대수 문제에 기반한 Blum-Miicali의 모의 랜덤 생성기(1982년)와 소인수분해 문제에 기반한 Rabin암호(1986년)와 같이 단일의 곤란성 가정으로의 비교적 단순한 귀착에 의한 증명이 제시되어 왔다.

하지만 공격자가 보다 적극적으로 암호 시스템의 입력-출력에 관여하는 것을 허용한 적응적 선택 암호문 공격에 대한 안전성(IND-CCA안전성, 1991년)과 같은 고도의 안전성은 그것을 달성하는 암호 방식 구성과 함께 안전성 증명도 복잡해졌다.

Mihir Bellare 연구팀이 개발한 해시함수를 이상화해 처리하는 랜덤 오라클 모델(1993년)은 암호의 구성과 안전성 증명을 단순화하는 데 크게 기여, 랜덤 오라클 모델의 안전성이 증명된 다양한 암호 방식 및 응용이 1990년대 후반부터 2000년대에 제안되어 증명 가능 안전성의 패러다임이 확대되었다.

NTT는 IND-CCA 안전한 공개키 암호의 일반적 구성 방법인 Fujisaki-Okamoto 변환(FO변환, 1998년), 키 캡슐화 메커니즘 PSEC-KEM(1999년), 메시지 회귀형 서명 방식 ECAOS(2008년) 등이 랜덤 오라클 모델에서 안전성을 증명할 수 있는 방식으로 개발되었다. 한편, 랜덤 오라클에 기반하지 않는 효율적이고 증명 가능이 안전한 구성을 추구하는 연구도 활발하게 추진되어 왔다.

현재의 컴퓨터를 대상으로 발전해온 암호 기술은 후반부에 소개하는 양자컴퓨터 등장 이후의 세계에서도 안전한 암호 구성에 도움이 될 것이며, 암호 기초 이론으로 이어져나갈 것이다.

■ 현대 암호에서 양자내성암호로
공격자가 범용 양자컴퓨터를 실제로 이용할 수 있게 되기까지는 아직 상당한 시간이 걸릴 것으로 생각된다. 그렇다고는 하지만, 현시점에서 유통되고 있는 대부분의 정보는 수집되고 저장되기 때문에 미래의 안전성을 확보하기 위해서는 현재의 암호 기술이 범용 양자컴퓨터를 이용한 미래의 공격에 버텨낼 필요가 있다.

양자컴퓨터 내성의 안전한 암호 구성에 이용되는 기본적인 곤란성 가정으로서 공격자(Lattices)에 기반한 문제가 유망시되고 있다. 격자 문제 암호로의 이용은 Ajtai의 일방향성 함수 구성(1996년)에서 시작, 이후 격자 베이스에서 실용적 효율을 가진 NTRU암호(1998년)가 제안되고 있다.

디지털 서명의 경우에는 다변수∙다항식 및 해시함수에 기반한 구성도 양자내성암호의 안전성을 위한 유망한 선택지이다.

2017년부터 개시된 NIST(미국국립표준기술연구소)의 Post-Quantum Cryptography(PQC) Competition에서 양자컴퓨터 내성의 안전한 공개키 암호, 디지털 서명 공모가 실시, 2022년에 최종 후보가 발표됨에 따라 양자내성암호는 급속도로 실용화에 가까워졌다. 2024년에는 새로운 표준이 되고, 2030년까지 현재의 암호를 대체할 수 있을 것으로 예상되고 있다.

NTT는 NTRU암호를 제안한 곳으로서 다수의 후보 평가를 실시하는 형태로 NIST PQC 대회에 기여하고 있다. 양자컴퓨터 분야에서는 양자얽힘 상태에서의 연산이 가능해 공격자의 계산 원리가 다르기 때문에 안전성 증명 방법도 양자컴퓨터에 맞춰 재구축되어왔다.

전술한 FO 변환도 양자 상태에서 계산하는 해시함수를 모델화한 양자 랜덤 오라클 모델에서 안전성이 성립할 수 있도록 재검토되고 있으며, NIST PQC 대회에서 채택된 암호 방식 CRYSTALSKyber를 IND-CCA 안전으로 하기 위해 사용되고 있다.

격자는 양자내성암호의 안전성 관점뿐만 아니라 고기능 암호를 실현하는 기반 기술이기도 하다. 특히 암호화한 채 평문의 가산 및 승산이 가능한 완전 준동형 암호는 클라우드 컴퓨팅을 비롯해 광범위한 응용이 가능한 강력한 암호 기술이다. NTT는 격자 암호의 안전성 해석 및 완전 준동형 암호 연구(2013~)를 추진하고 있다.

블록 암호 및 해시함수와 같은 공통키 암호계의 암호 기술에 대해서는 내부 구조를 고려하지 않은 범용적인 양자 알고리즘을 이용한 키 탐색 공격에 대해 키의 길이나 블록의 길이를 2~3배로 함으로써 안전성을 유지할 수 있다.

그렇기 때문에 정수론적 가정에 기반한 공개키 암호와 같은 치명적인 영향은 받지 않는다고 알려져 있다. 한편, 잘 알려진 특정 구조에 대해 효과적인 공격이 나타나고 있기 때문에 양자컴퓨터에 의한 공격은 공통키 암호에 있어서도 새로운 리스크이다.

본 특집 기사인 ‘양자컴퓨터를 이용한 공격에 대한 해시함수의 안전성을 보다 깊이 이해하기 위해’에서는 양자컴퓨터를 이용한 공격에 대한 해시함수의 안전성, 특히 현재 가장 널리 사용되고 있는 해시함수 SHA-256와 SHA-2의 양자내성암호의 안전성에 대해 소개한다.

양자내성암호의 안전한 영지식증명과 암호 프로토콜 연구도 진전되고 있지만, 지금 바로 현재의 기술을 대체할 수 있는 성능이 되기까지는 더 많은 연구가 필요하다.

예를 들어, 익명 전자 투표에서는 기존의 고전 암호 기술로는 수 kB의 투표이지만, 양자내성암호 안전성의 아래에서는 수 백 kB로 증가하게 된다. 이러한 것들은 현재의 암호 기술에 의해 정보 유통 시스템의 양자내성암호의 안전성으로 전환되는 데 불가결한 요소 기술로, 조기 발전이 기대되고 있다.

■ 양자 암호를 목표로
최근의 엣지 디바이스의 눈부신 계산 능력 향상은 다양한 어플을 가능하게 해왔다. 양자컴퓨터가 공격자뿐만 아니라, 일반 이용자에게까지 보급되는 미래에는 어떤 기술이나 응용이 있을 수 있을까? 양자물리학자인 Stephen Wiesner는 관측에 의한 양자 상태의 상실을 위조가 불가능한 양자화폐에 응용하는 아이디어를 1969년에 발표했다.

그는 “현재의 암호통화나 전자화폐의 위조 방지는 거래 장부를 이용한 온라인 검증, 암호 기술을 통한 사후 검출, 또한 TEE(Trusted Execution Environment)의 탬퍼 저항성 등에 근거하고 있다”라고 말했다. 현재의 디지털 기술에서는 정보가 보관되고 있다는 것을 증명하는 것은 가능하지만, 제거되었다는 것을 증명하는 것은 불가능하다.

이것이 정보의 폐기를 불확실하게 해 정보 유출 리스크를 낳게 된다. 이번 특집 기사 ‘비밀키를 안전하게 대여할 수 있는 함수형 암호’에서는 암호의 비밀키를 제거한 것을 증명하는 연구를 소개한다.

양자컴퓨터 이슈가 일반화된 현재, 기존에는 없었던 응용이 모색되고 있을 뿐만 아니라 기초 이론의 확립을 목표로 양자물리와 양자정보처리, 양자이론을 융합하는 연구가 실시되고 있다.

본 특집 기사 ‘새로운 응용 분야를 개척하는 양자컴퓨터용 알고리즘’에서는 양자 우위성, 즉 양자컴퓨터의 계산 능력이 현재의 컴퓨터를 뛰어넘는 것을 실증하는 연구에 대해 소개한다.

■ 맺음말
지금까지 NTT 암호연구를 양자컴퓨터 실현과 연결해 3개의 분야로 크게 나눠 살펴보았다. NTT 사회정보연구소에서는 기초 분야로서 지금도 중요하게 인식되고 있는 암호기초이론에서 먼 미래의 응용에 이르기까지 다채로운 테마로 암호 연구를 추진, 현재와 미래의 정보 유통에 기여하는 기술을 전달해나갈 방침이다.

 -- 끝 --