기술 요약: HE-LRM

문제 정의

완전 동형 암호(Fully Homomorphic Encryption, FHE)는 암호화된 데이터에 대한 프라이버시 보존형 신경망 추론을 가능하게 하지만, 기존 솔루션들은 주로 밀집 입력(예: CNN, MLP)을 다루는 모델에 집중되어 있습니다. 딥러닝 추천 모델(DLRM)은 대규모의 희소 범주형 입력이 거대한 임베딩 테이블을 통해 처리된다는 점에서 구별되는 독특한 과제를 제시합니다.

표준 DLRM에서 희소 특징(sparse features)은 임베딩 테이블 조회를 통해 밀집 벡터로 매핑됩니다. FHE 맥락(특히 CKKS 스킴 사용 시)에서 직접적인 인덱싱은 네이티브하게 지원되지 않으며, 오직 SIMD 덧셈, 곱셈 및 순환 회전(cyclic rotation)만 사용할 수 있습니다. 나이브한 방식의 암호화된 조회는 심각한 확장성 문제를 겪습니다:

1. 통신 오버헤드: $k$개의 행을 가진 테이블에 대해 인덱스를 원-핫(one-hot) 인코딩하려면 $k$ 크기의 벡터가 필요합니다. Criteo와 같은 산업 규모의 데이터셋(3,380만 행)의 경우, 추론당 1,000개 이상의 암호문(>1 GiB)을 업로드해야 합니다.
2. 서버 측 연산 비용: 이전 연구(Kim et al. [10])는 업로드 비용을 완화하기 위해 서버가 암호화된 인덱스로부터 원-핫 선택기를 구축하도록 시도합니다. 그러나 이는 상당한 곱셈 깊이(multiplicative depth)를 소비하는 심층 산술 회로(지시 함수, indicator functions)를 요구하며, 이로 인해 비용이 많이 드는 부트스트래핑(bootstrapping) 작업이 필수적이 됩니다.
3. 메모리 및 구조 누출: 기존의 압축 기술은 클라이언트가 학습된 코드 매핑(임베딩 상관관계를 드러냄)을 저장해야 하거나, 비효율적인 슬롯 활용 및 높은 메모리 풋프린트를 초래할 수 있습니다.

방법론: HE-LRM

저자들은 DLRM 추론에 최적화된 엔드 투 엔드 FHE 시스템인 HE-LRM을 제안합니다. 이 솔루션은 세 가지 핵심 기술 혁신을 통해 임베딩 조회 병목 현상을 해결합니다:

1. 클라이언트 측 자릿수 분해 압축 (Client-Side Digit Decomposition Compression)

구조를 누출하는 서버 측의 원-핫 벡터 구축이나 학습된 코드 매핑에 의존하는 대신, HE-LRM은 **자릿수 분해(digit decomposition)**에 기반한 결정론적인 클라이언트 측 압축 기술을 채택합니다.

• 메커니즘: 크기가 $k \times d$인 원래의 임베딩 테이블을 $k \approx p^\ell$ 관계를 갖는 $p \times d$ 크기의 $\ell$개 작은 테이블로 분해합니다.
• 과정: 클라이언트는 범주형 인덱스 $i$를 가져와 이를 base-$p$ 자릿수 튜플 $(i_0, i_1, \dots, i_{\ell-1})$로 분해합니다.
• 프라이버시: 클라이언트는 이러한 작은 자릿수들에 대한 원-핫 인코딩을 로컬에서 구성하고 이를 암호화합니다. 서버는 원래의 인덱스를 볼 수 없으며, 값비싼 호모모픽 지시 함수를 수행할 필요도 없습니다. 이 압축은 매핑 구조를 클라이언트에게 드러내지 않으면서 엔드 투 엔드로 학습 과정 중에 수행됩니다.

2. 블록 대각선 패킹 전략 (Block-Diagonal Packing Strategy)

DLRM은 일반적으로 여러 개의 임베딩 테이블(예: Criteo의 경우 26개)을 사용합니다. HE-LRM은 이를 동시에 처리하기 위해 블록 대각선 패킹 전략을 도입합니다.

• 구현: 여러 임베딩 테이블을 하나의 커다란 가중치 행렬 내에 대각선 방향으로 연결(concatenate)합니다.
• 이점: 이를 통해 클라이언트는 모든 특징에 대한 원-핫 인코딩을 하나의 벡터로 결합할 수 있습니다. 그러면 서버는 단 한 번의 베이비 스텝 자이언트 스텝(Baby-Step Giant-Step, BSGS) 행렬-벡터 곱셈을 수행하여 모든 테이블의 임베딩을 병렬로 검색할 수 있습니다. 이는 암호문 슬롯 활용도를 극대화하고 테이블을 순차적으로 처리하는 오버헤드를 방지합니다.

3. 최적화된 선형 변환

시스템은 행렬-벡터 곱셈을 위해 더블 호이스티드(double-hoisted) BSGS 알고리즘을 활용합니다

• 모든 임베딩 벡터 차원에 대해 별도의 회전을 요구하는 기존의 "Table-Mult" 방식과 달리, BSGS 방식은 조회를 표준 선형 변환으로 취급합니다.
• 이는 연산을 단일 곱셈 레벨로 줄여주며, 조회 단계 동안 중간 부트스트래핑이 필요하지 않게 합니다.

주요 기여

1. 최초의 엔드 투 엔드 FHE DLRM: HE-LRM은 FHE 환경에서 DLRM의 밀집 및 희소 특징을 모두 지원하는 최초의 시스템이며, UCI Heart Disease 및 Criteo 데이터셋을 통해 검증되었습니다.
2. 56배 속도 향상: 제안된 클라이언트 측 자릿수 분해 및 BSGS 조회 전략은 큰 임베딩 차원(768)에 대해 최신 기술(CodedHeLUT) 대비 56배의 속도 향상을 달ម្ត합니다. 이는 서버 측 지시 함수를 피하고, 곱셈 깊도 소비를 (~10단계에서 1단계로) 줄이며, 조회 단계에서의 부트스트래핑 필요성을 제거함으로써 달성됩니다.
3. 병렬 다중 테이블 조회: 블록 대각선 패킹 전략은 여러 임베딩 테이블에 대한 효율적인 병렬 조회를 가능하게 하여, 테이블을 개별적으로 처리할 때보다 통신 및 계산 오버헤드를 크게 줄입니다.
4. 깔끔한 누출 프로파일: 이 방법은 클라이언트가 입력 차원과 테이블 크기만 알 뿐, 임베딩 값, 상관관계 또는 모델 파라 meters에 대해서는 아무것도 알 수 없는 준-정직(semi-honest) 위협 모델을 준수합니다.

실험 결과

저자들은 오픈 소스 Orion FHE 프레임워크를 사용하여 단일 스레드 CPU(Intel Xeon Gold 5218)에서 HE-LRM을 평가했습니다.

• UCI Heart Disease: 엔드 투 엔드 추론 지연 시간 24초를 달성했습니다.
• Criteo 데이터셋: 압축률($10\times$에서 $10^5\times$ 사이)에 따라 228초에서 489초 사이의 지연 시간을 기록했습니다.
  • 고도로 압축된 모델($\approx 10^3\times$ ~ $10^5\times$)은 임베딩 조회 시간이 나머지 네트워크에 비해 무시할 수 있는 수준(35초)이 되었고, BSGS 연산을 단일 암호문 상에서 수행할 수 있었기 때문에 유사한 지연 시간(230초)을 보였습니다.
  • 덜 압축된 모델은 더 많은 암호문을 필요로 하여 행렬-벡터 곱셈 지연 시간이 증가했습니다.
• 하드웨어 투영:
  • GPU: Cheddar 가속기를 사용한 투영 결과, CPU 대비 ~200배의 속도 향상을 보여 Criteo 추론을 약 1초 내외로 단축할 수 있습니다.
  • ASIC: Osiris 비용 모델을 사용한 투영 결과, 압축된 모델에 대해 1초 미만의 지연 시간(약 0.037초)을 보여줍니다.

의의 및 주장

본 논문은 HE-LRM이 프라이버시 보존형 추천 시스템이 실질적인 배포 단계에 근접했음을 입증함으로써, 프라이버시 보호 추론의 중요한 간극을 메우고 있다고 주장합니다.

• 확장성: 본 연구는 FHE의 "임베딩 병목 현상"이 프라이버시를 희생하거나 클라이언트가 모델 가중치를 보유할 필요 없이 해결될 수 있음을 증명합니다.
• 시스템 효율성: 인덱스 인코딩의 복잡성을 (결정론적 분해를 통해) 클라이언트로 옮기고, 서버에서 효율적인 선형 대수(BSGS)를 활용함으로써, 과도한 부트스트래핑과 나이브한 원-핫 인코딩에 따른 막대한 통신 오버헤드를 피합니다.
• 광범위한 적용 가능성: 저자들은 암호화된 임베딩 조회 프리미티브가 DLRM에 국한되지 않고 Transformer 기반 모델에도 유효하며, 이는 미래의 프라이버시 보호 추론 시스템을 위한 재사용 가능한 추상화를 시사한다고 언급했습니다.

저자들은 현재의 CPU 성능(대규모 모델의 경우 몇 분 소요)에 대해 겸허한 태도를 유지하며, 실제 생산 환경 배포를 위해서는 GPU 및 ASIC 하드웨어에서 입증된 속도 향상이 필수적임을 강조합니다.