월요일에 Valsorda는 마침내 널리 퍼진 오해로 인해 수년간의 좌절감을 블로그 게시물이라는 제목으로 전달했습니다. 양자 컴퓨터는 128비트 대칭 키에 위협이 되지 않습니다..
그는 “양자 컴퓨터가 대칭 키의 보안을 ‘절반’해 128비트 보안을 위해 256비트 키가 필요하다는 일반적인 오해가 있습니다”라고 썼습니다. “이는 양자 알고리즘이 제공하는 속도 향상에 대한 정확한 해석이 아니며 규정 준수 의무에 반영되지 않으며 실제로 필요한 양자 전환 후 작업에서 에너지와 관심을 돌릴 위험이 있습니다.”
이것이 논쟁의 쉬운 부분이다. 훨씬 더 어려운 부분은 그것을 설명하는 수학과 물리학입니다. 가장 높은 수준에서는 무차별 대입 검색이 기존 컴퓨터에서 작동하는 방식과 Grover의 알고리즘을 사용하여 작동하는 방식의 근본적인 차이로 귀결됩니다. 기존 컴퓨터는 여러 검색을 동시에 수행할 수 있으며, 이를 통해 대규모 작업을 작은 조각으로 나누어 전체 작업을 더 빠르게 완료할 수 있습니다. 대조적으로 Grover의 알고리즘은 각 검색이 한 번에 하나씩 수행되는 장기 실행 직렬 계산이 필요합니다.
Valsorda는 인터뷰에서 “Grover를 특별하게 만드는 것은 병렬화할수록 비양자 알고리즘에 비해 이점이 작아진다는 것입니다.”라고 말했습니다. 그는 계속해서 이렇게 말했습니다.
작은 숫자로 상상해 보십시오. 하나의 자물쇠에 256개의 가능한 조합이 있다고 가정해 보겠습니다. 일반적인 공격에는 256번의 시도가 필요합니다. 시간이 너무 길다고 판단하여 세 명의 친구를 사귀고 각각 64번의 시도를 합니다. “이것이 고전적인 병렬화입니다. Grover를 사용하면 이론적으로 √256)=16회 연속 시도를 수행할 수 있지만 여전히 너무 길어서 다시 세 명의 친구에게 도움을 구해야 합니다. 각자는 √256/4)=8회 시도를 해야 합니다.
따라서 총 8*4=32번의 시도를 하게 되는데, 이는 혼자서 했을 16번보다 더 많은 것입니다! 공격을 병렬화하기 위해 도움을 요청하면 공격이 전반적으로 느려졌습니다. 고전적인 공격에는 해당되지 않습니다.
물론 숫자는 훨씬 더 크지만 공격자에게 합리적인 제약(예: 10년 안에 실행을 완료해야 하는 등)을 적용하면 전체 작업은 2보다 훨씬 더 많아집니다.64.
또한 264 이는 단일 큐비트에서 단일 작업으로 AES를 수행할 수 있는 것처럼 가장하기 때문에 결코 올바른 숫자가 아닙니다. 이것은 다소 직교합니다. 이 두 가지 관찰의 조합은 실제 비용을 2로 바꿉니다.104 주고받는 것은 보안의 한계를 훨씬 뛰어넘는 수준입니다.
Google의 수석 암호화 엔지니어인 Sophie Schmieg는 다음과 같이 설명했습니다.
