0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
Reed-Solomon Codes Beyond Johnson: Efficient Decoding and Smaller Cryptographic Proofs (원문, 새 창)
한국어 요약
Claude · 2026-11-04리드-솔로몬 코드의 리스트 디코딩은 코딩 이론의 핵심 문제이며 상호 연관 합의(MCA)와 함께 여러 축약 암호 증명의 건전성을 뒷받침한다. 연구진은 리드-솔로몬 리스트 디코딩과 MCA에 대해 용량까지 정밀한 정량적 경계를 제시하고, 암호학적으로 큰 체에서도 효율적인 결정적 디코딩 알고리즘을 제공하며, 이 경계를 실제 구현된 증명 시스템의 증명 크기 축소에 특화시켰다. 숨은 도함수 기법을 정교화해 존슨 경계보다 엄격히 낮은 명시적 합의 임계값을 얻었고, 고정 전송률에서 기존 MCA 오차 경계를 개선했다. 이 1차 도함수 경계를 적용해 ProveKit 패스포트 증명에서 79.4KB(11.1%), ZisK 압축 최종 증명에서 13.2KB(4.63%), LambdaVM CPU 서브증명에서 59.8KB(4.85%)의 증명 크기 절감을 달성했으며, 모든 결과는 Lean 라이브러리 ArkLib로 형식 검증됐다.
- 리드-솔로몬 리스트 디코딩과 MCA에 대해 용량까지 정밀한 정량적 경계와 결정적 디코딩 알고리즘 제시
- 숨은 도함수 기법을 정교화해 존슨 경계보다 엄격히 낮은 명시적 합의 임계값 도출
- ProveKit·ZisK·LambdaVM 등 실제 증명 시스템에서 최대 11.1% 증명 크기 절감 달성
- 모든 결과를 Lean 라이브러리 ArkLib로 형식 검증
AI 인사이트
- Johnson bound 아래 명시적 합치 임계값 도출, RS 디코딩·MCA 오차를 전 rate에서 정량화
- 기존 BCHKS MCA 오차 경계를 O(n/qη0^5)→O(n/qη0^3)로 개선, Lean으로 정식 검증
- 결정적 디코더로 Johnson 이상에서 다항시간 디코딩 구현, 큰 체에서도 효율적 동작
- 실배포 파라미터 기준 ProveKit 79.4KB, ZisK 13.2KB, LambdaVM 59.8KB 증명 크기 절감
왜 중요한가
이론적 경계 개선이 실제 증명 시스템의 증명 크기를 동일한 보안 수준에서 바로 줄여준다는 점에서, succinct proof의 실무 비용을 낮추는 직접적이고 정식 검증된 성과다.
AIChainDay 편집노트
왜 이 기사를 골랐나리드-솔로몬 코드의 디코딩 효율성 증진은 암호화 증명의 크기를 줄여 블록체인 트랜잭션 수수료 절감과 처리 속도 향상에 기여합니다. 이는 국내 블록체인 서비스의 사용자 경험 개선과 경제성 확보에 직접적인 영향을 미칠 수 있어 주목할 필요가 있습니다.
본문 미리보기
List decoding Reed–Solomon codes is a central problem in coding theory and, together with mutual correlated agreement (MCA), underpins the soundness of many succinct cryptographic proofs. In this work, we give precise quantitative bounds on Reed–Solomon list decoding and MCA up to capacity, provide deterministic decoding algorithms that remain efficient over cryptographically large fields, and specialize our bounds to reduce proof sizes in implemented proof systems. Our bounds apply to arbitrary
전체 내용이 궁금하다면?
IACR ePrint (암호학)에서 원문을 직접 읽어보세요
- #Reed-Solomon
- #영지식증명
- #리스트디코딩
이 글이 만들어진 과정
- 11:34AI 초안
관련 글
4건- Gate boasts 104% cold reserve coverage, but separate snapshot dates raise red flags
- Asian crypto exchanges batten down the hatches as hacks surge: Asia Express
- Solana developers propose major overhaul to address hidden risk that could disrupt its network
- Bitcoin traders face Friday’s $2.7 billion options expiry with a dangerous five-hour blind spot