Secure Sparse Matrix Multiplications and their Applications to Privacy-Preserving Machine Learning

이 논문은 희소 행렬 곱셈을 위한 전용 MPC 알고리즘을 제안하여 기존 밀집 행렬 방식의 메모리 및 통신 오버헤드를 획기적으로 줄이고, 이를 추천 시스템 및 유전체학 등 프라이버시 보호 머신러닝 응용 분야에 적용할 수 있음을 입증합니다.

핵심

이 논문은 **"비밀스럽게 유지하면서도, 거대한 데이터 속에서 '빈칸'을 효율적으로 처리하는 새로운 방법"**을 소개합니다.

마치 거대한 도서관에서 책을 찾는 상황을 상상해 보세요. 이 도서관에는 책이 수백만 권 있지만, 실제로 내용이 있는 페이지는 1% 미만이고 나머지는 하얀 빈 페이지로 가득 차 있습니다.

기존의 보안 기술 (MPC, 다자간 계산) 은 이 도서관을 다룰 때, 빈 페이지까지 모두 복사해서 가져와야만 했습니다. 이렇게 하면 메모리가 터지고, 통신 비용이 천문학적으로 늘어납니다. 이 논문은 "빈 페이지는 그냥 넘기고, 내용만 있는 부분만 안전하게 처리하자"는 아이디어를 제안합니다.

주요 내용을 일상적인 비유로 설명해 드리겠습니다.

---

1. 문제 상황: "빈 페이지"의 재앙

• 현실: 추천 시스템 (넷플릭스 등) 이나 유전체 분석 같은 분야에서는 데이터의 99% 이상이 '0(빈 값)'입니다.
• 기존 방식 (밀집형): 보안이 필요한 데이터를 처리할 때, 컴퓨터는 '0'이든 '1'이든 상관없이 모든 칸을 다 채워서 계산합니다.
  • 비유: 도서관 사서가 모든 빈 페이지를 복사해서 책상 위에 쌓아두고, 그 위에서 "내용이 있는 페이지만 찾아서 계산해"라고 하는 꼴입니다. 책상 (메모리) 이 터지고, 복사 비용 (통신) 이 너무 비쌉니다.
• 결과: 데이터가 너무 커서 아예 계산이 불가능해집니다.

2. 해결책: "빈 페이지 무시" 보안 알고리즘

저자들은 빈 페이지 (0) 는 아예 계산 목록에서 빼고, 내용만 있는 부분 (비밀 공유된 값) 만 골라서 계산하는 새로운 알고리즘을 만들었습니다.

• 핵심 기술:
  1. 정렬 (Sorting): 내용 있는 페이지들을 모아서 순서대로 정리합니다. (비밀을 유지한 채로요!)
  2. 짝 찾기: 같은 위치 (좌표) 에 있는 내용만 서로 곱하고 더합니다.
  3. 결과: 빈 페이지는 아예 계산에 참여하지 않으므로, 메모리 사용량과 통신 비용이 최대 1,000 배까지 줄어듭니다.

3. 실전 적용: 두 가지 예시

이 기술이 실제로 어떤 변화를 가져오는지 보여줍니다.

• 예시 1: 영화 추천 시스템 (도서 추천)

  • 상황: 27 만 명의 사용자가 34 만 권의 책을 평가한 데이터입니다. (99.998% 가 빈 값!)
  • 기존: 빈 페이지까지 다 복사하려다 컴퓨터 메모리가 터져서 (19TB 필요) 실행 불가.
  • 새로운 방식: 빈 페이지를 무시하고 계산하므로, 48 분 만에 "이 책을 본 사람은 이 책도 좋아할 거야"라는 추천을 안전하게 해냅니다.

• 예시 2: 병원 출입 통제 시스템

  • 상황: 환자의 진료 기록과 병원 출입 로그를 분석해 "위험한 접근"을 찾아내는 AI 를 만듭니다.
  • 기존: 데이터가 너무 커서 학습 자체가 불가능합니다.
  • 새로운 방식: 5 시간 만에 모델을 학습시켜, 민감한 환자 정보를 유출하지 않으면서도 보안 시스템을 구축합니다.

4. 민감한 정보 보호: "누가 얼마나 썼는지"도 숨기는 법

이 알고리즘을 쓰려면 "각 행 (사용자) 에 얼마나 많은 내용이 있는지 (빈 값이 아닌 개수)"를 미리 알아야 합니다. 하지만 이 정보조차 민감할 수 있습니다. (예: "이 사람은 100 개의 책을 봤는데, 저 사람은 1 개만 봤다"는 정보가 유출되면 개인을 특정할 수 있음)

저자들은 이를 해결하기 위해 3 가지 방법을 제안합니다.

1. 익명화 (Row Anonymization): 누가 몇 개를 썼는지 알 수 없게 행 순서를 섞고, 전체적인 분포만 공개합니다. (누가 몇 명인지 모르고, 전체 인구 통계만 알기)
2. 최대치로 채우기 (Padding): 가장 많은 내용을 가진 사람의 수준으로 모든 행을 맞춰서 채웁니다. (모두가 100 권을 읽은 것처럼 보이게 하지만, 실제로는 빈 페이지로 채움)
   • 단점: 데이터가 너무 커질 수 있음.
3. 템플릿 만들기 (Matrix Templating): 가장 똑똑한 방법. 데이터의 분포를 분석해서 "대부분은 10 개, 소수는 100 개"처럼 구간을 나누어 채웁니다.
   • 비유: 모든 사람을 같은 크기의 옷으로 입히는 게 아니라, "작은 옷, 중간 옷, 큰 옷" 세 가지 사이즈만 준비해서 입히는 방식입니다. 이렇게 하면 불필요한 채우기 (메모리 낭비) 를 크게 줄일 수 있습니다.

5. 결론: 왜 이것이 중요한가?

이 논문은 **"데이터의 99% 가 비어있다면, 그 99% 를 계산하지 말라"**는 상식을 보안 기술에 적용했습니다.

• 메모리: 터질 뻔했던 컴퓨터가 정상적으로 돌아갑니다.
• 속도: 통신 비용이 1,000 배 줄어듭니다.
• 보안: 민감한 데이터를 가진 수천 명의 사람들이 참여해도, 서로의 정보를 해치지 않고 함께 머신러닝을 할 수 있게 됩니다.

결국 이 기술은 **빅데이터 시대에, 개인정보 보호를 해치지 않으면서도 거대한 데이터를 실제로 활용 가능하게 만드는 '열쇠'**가 될 것입니다.

기술 요약

1. 문제 정의 (Problem Statement)

• 배경: 다자간 계산 (MPC, Multi-Party Computation) 은 프라이버시를 보호하면서 머신러닝 (ML) 알고리즘을 실행할 수 있게 해줍니다. 그러나 기존 MPC 프레임워크는 희소 데이터 (Sparse Data) 에 최적화된 연산을 제공하지 않습니다.
• 희소 데이터의 중요성: 추천 시스템, 유전체학, 자연어 처리 등 많은 ML 응용 분야에서 데이터는 대부분 0 으로 구성되어 있습니다 (예: Netflix 데이터의 99% 가 0).
• 기존 방식의 한계:
  • 메모리 문제: 희소 데이터를 밀집 (Dense) 형식으로 저장하면 메모리 요구량이 기하급수적으로 증가하여 대규모 데이터셋을 처리할 수 없게 됩니다. (예: 실험에서 밀집 연산은 19TB 메모리가 필요했으나, 제안된 방식은 60GB 로 충분했습니다.)
  • 비효율성: 밀집 행렬 곱셈 알고리즘은 0 인 값에 대한 불필요한 계산을 수행하여 연산 및 통신 비용을 낭비합니다.
  • 기존 보안 희소 연산의 제한: 기존 연구들은 주로 2 인 간 (Two-party) 설정이나 데이터 소유자가 연산에 직접 참여해야 하는 비아웃소싱 (Non-outsourced) 설정에 국한되어 있어, 현대적인 ML 애플리케이션이 요구하는 수천 명의 데이터 소유자를 지원하는 아웃소싱 (Outsourced) 환경에는 적합하지 않습니다.

2. 방법론 (Methodology)

저자들은 비밀 공유 (Secret-sharing) 된 희소 행렬을 곱하기 위해 오블리비우스 정렬 (Oblivious Sorting) 을 기반으로 한 두 가지 새로운 MPC 알고리즘을 제안했습니다.

• 데이터 표현: 희소 벡터를 (좌표, 값) 튜플의 리스트 (COO 형식) 로 표현하여 0 인 값을 저장하지 않습니다.
• 핵심 원리:
  1. 정렬 기반 접근: 희소 벡터/행렬의 비영 (Non-zero) 요소들을 좌표 기준으로 오블리비우스 정렬합니다.
  2. 조건부 연산: 정렬된 리스트에서 인접한 요소들의 좌표가 일치하는지 확인하여 (비밀 공유된 값에 대한 조건부 연산), 일치하는 경우에만 값을 곱하고 합산합니다.
  3. 플레이스홀더 제거: 불필요한 더미 데이터를 제거하기 위해 'Shuffle-and-Reveal' 기법을 사용합니다.
• 주요 알고리즘:
  1. 희소 행렬 - 벡터 곱셈 (Matrix-Vector): 행 단위 정렬을 최적화하여 행의 수 ($n$) 에 비례하는 선형 의존성을 제거하고, 비영 요소의 수 ($nnz$) 에만 의존하도록 설계했습니다.
  2. 희소 행렬 - 행렬 곱셈 (Matrix-Matrix): 특히 $X^T X$ (상관 행렬) 계산과 같은 ML 작업에 최적화되었습니다. 각 열/행의 비영 요소 수를 기반으로 스칼라 곱셈을 수행한 후 정렬하여 결과를 집계합니다.
• 공공 지식 (Public Knowledge) 최소화: 효율적인 희소 연산을 위해 행별 비영 요소 수와 같은 '희소성 지표'가 필요하지만, 이는 민감할 수 있습니다. 이를 해결하기 위해 다음과 같은 기법을 제안합니다:
  • 행 익명화 (Row Anonymization): 행 순서를 무작위화하여 데이터 소유자와 행의 비영 개수를 연결하지 못하게 합니다.
  • 최대 행 패딩 (Max-row Padding): 모든 행을 최대 비영 개수로 패딩하여 상한선만 공개합니다.
  • 행렬 템플릿 (Matrix Templating): 데이터 분포의 분위수 (Quantiles) 를 기반으로 행렬을 여러 서브행렬로 나누어 패딩함으로써 불필요한 더미 데이터 생성을 최소화합니다.
  • 프라이버시 보존 추정: MPC 기반 분위수 추정 또는 차분 프라이버시 (Differential Privacy) 를 사용하여 템플릿 파라미터를 안전하게 추정합니다.

3. 주요 기여 (Key Contributions)

1. 새로운 보안 희소 곱셈 알고리즘: 아웃소싱된 MPC 설정 (데이터 소유자와 연산 서버 분리) 에서 작동하는 최초의 효율적인 희소 행렬 곱셈 알고리즘을 제안했습니다.
2. 메모리 및 통신 비용 획기적 개선:
   • 메모리: 밀집 연산으로 인한 메모리 오버플로우 (19TB) 를 방지하고 60GB 수준으로 줄였습니다.
   • 통신: 현실적인 문제 크기에서 밀집 연산 대비 최대 1000 배 ($\times 1000$) 까지 통신 비용을 절감했습니다.
3. 실제 ML 애플리케이션 검증: 기존 보안 알고리즘으로는 실행이 불가능했던 두 가지 실제 ML 애플리케이션을 구현하여 검증했습니다.
4. 프라이버시 강화 기법: 희소 연산에 필수적인 '공공 지식'을 최소화하고, 이를 프라이버시를 보호하면서 추정하는 3 가지 기법 (익명화, 패딩, 템플릿) 을 제안했습니다.

4. 실험 결과 (Results)

• 실험 환경: 188GB RAM 서버, 3-Party MPC 시뮬레이션 (MPyC 프레임워크 사용), 64-bit 고정 소수점 연산.
• 성능 비교:
  • 희소도 99.99% 기준: 행렬 - 행렬 곱셈 ($X^T X$) 에서 밀집 연산 대비 통신 비용이 1000 배 감소했습니다.
  • 확장성: 밀집 알고리즘은 행렬 크기가 10K 이상일 때 메모리 부족으로 실패했으나, 제안된 희소 알고리즘은 1M 열까지 확장 가능했습니다.
• 애플리케이션 사례:
  1. 추천 시스템 (Bookcrossing 데이터): 279K 사용자, 340K 책 데이터 (99.998% 희소). 밀집 방식은 메모리 오버플로우로 실행 불가였으나, 희소 방식은 평균 48 분에 실행 완료.
  2. 접근 제어 시스템 (Amazon 데이터): 15K 특징, 99.95% 희소. 공분산 행렬 추정을 위해 행렬 곱셈이 필요했으나, 밀집 방식은 메모리 부족, 희소 방식은 5 시간 내에 훈련 완료.

5. 의의 및 결론 (Significance)

• 실용적 가치: 이 연구는 MPC 를 활용한 프라이버시 보존 머신러닝 (PPML) 의 주요 병목 현상이었던 '희소 데이터 처리' 문제를 해결했습니다. 이를 통해 추천 시스템, 유전체 분석 등 대규모 희소 데이터를 다루는 실제 산업 응용이 MPC 환경에서 가능해졌습니다.
• 기술적 혁신: 기존 MPC 프레임워크에 최적화된 희소 연산 모듈을 제공하며, 메모리 효율성과 통신 효율성을 동시에 극대화했습니다.
• 프라이버시와 효율성의 균형: 필수적인 공공 지식 (희소성 정보) 을 공개해야 하는 딜레마를 해결하기 위해, 데이터의 실제 분포 특성을 활용한 템플릿 기법과 차분 프라이버시를 결합하여 프라이버시 손실을 최소화하면서도 알고리즘 효율성을 유지하는 방법을 제시했습니다.

이 논문은 MPC 기반 ML 의 확장성을 크게 높였으며, 오픈 소스 코드 (GitHub) 를 통해 실제 프레임워크로의 이식을 용이하게 하고 있습니다.