우리는 구글의 양자 암호해독에 대한 제로 지식 증명의 기록을 깨뜨렸다
구글의 양자 AI 그룹은 제 1세대 양자 컴퓨터가 제로 지식 증명을 사용하여 9분 안에 타원 곡선 암호를 깨뜨릴 수 있다고 주장했다. Trail of Bits는 구글의 러스트 프로버 코드의 취약성을 악용하여 구글의 지표를 크게 개선한 가짜 제로 지식 증명을 만들었다. 이러한 취약성에는 메모리 안전성 문제와 논리적 결함이 포함되어 있었으며, 구글은 이후 이를 패치했다. Trail of Bits의 증명은 총 연산을 830만 개로, 큐비트를 1,164개로 줄였으며, 토플리 게이트를 제거했다. 가짜 증명은 여전히 구글의 패치되지 않은 검증을 통과했으며, 정당한 증명과 구별할 수 없었다. 구글의 증명은 양자 회로의 비용을 계산하기 위해 제로 지식 가상 머신(zkVM)을 사용했다. zkVM 시뮬레이션에는 개인 입력(예: 양자 회로)과 함께 프로그램이 특정 공개 출력(리소스 제한 포함)을 생성하는 것을 증명하는 것이 포함된다. 주요 취약성 중 하나는 회로의 어셈블리 스크립트에서 연산 유형을 조작하여 토플리 게이트 카운터를 우회하는 것이었다. 이러한 조작으로 프로그램은 연산을 수행할 수 있었지만, 그 비용을 올바르게 보고하지 않았기 때문에, 효과적으로 증명을 위조할 수 있었다. 이 사건은 제로 지식 증명 시스템에 의해 도입된 고유한 공격 표면을 보여준다.
