Descent-PBS: Programmable Bootstrapping beyond the Ring Dimension↗ (원문, 새 창)

이 논문은 FHEW/TFHE 기반 프로그래머블 부트스트래핑(PBS)에서 큰 테이블을 다룰 때 모듈 랭크(rank)에 따른 비용을 첫 회전에서만 부담하는 'Descent-PBS'를 제안한다. 서브링에서 임베드된 모듈 비밀에 대해 절삭(truncation)이 비밀과 교환 가능함을 증명해, 공개 함수형 키 스위칭 한 번으로 모듈 누산기의 모든 구성 요소를 링으로 재패킹함으로써 반복되는 랭크 비용을 제거했다. 블록 원-핫 비밀의 경우 결합된 키가 스칼라 행렬이 되어 모든 회전의 키를 한 번에 구축할 수 있으며, 반올림 편향을 없애는 짝수 올림 가젯도 함께 적용했다. TFHE-rs 기반 구현에서 16비트 네가사이클릭 LUT를 128비트 보안 수준에서 196ms에 평가해, 기존 Meta-PBS보다 최대 3.32배, WoP-PBS보다 최대 6.6배 빠른 성능을 보였다.

• 모듈 비밀의 절삭이 비밀과 교환 가능함을 증명해 모듈 랭크 비용을 첫 회전에서만 지불하는 Descent-PBS 제안
• 공개 함수형 키 스위칭 한 번으로 모듈 누산기 구성 요소를 링으로 재패킹해 반복 비용 제거
• 블록 원-핫 비밀에서는 결합 키가 스칼라 행렬이 되어 전체 회전 키를 한 번에 구축 가능
• 16비트 LUT를 196ms에 평가, 밀집 비밀 기준 Meta-PBS 대비 1.44~2.40배, 블록 원-핫 비밀 기준 최대 3.32배 빠름
• 13~16비트 일반 LUT는 WoP-PBS보다 3.8~6.6배 빠르나 메모리는 약 2배 사용