실용적인 익명 양자 보급 결정 트리

Practical Anonymous Two-Party Gradient Boosting Decision Tree

경사 부스팅 결정 트리(GBDT)는 구조화된 데이터를 효과적으로 처리하며, 일반적으로 상호 불신하는 당사자 간에 수직 분할된 특징을 사용하여 학습됩니다. 높은 속도와 해석 용이성으로 인해 GBDT는 금융 및 의료 분야에서 널리 사용되며, 신경망으로는 해결하기 어려운 문제를 다룹니다. GBDT에 대한 안전한 연산을 구현하는 것은 독특한 과제를 안고 있으며, 비교를 위한 안전한 레코드 정렬이 필요합니다. 개인 집합 교차(PSI)는 사실상 표준적인 접근 방식입니다. PSI를 보안 조치로 착각하면 데이터 세트 간에 공유되는 레코드 식별자(ID)가 무엇인지 노출될 수 있습니다. 회로-PSI는 이 문제를 완화할 수 있지만, 일반적인 용도로 사용하기에는 비용이 많이 듭니다. '어둠의 숲'에서 효율적으로 학습하기 위해서는 새로운 아이디어가 필요합니다. 본 연구에서는 ID를 숨기는 것을 목표로, 두 당사자가 보유한 분할 데이터를 사용하여 익명 GBDT 학습을 수행하는 방법을 탐구합니다. 제안하는 방식은 양방향 회로-PSI를 활용하여 각 당사자가 교대로 수신자 역할을 맡아 로컬 특징에 대한 '선택 후 합' 연산을 수행하도록 합니다. 또한, 가려진 프로그래밍 가능한 의사 난수 함수를 사용하여 회로-PSI의 결과를 공유 상태로 전파합니다. 범용 정렬을 피하고, ID 숨김으로 인해 발생하는 비용이 도메인 크기에 따라 증가한다는 간과된 문제를 해결합니다. 더 나아가, 기존의 안전한 GBDT(Usenix Security '23) 및 관련 안전한 머신러닝 연산에서 사용되었던 단일 명령어 다중 데이터 동형 암호화를 위한 암호문 패킹 비용을 절반으로 줄입니다. 비교 실험 결과, 제안하는 프로토콜은 효율성 측면에서 기존의 보안 취약한 방식과 경쟁력이 있음을 보여줍니다. ID 숨김 기능을 제공하는 본 연구의 기술은 다른 수직 분할 분석에도 적용될 수 있습니다.

Structured data is well handled by gradient-boosted decision trees (GBDT), which are usually trained on vertically partitioned features across mutually distrustful parties. High speed and interpretability make GBDTs popular in finance and healthcare, where neural networks may fall short. Enabling secure computation for GBDTs poses unique challenges, requiring secure record alignment for comparison. Relying on private set intersection (PSI) is a de facto approach. Mistaking PSI for a safety measure actually exposes which record identifiers (IDs) are shared between the datasets. Although circuit-PSI could help, it is costly for generic uses. New ideas are needed to efficiently train in a "dark forest". Aiming to hide the IDs, we initiate the study of anonymous GBDT training on split data held by two parties. Dual circuit-PSI in our design lets the parties alternate as receiver to run pick-then-sum over local features. Via oblivious programmable pseudorandom functions, we propagate circuit-PSI outputs as shared state across runs. Avoiding universal alignment, we resolve the neglected dilemma that ID hiding incurs a cost that scales with domain size. Next, we halve the cost of ciphertext packing used to convert single-instruction multiple-data homomorphic encryption from (ring) learning with errors in prior secure GBDT (Usenix Security' 23) and related secure machine-learning computations. Comparative experiments show our protocol remains competitive with leaky approaches in efficiency. Enabling ID-hiding aggregation, our techniques can extend to other vertically partitioned analytics.