Volley Revolver: A Novel Matrix-Encoding Method for Privacy-Preserving Neural Networks (Inference)

이 논문은 동형 암호화를 활용한 프라이버시 보호 신경망 추론을 위해 새로운 행렬 인코딩 기법을 제안하고, 이를 MNIST 손글씨 이미지 분류에 적용하여 암호화된 데이터를 클라우드에서 효율적으로 처리하는 방법을 제시합니다.

핵심

볼리 리볼버 (Volley Revolver): 암호화된 데이터로 머신러닝을 하는 새로운 방법

이 논문은 "비밀을 지키면서 클라우드에서 인공지능 (AI) 을 작동시키는" 아주 똑똑한 새로운 방법을 소개합니다. 제목인 '볼리 리볼버 (Volley Revolver)'는 이 기술의 핵심 아이디어를 잘 표현하는 이름입니다.

이 복잡한 기술을 일상적인 비유로 쉽게 설명해 드리겠습니다.

---

1. 문제 상황: "비밀스러운 편지"와 "신뢰할 수 없는 우체국"

상상해 보세요. 당신이 **비밀스러운 편지 (개인 정보나 의료 기록 등)**를 쓰고 있습니다. 하지만 이 편지를 처리할 수 있는 **고급 AI(우체국)**는 당신에게 편지를 직접 보여주고 싶지 않습니다.

• 기존 방식: 편지를 봉인 (암호화) 해서 우체국에 보냅니다. 우체국은 봉인을 뜯지 않고는 내용을 알 수 없으니, 편지를 처리할 수 없습니다.
• 해결책 (동형 암호화): 편지를 봉인한 채로 우체국에 보내면, 우체국이 봉인된 상태 그대로 편지를 읽고, 계산하고, 답장을 다시 봉인해서 돌려보낼 수 있다면 어떨까요? 이것이 바로 '동형 암호화 (Homomorphic Encryption)'입니다.

하지만 문제는 속도입니다. 봉인된 상태에서 계산을 하려면 보통 시간이 매우 오래 걸립니다. 마치 봉인된 상자를 열지 않고도 내용물을 섞고 계산해야 하는 것처럼, 매우 비효율적입니다.

2. 이 논문의 해결책: "볼리 리볼버 (Volley Revolver)"

이 논문은 이 비효율적인 계산을 획기적으로 빠르게 만드는 새로운 데이터 포장 (인코딩) 기술을 제안합니다. 이름은 **'볼리 리볼버'**입니다.

🎯 비유 1: 볼리 (Volley) - 한 번에 여러 발 쏘기

기존 방식은 데이터를 하나씩 처리하거나, 데이터를 잘게 쪼개서 여러 개의 봉투 (암호문) 에 나누어 넣었습니다. 마치 한 번에 한 발씩 총을 쏘는 것과 같습니다.

하지만 '볼리'는 한 번에 여러 발을 동시에 쏘는 것입니다.

• 비유: 32 장의 사진 (예: 손글씨 숫자) 을 각각 따로따로 봉투에 넣는 대신, 하나의 거대한 투명 상자 (단일 암호문) 안에 32 장의 사진을 모두 꽉 채워 넣습니다.
• 효과: 우체국 (클라우드) 은 이 하나의 상자를 처리할 때, 안의 32 장을 한 번에 동시에 계산합니다. 마치 32 발의 총알을 한 번에 발사하는 것처럼 효율이 극대화됩니다.

🔄 비유 2: 리볼버 (Revolver) - 회전하는 총알

이 기술의 가장 멋진 부분은 데이터의 배열 방식입니다.

• 기존 방식: 데이터를 계산하려면 상자를 열고 내용을 다시 정렬해야 하는 복잡한 과정이 필요했습니다.
• 볼리 리볼버 방식: 데이터를 **회전식 총알통 (리볼버)**처럼 배열합니다.
  • AI 가 계산할 때, 데이터가 고정된 채로 총알통만 빙글빙글 돌립니다.
  • 이 '회전' 동작은 암호화된 상태에서도 매우 빠르게 일어납니다.
  • 마치 리볼버 총의 방아쇠를 당길 때마다 총알이 자동으로 다음 위치로 이동하듯, 데이터가 필요한 자리로 자동으로 이동하며 계산을 수행합니다.

3. 구체적인 작동 원리 (손글씨 인식 예시)

이 논문은 MNIST 라는 유명한 손글씨 숫자 데이터셋을 예로 들었습니다.

1. 준비 (데이터 주인): 32 장의 손글씨 사진을 하나의 거대한 암호문으로 만듭니다. (이때 32 장의 사진이 마치 32 개의 가상의 작은 암호문처럼 동작하도록 설계합니다.)
2. 전송: 이 거대한 암호문 (약 20MB) 을 클라우드 서버로 보냅니다. (기존 방식보다 훨씬 적은 데이터를 전송합니다.)
3. 계산 (클라우드 서버):
   • 서버는 이 암호문을 열지 않고도 **합성곱 (Convolution, 이미지 특징을 찾는 과정)**을 수행합니다.
   • '볼리 리볼버' 기술을 통해, 서버는 32 장의 사진을 동시에 처리합니다.
   • 마치 32 개의 카메라가 동시에 사진을 찍고 분석하는 것처럼, 한 번의 작업으로 32 개의 결과를 얻습니다.
4. 결과: 서버는 암호화된 답장을 돌려보냅니다. 데이터 주인은 이 답장을 열어 32 장의 사진이 어떤 숫자인지 (0~9) 확인합니다.

4. 왜 이것이 중요한가요? (장점)

• 속도 향상: 32 장의 사진을 동시에 처리하므로, 기존 방식보다 훨씬 빠릅니다. (실제 실험에서 40 개의 가상 코어를 가진 서버에서 32 장의 사진을 처리하는 데 약 4 분 47 초가 걸렸습니다.)
• 보안 유지: 클라우드 서버는 어떤 데이터도 볼 수 없습니다. 오직 암호화된 상태에서만 계산을 합니다.
• 효율성: 데이터가 낭비되지 않고 암호문 공간 (슬롯) 을 꽉 채워 사용합니다.

5. 요약: 이 기술이 주는 메시지

이 논문은 **"비밀을 지키면서도, AI 를 빠르게 작동시킬 수 있는 새로운 포장 기술"**을 제안합니다.

• 기존: "비밀을 지키려면 속도를 포기해야 해."
• 이 논문 (볼리 리볼버): "아니야! 한 번에 여러 일을 동시에 처리하는 (볼리) 방식과 데이터를 회전시켜 계산하는 (리볼버) 방식을 쓰면, 비밀도 지키면서 속도도 낼 수 있어!"

이 기술은 의료 기록 분석, 금융 사기 탐지, 개인 정보 보호가 필요한 모든 AI 서비스에서 보안과 성능을 동시에 잡는 핵심 열쇠가 될 것입니다.

기술 요약

1. 문제 정의 (Problem)

• 프라이버시 보호의 필요성: 의료, 금융 등 민감한 데이터가 포함된 머신러닝 애플리케이션에서는 데이터의 기밀성을 유지하면서 추론 (Inference) 을 수행해야 합니다.
• 기존 기술의 한계:
  • 동형 암호화 (Homomorphic Encryption, HE): 데이터를 암호화한 상태에서 연산이 가능하지만, 연산 오버헤드가 크고 특히 행렬 곱셈 및 합성곱 (Convolution) 연산 시 효율성이 떨어집니다.
  • 기존 인코딩 방식: CryptoNets 와 같은 기존 연구들은 데이터 패킹 (SIMD) 효율이 낮거나, 깊은 신경망 구조를 지원하기 위해 복잡한 보정 과정이 필요했습니다.
  • 커널 확장 문제: 합성곱 연산을 위해 커널을 확장할 때 많은 수의 암호문 (Ciphertext) 이 필요하거나, 데이터owner 와 클라우드 간의 통신 비용이 과다하게 발생합니다.
• 목표: 암호화된 데이터 위에서 CNN(합성곱 신경망) 추론을 수행할 때, 행렬 곱셈과 합성곱 연산의 효율성을 극대화하고, SIMD(Single Instruction Multiple Data) 패킹 효율을 높여 대규모 배치 처리를 가능하게 하는 새로운 인코딩 기법 개발.

2. 방법론 (Methodology)

이 논문은 **"Volley Revolver"**라는 새로운 행렬 인코딩 기법을 제안하며, 이를 통해 암호화된 행렬 곱셈과 CNN 추론을 최적화합니다.

2.1 Volley Revolver 인코딩 기법

• 핵심 아이디어: 행렬 곱셈 $C = A \times B$를 수행할 때, 행렬 $A$는 그대로 인코딩하고, 행렬 $B$는 전치 (Transpose) 된 후 패딩된 형태로 인코딩합니다.
• 구현 방식:
  • 행렬 $B$를 전치한 후, 행렬 $A$의 행 수 ($m$) 에 맞춰 수직으로 타일링 (Tiling) 하여 인코딩합니다.
  • 이를 통해 $B$의 행들이 회전 (Rotation) 될 때, $A$의 특정 행과 곱해져서 결과 행렬 $C$의 요소를 동시에 계산할 수 있도록 합니다.
  • 이 과정은 "여러 발의 총알을 동시에 발사하는 리볼버 (Revolver)"와 유사하여 Volley Revolver라는 이름이 붙었습니다.
• 효율성: $m > p$인 경우, $O(p \log p)$의 회전 연산과 $O(p)$의 곱셈 연산으로 행렬 곱셈을 수행할 수 있습니다.

2.2 동형 합성곱 연산 (Homomorphic Convolution)

• Kernelspanner: 합성곱 커널을 입력 이미지 크기와 동일한 행렬 공간으로 미리 확장 (Span) 하여 여러 개의 암호문을 생성합니다.
• SumForConv 알고리즘:
  • 암호화된 이미지와 확장된 커널 암호문을 곱한 후, SumForConv 연산을 통해 부분 합계 (Partial Sum) 를 계산합니다.
  • 이 과정은 회전 (Rotation) 과 덧셈을 반복하여 수행되며, 불필요한 값 (Garbage values) 은 상수 곱셈을 통해 필터링합니다.
  • 가상 암호문 (Virtual Ciphertext) 시뮬레이션: 하나의 실제 암호문에 여러 개의 이미지를 배치하고, 이를 마치 별도의 암호문인 것처럼 취급하여 **3 차원 구조 (Batch $\times$ Height $\times$ Width)**로 데이터를 표현합니다. 이를 통해 한 번의 암호문 연산으로 여러 이미지의 합성곱을 병렬 처리합니다.

2.3 병렬 처리 및 확장성

• SIMD 패킹 최적화: 하나의 암호문에 여러 이미지 (예: MNIST 의 32 개 이미지) 를 패킹하여 처리합니다.
• 가상 노드 (Virtual Nodes): 완전 연결층 (Fully Connected Layer) 의 출력 차원을 2 의 거듭제곱으로 맞추기 위해 가상의 0 값 노드를 추가하여, 행 회전 (RowShifter) 연산을 단순화하고 효율성을 높입니다.

3. 주요 기여 (Key Contributions)

1. Volley Revolver 인코딩 기법: 임의의 모양을 가진 행렬 곱셈을 암호화된 상태에서 효율적으로 수행할 수 있는 새로운 데이터 인코딩 방법을 제안했습니다.
2. 효율적인 합성곱 연산 전략: 중간 결과를 효율적으로 누적 (Accumulate) 하는 동형 알고리즘을 설계하여, 커널 확장 및 합성곱 연산의 복잡도를 줄였습니다.
3. 3 차원 데이터 구조 시각화: 패킹된 암호문 내에서 여러 개의 "가상 암호문"을 시뮬레이션하여, 이미지 데이터셋을 3 차원 구조로 다루는 새로운 관점을 제시했습니다. 이는 기존 1 차원 또는 2 차원 매핑의 한계를 극복합니다.

4. 실험 결과 (Results)

• 실험 환경: MNIST 데이터셋 (28x28 그레이스케일 이미지), 40 vCPU 클라우드 환경, HEAAN 라이브러리 사용.
• 성능 지표:
  • 처리량: 32 개의 암호화된 이미지를 한 번에 처리 (Batching).
  • 처리 시간: 32 개의 이미지에 대한 10 개 클래스의 확률 계산 (추론) 에 약 287 초 소요.
  • 통신 오버헤드: 데이터 소유자는 암호화된 32 개 이미지를 포함하는 **단 하나의 암호문 (약 19.8 MB)**만 클라우드에 업로드하면 됩니다. (기존 방식 대비 통신량 대폭 감소).
  • 정확도: 98.61% (기존 평문 모델 98.66% 와 비교하여 미세한 오차 발생, 이는 동형 암호의 정밀도 제한 때문).
• 비교 분석:
  • 패킹 효율: 기존 방식은 64 개 이미지를 처리하기 위해 49 개의 암호문이 필요했으나, Volley Revolver 는 32 개 이미지를 1 개의 암호문으로 처리하여 SIMD 패킹 효율이 극대화되었습니다.
  • 확장성: 40 vCPU 환경에서 12 vCPU 환경 대비 처리 시간이 30 분에서 4.7 분 (약 285 초) 으로 단축되어 하드웨어 병렬 처리에 대한 확장성이 입증되었습니다.

5. 의의 및 결론 (Significance)

• 실용적인 프라이버시 보호: 데이터 소유자는 원본 데이터를 공개하지 않고도 클라우드에서 고도로 복잡한 CNN 추론을 수행할 수 있게 되었습니다.
• 효율성 혁신: 행렬 곱셈과 합성곱 연산에 특화된 인코딩 기법을 통해, 동형 암호화의 가장 큰 병목 현상이었던 연산 속도와 통신 비용을 획기적으로 개선했습니다.
• 미래 전망:
  • 현재는 추론 (Inference) 에 초점을 맞추었으나, 역전파 (Backpropagation) 알고리즘에도 적용 가능하여 **프라이버시 보호 신경망 학습 (Training)**으로 확장될 가능성이 높습니다.
  • 고해상도 컬러 이미지 (다중 채널) 처리를 위한 확장 연구가 진행 중이며, 다양한 스트라이드 (Stride) 크기와 패딩 기법에도 적용 가능합니다.

요약하자면, 이 논문은 동형 암호화 기반의 신경망 추론에서 발생하는 계산 및 통신 오버헤드를 해결하기 위해, 행렬의 전치와 회전, 그리고 가상 암호문 시뮬레이션을 결합한 **"Volley Revolver"**라는 혁신적인 인코딩 기법을 제안했습니다. 이를 통해 대규모 데이터셋에 대한 효율적이고 안전한 클라우드 기반 AI 추론을 실현 가능하게 만들었습니다.