키 길이가 n비트인 대칭 키 암호의 키를 양자 컴퓨터의 그로버 알고리즘으로 찾으면, 필요한 계산 횟수는 약 2^(n/2)회가 된다고 한다. 이 단순한 기준으로 생각했을 때, 양자 컴퓨터에 대한 AES-128의 안전성으로 가장 가까운 것은?

정답: A. 약 64비트 상당

그로버 알고리즘은 무차별 대입 횟수를 2ⁿ에서 약 2^(n/2)로, 제곱근까지 줄입니다. AES-128에서는 2^(128/2) = 2⁶⁴회가 되어, 안전성은 약 64비트 상당이 됩니다. 공개 키 암호를 다항 시간에 깨는 쇼어 알고리즘과 달리 키를 길게 하면 대응할 수 있으며, AES-256이라면 약 128비트 상당이 남습니다. 다만 그로버 알고리즘은 병렬화의 효과가 작고 긴 계산을 오류 없이 계속해야 하므로 이는 어디까지나 단순한 기준이며, NIST의 양자 내성 암호 평가에서도 AES-128의 키 탐색과 같은 정도로 어렵다는 것이 가장 낮은 안전성 구분의 기준으로 되어 있습니다.