코드 기반 다항식 커밋먼트 스킴의 근본적 병목이던 '최적 근접 간격' 문제를 해결하는 첫 폴딩 스킴이 제시됐다. 연구진은 폴디드 리드-솔로몬(FRS) 코드와 단변량 다중도(UM) 코드에 대해 근접성 증명 IOPP를 구성해, 최근 Goyal과 Guruswami(STOC 2026)가 제시한 최적 근접 간격 1-R-ε을 달성했다. 핵심 관찰은 짝/홀 폴딩이 적절히 짝지어진 모듈러스에 대해 다항식 축소와 교환 가능하다는 점으로, 중국인의 나머지 정리 기반 일관성 검사가 가능한 새로운 일반 폴딩 프레임워크를 얻었다. 이 IOPP는 O(N) 증명 시간, O(λlogN) 질의 복잡도로 FRI와 같은 점근적 복잡도를 유지하면서도 더 작은 기반 필드를 허용해, 100비트 보안에 128비트 필드로 충분함을 보였다.
- •코드 기반 PCS의 병목이던 최적 근접 간격 문제를 해결하는 첫 폴딩 스키임 제시
- •FRS 코드와 UM 코드 모두에 최적 근접 간격 1-R-ε을 달성하는 IOPP 구성
- •짝/홍 폴딩과 다항식 축소의 교환 가능성을 이용한 새 일반 폴딩 프레임워크 제안
- •O(N) 증명 시간·O(λlogN) 질의 복잡도로 FRI와 동등한 점근적 성능 유지
- •더 작은 기반 필드로도 동일 보안 수준 달성, 100비트 보안에 128비트 필드로 충분
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
How to Fold Linear Error-Correcting Codes with Optimal Proximity Gaps
- 1.코드 기반 폴딩에서 RS·foldable 코드 모두 미달이던 '최적 근접 간격'을 최초 달성
- 2.짝/홀 폴딩과 다항식 축소가 짝지은 모듈러스에서 교환됨을 이용, CRT로 일관성 검증
- 3.FRI 수준 효율 유지하며 더 작은 체 사용 가능, 100비트 보안에 128비트 체로 충분
왜 중요한가?
증명 크기의 근본 병목이던 근접 간격 손실을 없애면서도 FRI 수준의 효율을 유지해, zk-SNARK 등 다항식 커밋먼트 기반 증명 시스템의 증명 크기·필드 크기를 함께 줄일 수 있는 실용적 개선이다.
본문 미리보기
Folding is a core technique in building efficient code-based polynomial commitment schemes with polylogarithmic proof size and verification. To date, there are two families of linear error-correcting codes that have been known to allow folding, i.e., Reed-Solomon (RS) codes and foldable codes. However, neither admits optimal proximity gaps, which constitutes a fundamental bottleneck in the resulting proof sizes. In this work, we give the first folding scheme that enjoys optimal proximity gaps
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:24AI 초안
