기술 요약: 완전 동형 암호화 기반의 암호화된 압축 쿼리를 이용한 프라이빗 임베딩 룩업

문제 정의

완전 동 홈 암호화(Fully Homomorphic Encryption, FHE)를 사용하는 프라이버시 보존 머신러닝(PPML)에서, 이산적 입력(예: 단어 토큰)에 의존하는 모델의 추론 과정 중 임베딩 레이어는 중요한 병목 구간이 됩니다. 이러한 모델은 일반적으로 이산 인덱스(예: 단어 토큰)를 연속적인 벡터로 매핑하는 임베딩 레이어를 가집니다.

FHE 환경에서 서버는 암호화된 인덱스를 기반으로 표준적인 메모리 접근을 수행할 수 없습니다. 따라서 룩업은 동형 연산을 통해 구현되어야 합니다. 기존 방식들은 다음과 같은 트레이드오프에 직면해 있습니다:

1. 클라이언트 측 룩업: 클라이언트가 암호화된 임베딩 벡터를 전송합니다. 이는 임베딩 차원($d$)에 비례하는 막대한 통신 오버헤드를 발생시키며, 대규모 테이블(예: 190만 개의 토큰을 가진 GloVe)의 경우 매우 비효율적입니다.
2. 원-핫 생성(One-Hot Generation)을 이용한 서버 측 룩업: 클라이언트가 압축된 암호화 스칼라 인덱스를 전송합니다. 서버는 이를 바탕으로 임베딩을 선택하기 위해 원-핫 벡터를 동형적으로 구축해야 합니다. 기존 연구(Kim et al., ICML 2024)는 암호화된 지표 함수(Encrypted Indicator Function, EIF)를 사용하여 이를 달성하지만, 이는 $O(p \log p)$(여기서 $p$는 테이블 크기)의 동형 연산을 요구하며, 상당한 곱셈 깊이(multiplicative depth)를 소비하여 추론 파이프라인의 지배적인 비용이 됩니다.

본 연구의 목표는 클라이언트의 통신량을 작게 유지하면서(스칼라 인덱스 전송), 서버 측의 동형 연산 비용을 최소화하고(비싼 원-핫 생성 단계 회피), **프라이빗 임베딩 룩업(Private Embedding Lookup, PEL)**을 달하는 것입니다.

방법론: 독립 벡터 평가 (Independent Vector Evaluation, IVE)

저자들은 원-핫 벡터의 구축 과정을 완전히 우회하는 방법인 **독립 벡터 평가(IVE)**를 제안합니다.

핵심 통찰

서버가 임베딩 $M_j$를 검색하기 위해 반드시 원-핫 벡터($e_j$)를 엄격하게 요구하는 것은 아닙니다. 서버는 단지 인덱스 $j$를 서로 다른 인덱스 간에 **선형 독립(linearly independent)**인 형태로 표현하기만 하면 됩니다. 만약 벡터 집합 $\{v_j\}$가 선형 독립이라면, $L v_j = e_j$를 만족하는 기저 변환 행렬(change-of-basis matrix) $L$이 존재합니다. 결과적으로 임베딩 검색은 다음과 같이 재작성될 수 있습니다:
$$M_j = M e_j = M (L v_j) = (M L) v_j$$
$M$과 $L$은 평문(plaintext)으로 알려져 있으므로, 서버는 행렬 $M' = ML$을 사전 계산할 수 있습니다. 이제 온라인 작업은 원-핫 벡터를 생성하는 것에서 벡터$v_j$를 동형적으로 평가하는 것으로 전환됩니다.

벡터 구축 및 안정성

CKKS 스킴(근사 산술을 지원) 하에서의 효율성과 수치적 안정성을 보장하기 위해 다음을 수행합니다:

1. 효율성: 벡터 $v_j$는 단일 암호화된 값 $\alpha_j$의 연속적인 거듭제곱을 사용하여 구축됩니다. 이를 통해 서버는 복잡한 등가성 테스트 대신 표준 산술 연산(곱셈)을 사용하여 벡터 성분을 생성할 수 있습니다.
2. 안정성: 기저 변환 과정에서 발생하는 오차 증폭을 방지하기 위해, 행렬 $L$은 양호한 조건(ideally orthogonal, 이상적으로 직교)을 가져야 합니다. 저자들은 이산 코사인 변환(Discrete Cosine Transform, DCT) 행렬을 활용합니다. 단위근(roots of unity)을 사용하고 실수부와 허수부를 분리함으로써, CKKS의 복소 산술 역량과 일치하는 직교 기저를 구축합니다.

알고 $\리즘 흐름

1. 클라이언트: 인덱스 $j$를 $\alpha_j$(단위근으로부터 유도됨)로 암호화하여 압축된 스칼라 쿼리로 전송합니다.
2. 서버 (IVE 단계):
   • 암호화된 $\alpha_j$를 수신합니다.
   • 곱셈 트리(multiplication tree, 로그 깊이)를 사용하여 $\alpha_j^0, \alpha_j^1, \dots, \alpha_j^{p/2}$를 계산합니다.
   • 켤레 복소수(conjugation)를 통해 실수부와 허수부를 분리하여 벡터 $v_j$를 형성합니다.
   • 이 과정은 $O(p)$의 동형 연산을 필요로 하며, 이는 원-핫 생성에 필요한 $O(p \log p)$보다 크게 감소한 수치입니다.
3. 서버 (PCMM 단계):
   • 사전 계산된 행렬 $M' = ML$과 생성된 벡터$v_j$ 사이의 평문-암호문 행렬 곱셈(Plaintext-Ciphertext Matrix Multiplication, PCMM)을 수행합니다.
   • 이를 통해 암호화된 임베딩 벡터를 얻습니다.

주요 기여

1. 독립 벡터 평가 (IVE): 암호화된 원-핫 생성을 선형 독립 벡터 패밀리의 평가로 대체하는 새로운 알고리즘을 제안합니다. 이는 벡터 생성 복잡도를 $O(p \log p)$에서 $O(p)$로 줄입니다.
2. DCT를 통한 직교 기저: IVE를 DCT 기반 직교 행렬로 구체화함으로써, 기저 변환 시 발생하는 CKKS 근사의 오차 증폭 문제를 완화하고 수치적 안정성을 확보했습니다.
3. 통합된 PEL 파이프라인: IVE를 PCMM과 결합하여 배치 쿼리(batched queries)를 효율적으로 처리하도록 설계했습니다. 이 파이프라인은 여러 토큰 쿼리를 동시에 지원하여 CKKS SIMD 슬롯 전체에 걸쳐 비용을 분담(amortize)합니다.
4. 엔드 투 엔드 구현: 본 방법론을 FastText 스타일의 텍나 분류 파이프라인에 구현하여, 실제 프라이버시 민감도가 높은 추론 작업에서의 실행 가능성을 입증했습니다.

실험 결과

저자들은 세 가지 임베딩 데이터셋(GloVe.6B.50d, GloVe.42B.300d, GPT-2)과 Enron-Spam 데이터셋에 대한 엔드 투 엔드 FastText 추론을 사용하여 IVE-PEL을 기존 최첨단 방식(Kim et al.)과 비교 평가했습니다.

• 벡터 생성 속도 향상: IVE-PEL은 벡터 생성 시간을 크게 단축했습니다. 서브테이블 크기 $\log p = 10$일 때, GloVe.6B.50d 기준으로 벡터 생성 시간(VecGen time)이 Kim et al.의 약 424ms에서 IVE-PEL의 약 3.15ms로 감소하여, 이 특정 단계에서 134.6배의 속도 향상을 보였습니다.
• 전체 파이프라인 속도 향상: 데이터셋과 임베딩 차원에 따라 아마티즈된(amortized) 룩업 시간이 18.5배에서 78.4배 개선되었습니다. 가장 큰 이득은 벡터 생성이 지배적인 비용이었던 시나리오에서 관찰되었습니다.
• 곱셈 깊이: IVE-PEL은 원-핫 생성 방식에 필요한 곱셈 깊이의 약 1/3만을 소비하므로, CKKS 노이즈 예산을 소진하지 않고도 더 큰 서브테이블 크기와 더 나은 압축 품질을 유지할 수 있습니다.
• 엔드 투 엔드 영향: Enron-Spam 분류 작업에서, 원-핫 방식을 IVE로 교체했을 때 전체 암호화 추론 시간 중 벡터 생성이 차지하는 비중이 99.6%에서 66.3%로 감소하여 전체 지연 시간을 실질적으로 낮추었습니다.

의의 및 주장

본 논문은 IVE-PEL이 프라이빗 임베딩 룩업의 "누락된 설계 지점(missing design point)", 즉 컴팩트한 클라이언트 통신(스칼라 인덱스)을 달성하면서도 과도한 서버 측 비용(동형 원-핫 생성)을 발생시키지 않는 방법을 해결했음을 주장합니다.

원-핫 기저의 필요성을 검색 과정에서 분리함으로써, 저자들은 프라이빗 임베딩 룩업이 경량 클라이언트와 대규모 모델을 위해 실용적으로 만들어질 수 있음을 입증했습니다. 결과는 IVE-PEL이 사용자 입력 인덱스의 기밀성을 유지하면서도 NLP 및 추천 모델을 위한 효율적인 프라이버시 보존 추론을 가능하게 한다는 것을 보여줍니다. 또한, IMDB 감성 분류 및 스팸 탐지 결과에서 나타나듯, 본 방법론은 모델의 정확도를 유지하면서도 계산 효율성을 획기적으로 개선했습니다.