이 논문은 CKKS 기반 암호화 연산에서 워드 단위 산술과 비트 단위 논리를 결합하는 ALU의 산술-불리언(A2B) 변환을 O(1) 부트스트래핑으로 가속하는 방법을 제안한다. 기존 삼각 인코딩 방식은 ℓ비트 메시지를 변환하는 데 순차적 함수형 부트스트래핑이 Θ(ℓ)번 필요했으나, 오버플로 상쇄 기법을 도입해 입력 길이와 무관하게 단 두 번의 순차 부트스트래핑만으로 변환을 완료한다. OpenFHE로 64·128·256비트 워드에 대해 구현한 결과, 기존 3-부트스트랩 방식 대비 약 1.3배 빠르며 Gao-Zheng 대비 최대 8.12배(지연시간), 11.32배(분할상환) 속도 향상이 추정된다. 동형암호 기반 프라이버시 보존 연산의 실용성을 크게 높일 수 있는 결과다.
- •삼각 인코딩을 이진에서 일반 진법으로 확장해 워드당 패킹 효율을 높였다.
- •오버플로 상쇄 기법으로 입력 비트수와 무관하게 두 번의 순차 부트스트랩만 필요하도록 만들었다.
- •병렬 캐리 전파로 O(log ℓ) 수준의 레벨드 곱셈 깊이만 요구한다.
- •OpenFHE 구현에서 기존 대비 최대 11.32배의 분할상환 속도 향상이 추정된다.
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
Arithmetic-to-Boolean Conversion in ALU with O(1) Bootstrapping via Overflow Cancellation
- 1.CKKS 기반 삼각 인코딩을 이진에서 일반 진법으로 확장해 워드당 부트스트래핑 비용 절감
- 2.오버플로 상쇄 기법으로 산술-불리언 변환을 입력당 두 단계 함수형 부트스트랩으로 단축
- 3.64/128/256비트 워드 대상 OpenFHE 구현, 기존 대비 최대 8.12배 지연 개선 추정
왜 중요한가?
동형암호 ALU의 산술-불리언 변환은 암호화 상태 워드 연산의 핵심 병목인데, 이를 길이(ℓ)와 무관한 상수 단계로 줄여 실용적 FHE 연산 성능 개선에 기여한다.
언급 프로젝트
본문 미리보기
Arithmetic logic unit (ALU) can combine word-level arithmetic with bit-level logic on encrypted machine words. Triangle encoding provides a CKKS-based representation for leveled word arithmetic, but its existing arithmetic-to-Boolean (A2B) conversion recovers only one window per bootstrapping. Consequently, converting an \(\ell\)-bit message requires \(\Theta(\ell)\) sequential functional-bootstrapping on the critical path of each input ciphertext. We first extend triangle encoding fr
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:24AI 초안
