연구진이 딜러가 있는 부정직 다수 다자간 계산(MPC)에서 환(ring) Z_2^k 위 계산에 특화된 최초의 서브리니어 검증 프로토콜을 제안했다. 기존 방식은 각 참여자를 개별적으로 검증하기 위해 n개의 분산 영지식(DZK) 증명을 사용했지만, 이번 연구는 모든 참여자의 정당한 행동을 단일한 새로운 DZK 증명으로 한 번에 검증해 통신 복잡도를 O(n·log m)에서 O(n+log m)으로 줄였다. 이로써 참여자 수 n이 늘어나도 능동 안전성이 잘 확장되는 것을 처음으로 보였다. 실험에서 백만 번의 곱셈, 30개 레이어 연산 시 통신 오버헤드는 수동 안전 프로토콜 대비 0.7%에 불과했고, WAN 환경에서는 34%의 실행시간 오버헤드로 능동 안전성을 달성했다. 기존 방식 대비 통신은 1.8배, 실행시간은 WAN에서 2.5배, LAN에서 11.9배 개선됐다.
- •부정직 다수·딜러 환경의 환(Z_2^k) 계산에 특화된 최초의 서브리니어 검증 프로토콜이다
- •개별 참여자별 DZK 증명 대신 전체를 검증하는 단일 증명으로 통신량을 O(n+log m)으로 축소했다
- •100만 곱셈·30 레이어 연산에서 통신 오버헤드가 수동 안전 대비 0.7%에 그쳤다
- •WAN 환경에서 34% 실행시간 오버헤드만으로 능동 안전성을 확보했다
- •기존 최고 방식 대비 통신 1.8배, LAN 실행시간 11.9배 개선됐다
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
One Proof to Rule Them All: Practical, Sublinear Verification for Actively Secure MPC on $\mathbb{Z}_{2^k}$ with Dishonest Majority and a Dealer (Full Version)
- 1.n자 참여자·부정직 다수·딜러 환경, 링 Z_2^k 위에서 동작하는 최초의 sublinear 검증 DZK 프로토콜 제안
- 2.개별 검증 대신 단일 통합 증명으로 통신복잡도를 O(n·log m)에서 O(n+log m)로 절감
- 3.100만 곱셈·30계층 기준 수동 안전 프로토콜 대비 통신 오버헤드 단 0.7%
- 4.Asterisk(IEEE S&P'24) 대비 통신 1.8배, WAN 실행시간 2.5배, LAN 11.9배 개선
왜 중요한가?
액티브 시큐어 MPC가 참여자 수 증가에도 효율적으로 확장되는 최초 사례로, WAN 환경 실행시간 오버헤드를 34%까지 낮춰 실제 다자간 프라이버시 컴퓨팅 서비스에 적용될 가능성을 높인다.
언급 프로젝트
본문 미리보기
Towards bridging the gap between passively and actively secure multiparty computation (MPC), the use of sublinear distributed zero-knowledge (DZK) proofs gained popularity. Such proofs enable extending a passively secure protocol by adding a verification step whose communication is sublinear in the circuit size. For arbitrarily many parties and a dishonest majority, adding a trusted dealer enables efficient computation, as recently shown by Asterisk (IEEE S&P'24) without requiring DZK. This sett
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:24AI 초안
