TFHE 같은 비트단위 FHE 스킴에서 블라인드 회전이 부트스트래핑의 주된 병목이며, 기존 구현은 차원 n의 LWE 비밀에 대해 O(n)개의 순차적 외부곱을 평가해 지연시간과 NTT/iNTT 연산이 많다는 문제를 다룬 연구다. Jain 등(CRYPTO 2026)에서 착안해 Cuckoo 해싱으로 해밍 가중치 h인 이진 LWE 비밀을 원-핫 표현의 확장 버킷으로 변환, 블라인드 회전의 순차 외부곱을 O(n)에서 O(h)로 줄이는 NTRU 기반 부트스트래핑 프레임워크를 제안했다. 온라인 NTT/iNTT 연산을 모두 제거한 NTT-프리 변형도 함께 제시한다. AVX-512 CPU 단일 스레드에서 불리언·4비트·6비트 부트스트래핑을 각각 0.83ms, 1.75ms, 2.65ms에 수행해 TFHE-rs 대비 3.31~20.47배 빨랐고, RTX 4090 GPU에서는 초당 154,739회의 게이트 부트스트래핑을 달성해 VeloFHE 대비 13.6배 빨랐다.
- •Cuckoo 해싱으로 희소 이진 LWE 비밀을 원-핫 버켓 표현으로 변환해 블라인드 회전 순차 복잡도를 O(n)에서 O(h)로 감소
- •온라인 NTT/iNTT 연산을 전혀 쓰지 않는 NTT-프리 변형 제시
- •AVX-512 CPU에서 불리언/4비트/6비트 부트스트래핑을 TFHE-rs 대비 3.31~20.47배 가속
- •RTX 4090 GPU에서 초당 154,739회 게이트 부트스트래핑, VeloFHE 대비 13.6배 가속
- •최초의 NTRU 기반 8비트 FHE 명령어 집합 구현, 기존 대비 10배 이상 속도·100배 이상 작은 키 크기
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
Compiling Sparse Keys for Bootstrapping FHEs: Algorithms, Hardware Acceleration, and Beyond
- 1.Cuckoo 해싱으로 희소 이진 LWE 비밀을 원-핫 버킷화, 블라인드 회전 순차연산을 O(n)에서 O(h)로 축소
- 2.AVX-512 단일 CPU에서 Boolean/4비트/6비트 부트스트래핑 0.83/1.75/2.65ms, TFHE-rs 대비 최대 20.47배
- 3.RTX 4090 GPU에서 초당 154,739 게이트 부트스트랩, CPU 대비 86.7배, VeloFHE 대비 13.6배 향상
- 4.첫 NTRU 기반 8비트 FHE 명령어셋 개발, 기존 대비 10배 이상 속도·100배 이상 작은 키 달성
왜 중요한가?
TFHE류 비트단위 FHE의 최대 병목인 블라인드 회전 순차연산을 구조적으로 줄여 CPU·GPU 양쪽에서 최신 성능을 경신했고, 하드웨어 친화적 NTT-프리 변형까지 제시해 실용적 FHE 배포 가능성을 넓혔다.
이 연구는 비트 단위 동형암호(FHE)의 주요 병목 현상인 부트스트래핑 과정의 블라인드 회전(blind rotation)을 희소 키와 하드웨어 가속을 통해 혁신적으로 개선합니다. 막대한 지연 시간과 연산량을 줄여 FHE의 실용성을 크게 높일 수 있으며, 이는 국내 인공지능 학습 및 민감 데이터 분석 환경에서 개인정보 보호 기술 도입을 가속화할 중요한 기반이 됩니다. 한국의 마이데이터(MyData) 산업 및 데이터 3법 개정 이후 안전한 데이터 활용 수요가 급증하는 가운데, 본 기술은 FHE의 상용화를 앞당겨 다양한 산업 분야에서 프라이버시 보호 컴퓨팅의 확산을 이끌 것으로 기대됩니다.
본문 미리보기
Blind rotation is the dominant computational bottleneck in bootstrapping for bitwise FHE schemes such as TFHE. Existing constructions typically evaluate $O(n)$ sequential external products for an LWE secret of dimension $n$, incurring substantial latency and a large number of NTT/iNTT operations. In this work, we present a new framework for NTRU-based bootstrapping that reduces the sequential complexity of blind rotation for sparse binary LWE secrets. Inspired by Jain et al. (CRYPTO 2026), we
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:24AI 초안
