기술 요약: SilentWood – 그래디언트 부스팅 결정 포레스트를 위한 효율적인 프라이빗 추론

문제 정의

그래디언트 부스팅 결정 포레스트(예: XGBoost, AdaBoost)는 단일 결정 트리와 비교하여 대규모 데이터셋에 대해 우수한 정확도와 학습 효율성을 제공하는 동시에 모델의 해석 가능성을 유지합니다. 그러나 이러한 모델을 "서비스형 머신러닝(MLaaS)" 맥락에서 배포하는 것은 심각한 개인정보 보호 문제를 야기합니다: 사용자는 민감한 입력 데이터를 공개하기를 꺼리며, 서비스 제공자는 자신들의 독점적인 모델 파라미터를 보호하고자 합니다.

단일 결정 트리를 위한 프라이빗 결정 트리 평가(PDTE)를 위한 완전 동형 암호(FHE) 또는 2자간 계산(2PC) 기반의 프로토콜은 존재하지만, 이를 결정 포레스트로 나이브하게 확장하는 것은 비현실적입니다. 본 논문은 세 가지 주요 과제를 식별했습니다:

1. 계산 오버헤드 (C1): 프라이빗 결정 트리 평가(PDTE)는 모든 노드에서 동형 비교(homomorphic comparisons)를 요구합니다. 수백 개의 트리가 있는 포레스트의 경우, 고유한 [특징, 임계값] 쌍의 수가 많아지면 SIMD(Single Instruction Multiple Data) 연산을 위해 데이터를 정렬하는 데 과도한 동형 회전(homomorphic rotations)과 암호문 클로닝(ciphertext cloning)이 필요합니다.
2. 점수 집계 불호환성 (C2): 여러 트리의 결과를 집계하려면 "참(true)" 경로의 리프 값을 합산해야 합니다. 기존 FHE 기반 PDTE 방식은 딜레마에 직면합니다: SumPath(효율적인 덧셈)는 출력값으로 0(참인 경우) 또는 무작위의 0이 아닌 값(거짓인 경우)을 생성하는데, 이는 복잡한 로직 없이 산술적으로 리프 점수로 변환될 수 없습니다. 반면 MultiplyPath(곱셈)는 직접적인 점수 산출을 가능하게 하지만, 과도한 곱셈 깊이와 비용을 초0 발생시킵니다.
3. 통신 비용 (C3): 표준 PDTE 프로토콜은 SIMD 연산을 가능하게 하기 위해 반복적인 데이터 인코딩(예: 모든 비교에 대해 특징 입력을 반복)을 요구하는 경우가 많으며, 이는 거대한 암호문 크기(예: 32비트 특징의 경우 >85 MB)와 네트워크 병목 현상을 초래합니다.

방법론: SilentWood

SilentWood는 FHE(특히 BFV 스킴)를 활용하고 위에서 언급한 과제들을 해결하기 위해 세 가지 새로운 최적화 기술을 도입한 그래디언트 부스팅 포레스트 전용 프라이빗 추론 프로토콜입니다.

1. 계산 클러스터링 (Computation Clustering)

동형 회전 및 비교의 오버헤드를 줄이기 위해, SilentWood는 포레스트 전반에 걸쳐 중복된 계산을 클러스터링합니다:

• 노드 클러스터링 (Node Clustering): 동일한 특징 이름을 공유하고 유사한 임계값을 가진 서로 다른 트리 간의 노드들을 그룹화합니다. 각 노드에 대해 개별적으로 비교를 수행하는 대신, 프로토콜은 임계값의 가중 평균(트리 및 노드 중요도에 따라 가중치 부여)을 계산하고 모델을 업데이트합니다. 이는 고유 비교 횟수를 줄여줍니다. 이 과정에는 모델 정확도를 보존하기 위해 새로운 임계값에 따라 리프 점수를 조정하는 "리프 값 재최적화(leaf value re-optimization)" 단계가 포함됩니다. 검증 체크를 통해 정확도를 저하시키는 모든 병합은 중단됩니다.
• 경로 클러스터링 (Path Clustering): 순서가 정해지지 않은 노드 조건들의 집합이 동일한 경로들(예: A > 5 AND B > 10 vs. B > 10 AND A > 5)을 식별합니다. 결과는 순서에 무관하므로, 프로토콜은 고유한 조건 집합에 대해 경로 평가(SumPath)를 한 번만 수행하고 그 결과를 일치하는 모든 경로에 재사용합니다.

2. 블라인드 코드 변환 (Blind Code Conversion, BCC)

점수 집계 딜레마(C2)를 해결하기 위해, Silentwood는 효율적인 SumPath 평가와 산술 점수 집계 사이의 간극을 메우는 경량 2자간 프로토콜인 BCC를 도입합니다:

• 프로세스: 서버는 SumPath 암호문(0은 참 경로를, 무작위의 0이 아닌 값은 거짓 경로를 포함함)을 동형적으로 셔플링하고 패딩하여 균등한 무작위 분포를 만듭니다. 이 암호문은 클라이언트로 전송됩니다.
• 클라이언트의 역할: 클라이언트는 데이터를 복호화하여 0을 1로, 0이 아닌 값을 0으로 변환(값을 블라인드하게 반전)한 후, 결과를 다시 암호화하여 서버로 보냅니다.
• 서버의 역할: 서버는 변환된 암호문(이제 참 경로에는 1이, 거짓 경로에는 0이 포함됨)을 받고, 이를 평문 리프 점수와 단 한 번의 동형 곱셈을 수행합니다. 이는 복잡한 곱셈 체인을 요구하지 않고도 올바른 리프 값을 선택할 수 있게 합니다.
• 보안: 셔플링을 통해 클라이언트는 특정 경로의 결과를 알 수 없으며, 서버는 클라이언트의 변환 과정 중 중간값을 알 수 없습니다.

3. 암호문 압축 (Ciphertext Compression)

통신 오버헤드(C3)를 해결하기 위해, SilentWood는 클라이언트의 초기 쿼리를 최적화합니다:

• 메커니즘: 표준 SIMD 정렬에 필요한 것처럼 모든 비교 슬롯에 특징 입력을 반복적으로 인코딩하는 대신, 클라이언트는 암호화 전에 이러한 반복을 제거하여 압축된 암호문을 생성합니다.
• 압축 해제: 수신 시, 서버는 회전(rotation)과 덧셈을 사용하여 원래의 반복적인 데이터 형식을 복원하는 동형 압축(homomorphic decompression)을 수행합니다.
• 이점: 이는 압축 해제 과정 중에 평년 정보가 유출되지 않으면서도 클라이언트-서버 간 통신 크기를 크게 줄여줍니다(예: 32비트 특징의 경우 약 85 MB에서 15 MB로 감소).

주요 기여

본 논문은 다음과 같은 기여를 제시합니다:

1. 프로토콜 설계: 고도로 확장 가능한 그래디언트 부스팅 결정 포레스트에 특화되어 최적화된 최초의 프라이빗 추론 프로토콜인 SilentWood를 제안합니다.
2. 최적화 기술: 세 가지 특정 기술을 도입합니다:
   • 계산 클러스터링: 중복된 동형 연산을 제거하기 위한 노드 및 경로 클러스터링.
   • 블라인드 코드 변환 (BCC): 높은 곱셈 비용 없이 SumPath를 사용하여 효율적인 산술 집계를 가능하게 하는 프로토콜.
   • 암호문 압축: 암호화 전 반복되는 데이터 인코딩을 제거하여 클라이언트 쿼리 크기를 줄이는 방법.
3. 구현 및 평가: C++ 프로토타입 구현과 13개의 UCI 데이터셋에 대한 광범한 평가를 통해 기존의 최첨단 베이스라인들과 성능을 비교하였습니다.

결과

저자들은 SilentWood를 세 가지 베이스라인과 비교 평가했습니다:

• 베이스라인: Naive MultiplyPath 집계를 사용하는 최첨단 FHE 프로토콜인 RCC-PDTE.
• Zama Concrete ML: TFHE 기반 구현체.
• SoK-GGG: 최첨단 2자간 가려진 회로(Garbled Circuit, GC) 프로토콜.

성능 지표 (CPU-FHE, 32비트 특징, 100개 트리 기준):

• 베이스라인 대비 속도 향상: SilentWood는 최대 42.5배 빠릅니다 (평균 32.7배).
• Zama 대비 속도 향상: SilentWood는 최대 27.8배 빠릅니다 (평균 27.8배).
• SoK-GGG 대비 속도 향상: SilentWood는 최대 2.94배 빠릅니다 (평균 2.2배).
• 통신: SilentWood는 베이스라인에 비해 클라이언트-서버 통신 크기를 약 5배 줄였습니다 (예: 32비트 데이터의 경우 85.7 MB 대비 15.12 MB).

절제 연구 (Ablation Study):

• BCC는 값비싼 곱셈 체인을 피함으로써 가장 큰 속도 향상 기여(약 19.7배)를 제공했습니다.
• 계산 클러스터링은 약 1.54배의 속도 향상에 기여했습니다.
• 암호문 압축은 저지연 설정에서 약 1.08배의 속도 향상을 제공했으나, 네트워크 왕복 시간(RTT)이 증가할수록 그 이점이 크게 커집니다.

정확도: 노드 클러스터링 기술은 모델 정확도를 보존하며, 다양한 클러스터링 강도와 트리 구성에 대해 평균 정확도가 0.90을 유지합니다.

의의

본 논문은 SilentWood가 그래디언트 부스팅 모델을 위한 프라이빗 추론을 실용적으로 만드는 데 있어 중요한 진전을 이루었다고 주장합니다. 단일 트리에서 포레스트로 PDTE를 확장할 때 발생하는 구체적인 비효율성(회전의 폭발, 집계 방법의 불호환성, 통신 팽창)을 해결함으로써, SilentWood는 기존 FHE 방식보다 수십 배 빠른 추론 시간을 달 achieve하고 MPC 기반 방식과 대등하거나 더 빠른 성능을 보여줍니다. 저자들은 이것이 이전의 프로토콜들이 너무 느리거나 통신량이 많아 실행 불가능했던 프라이버시 민감형 MLaaS 환경에서, 고정밀도 및 설명 가능한 그래디언트 부스팅 모델의 배포를 가능하게 한다고 강조합니다.