GlueLUT: Efficient Lookup Table Arguments over Residue Rings

출처:IACR ePrint (암호학)

AI 인사이트

개발자

1.룩업테이블 증명(LUT PIOP)을 합성수 잊여환 Z_Q에 그대로 적용하면 'CRT 정렬 모호성'으로 안전하지 않음을 규명
2.보조 체에서 룩업을 수행하면서 Z_Q 위 산술 증명을 유지하고 둘 사이 일관성을 증명하는 GlueLUT 기법군 제안
3.GlueLUT-4Sq는 라그랑주 네 제곱수 분해와 GKR 스타일 검사로 O(n+m) 증명자 연산을 달성
4.GlueLUT-Fold는 랜크원 폴딩 일관성 검사로 더 나은 실제 효율을 내며 프로토타입 구현으로 이론을 검증

왜 중요한가?

룩업테이블 기반 SNARK는 zkEVM 등에서 산술화를 간결하게 만드는 핵심 기법인데, 간과돼 온 합성수 환에서의 보안 허점을 지적하고 수정 구성을 제시해 해당 환경을 쓰는 영지식증명 시스템의 안전성 재검토가 필요함을 보여준다.

언급 프로젝트

GlueLUT

본문 미리보기

Lookup table polynomial interactive oracle proofs (LUT PIOPs) make SNARK arithmetizations concise, yet almost all efficient constructions assume field arithmetic. We show that directly instantiating them over a composite residue ring \(\mathbb Z_Q\) can be unsound: component-wise set checks preserve the residue multiset in each CRT component but lose the alignment across components. We formalize this obstruction, which we call the CRT alignment ambiguity. To overcome this ambiguity, we presen

전체 내용이 궁금하다면?

원문을 직접 읽어보세요

원문 보기