By 제이 리우 18년 2022월 XNUMX일 게시됨
양자 컴퓨터는 적어도 15년 동안 우리의 보안 시스템에 심각한 피해를 입힐 수 없을 것이라고 널리 알려져 있습니다. 이는 본격적인 내결함성 양자 컴퓨터가 출시되고 Shor의 알고리즘을 실행하여 합리적인 시간 내에 RSA를 크랙할 수 있을 것으로 예상되는 때입니다. 글쎄요, 현실은 훨씬 더 어둡습니다. 실제 양자 보안 위협은 훨씬 더 즉각적이며, 대부분 XNUMX년 이내에 발생할 가능성이 높습니다.
“정말요?”라고 물을 수도 있습니다. 어떻게요?”
이러한 단기 보안 위협은 이미 우리가 살고 있는 NISQ 시대의 오류가 발생하기 쉬운 양자 장치에서 실행되는 경험적 알고리즘에서 비롯될 것입니다.
Shor의 알고리즘을 사용하여 2048비트 RSA 번호를 인수분해하려면 100,000일 동안 실행되는 10개의 내결함성 큐비트 또는 20시간 동안 8천만 NISQ 큐비트가 필요합니다. 적어도 XNUMX년 동안은 이런 대규모 양자컴퓨터가 나오지 않기 때문에 준비할 시간이 많다고 느낄 수도 있다.
하지만 오늘날의 NISQ 장치를 사용하여 Zapata Computing에서는 다음과 같은 휴리스틱 알고리즘을 생각해 냈습니다. 변이 양자 인수분해 (VQF, 특허)를 사용하면 2048시간 내에 약 6,000개의 NISQ 큐비트로 XNUMX비트 RSA 수치를 인수분해할 수 있을 것으로 추정됩니다. 주요 양자 컴퓨터 회사가 발표한 제품 로드맵을 기반으로 이 규모의 NISQ 양자 컴퓨터는 XNUMX년 이내에 출시될 것으로 예상됩니다.
생각해 보세요. 양자 보안 위협은 대부분이 인식하는 것보다 훨씬 더 즉각적입니다.
글쎄, 당신은 "휴리스틱 알고리즘이 무엇이며 왜 이 경우 RSA 수치를 깨뜨릴 때 Shor의 알고리즘보다 훨씬 더 강력합니까?"라고 궁금할 것입니다.
컴퓨팅 복잡성의 선구자이자 튜링상 수상자인 스티븐 쿡(Stephen Cook)은 이를 다음과 같이 잘 정의합니다.
"A 휴리스틱 알고리즘 속도를 위해 최적성, 정확성, 정밀도 또는 완전성을 희생하여 기존 방법보다 더 빠르고 효율적인 방식으로 문제를 해결하도록 설계된 방법입니다.”
즉, 휴리스틱 알고리즘은 수학적으로 완전하지도 않고 이론적으로 입증되지도 않지만 실제로는 작동합니다. 휴리스틱 알고리즘의 잘 알려진 예로는 신경망이 있는데, 이는 작동해야 한다는 수학적 증거가 없음에도 불구하고 얼굴 인식과 같은 응용 분야에서 매우 효과적인 것으로 입증되었습니다. 더욱이, 더 나은 컨볼루션 신경망이 설계됨에 따라 더욱 정확하고 강력해지고 있습니다.
VQF 알고리즘은 또 다른 예입니다. Shor의 알고리즘과 달리 양자 컴퓨터와 고전 컴퓨터를 모두 사용하는 하이브리드 알고리즘입니다. 구체적으로, 인수분해 문제를 조합 최적화 문제로 매핑하고, 전처리를 위해 기존 컴퓨터를 사용하며, 잘 알려진 QAOA(양자 근사 최적화 알고리즘)를 사용합니다. 이 접근 방식은 많은 수를 인수분해하는 데 필요한 큐비트 수를 크게 줄였습니다.
NISQ 위협은 PQC 위협보다 훨씬 더 임박한 위협입니다.
학계, 표준 기관 및 보안 회사 전반에 걸친 대부분의 노력은 XNUMX년 이상 후에 PQC(포스트 양자 암호화) 시대의 보안 위협을 완화하는 데 초점을 맞추고 있지만 Shor의 알고리즘은 본격적인 내결함성 양자에서 실행될 것으로 예상됩니다. VQF 알고리즘은 이미 우리가 살고 있는 NISQ 시대에 양자 컴퓨터에서 실행되는 휴리스틱 알고리즘의 단기 보안 위협 가능성을 노출시켰습니다.
우리는 이 문제를 면밀히 살펴보고 대기업, 정부 및 조직과 이야기를 나눴습니다. 이것이 그들이 가장 우려하는 일종의 양자 사이버보안 위협이다.
우리의 양자 과학자들로 구성된 심층 연구단과 Orquestra® 소프트웨어 플랫폼 양자 컴퓨터에서 실행되는 우리는 연구, 평가, 테스트, 등급 및 검증을 포함하여 NISQ 시대 이후의 보안 위협에 더 잘 대비할 수 있도록 돕는 일련의 도구와 서비스를 개발했습니다.
오늘 시작해 보겠습니다.
Jay Liu, Zapata Computing 제품 담당 부사장
