Secure and Parallel Determinant Computation for Large-Scale Matrices in Edge Environments

기술 요약: 엣지 환경에서 대규모 행렬을 위한 안전하고 병렬적인 행렬식 계산

문제 제기
사물인터넷 (IoT) 과 엣지 컴퓨팅의 급속한 도입은 집약적인 계산 작업을 처리하기 위한 확장 가능하고 에너지 효율적인 프레임워크에 대한 수요를 창출했습니다. 행렬식 계산 (MDC) 은 제어 시스템, 암호학, 머신러닝에서 중요한 연산입니다. 그러나 LU 분해와 같은 전통적인 알고리즘은 $O(n^3)$의 입방 계산 복잡성을 가지므로, 자원이 제한된 엣지 환경에서 대규모 행렬에 적용하기 어렵습니다. 또한, 동형 암호화 및 안전한 다자간 계산 (SMPC) 을 포함한 기존 안전한 위임 기술들은 상당한 계산 오버헤드를 초래하여 실시간 적용 가능성을 제한합니다. 일부 병렬 솔루션이 존재하지만, 이들은 주로 확장성 문제를 겪으며, 고정된 2 서버 모델에 의존하여 분산 엣지 자원을 효율적으로 활용하지 못하거나 과도한 패딩 없이 행렬 차원을 나누지 못할 경우 처리에 어려움을 겪습니다.

방법론
본 논문은 신뢰할 수 없는 엣지 서버의 임의 개수 ($N$) 에 걸쳐 프라이버시를 보호하는 MDC 를 가능하게 하는 안전한 병렬 행렬식 계산 (SPDC) 프레임워크를 제안합니다. 이 프레임워크는 프라이버시 보호 행렬 난독화 프로토콜 (PMOP), 안전한 병렬 계산 프로토콜 (SPCP), 결과 복구 및 검증 프로토콜 (RRVP) 의 세 가지 핵심 프로토콜을 통해 운영됩니다.

1. 복합 요소 왜곡 (CED): 프라이버시를 보장하기 위해 프레임워크는 두 가지 기법을 결합한 경량 암호화 방식을 사용합니다.

   • 요소별 난독화 (EWO): 행렬 요소들은 암호학적 시드에서 유도된 비밀 블라인딩 벡터를 사용하여 요소별 나눗셈 (EWD) 또는 요소별 곱셈 (EWM) 을 통해 변환됩니다.
   • 판트 회전 정리 (PRT): 시드를 기반으로 행렬 구조를 90°, 180°, 또는 270° 회전시키는 새로운 기하학적 변환입니다. PRT 는 행렬 크기를 4 로 나눈 나머지에 관계없이 행렬식의 절대값이 불변 (또는 부호가 예측 가능하게 변경) 되도록 보장하여, 기본 행렬식 속성을 변경하지 않으면서 구조적 패턴을 은폐합니다.

2. 병렬 LU 분해: 프레임워크는 $N \geq 2$개의 서버를 지원하도록 병렬 LU 분해 모델을 일반화합니다.

   • 행렬 확장: $N$으로 균등하게 나뉘지 않는 행렬의 차원을 처리하기 위해 행렬식을 보존하는 확장 기법이 적용됩니다. 이는 행렬식을 변경하지 않으면서 균형을 맞춘 분할을 보장하기 위해 행렬 크기를 최소한으로 확장합니다.
   • 단방향 통신: 알고리즘은 계단식 단방향 통신 패턴을 사용합니다. 각 서버는 중간 결과물을 바로 다음 하위 서버에게만 전송합니다. 이는 브로드캐스트 통신의 필요성을 제거하여 조정 오버헤드를 줄이고, 하위 서버들이 필요한 데이터를 수신하자마자 계산을 시작할 수 있도록 합니다.

3. 검증 및 복구:

   • 인증: 최소한의 클라이언트 부담으로 결과 무결성을 검증하기 위해, 논문은 두 가지 경량 인증 알고리즘인 Q2(확률적, 무작위 벡터를 사용한 스칼라 기반) 와 Q3(결정론적, 대각 요소를 사용한 스칼라 기반) 를 도입합니다. 이는 벡터 출력 방식을 대체하여 계산 부하를 줄입니다. 다중 서버 환경의 부동소수점 오차를 고려하기 위해 임계값 $\epsilon(N)$이 도입됩니다.
   • 복호화: 클라이언트는 시드와 검증된 LU 구성 요소를 사용하여 원래 행렬식을 복구하며, 사용된 회전 각도와 난독화 방법에 기반한 보정 인자를 적용합니다.

주요 기여

• 확장 가능한 N-서버 아키텍처: 이전 작업들이 2 개 서버로 제한된 것과 달리, SPDC 는 임의 개수의 신뢰할 수 없는 엣지 서버를 지원하여 자원 활용도와 확장성을 향상시킵니다.
• 새로운 난독화 메커니즘: 판트 회전 정리 (PRT) 와 요소별 난독화의 통합은 행렬식 속성을 보존하면서 수치 값과 행렬 구조 모두를 은폐함으로써 강력한 프라이버시 보장을 제공합니다.
• 효율적인 검증: 스칼라 기반 인증 알고리즘 (Q2 및 Q3) 의 도입은 기존 벡터 기반 검증 방식에 비해 클라이언트의 계산 오버헤드를 크게 줄입니다.
• 유연한 행렬 처리: 프레임워크는 짝수 및 홀수 크기의 정방 행렬 모두를 지원하며, 분할을 위해 엄격하게 필요할 때만 차원 확장을 적용하여 불필요한 계산을 최소화합니다.

결과 및 성능 분석
본 논문은 실험적 테스트가 아닌 이론적 성능 평가를 제시합니다.

• 계산 오버헤드: 제안된 프로토콜은 Seed 생성, 키 생성, 암호화, 인증, 복호화 단계 전반에 걸쳐 최신 프로토콜 (예: Lei 외, Fu 외, Liu 외, Gao 외) 보다 가장 낮은 전체 복잡성을 보여줍니다.
• 확장성: 병렬 계산의 복잡성은 $N$개의 서버에 작업 부하를 분산함으로써 $O(n^3)$에서 약 $O(n^2)$로 감소합니다.
• 보안성: 이 프레임워크는 원래 행렬이나 행렬식을 추론하려는 적대자에 대해 구별 불가능성을 제공합니다. 단방향 통신 패턴과 분산 암호화로 인해 클라이언트의 비밀 시드 없이는 서버의 어떤 부분집합도 원래 데이터를 재구성할 수 없으므로, 결탁 공격에 견고합니다.
• 배포 적합성: 이 프레임워크는 이전의 클라우드 중심 또는 고정 토폴로지 솔루션과 달리 자원이 제한된 장치와 이기종 서버 구성을 지원하는 엣지 환경을 명시적으로 대상으로 설계되었습니다.

의의
본 논문은 SPDC 프레임워크가 분산 엣지 지원 시스템을 위한 프라이버시 보호 및 안전한 MDC 의 중요한 과제를 해결한다고 주장합니다. 효율성, 확장성, 강력한 프라이버시 메커니즘을 결합함으로써 실시간 안전한 계산을 위한 실용적인 솔루션을 제공합니다. 이 프레임워크는 동형 암호화나 SMPC 에서 흔히 발견되는 보안과 성능 간의 트레이드오프를 제거하여, 대규모 행렬 연산이 신뢰할 수 없는 분산 인프라에서 안전하게 수행되어야 하는 IoT, 제어 시스템, 머신러닝 응용 분야에 적합합니다. 저자들은 이 작업을 대규모 분산 컴퓨팅 시나리오에서의 실용적이고 효율적이며 안전한 행렬식 위임을 위한 새로운 벤치마크로 위치시킵니다.