양자 컴퓨터의 하드웨어
대규모 오류 내성 양자 컴퓨터가 실현되었을 때, 쇼어 알고리즘에 의해 안전성이 크게 손상될 것으로 생각되는 암호는?
- ARSA 암호나 타원 곡선 암호 등의 공개 키 암호
- BAES 등의 대칭 키 암호만
- C일회용 패드(한 번 쓰고 버리는 난수 키로 암호화하는 방식)
정답과 해설 보기
정답: A. RSA 암호나 타원 곡선 암호 등의 공개 키 암호
RSA 암호의 안전성은 큰 수의 소인수분해의 어려움에, 타원 곡선 암호는 이산 로그 문제의 어려움에 기반하고 있습니다. 쇼어 알고리즘은 양자 푸리에 변환을 사용해 주기를 구함으로써 이러한 문제를 다항 시간에 풀 수 있습니다. 고전 컴퓨터로는 현실적인 시간에 풀 수 없는 길이의 키라도, 충분히 큰 오류 내성 양자 컴퓨터가 있으면 해독할 수 있게 됩니다. AES 등의 대칭 키 암호에 대해서는 그로버 알고리즘에 의한 제곱의 고속화밖에 없어, 키를 길게 하는 것으로 대응할 수 있습니다.