Efficient Privacy-Preserving Sparse Matrix-Vector Multiplication Using Homomorphic Encryption

이 논문은 동형 암호화를 활용한 효율적인 희소 행렬 - 벡터 곱셈을 위해 압축된 희소 정렬 열 (CSSC) 형식을 도입하여 연산 효율성과 데이터 프라이버시를 동시에 해결하는 최초의 프레임워크를 제안하고 있습니다.

핵심

이 논문은 **"비밀스러운 데이터를 암호화한 채로, 아주 빠르고 효율적으로 계산하는 새로운 방법"**을 소개합니다.

구체적으로는 **'희소 행렬 (Sparse Matrix) × 벡터'**라는 수학적 연산을, 동형 암호 (Homomorphic Encryption) 기술을 이용해 안전하게 수행하는 기술을 개발했습니다.

일반인도 쉽게 이해할 수 있도록 창고 관리와 택배 배송에 비유해서 설명해 드릴게요.

---

1. 문제 상황: "빈 상자로 가득 찬 창고"

우리가 가진 데이터 (예: 의료 기록, 금융 내역) 는 대부분 비밀입니다. 하지만 이 데이터를 분석하려면 클라우드 서버에 보내야 합니다. 그런데 서버는 신뢰할 수 없다면? 데이터를 암호화해서 보내야겠죠.

여기서 **동형 암호 (HE)**라는 마법 같은 기술이 등장합니다. "봉인된 상자 (암호화된 데이터) 를 열지 않고도, 상자 안에서 계산을 할 수 있게 해주는 기술"입니다.

하지만 기존 기술에는 치명적인 문제가 있었습니다.

• 문제: 대부분의 데이터는 **빈칸 (0)**이 훨씬 많습니다. (예: 친구 목록에서 1000 명 중 대화한 사람은 10 명뿐인 경우).
• 기존 방식의 비효율: 암호화된 상태에서 계산을 할 때, 컴퓨터는 빈칸 (0) 까지 모두 계산해야 했습니다. 마치 빈 상자가 99% 인 창고에서, 비어있는 상자를 하나하나 세고 옮기느라 시간이 너무 오래 걸리고, 창고 공간도 다 채워버린 셈입니다.

2. 해결책: "새로운 창고 정리법 (CSSC)"

이 논문은 **"Compressed Sparse Sorted Column (CSSC)"**이라는 새로운 정리법을 제안합니다.

• 비유: 기존 방식은 빈 상자를 다 챙기느라 고생했지만, 이 새로운 방식은 빈 상자는 아예 무시하고, 물건이 들어있는 상자들만 뽑아서 줄을 서게 합니다.
• 어떻게 하나요?
  1. 정렬: 물건이 많은 줄 (행) 부터 모아서 정리합니다.
  2. 밀집: 빈 공간은 다 버리고, 물건들만 왼쪽으로 쏙쏙 밀어 넣습니다.
  3. 편의: 이렇게 정리된 데이터는 암호화되어도 상자 (데이터) 를 효율적으로 채울 수 있게 됩니다.

이제 암호화된 상태에서도 빈 상자를 계산할 필요가 없어지기 때문에 속도가 엄청나게 빨라집니다.

3. 작동 원리: "세 명의 주인공"

이 시스템은 세 명이 협력합니다.

1. 고객 A (데이터 소유자):

   • 자신의 데이터를 CSSC라는 새로운 방식으로 정리합니다.
   • **물건 (숫자)**만 암호화해서 서버에 보냅니다.
   • **상자 번호 (어떤 줄에 있는지)**는 암호화하지 않고 고객 B 에게 알려줍니다. (이건 공개되어도 괜찮은 구조 정보입니다.)

2. 고객 B (벡터 소유자):

   • 고객 A 가 준 '상자 번호'를 보고, 자신의 데이터를 서로 맞춰서 재배치합니다.
   • 이렇게 맞춰진 데이터를 암호화해서 서버에 보냅니다.

3. 클라우드 서버 (계산자):

   • 두 고객으로부터 암호화된 데이터를 받습니다.
   • 물건 × 물건 계산을 합니다. (이때 빈 상자가 없으니 계산이 매우 빠릅니다.)
   • 결과를 다시 합쳐서 (Aggregation) 고객에게 돌려줍니다.
   • 중요: 서버는 계산하는 동안 데이터가 무엇인지 전혀 모릅니다.

4. 놀라운 성과: "기존보다 100 배~1000 배 빠르고, 공간도 적게 씀"

이 논문은 실제 데이터로 실험해 보았습니다. 결과는 정말 놀라웠습니다.

• 속도: 기존 방식보다 최대 100 배에서 1,000 배 이상 빨라졌습니다. (예: 3 일 걸리던 작업이 10 분 만에 끝남)
• 공간 (메모리): 암호화된 데이터가 차지하는 메모리도 최대 18 배나 줄었습니다.
• 이유: 불필요한 빈 상자를 계산하지 않고, 필요한 데이터만 딱 맞춰서 계산했기 때문입니다.

5. 요약: 왜 이것이 중요한가요?

이 기술은 **"비밀을 지키면서도, 복잡한 계산을 빠르게 할 수 있는 길"**을 열었습니다.

• 의료: 환자의 유전체 데이터를 암호화한 채로 병원에서 분석할 수 있습니다.
• 금융: 은행 간 거래 내역을 암호화한 채로 사기 탐지를 할 수 있습니다.
• AI: 사용자의 개인 정보를 노출하지 않고도 AI 모델을 훈련시킬 수 있습니다.

한 줄 요약:

"기존에는 암호화된 데이터로 계산할 때 빈 공간까지 다 계산해서 너무 느리고 비쌌는데, 이 논문은 빈 공간은 다 버리고 필요한 것만 모아서 계산하는 새로운 방법을 만들어 속도와 효율을 극적으로 높였습니다."

기술 요약

논문 요약: 동형 암호화를 활용한 효율적인 개인정보 보호형 희소 행렬 - 벡터 곱셈 (SpMV)

1. 문제 정의 (Problem)

• 배경: 희소 행렬 - 벡터 곱셈 (SpMV) 은 과학적 계산, 데이터 분석, 머신러닝의 핵심 연산입니다. 그러나 의료 기록, 금융 데이터 등 민감한 정보를 다루는 경우, 데이터의 프라이버시를 보호하면서 계산을 수행해야 합니다.
• 현황: 동형 암호화 (Homomorphic Encryption, HE) 는 암호화된 상태에서 계산을 가능하게 하는 유망한 기술이지만, 기존 HE 기반 행렬 연산 연구는 주로 밀집 행렬 (Dense Matrix) 에 초점을 맞추고 있습니다.
• 핵심 난제:
  • 기존 희소 행렬 포맷 (CSR, CSC, COO 등) 은 HE 환경에 적합하지 않습니다. HE 는 암호문 간 연산 (Rotation, Addition 등) 이 매우 비싸기 때문에, 0 인 요소를 처리하거나 불규칙한 희소 구조를 맞추기 위해 과도한 연산이 발생합니다.
  • 특히, 희소 데이터의 불규칙한 구조는 암호문 슬롯 (Slot) 정렬을 어렵게 하여 회전 (Rotation) 과 덧셈 연산의 수를 급격히 증가시키고, 메모리 사용량과 실행 시간을 폭발적으로 늘립니다.
  • 기존 연구들은 행렬이나 벡터 중 하나가 평문 (Plaintext) 일 때만 최적화되어 있어, 행렬과 벡터 모두 암호화된 상태에서의 SpMV 를 효율적으로 수행하는 방법은 부재했습니다.

2. 방법론 (Methodology)

저자들은 암호화된 SpMV 를 효율적으로 수행하기 위해 CSSC (Compressed Sparse Sorted Column) 라는 새로운 포맷과 이를 활용한 엔드 - 투 - 엔드 파이프라인을 제안했습니다.

• CSSC 포맷 (핵심 기여):

  • 행 재배열: 행렬의 행을 비영 (Non-zero) 원소의 개수가 많은 순서대로 내림차순으로 정렬합니다.
  • 왼쪽 정렬: 각 행의 비영 원소들을 왼쪽으로 밀어냅니다.
  • 열 우선 추출: 정렬된 행렬을 열 우선 (Column-major) 순서로 스캔하여 값 배열 (Value Array), 원래 열 인덱스 (Column Index), 행 매핑 (Row Map), 열 포인터 (Column Pointer) 를 추출합니다.
  • 효과: 이 구조를 통해 비영 원소들이 암호문의 슬롯 (Slot) 에 정렬되어 매핑되도록 하여, 불필요한 회전 연산을 최소화하고 암호문 패킹 효율을 극대화합니다.

• Secure Computation Framework (보안 계산 프레임워크):

  • 클라이언트 A (행렬 소유자): 행렬을 CSSC 로 변환하고, 값을 암호화하여 클라우드에 업로드합니다. 열 인덱스 정보는 클라이언트 B 에게 평문으로 공유합니다.
  • 클라이언트 B (벡터 소유자): 공유된 열 인덱스를 기반으로 벡터를 재구성 (Reorganization) 하고 암호화하여 클라우드에 업로드합니다.
  • 클라우드 서버:
    1. Chunking: 행렬과 벡터를 암호문 크기 제한에 맞는 청크 (Chunk) 단위로 분할합니다.
    2. Multiplication: 각 청크 내에서 암호문 - 암호문 곱셈 (HE-Mult) 을 수행합니다.
    3. Aggregation: 이진 트리 (Binary-tree) 방식의 회전 및 덧셈을 사용하여 부분 합을 집계합니다. 각 청크 내에서는 행 단위 합계를, 청크 간에는 마스크 (Mask) 를 적용하여 최종 결과를 도출합니다.
  • 최적화: 곱셈 깊이 (Multiplicative Depth) 를 1 로 유지하고, 회전 및 덧셈 연산을 최소화하여 HE 의 성능 병목 현상을 해결합니다.

3. 주요 기여 (Key Contributions)

1. 최초의 암호문 - 암호문 SpMV 프레임워크: 행렬과 벡터가 모두 암호화된 상태에서도 SpMV 를 수행하는 최초의 프레임워크를 제시했습니다.
2. HE 인지형 희소 포맷 (CSSC) 개발: 기존 CSR/CSC/COO 가 가진 HE 환경에서의 불일치 문제를 해결했습니다. CSSC 는 비영 원소를 벡터 슬롯에 정렬하여 회전과 덧셈 연산을 대폭 줄이고, 희소성을 유지하며 저장 공간을 절약합니다.
3. 저 깊이 (Low-depth) 배치 처리 파이프라인: 암호문 청킹, 벡터 재구성, 결정론적 슬롯 정렬, 로그 깊이 (Logarithmic depth) 집계 알고리즘을 통합하여 곱셈 깊이를 1 로 고정하고 배치 처리를 통해 비용을 분산시켰습니다.

4. 실험 결과 (Results)

실제 SuiteSparse Matrix Collection 의 다양한 희소 행렬 데이터셋을 사용하여 실험을 수행했습니다.

• 실행 시간 (Speedup):
  • 기존 방법 (Diagonal method, HEGMM, HETAL 등) 대비 평균 100 배 이상, 최대 3 차수 (1,000 배 이상) 의 속도 향상을 달성했습니다.
  • 특히 대규모 행렬 (예: ship_001, p2p-Gnutella31) 의 경우, 기존 방법들은 3 일 이상 소요되거나 실행 불가 (Time-out) 인 반면, 제안된 방법은 수 초에서 수 분 내에 완료되었습니다.
• 메모리 사용량:
  • 암호문 수를 획기적으로 줄여 메모리 사용량을 2.4 배에서 최대 18 배까지 감소시켰습니다.
  • 기존 밀집 행렬 기반 접근법은 불필요한 0 요소 처리로 인해 메모리 폭주 현상이 발생했으나, CSSC 는 이를 방지했습니다.
• 복잡도 분석: 클라우드 서버 측의 실행 시간이 비영 원소 수 (NNZ) 에 대해 선형적으로 증가하는 것을 확인하여, 대규모 데이터에 대한 확장성 (Scalability) 을 입증했습니다.

5. 의의 및 중요성 (Significance)

• 프라이버시 보호의 새로운 기준: 연방 학습 (Federated Learning), 암호화된 데이터베이스, 과학적 계산 등 민감한 데이터가 관여하는 분야에서 행렬 연산의 종단 간 (End-to-End) 기밀성을 보장할 수 있는 실용적인 솔루션을 제시했습니다.
• HE 기술의 실용화: 동형 암호화의 높은 계산 비용이라는 주요 장벽을 희소 데이터 특성에 맞춘 최적화 기법으로 극복함으로써, HE 기반 애플리케이션의 실제 배포 가능성을 높였습니다.
• 향후 연구의 기초: 이 연구는 동형 암호화 하의 희소 선형 대수 연산을 위한 표준적인 접근법을 마련하였으며, 향후 다중 참여자 환경이나 동적 희소성 처리 등으로 확장될 수 있는 기반을 제공합니다.

---

결론적으로, 이 논문은 동형 암호화 환경에서 희소 행렬 연산의 비효율성을 해결하기 위해 CSSC 포맷을 도입하고, 이를 통해 압도적인 성능 향상과 메모리 절감을 달성한 획기적인 연구입니다.