양자 내성 암호

양자 내성 암호는 쇼어 알고리즘(Shor's algorithm)에 의해 해독될 수 있는 RSA 및 타원 곡선 암호를 대체하기 위해, 양자 컴퓨터로도 풀기 어렵다고 여겨지는 문제에 보안을 의존하는 공개 키 방식을 개발합니다.

Definition

양자 내성 암호는 대규모 양자 컴퓨터를 갖춘 공격자에게도 안전하게 유지되도록 설계된 고전적(비양자) 암호 알고리즘으로, 효율적인 양자 알고리즘이 알려지지 않은 문제에 의존합니다.

Scope

이 주제는 양자 위협(쇼어 알고리즘 및 그로버 알고리즘), 양자 내성 방식의 주요 계열(격자 기반, 코드 기반, 해시 기반, 다변수), NIST 표준화 노력 및 선정된 알고리즘(ML-KEM, ML-DSA, SLH-DSA), 그리고 '지금 수확하여 나중에 해독(harvest-now-decrypt-later)' 및 하이브리드 배포와 같은 마이그레이션 문제를 다룹니다. 양자 하드웨어를 사용하는 양자 암호학(양자 키 분배)은 제외됩니다.

Core questions

• 양자 컴퓨터는 왜 RSA와 타원 곡선 암호는 해독하지만 대칭 암호는 그렇게 심각하게 해독하지 못합니까?
• 어떤 어려운 문제(격자, 코드, 해시)가 양자 공격에 저항한다고 여겨집니까?
• NIST는 표준화를 위해 어떤 방식을 선택했으며, 그 장단점은 무엇입니까?
• '지금 수확하여 나중에 해독' 위협은 무엇이며, 왜 긴급성을 야기합니까?
• 마이그레이션 중 하이브리드 배포에서 양자 내성 방식과 고전적 방식은 어떻게 결합됩니까?

Key concepts

• 쇼어 알고리즘
• 그로버 알고리즘
• 격자 기반 암호학 (학습 오류)
• 코드 기반 암호학
• 해시 기반 서명
• ML-KEM (Kyber) 및 ML-DSA (Dilithium)
• 지금 수확하여 나중에 해독
• 암호 민첩성
• 하이브리드 키 교환

Key theories

쇼어 알고리즘으로 인한 양자 위협

쇼어의 양자 알고리즘은 정수를 인수분해하고 이산 로그를 다항 시간 내에 계산하여 RSA, Diffie-Hellman 및 타원 곡선 암호를 해독합니다. 그로버 알고리즘은 무차별 대입 속도를 제곱근만큼만 가속화하므로 대칭 키는 단순히 길이를 두 배로 늘리면 됩니다.

양자 난해 문제군

양자 내성 보안은 격자에서의 학습 오류 및 최단 벡터 문제, 무작위 선형 코드 해독, 해시 함수의 보안과 같은 문제에서 찾고 있습니다. 이들 중 효율적인 양자 알고리즘이 알려진 것은 없습니다.

Mechanisms

ML-KEM(CRYSTALS-Kyber에서 파생)과 같은 격자 방식은 모듈 학습 오류 문제(module learning-with-errors problem)의 난이도에 키 캡슐화를 기반하며, 개인 키만 제거할 수 있는 작은 무작위 '오류'를 추가합니다. 해시 기반 서명(SLH-DSA/SPHINCS+)은 해시 함수의 보안에 전적으로 의존하여 서명을 생성합니다. 코드 기반 방식은 무작위처럼 보이는 선형 코드(linear code) 내에 해독 가능한 구조를 숨깁니다. 마이그레이션은 일반적으로 고전적 방식과 양자 내성 방식을 결합한 하이브리드 구성을 사용하여 둘 중 하나라도 살아남으면 보안이 유지되도록 합니다.

Clinical relevance

배포된 시스템에서는 이미 마이그레이션이 진행 중입니다. 주요 브라우저와 TLS 라이브러리는 하이브리드 ML-KEM 키 교환을 활성화했으며, 메시징 앱(Signal의 PQXDH)과 SSH는 양자 내성 핸드셰이크를 추가했습니다. 표준화 기관들은 조직에 암호화를 재고하고 전환을 계획하도록 촉구하고 있습니다. '지금 수확하여 나중에 해독' 위험은 장기적인 기밀성이 필요한 데이터가 오늘날 양자 공격으로부터 보호되어야 함을 의미합니다.

Evidence & guidelines

NIST는 2024년에 첫 번째 양자 내성 표준을 확정했습니다. 키 캡슐화를 위한 FIPS 203 (ML-KEM), 서명을 위한 FIPS 204 (ML-DSA) 및 FIPS 205 (SLH-DSA)입니다. NIST, NSA (CNSA 2.0) 및 국가 기관의 지침은 마이그레이션 일정을 설정합니다. 전환 기간 동안의 모범 사례는 양자 내성 알고리즘과 고전적 알고리즘을 결합한 하이브리드 방식을 선호합니다.

History

피터 쇼어(Peter Shor)의 1994년 알고리즘은 양자 컴퓨터가 지배적인 공개 키 시스템을 해독할 수 있음을 보여주었으며, 이는 대안을 찾기 위한 동기를 부여했습니다. 격자 기반 암호학은 Ajtai의 최악의 경우 난이도 결과와 Regev의 학습 오류 문제(2005)를 통해 발전했습니다. NIST는 2016년에 공개 표준화 프로세스를 시작했으며, 여러 차례의 라운드 후에 CRYSTALS-Kyber 등을 선정하고 2024년에 첫 번째 표준(FIPS 203-205)을 발표했습니다.

Key figures

• Peter Shor
• Daniel J. Bernstein
• Tanja Lange
• Oded Regev
• Chris Peikert

Seminal works

• shor1997
• nist2024mlkem
• bernstein2017

Frequently asked questions

RSA를 해독할 수 있는 양자 컴퓨터가 이미 존재합니까?

아니요. 현재의 양자 컴퓨터는 실제 키 크기에 쇼어 알고리즘을 실행하기에는 너무 작고 노이즈가 많습니다. 문제는 미래의 기계와, 오늘날 암호화된 데이터가 그러한 기계가 존재할 때 저장되고 해독될 수 있다는 사실에 있습니다.

양자 내성 암호는 양자 하드웨어를 필요로 합니까?

아니요. 양자 내성 방식은 일반적인 고전적 컴퓨터에서 실행됩니다. 단지 양자 공격자에게도 풀기 어렵다고 여겨지는 수학적 문제에 의존할 뿐입니다. 양자 하드웨어를 사용하는 양자 키 분배는 별개의 접근 방식입니다.