Stability Buys Time: A Re-Keying Game for Encrypted Multi-Agent Control

기술 요약: 안정성이 시간을 벌어준다: 암호화된 다중 에이전트 제어를 위한 재키잉(Re-Keying) 게임

문제 정의
본 논문은 완전 동형 암호(FHE)를 사용하는 암호화된 다중 에이전트 제어 시스템의 치명적인 취약점을 다룬다. FHE는 클라우드 서버가 평문을 보지 않고도 암호화된 데이터를 통해 함대(fleet)를 조율할 수 있게 해주지만, 실수 기반 제어에 사용되는 특정 스킴인 CKKS는 보안 역설을 야기한다. CKKS는 복호화 시 노이즈($z + e/\Delta$)가 포함된 값을 반환하는 근사적 스킴이다. 제어 루프에서 액추에이터는 명령을 실행하기 위해 반드시 복호화를 수행해야 하므로, 이러한 노이즈가 섞인 복호화는 피할 수 없는 과정이다. 최근의 암호 해독 연구에 따르면, 이러한 복호화 결과물을 관찰함으로써 비밀 키를 재구성할 수 있음이 밝혀졌다.

기존 문헌들은 이 문제를 개별적으로 다루었다: FHE 보안은 정적(static)으로 분석되었고(단일 복호화를 위한 노이즈 플러딩), 암호화된 제어는 "정직하지만 호기심 많은(honest-but-curious)" 클라우드를 가정하며, 게임 이론적 지속적 위협 모델은 암호 체계 자체까지 침투하지는 않았다. 본 논문은 함대와, 시간이 지남에 따라 발생하는 불가피한 복호화 누출을 악용하는 고등 지속 위협(APT) 사이의 상호작용을 모델링하며, 정적 방어만으로는 장기 미션에서 불충분하다고 주장한다.

방법론
저자들은 암호화된 제어 루프의 보안을 협력적인 함대 방어자와 APT 공격자 사이의 2단계 게임으로 모델링한다:

1. 1단계: 수동적 정찰 (정적 게임)

   • 공격자는 암호화된 트래픽을 도청하고 에이전트 일부의 복호화된 명령을 관찰한다.
   • 방어자는 키를 은닉하기 위해 복호화된 값에 추가할 정적 "노이즈 플러딩" 수준($\sigma$)을 결정한다.
   • 이 단계는 방어자가 먼저 $\sigma$를 결정하는 스택켈버그 게임(Stackelberg game)으로 모델링된다. 공격자는 노이즈가 "디플러딩(de-flooded)"되어 키를 회복할 수 있을 때까지 관찰을 축적한다.
   • 저자들은 시스템이 공유된 키 아래에서 단일 암호문을 인플레이스(in-place)로 진화시키기 때문에, 부트스트래핑(노이즈 재생성)이 키나 축적된 누출을 초기화하지 못하며, 누출은 매 제어 주기마다 독립적인 관측치 하나가 축적되는 속도로 발생한다고 규정한다.

2. 2단계: 능동적 조작 (동적 타이밍 게임)

   • 공격자가 행동하기로 결정하면, 키 회복을 가속화하거나 함대를 교란하기 위해 암호화된 연산을 조작한다.
   • 이러한 조작은 제어 루프에 섭동(perturbation)을 일으키며, 이는 모델 기반 제어 잔차($\chi^2$ 검정으로 탐지됨)로 나타난다.
   • 방어자의 적응적 대응은 **재키잉(re-keying)**이다: 새로운 비밀 키를 생성하고 함대의 상태를 재암호화한다. 이는 공격자의 축적된 누출 장부를 제로로 리셋한다.
   • 이 단계는 "FlipIt" 스타일의 탐지-회피 타이밍 게임으로 모델링된다. 방어자는 재키잉 간격($T$)을 선택하고, 공격자는 키 회복 속도를 최대화하면서 탐지를 피하기 위해 포지션(수동적, 은밀한 능동, 또는 공격적 능동)을 선택한다.

주요 기여

• 2단계 APT 모델: 본 논문은 암호화된 다중 에이전트 루프의 보안을 두 단계 게임(수동적 정찰 후 능동적 조작)으로 정식화하여, 탐지 불가능한 누출 축적과 탐지 가능한 조작 단계를 분리한다.
• 재키잉 vs 부트스트래핑: 저자들은 부트스트래핑(동일한 키 아래에서 노이즈를 재생성함)과 재키잉(키 자체를 교체함)을 구분한다. 재키잉만이 공격자의 축적된 지식을 리셋한다는 것을 증명하며, 이를 필수적인 보안 레버로 제시한다.
• 정밀도 의존적 영역(Regimes): 분석은 FHE 정밀도($\Delta$), 제어 정확도(최대 허용 노이즈 플러딩 $\sigma_{max}$에 의해 제한됨), 그리고 재키링 간격 사이의 삼각 관계를 식별한다. 이는 세 가지 뚜렷한 운영 영역으로 이어진다:
  1. 불안전한 바닥(Insecure Floor): 정밀도가 너무 낮아, 최대 플러딩을 적용하더라도 단일 주기 내에 키 회복을 막을 수 없다.
  2. 재키링 윈도우(Re-Key Window): 정밀도가 특정 범위 내에 있어 정적 플러딩은 불충분하지만, 재키링이 가능한 상태이다. 이것이 "효율적인 보안 지점"이다.
  3. 정적 충분성 천장(Static Sufficiency Ceiling): 정밀도가 충분히 높아 정적 노이즈 플러딩만으로도 미션 기간 동안 키를 보호할 수 있어, 재키링이 불필요한 상태이다.
• 토폴로지 의존적 간격: 최적의 재키링 간격은 네트워크 토폴로지의 제어 이론적 취약성에 의해 결정된다. 더 취약한 토폴로지(예: 한계 안정 상태의 토러스)는 잘 연결된 토폴로지(예: 완전 그래프)보다 더 빈번한 재키링을 요구한다.

결과
저자들은 OpenFHE 라이브러리를 사용하여 세 가지 토폴로지(링, 토러스, 완전 그래프)에 대해 9개 에이전트 함대에 이 프레임워크를 구현하였다.

• 제어 허용 오차: 최대 허용 노이즈 플러딩($\sigma_{max}$)은 폐루프 스펙트럼 반지름과 직접 연결된다. 가장 취약한 토러스 토폴로지는 가장 적은 노이즈($\sigma_{max} \approx 0.3$)를 허용하는 반면, 완전 그래프는 가장 많은 노이즈($\sigma_{max} \approx 0.75$)를 허용한다.
• 누출률: 실험 결과, 각 주기가 동일한 키 아래에서 새로운 측정 제약 조건을 도입하므로, 폐루프 수축률과 관계없이 누출은 주기당 하나의 관측치 속도로 축적됨을 확인했다.
• 영역 매핑: 정밀도가 $\Delta \approx 2^{37}$일 때, 시스템은 "재키링 윈도우"에 진입한다.
  • 토러스 (가장 취약함)는 "경계(Vigilant)" 간격(약 200 주기마다 재키링)이 필요하다.
  • 링은 "보통(Moderate)" 간격(~600 주기)이 필요하다.
  • 완전 그래프는 "느긋한(Lazy)" 간격(~1500 주기)을 허용한다.
• 공격자 행동: 모델 기반 탐지기는 "공격적" 조작(높은 크기의 공격)을 효과적으로 차단하여, 합리적인 공격자가 "은밀한" 상태를 유지하도록 강제한다. 방어자의 최적 전략은 탐지되기 전에 은밀한 공격자가 회복 임계치에 도달하는 것을 방지할 수 있는 가장 "느긋한" 간격으로 재키링을 수행하는 것이다.

의의 및 주장
본 논문은 근사적 암호 체계의 보안은 근본적으로 방어자의 움직임이 암호 체계 자체의 갱신 메커니즘(재키링)인 동적 게임이라고 주장한다.

• 안정성이 시간을 벌어준다: 제어 이론적 안정성이 암호학적 보안 간격을 결정한다는 것이 본 논문의 핵심이다. 더 안정적인 시스템(높은 $\sigma_{max}$)은 재키링 이벤트 사이의 간격을 더 길게 가져갈 수 있게 한다.
• 효율성의 "윈도우": 저자들은 효율적인 보안 운영 지점이 정적 플러딩은 실패하지만 재키링은 가능한 제한된 정밀도 구간에 있다고 주장한다. 이는 높은 정밀도가 항상 더 좋다는 가설에 도전하며, 특정 정밀도 범위에서 운영하는 것이 재키링 비용을 최소화하면서 보안을 유지하는 방법임을 시사한다.
• 제어를 넘어: 이 프레임워크는 반복적으로 복호화하여 행동해야 하는 모든 시스템에 적용될 수 있으며, 재키링 간격을 지속적 누출에 대한 동적 방어책으로 위치시킨다.

본 논문은 분석이 모든 에이전트를 완전히 관찰($\kappa = M$)하고 협력적인 함대 방어자가 있다는 가정을 전제로 한다는 점을 명시하며 범위를 겸손하게 설정하였다. 부분 관찰 임계값 및 전략적/부패된 에이전트에 대한 분석을 향후 과제로 남겨두었다.