연구진이 Fiat-Shamir(FS) 변환이 프로그램으로 생성되는 증명 시스템에서 새로운 방식으로 무너질 수 있음을 보였다. 계산이 프로그램에 의해 R1CS 같은 관계로 자동 변환되는 현대적 증명 시스템 설계 방식에서, 변환 과정이 충분히 표현력이 높으면 프로그램 코드를 조작하는 공격자가 비대화형 증명 시스템의 완전성을 깨뜨릴 수 있음을 밝혔다. 이 공격은 부정직한 증명자가 진술이 확정되기 전에 수락 가능한 트랜스크립트를 미리 준비할 수 있는 광범위한 프로토콜 부류로 일반화되며, Spartan과 Aurora의 변형도 이에 해당한다. 대응책으로 최초의 FS 챌린지를 프로그램이 아닌 생성된 진술 자체에서 도출하도록 하면 안전성이 원래 프로토콜 수준으로 회복됨을 증명했다. 실제 배포된 증명 시스템 컴파일러 설계에 직접적인 함의를 갖는 결과다.
- •프로그램이 자동으로 R1CS 등 관계로 변환되는 증명 시스템에서 FS 변환의 새로운 공격 부류를 제시했다
- •부정직한 증명자가 진술 확정 전 수락 트랜스크립트를 준비할 수 있는 프로토콜 전반에 적용된다
- •Spartan(CRYPTO 2020), Aurora(EUROCRYPT 2019) 변형도 공격 대상이 될 수 있음을 보였다
- •첫 FS 챌린지를 생성된 진술에서 도출하는 완화책을 제시하고 안전성을 증명했다
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
How to prove more false statements: Fiat–Shamir limitations on (generated) R1CS
- 1.프로그램이 생성하는 증명 인스턴스(R1CS 등)에서 Fiat-Shamir 변환의 안전성이 깨질 수 있음을 증명
- 2.적대적 프로그램 코드가 변환 과정이 충분히 표현력 있을 때 비대화형 증명의 완전성을 무력화
- 3.Spartan(CRYPTO 2020), Aurora(EUROCRYPT 2019) 등 실제 R1CS 증명 시스템이 이 공격 범주에 포함됨을 규명
- 4.첫 Fiat-Shamir 챌린지를 생성된 statement에서 유도하는 완화책 제시 및 안전성 환원 증명
왜 중요한가?
zk-SNARK 등 실전 배포된 R1CS 기반 증명 시스템(Spartan, Aurora 계열)의 표준 컴파일 방식에서 구체적 공격 벡터를 지적한 것으로, 영지식증명 라이브러리 구현자들이 챌린지 생성 방식을 재점검해야 할 근거를 제공한다.
본문 미리보기
The Fiat--Shamir (FS) transformation is a technique that converts interactive protocols into non-interactive ones. FS is secure in idealized models such as the random oracle model (ROM) (if the interactive protocol satisfies a condition known as state-restoration soundness). It is known that there are protocols whose FS transformation is secure in the ROM, yet insecure when instantiated with any concrete hash function. Historically, these protocols were contrived (as in, they were designed s
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:24AI 초안
