이 논문은 모든 다항식 T, b에 대해 길이가 O~(T(n)+b(n)^2)인 O(1)-쿼리 확률적으로 검사 가능한 증명(PCP)을 NTIME(T)에 대해 구성할 수 있으며, 이 PCP가 b(n)-쿼리 완전 영지식(perfect zero knowledge)을 만족함을 보인다. 이는 Gur, O'Connor, Spooner(STOC 2024, STOC 2025)가 제시한 다항식 길이의 영지식 PCP보다 엄격하게 개선된 결과다. 저자들은 Ben-Sasson과 Sudan(SICOMP 2008), Dinur(JACM 2007)의 PCP 구성을 기반으로 하며, '국소적으로 시뮬레이션 가능한 시프 코드(locally simulatable sheaf codes)'라는 새로운 기법을 통해 영지식 성질을 증명한다.
- •O(1)-쿼리 PCP를 길이 O~(T(n)+b(n)^2)로 구성, NTIME(T)에 대해 b(n)-쿼리 완전 영지식 달성
- •기존 Gur·O'Connor·Spooner(STOC 2024/2025)의 다항식 길이 영지식 PCP보다 개선된 준선형(quasilinear) 크기
- •Ben-Sasson·Sudan(2008), Dinur(2007)의 PCP 구성을 기반으로 확장
- •'국소적으로 시뮬레이션 가능한 시프 코드'라는 새로운 기법으로 영지식 성질 증명
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
Zero-Knowledge PCPs of Quasilinear Size via Locally Simulatable Sheaf Codes
- 1.모든 다항식 T,b에 대해 길이 Õ(T(n)+b(n)²)인 O(1)-질의 완전영지식 PCP 구성법 제시
- 2.Gur·O'Connor·Spooner(STOC 2024/2025)의 다항식 길이 영지식 PCP를 준선형 길이로 개선
- 3.Ben-Sasson–Sudan(2008), Dinur(2007)의 PCP 구성을 기반으로 확장
- 4.'국소적으로 시뮬레이션 가능한 시프 코드'라는 새 도구로 영지식 성질을 증명
왜 중요한가?
PCP 길이를 다항식에서 준선형으로 줄이면서도 완전 영지식을 유지해, 검증 효율이 중요한 확장성 있는 증명 시스템 이론의 한계를 한 단계 끌어올린다.
이 기술 문서는 영지식 증명(ZKP)의 효율성을 획기적으로 개선하는 이론적 진전을 다룹니다. 이는 블록체인 기술의 핵심인 개인정보 보호와 확장성을 강화하는 데 필수적인 기반 연구로, 국내 블록체인 산업의 장기적인 발전 방향에도 중요한 시사점을 제공합니다.
본문 미리보기
We show that for every polynomial $T,b \colon \mathbb{N} \to \mathbb{N}$, there exist an $O(1)$-query probabilistically checkable proof (PCP) for $\operatorname{NTIME}(T)$ of length $\widetilde{O}\bigl(T(n)+b(n)^2\bigr)$, which is $b(n)$-query perfect zero knowledge. This strictly improves on the polynomial-length zero-knowledge PCPs of Gur, O'Connor, and Spooner (STOC 2024; STOC 2025). Our construction builds on the PCPs of Ben-Sasson and Sudan (SICOMP 2008) and Dinur (JACM 2007). We prove the
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:24AI 초안
