큰 정수의 소인수분해나 이산 로그 문제를, 양자 푸리에 변환으로 주기를 구함으로써 다항 시간에 푸는 양자 알고리즘. 1994년에 피터 쇼어가 발표했다. RSA 암호나 타원 곡선 암호를 깰 수 있지만, 실행에는 대규모 오류 내성 양자 컴퓨터가 필요하다.
일본어 명칭: ショアのアルゴリズム
쇼어 알고리즘(Shor's Algorithm)은(는) 양자 컴퓨터의 하드웨어 등 1개 분야의 연습 문제 4개에 나와요.
분야: 양자 컴퓨터의 하드웨어
정답: A. RSA 암호나 타원 곡선 암호 등의 공개 키 암호
RSA 암호의 안전성은 큰 수의 소인수분해의 어려움에, 타원 곡선 암호는 이산 로그 문제의 어려움에 기반하고 있습니다. 쇼어 알고리즘은 양자 푸리에 변환을 사용해 주기를 구함으로써 이러한 문제를 다항 시간에 풀 수 있습니다. 고전 컴퓨터로는 현실적인 시간에 풀 수 없는 길이의 키라도, 충분히 큰 오류 내성 양자 컴퓨터가 있으면 해독할 수 있게 됩니다. AES 등의 대칭 키 암호에 대해서는 그로버 알고리즘에 의한 제곱의 고속화밖에 없어, 키를 길게 하는 것으로 대응할 수 있습니다.
정답: C. 매우 많은 게이트를 오류 없이 실행해야 하며, 오류 정정으로 만든 많은 논리 큐비트와 그것을 떠받치는 막대한 수의 물리 큐비트가 필요하기 때문
RSA-2048의 해독에는 천~수천 개 정도의 논리 큐비트로 수십억 회 규모의 게이트를 연속해서 실행해야 합니다. 그래서 논리 오류율을 극히 낮게 해야 하며, 오류 정정을 위해 논리 큐비트 하나당 수백 개 이상의 물리 큐비트가 필요해집니다. 2020년대의 추산에서는 오류율 0.1% 정도의 물리 큐비트가 수십만~수천만 개 정도 필요하다고 여겨지며(전제에 따라 크게 다릅니다), 현재 장치의 규모와는 자릿수가 다른 차이가 있습니다. 다만 필요한 규모의 추산은 알고리즘의 개량으로 작아지고 있으므로, 암호 이행의 준비는 일찍 진행해야 합니다.
쇼어 알고리즘은 양자 푸리에 변환을 사용해 주기를 구함으로써 이러한 문제를 다항 시간에 풀 수 있습니다.
대규모 오류 내성 양자 컴퓨터가 실현되었을 때, 쇼어 알고리즘에 의해 안전성이 크게 손상될 것으로 생각되는…빨라지는 것은 제곱만큼뿐이며, 쇼어 알고리즘 같은 지수적인 차이는 없습니다.
정렬 순서에 규칙이 없는 100만 건의 데이터에서 조건에 맞는 1건을 찾을 때, 그로버 알고리즘으로 필요한…양자 내성 암호는 쇼어 알고리즘으로 풀려 버리는 소인수분해나 이산 로그 문제 대신, 격자 문제나 해시 함수 등에 기반한 암호로, 현재의 컴퓨터나 네트워크 기기에서 그대로 동작합니다.
양자 내성 암호(포스트 양자 암호, PQC)의 설명으로 올바른 것은?대칭 키 암호(Symmetric-key Cryptography) 큐비트(Qubit) 양자 내성 암호(Post-Quantum Cryptography) 해시 함수(Hash Function) 결어긋남(Decoherence) 스핀 큐비트(Spin Qubit) 양자 게이트(Quantum Gate) 양자 얽힘(Quantum Entanglement) 양자 오류 정정(Quantum Error Correction) 양자 중첩(Quantum Superposition)