연구진이 상관 생성과 증명 시스템에 쓰이는 이진 코드의 새로운 구성인 SPIN(Single-Permutation INterleaved) 코드를 제안했다. 블록 단위 외부 인코더, 하나의 전역 인터리버, 재귀적 내부 구조를 결합해 비율 1/2에서 순서·전치 인코딩 모두 O(N) 비트 연산으로 처리하면서, 무작위로 선택한 코드가 0.11N 이상의 최소 거리를 가질 확률이 1-o(1)에 달함을 증명하고 이를 Lean으로 형식 검증했다. 유사 난수 상관 생성기(PCG) 적용 시 전치 인코더가 Ryzen 9 7950X 한 코어에서 2^20개의 128비트 상관 블록을 약 9.3ms에 처리해, 기존 Kolesnikov 등의 비율 1/2 BAA 코드보다 약 3.4배 빠르다. 다항식 커밋먼트 스킴에 적용한 SPIN-Brakedown 조합은 512MiB 커밋과 하나의 오프닝을 509ms에 처리하며, 기존 Ligerito 대비 증명자 처리량을 1.63~2.29배 높였다(단, 증명 크기는 커지고 검증은 느려짐).
- •블록 외부 인코더·전역 인터리버·재귀 내부구조를 결합한 SPIN 코드로 비율 1/2에서 O(N) 연산 달성
- •무작위 코드의 최소 거리가 0.11N을 넘을 확률 1-o(1)을 증명, Lean으로 형식 검증
- •PCG 적용 시 기존 BAA 코드(CRYPTO 2026)보다 약 3.4배 빠른 전치 인코딩 속도
- •Silent OT 센더가 2^18 배치에서 초당 8900만 해시드 OT 처리
- •Brakedown 다항식 커밋먼트에 적용 시 Ligerito 대비 증명자 처리량 1.63~2.29배 향상, 증명 크기·검증 속도는 희생
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
SPIN: Fast Codes for Correlation Generation and Polynomial Commitments
- 1.외부 인코더·전역 인터리버·재귀 내부를 결합한 SPIN 코드 제안
- 2.비율1/2 SPIN이 O(N) 연산으로 최소거리 0.11N 초과 달성, Lean으로 형식검증
- 3.라이젠 9 7950X서 2^20개 상관블록 9.3ms 생성, 기존 BAA 대비 3.4배 빠름
- 4.Flock 구현서 Ligerito 대비 증명자 처리량 1.63~2.29배 개선
왜 중요한가?
PCG·Silent OT·다항식 커밋먼트 등 MPC·증명시스템 핵심 연산을 실측 기준으로 끌어올려 Flock 같은 실제 프레임워크에 바로 적용된다.
SPIN(Single-Permutation INterleaved) 코드는 증명 시스템과 다항식 커밋먼트에서 요구되는 빠른 인코딩 속도와 강력한 거리를 제공합니다. 이는 영지식 증명(ZKP) 기반의 프라이버시 보호 및 확장성 솔루션의 성능을 획기적으로 향상시켜 한국 블록체인 생태계의 기술 발전에 크게 기여할 수 있습니다.
본문 미리보기
Binary codes used in correlation generation and proof systems need strong distance, fast ordinary and transposed encoding, and regular memory access. We introduce Single-Permutation INterleaved (SPIN) codes, combining a blockwise outer encoder, one global interleaver, and a recursive inner. Our main result is a Structured SPIN family with rate $1/2$ and $O(N)$ bit operations for ordinary and transposed encoding at its native output lengths $N$. With probability $1-o(1)$ over the random choice
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:24AI 초안
