Almost-Free Queue Jumping for Prior Inputs in Private Neural Inference

이 논문은 암호학적 비용 증가 없이 우선순위가 높은 입력을 배치 추론에 효율적으로 통합하여 대기 중인 요청의 지연을 획기적으로 줄이는 새로운 프라이버시 보호 큐 점프 프레임워크 'PrivQJ'를 제안합니다.

핵심

1. 배경: 비밀스러운 병원과 긴 대기실

상상해 보세요. 여러분이 아주 중요한 의료 데이터를 가지고 있습니다. 하지만 이 데이터를 그대로 보내면 병원 (서버) 이 여러분의 사생활을 다 알게 되겠죠? 반대로 병원은 자신들이 개발한 '명약 (AI 모델)'의 비법을 알려주고 싶지 않습니다.

이때 암호화 기술을 써서, 병원은 데이터도 모델도 모른 채 치료 결과만 알려주는 '비밀 진료'를 합니다. 이것이 PP-MLaaS입니다.

하지만 여기서 문제가 생깁니다.

• 대기실의 혼란: 환자들이 줄을 서서 기다리고 있는데, 갑자기 **응급 환자 (우선 입력)**가 도착합니다.
• 기존 방식의 문제: 기존 시스템은 "응급 환자를 먼저 치료하려면, 뒤에 있는 모든 환자들의 치료를 멈추고 다시 처음부터 계산해야 해!"라고 말합니다.
  • 결과: 뒤에 있던 환자들 (기존 대기자) 은 치료받기까지 기다리는 시간이 몇 시간에서 몇 날로 늘어납니다. 이는 '대기 비용'이 너무 비싸다는 뜻입니다.

2. 해결책: PrivQJ 의 '공유된 계산' 마법

이 논문이 제안한 PrivQJ는 이 문제를 완전히 다르게 접근합니다.

비유: "버스 한 대에 타서 가는 것"

기존 방식은 응급 환자가 오면 새로운 버스를 따로 불러서 보냈습니다. 그래서 뒤에 있던 사람들은 버스가 떠날 때까지 기다려야 했습니다.

하지만 PrivQJ는 다릅니다.

• 이미 출발한 버스 (대기 중인 환자들) 를 활용합니다.
• 버스는 이미 정해진 경로 (계산 과정) 를 따라 가고 있습니다.
• PrivQJ 는 응급 환자를 이 버스의 빈 자리 (여유 공간) 에 태워줍니다.
• 버스 운전사 (서버) 는 "응급 환자를 태우기 위해 버스를 멈추거나 경로를 바꾸지 않아도 돼. 그냥 빈 자리에 앉히면 돼!"라고 말합니다.

이것이 바로 논문의 핵심인 '슬롯 재활용 (Slot Recycling)' 기술입니다.

3. 어떻게 가능한 걸까? (조각 puzzle 비유)

컴퓨터 암호화 (HE) 는 데이터를 처리할 때 마치 퍼즐을 맞추는 것과 비슷합니다.

• 기존 방식: 한 명을 계산할 때 퍼즐 조각을 다 채우는데, 남은 빈 공간은 버려집니다. 응급 환자가 오면 새로운 퍼즐을 다시 만들어야 하므로 시간이 걸립니다.
• PrivQJ 방식: "아, 이 퍼즐을 만들 때 생긴 빈 조각들이 있네? 그 빈 조각들을 이용해 응급 환자의 퍼즐 조각도 같이 끼워 넣자!"라고 합니다.

구체적인 과정:

1. **대기 중인 환자들 (일반 입력)**을 계산하는 과정에서, 암호화된 데이터의 **빈 공간 (슬롯)**이 자연스럽게 발생합니다. (예: 100 개의 자리 중 90 개만 쓰고 10 개는 비어있는 경우)
2. PrivQJ는 이 10 개의 빈 자리에 **응급 환자 (우선 입력)**의 데이터를 쑤셔 넣습니다.
3. 서버는 "아, 이 버스를 타고 가면서 응급 환자도 같이 계산했네?"라고 생각하며, 별도의 추가 비용 없이 두 사람을 모두 처리합니다.
4. 결과적으로 응급 환자는 즉시 처리되고, 뒤에 있던 환자들도 기다리는 시간이 거의 늘지 않습니다.

4. 왜 이것이 대단한가요?

논문의 실험 결과에 따르면, 이 방식은 놀라운 성과를 냅니다.

• 기존 방식: 응급 환자를 처리하면 뒤에 있는 사람들은 10 배 이상 더 기다려야 했습니다.
• PrivQJ: 뒤에 있는 사람들은 거의 기다리는 시간이 늘지 않습니다. (약 10 배 이상 효율이 좋아짐)
• 비용: 응급 환자를 처리하는 데 드는 추가 암호화 비용은 거의 0 에 수렴합니다. 마치 버스에 타는 것만큼이나 저렴합니다.

5. 요약: 한 줄로 정리하면?

"PrivQJ 는 비밀스러운 AI 진료소에서, 응급 환자가 왔을 때 뒤에 있던 환자들을 기다리게 하지 않고, 이미 진행 중인 계산 과정의 '빈 자리'를 clever하게 활용하여 응급 환자도 즉시 치료해 주는 혁신적인 시스템입니다."

이 기술은 앞으로 의료, 금융 등 민감한 데이터를 다루는 AI 서비스에서, 긴급한 상황에도 시스템이 멈추지 않고 효율적으로 작동할 수 있는 길을 열어줄 것입니다.

기술 요약

1. 문제 정의 (Problem Statement)

개인정보 보호 머신러닝 서비스 (PP-MLaaS) 는 동형 암호 (HE) 와 다자간 계산 (MPC) 같은 암호학적 기법을 활용하여 클라이언트의 데이터와 서버의 모델 가중치를 보호하면서 신경망 추론을 수행합니다. 최근의 혼합 원시 (mixed-primitive) 프레임워크들은 추론 효율성을 크게 개선했으나, 대량 배치 (batched) 입력을 순차적으로 처리하는 방식에 의존하고 있어 긴급한 요청에 대한 유연성이 부족합니다.

기존 시스템에서 우선순위가 높은 입력 (Prior Inputs) 이 대기 중인 입력들 사이로 끼어들어 처리되기를 원할 때 (Queue Jumping), 다음과 같은 심각한 문제가 발생합니다:

• 기존 입력의 대기 비용 급증: 긴급 입력을 처리하기 위해 기존 배치의 계산을 중단하거나 새로운 배치를 생성해야 하므로, 기존 대기 중인 입력들의 지연 시간 (Latency) 이 크게 증가합니다.
• 과도한 암호학적 오버헤드: 긴급 입력을 처리하기 위해 별도의 암호화 연산 (HE 연산 등) 과 통신 라운드가 추가되어 시스템 전체 성능이 저하됩니다.
• 실용성 부족: 의료 진단 등 긴급한 상황에서는 이러한 지연이 수용 불가능할 수 있습니다.

2. 제안 방법론: PrivQJ (Methodology)

저자들은 PrivQJ라는 새로운 프레임워크를 제안하여, 기존 대기 중인 입력의 성능을 저하시키지 않으면서 우선순위 입력을 거의 무료로 처리할 수 있는 방식을 개발했습니다. 핵심 아이디어는 **배치 내 입력들 간의 공유 계산을 활용하는 "처리 중 슬롯 재활용 (In-processing Slot Recycling)"**입니다.

핵심 메커니즘

1. 슬롯 재활용 (Slot Recycling):

   • 동형 암호 (HE) 의 암호문은 여러 개의 '슬롯 (slot)'을 포함하며, 각 슬롯은 평문 값을 담을 수 있습니다.
   • 기존 방식에서는 배치 처리 시 일부 슬롯이 유휴 (idle) 상태로 남거나, 긴급 입력을 위해 완전히 새로운 암호문을 생성했습니다.
   • PrivQJ 는 기존 대기 중인 입력들의 암호문에서 발생하는 **유휴 슬롯 (tail slots)**을 활용하여, 우선순위 입력의 계산 데이터를 '피그백 (piggyback)'합니다.
   • 이를 통해 우선순위 입력에 대한 계산을 기존 배치의 계산 과정에 자연스럽게 통합합니다.

2. 조각 퍼즐 방식의 계산 (Jigsaw-style Computation):

   • 각 대기 중인 입력의 계산 결과 조각들이 모여 우선순위 입력의 완전한 결과를 구성하도록 설계되었습니다.
   • 선형 함수 (Convolution 등): 서버가 키 (Kernel) 를 가지고 있고, 클라이언트가 임의의 값 ($r_0$) 을 암호화하여 전송합니다. 이때 생성된 암호문 ($\tilde{r}_0$) 의 유휴 슬롯에 우선순위 입력의 데이터를 채워 넣습니다.
   • 비선형 함수 (ReLU 등): OT(Oblivious Transfer) 기반의 비교 연산 후, 중간 암호문 ($t$) 의 유휴 슬롯에 우선순위 입력의 데이터를 삽입합니다.

3. 오프라인/온라인 프로토콜:

   • 오프라인 (Offline): 서버와 클라이언트가 미리 계산된 암호문을 교환합니다. 이때 슬롯 재활용을 통해 여러 우선순위 입력의 데이터를 암호화합니다.
   • 온라인 (Online): 클라이언트가 새로운 입력을 받아 OT 기반의 부분 계산을 수행하고, 서버는 이를 결합하여 최종 결과를 도출합니다. 이 과정에서 우선순위 입력에 대한 추가적인 HE 연산 (덧셈, 곱셈, 회전 등) 이 거의 발생하지 않습니다.

3. 주요 기여 (Key Contributions)

1. 새로운 문제 정의 및 해결: 배치 기반 추론에서의 개인정보 보호 큐 점프 (Privacy-preserving Queue Jumping) 문제를 최초로 연구하고 이를 해결하는 PrivQJ 를 제안했습니다.
2. 거의 무료 (Almost-Free) 계산: 기존 대기 중인 입력의 성능을 저하시키지 않으면서, 우선순위 입력에 대한 암호학적 비용 (HE 연산, 통신 오버헤드) 을 거의 0으로 줄였습니다.
3. 이론적 및 실험적 검증:
   • 이론적 분석을 통해 기존 방식 대비 **10 배 이상 (Order-of-magnitude)**의 오버헤드 감소를 증명했습니다.
   • 실험 결과, 다양한 네트워크 환경 (LAN, WAN) 에서 대기 중인 입력에 추가되는 지연 시간이 기존 최첨단 시스템 (CrypTFlow2, Cheetah, FIT 등) 에 비해 150 배~800 배 이상 감소함을 확인했습니다.

4. 실험 결과 (Results)

• 대기 비용 감소: 우선순위 입력이 끼어들었을 때, 기존 대기 입력들이 겪는 추가 통신량과 시간 비용이 극적으로 감소했습니다.
  • 예: LAN 환경에서 CrypTFlow2 대비 300 배~792 배의 속도 향상, Cheetah 대비 20 배~35 배 향상.
  • WAN 환경에서는 더 큰 속도 향상 (최대 900 배) 을 보였습니다.
• 기존 입력 성능 유지: PrivQJ 를 적용하더라도 일반 대기 입력들의 전체 처리 시간과 통신 비용은 기존 최적화 프레임워크 (FIT 등) 와 유사하거나 더 나은 수준을 유지했습니다.
• 모델 적용: AlexNet, VGG, ResNet 등 다양한 CNN 모델에서 테스트되었으며, 암호문 내 유휴 슬롯이 많은 모델 (ResNet 등) 에서 특히 높은 효율을 보였습니다.

5. 의의 및 중요성 (Significance)

• 실시간 프라이버시 보호 서비스의 실현: 의료 진단, 금융 사기 탐지 등 긴급성이 요구되는 시나리오에서 개인정보 보호를 유지하면서도 실시간으로 우선순위를 처리할 수 있는 가능성을 열었습니다.
• 시스템 효율성 극대화: 암호학적 연산의 비효율성을 줄이기 위해 '계산의 공유'와 '자원 재활용'이라는 새로운 패러다임을 제시했습니다.
• 2-Party 환경 최적화: 제 3 자 서버가 없는 일반적인 클라이언트 - 서버 (2-Party) 환경에서도 높은 효율을 제공하여 실제 배포가 용이합니다.

결론적으로, PrivQJ 는 PP-MLaaS 시스템이 긴급 요청에 유연하게 대응하면서도 전체 시스템의 성능과 프라이버시를 유지할 수 있는 획기적인 솔루션을 제시합니다.