이 논문은 이진 확장체 위에서 매우 효율적인 의사난수 상관 생성기(PCG)를 구축했다. PCG는 각 참여자가 짧은 시드를 로컬에서 확장해 대량의 상관 무작위성을 분배함으로써 조용하고 준선형적인 전처리로 효율적인 다자간계산(MPC)을 가능케 한다. 제안 방식은 F_2^128 위에서 N개의 VOLE를 O(N) PRG 호출·곱셈과 O(kN log N) XOR로 확장해 초당 약 500만 VOLE의 처리량을 달성했으며, 이는 최신 Expand-Accumulate·Block-Accumulate·Expand-Convolute 코드 기반 PCG보다 각각 4.7배, 1.9배, 1.6배 빠르다. 핵심 기여는 다변수 고속푸리에변환(FFT) 알고리즘으로, 일반 FFT가 O(N log N)번의 체 곱셈을 필요로 하는 것과 달리 개별 차수 2 이하의 n변수 다항식을 훨씬 적은 연산으로 평가하며, 이 접근은 갈루아 환으로도 일반화된다. 부가적으로 유사아벨 코드에 대한 빠른 부호화 알고리즘도 도출해 RAA 코드보다 1.66배 빠르면서 CRYPTO 2026 연구에서 입증된 큰 최소거리를 활용해 확장체 위의 더 효율적인 간결 논증 구축의 길을 열었다.
- •F_2^128에서 초당 약 500만 VOLE 처리량으로 기존 최고 PCG 대비 최대 4.7배 가속
- •확장체 위 OLE의 최초 완전 구현을 libOTe 기반으로 제공, 초당 4만2천 OLE
- •기존 FFT보다 훨씬 적은 곱셈으로 다변수 다항식을 평가하는 알고리즘 개발, 갈뤘아 환으로 일반화
- •유사아벨 코드 부호화 알고리즘이 RAA 코드보다 1.66배 빠름
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
Efficient Pseudorandom Correlation Generators over Binary Extension Fields and More
- 1.이진 확장체 위에서 동작하는 의사난수 상관생성기(PCG)를 새로 설계, 초당 약 500만 VOLE 처리 달성
- 2.기존 최고 성능인 Expand-Accumulate·Block-Accumulate·Expand-Convolute 대비 최대 4.7배 빠름
- 3.libOTe 기반 확장체 위 OLE용 PCG를 세계 최초로 완전 구현, 초당 약 4만2천 OLE 처리
- 4.핵심은 새로운 다변수 FFT 알고리즘으로, 기존 FFT보다 곱셈 연산 수를 크게 줄임
왜 중요한가?
다자간 연산(MPC)의 전처리 단계 병목이던 상관 난수 생성을 대폭 가속함으로써, 실전 MPC 프로토콜의 실행 속도를 끌어올릴 수 있는 실질적 기반 기술이다.
언급 프로젝트
본문 미리보기
In this work, we construct highly efficient pseudorandom correlation generators (PCGs) over binary extension fields. PCGs allow for the distribution of a great amount of correlated randomness by having each party locally expand a short seed, enabling efficient multi-party computation (MPC) protocols with silent and sublinear preprocessing. Our PCGs achieve nearly linear time, both asymptotically and concretely, where expanding $N$ VOLEs (vector oblivious linear evaluations) over $\mathbb{F}_{2^k
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:24AI 초안
