이진 확장체 위의 단변수 다항식 대화형 오라클 증명(IOP)에 기반한 포스트퀀텀 zkSNARK에서, 큰 도메인 평가와 소멸 다항식 나눗셈이 프루버 비용의 대부분을 차지하는 문제를 다룬 연구다. Gao-Mateer, LCH 같은 범용 기저 가법적 FFT는 평가는 가속하지만, 실무에서 지배적인 O(n(log n)²) 덧셈과 O(n log n) 곱셈이 드는 기저 변환 단계를 요구한다. 이 논문은 LCH 다항식 기저에서 직접 작동하는 분할정복 알고리즘을 도입해 기저 변환을 완전히 제거하고 최적 O(n log n) 복잡도를 달성했으며, 소멸 다항식과 무작위 블라인딩 다항식의 곱셈이 무작위 원소 추가로 환원돼 곱셈 자체가 사라진다. Aurora IOP 기반 NIST PQC 1라운드 후보 서명 스킴 Preon에 적용한 벤치마크에서 Preon-128A는 5.0배, Preon-256C는 5.8배의 전체 서명 속도 향상을 얻었고, 다항식 변환 단계만 보면 12.6~17.9배 빨라졌다.
- •LCH 다항식 기저에서 직접 동작하는 분할정복 나눗셈 알고리즘으로 기저 변환 단계 완전 제거
- •임의의 F2-기저 원소에 대해 최적 O(n log n) 복잡도 달성
- •LCH 기저에서는 소멸 다항식×블라인딩 다항식 곱셈이 무작위 원소 추가로 환원되어 곱셈 연산 자체 제거
- •Aurora IOP 전 단계에 네이티브 LCH 기저 산술과 보조 최적화 통합
- •Preon 서명 스킴에서 전체 서명 속도 5.0~5.8배, 다항식 변환만은 12.6~17.9배 향상
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
Faster Post-Quantum zkSNARK Provers Using the LCH Polynomial Basis
- 1.LCH 다항식 기저에서 직접 동작하는 분할정복 알고리즘으로 기저 변환 단계를 제거, O(n log n) 최적 복잡도 달성
- 2.NIST PQC 후보 서명 스킴 Preon(Aurora 기반)에서 서명 속도 최대 5.0~5.8배 향상
- 3.다항식 변환 단계만 보면 12.6~17.9배 가속, 랜덤 블라인딩 다항식 곱셈은 필드원소 추가로 대체해 제거
왜 중요한가?
이진 확장체 기반 포스트퀀텀 zkSNARK의 고질적 병목이던 기저 변환 오버헤드를 제거함으로써, NIST 표준화 후보 서명 스킴의 실제 서명 속도를 유의미하게 끌어올린 실용적 최적화다.
본 연구는 이진 확장 필드 기반의 차세대 양자 내성 zkSNARK 프로버 속도를 LCH 다항식 기저를 활용하여 획기적으로 향상시키는 방법을 제시합니다. 이는 양자 컴퓨터의 위협에 대비해 국내 핵심 디지털 인프라와 블록체인 시스템의 보안을 강화하려는 노력이 활발한 시점에서, 양자 내성 영지식 증명 기술의 실용화에 결정적인 기여를 할 것입니다. 한국 정부와 연구기관들이 양자 내성 암호 표준화 및 도입을 추진하는 가운데, 더 빠른 검증 과정은 프라이버시와 확장성을 동시에 잡는 미래형 블록체인 기술 도입을 가속화하는 중요한 토대가 될 것입니다.
본문 미리보기
Univariate-polynomial interactive oracle proofs (IOPs) over binary extension fields $\mathbb{F}_{2^m}$ underpin a class of plausibly post-quantum zkSNARKs, but rely heavily on polynomial arithmetic, where large-domain evaluation and division by subspace vanishing polynomials are the dominant prover costs. General-basis additive FFTs, such as Gao--Mateer and Lin-Chung-Han (LCH), accelerate the evaluation but impose a basis-conversion stage costing $O(n (\log n)^2)$ field additions and $O(n \log n
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:24AI 초안
