양자 알고리즘은 양자역학적 현상(중첩, 얽힘, 간섭)을 활용해 고전 컴퓨터보다 특정 문제를 더 빠르게 해결하는 알고리즘이다. Grover와 Shor 알고리즘이 가장 유명하다.
대표 양자 알고리즘 비교
| 알고리즘 | 문제 | 고전 복잡도 | 양자 복잡도 | 위협 대상 |
|---|
| Shor | 소인수분해 | O(exp(n^1/3)) | O(n³) | RSA, ECC |
| Grover | 비정렬 검색 | O(N) | O(√N) | AES 키 강도 절반 |
| HHL | 선형 방정식 | O(Ns) | O(log N) | 머신러닝 |
| VQE | 분자 시뮬레이션 | O(exp(N)) | O(poly(N)) | 화학/신약 |
Grover 알고리즘
목적: N개 항목 중 f(x)=1을 만족하는 x 탐색
일반 DB 검색은 평균 N/2번, Grover는 √N번
동작:
1. 균등 중첩 생성: H⊗n |0⟩
2. Oracle (O): 정답 상태의 위상 반전
O|x⟩ = -|x⟩ (정답)
O|x⟩ = |x⟩ (오답)
3. Diffusion (D): 평균에 대한 반전
4. 2~3번을 π√N/4 번 반복
5. 측정
AES-128에 미치는 영향:
- Grover 적용 시 효과적 키 공간: 128 → 64비트
- 대응: AES-256 사용 권장
Shor 알고리즘
목적: N = p × q 소인수분해
RSA-2048 고전 컴퓨터로 수천 년 → 양자로 수 시간
핵심 단계:
1. 임의 a 선택 (gcd(a,N)=1)
2. QPE로 f(x) = a^x mod N 의 주기 r 탐색
(Quantum Phase Estimation + QFT 사용)
3. r이 짝수이면 p = gcd(a^(r/2)±1, N)
위협:
- RSA, DSA, ECDSA 모두 취약
- 2048비트 RSA 파괴에 약 4000개 논리 큐비트 필요
양자 내성 암호 (Post-Quantum Cryptography)
NIST PQC 표준화 (2024):
- ML-KEM (CRYSTALS-Kyber) : 키 캡슐화 (격자 기반)
- ML-DSA (CRYSTALS-Dilithium): 디지털 서명 (격자 기반)
- SLH-DSA (SPHINCS+) : 디지털 서명 (해시 기반)
관련 문서
