양자 컴퓨터는 128비트 대칭 키에 위협이 아니다

Shor’s algorithm은 ECDH, RSA, ECDSA, EdDSA 같은 비대칭 암호를 깨뜨리지만, AES와 SHA-2/SHA-3 같은 대칭 암호와 그 키 크기에는 영향을 주지 않는다.

흔히 말하는 “양자 컴퓨터가 대칭 키 보안을 절반으로 줄인다”는 해석은 Grover’s algorithm을 잘못 이해한 것이다. Grover는 비정형 탐색에 제곱근 수준의 속도를 주지만, 공격을 병렬화하면 이 이득이 크게 희석된다.

• 고전적 brute force는 수많은 CPU로 쉽게 분할 가능하지만, Grover 공격은 그처럼 선형적으로 분산되지 않는다.
• 64비트 키를 깨는 고전 공격은 병렬화해도 전체 작업량은 유지되지만, Grover 공격은 검색 공간을 나누면 각 인스턴스의 이득이 줄어든다.
• 128비트 키에 Grover를 적용해도, 실제로는 거대한 수의 양자 회로와 장시간의 안정적 실행이 필요하다.

저자는 보수적으로 가정해도, 1µs 게이트 시간의 양자 하드웨어에서 10년 동안 실행 가능한 깊이를 잡고, AES-128에 대한 최적화된 Grover oracle 연구를 대입하면, AES-128을 깨기 위해서는 대략 2^47 수준의 병렬화가 필요하다고 계산한다. 이는 약 140조 개의 양자 회로가 동시에 돌아가야 한다는 뜻이다.

또한 이 공격의 DW cost는 약 2^104.5로 추정되며, 최근 제안된 256비트 타원곡선에 대한 Shor 공격보다 훨씬 비싸다. 글은 AES-128을 Grover로 깨는 비용이 Shor로 256-bit ECC를 깨는 비용보다 극단적으로 크다고 강조한다.

마지막으로 NIST도 AES-128을 포스트-퀀텀 암호의 기준선으로 삼고 있으며, 현재의 포스트-퀀텀 전환에서 바뀌어야 하는 것은 비대칭 암호이지 대칭 키 길이가 아니라는 점을 분명히 한다.