기술 요약: 선, 악, 그리고 추악함: 워터마크, 전이 가능한 공격 및 적대적 방어에 대한 메타 분석

문제 정의

본 논문은 백도어 기반 워터마크(모델 소유권 검증에 사용됨)와 적대적 방어(입력 섭동에 대한 강건성을 보장하기 위해 사용됨) 사이의 근본적인 트레이드오프를 다룹니다. 기존의 경험적 연구들은 적대적 공격에 강건한 모델이 적대적 공격에 취약해질 수 있고, 그 반대의 경우도 발생할 수 있음을 관찰해 왔으나, 이들 사이의 상호작용에 대한 공식적인 이론적 이해는 부족했습니다.

저자들은 이 지형을 **검증자(Alice)**와 증명자(Bob) 사이의 상호작용 프로토콜로 정식화하며, 각자의 계산 자원을 고려합니다. 핵심 질문은 다음과 같습니다: 주어진 모든 학습 작업에 대해 다음 세 가지 속성 중 반드시 존재하는 것은 무엇인가?

1. 워터마크(Watermark): 제거 불가능하고 탐지 불가능한 백도어를 삽입하는 메커니즘.
2. 적대적 방어(Adversarial Defense): 데이터 분포와 구별 불가능한 적대적 예제를 탐지하고 거부하는 메커니즘.
3. 전이 가능한 공격(Transferable Attack): 데이터 분포와 구별 불가능하면서도 모든 효율적인 방어자를 속일 수 있는 효율적인 알고리즘.

본 논문은 이 세 가지 옵션이 '삼분법(trichotomy)'을 형성하며, 공격자와 방어자의 계산적 제약 조건에 따라 이 중 적어도 하나는 반드시 존재해야 한다고 주장합니다.

방법론 및 정식화

1. 계산 모델

저자들은 학습 작업과 에이전트를 크기 매개변수 $n$에 의해 인덱싱된 **불리언 회로(Boolean circuits) 군(families)**을 사용하여 모델링합니다. 이는 계산 복잡도 이론에서 표준적인 방식으로, 단순히 실행 시간뿐만 아니라 계산 자원(회로 크기)에 대한 미세한 제어를 가능하게 합니다.

• 학습 작업 ($L$): 쌍 $(D_n, h_n)$에 대한 분포들의 시퀀스로 정의됩니다. 여기서 $D_n$은 데이터 분포이고 $h_n$은 정답 레이블링 함수입니다.
• 에이전트: 공격자/워터마크 삽입자 Alice와 방어자/워터마크 제거자 Bob은 각각 크기 경계 $S_A(n)$와 $S_B(n)$를 가진 회로로 표현됩니다.

2. 세 가지 체계의 정의

논문은 세 가지 개념을 다음과 같은 상호작용 프로토콜로 정식화합니다:

• 워터마크 (정의 3): 낮은 오차를 가진 분류기 $f$와 쿼리 집합 $x$를 생성하는 효율적인 알고리즘입니다.
  • 정확성(Correctness): $f$는 낮은 오차를 가집나다.
  • 유일성(Uniqueness): 유사한 자원을 가진 증명자(워터마크를 사용하지 않은 자)는 $x$에 대해 낮은 오차의 답을 생성할 수 없습니다.
  • 제거 불가능성(Unremovability): 제한된 자원($S_B$)을 가진 증명자는 $x$에 대해 낮은 오차의 답을 생성할 수 없습니다.
  • 탐지 불가능성(Undetectability): 쿼리 $x$는 데이터 분포 $D_n$과 계산적으로 구별 불가능합니다.
• 적대적 방어 (정의 4): 분류기 $f$와 탐지 비트 $b$를 생성하는 효율적인 알고리즘입니다.
  • 정확성(Correctness): $f$는 낮은 오차를 가집니다.
  • 완전성(Completeness): 자연스러운 입력($x \sim D_n$)은 플래그가 지정되지 않습니다 ($b=0$).
  • 건전성(Soundness): 만약 공격자($S_A$)가 높은 오차를 유발하는 입력을 제공하더라도, 해당 입력이 $D_n$과 구별 불가능하다면 방어는 이를 플래그 지정해야 합니다 ($b=1$).
• 전이 가능한 공격 (정의 5): 쿼리 $x$를 생성하는 효율적인 알고리즘입니다.
  • 전이 가능성(Transferability): 제한된 자원을 가진 모든 증명자에게 대하여, 쿼리 $x$는 높은 오차를 유발합니다.
  • 탐지 불가능성(Undetectability): 쿼리 $x$는 $D_n$과 구별 불가능합니다.
  • 참고: 표준적인 전이 가능성(모델 유사성에 의존함)과 달리, 이 정의는 아키텍처와 상관없이 모든 효율적인 방어자를 속일 수 있는 능력을 요구합니다.

3. 게임 이론적 프레임워크

핵심 이론 엔진은 Alice(워터마크 삽입 시도)와 Bob(워터마크 제거/공격 탐지 시도) 사이의 **영합 게임(zero-sum game)**입니다.

• 게임의 보상은 워터마크가 성공적으로 제거되었는지 또는 공격이 성공적으로 탐지되었는지에 따라 달라집니다.
• Min-Max 정리와 대규모 영합 게임에 관한 결과(Lipton and Young, 1994)를 사용하여, 저자들은 이 게임이 내쉬 균형(Nash Equilibrium)을 가짐을 논증합니다.
• 이 균형의 값은 어떤 체계가 존재하는지를 결정합니다:
  • 게임의 값이 높으면, 적대적 방어가 존재합니다.
  • 게임의 값이 낮으면, 워터마크 또는 전이 가능한 공격이 존재합니다.

주요 기여 및 결과

1. 주요 정리 (삼분법)

정리 1: 회로 복잡도 $S(n)$를 가지며 오차 $\epsilon$으로 학습 가능한 모든 학습 작업 $L$에 대하여, 다음 중 적어도 하나가 존재한다:

• 워터마크 (방어자 크기 $o(\sqrt{S(n)/\log S(n)})$인 경우).
• 적대적 방어 (방어자 크기 $O(S(n))$인 경우).
• 전이 가능한 공격 (공격자 크기 $S(n)$인 경우).

이 결과는 보안이 확보된 워터마크, 모든 효율적인 공격자에 대한 강건한 방어, 그리고 전이 가능한 공격의 부재를 동시에 갖는 것이 불가능함을 의미합니다. 즉, 특정 자원 제약 하에서 하나의 존재는 다른 것들의 존재를 배제합니다.

2. 전이 가능한 공격과 암호학

논문은 **완전 동형 암호(Fully Homomorphic Encryption, FHE)**를 기반으로 한 특정 학습 작업을 구축하여 전이 가능한 공격의 존재를 입증합니다.

• 구성: 이 작업은 FHE가 추가된 "원 위의 직선(Lines on a Circle)" 학습 문제를 포함합니다. 데이터 분포는 "명확한(clear)" 샘플과 "암호화된" 샘플의 혼합입니다.
• 메커니즘: 공격자(Alice)는 명확한 샘로에 대한 분류기를 학습합니다. 그 후, 그녀는 무작위 명확한 점이거나 결정 경계 근처의 암호화된 점인 쿼리를 생성합니다. FHE의 보안성 덕분에, 이 암호화된 점들은 효율적인 공격자에게 무작위 암호화된 점들과 구별 불가능합니다.
• 결과: 공격자는 (경계를 학습하기 위해 계산 자원이 부족한) 모든 방어자에 대해 높은 오차율을 강제할 수 있는 동시에, 데이터 분포와의 구별 불가능성을 유지할 수 있습니다.
• 시사점: 전이 가능한 공격의 존재는 EFID 쌍(Efficiently samplable, statistically Far, computationally Indistinguishable)이라는 암호학적 프리미티브의 존재를 함의합니다. 따라서 전이 가능한 공격은 계산적으로 복잡한 작업에서만 존재할 수 있습니다.

3. 제한된 VC-Dimension 결과

논문은 VC-dimension이 유계된 작업들을 분석합니다:

• 적대적 방어: VC-dimension이 유계된 작업의 경우, 방어자가 VC-dimension에 대한 다항식 자원을 가진다면, (계산 능력이 무한한 공격자에 대해서도) 적대적 방어가 존재합니다. 이는 이러한 환경에서 전이 가능한 공격이 존재할 수 없음을 의미합니다.
• 워터마크: 유계된 VC-dimension 작업의 하위 클래스에 대해서는, "빠른" 공격자(방어자보다 엄격히 적은 자원을 가진 공격자)에 대해 안전한 워터마크가 존재합니다. 이 특정 영역에서는 워터마크와 적대적 방어가 공존할 수 있습니다.

의의 및 주장

본 논문은 워터마크, 방어, 공격 사이의 트레이드오프를 이해하기 위한 최초의 모델 불가지론적(model-agnostic)이고 정량적인 프레임워크를 제공한다고 주장합니다.

1. 트레이드오프의 정식화: 경험적 관찰을 넘어, 공격자와 방어자의 상대적 계산 자원에 의해 결정되는 보안 지형에 대한 엄밀한 이론적 증명을 제공합니다.
2. 제3의 선택지: 표준적인 적대적 예제와 구별되는, 데이터와 구별 불가능하지만 모든 효율적인 방어자를 속이는 전이 가능한 공격을 트레이드오프의 필수적인 세 번째 옵션으로 식별했습니다.
3. 암호학적 연결: 전이 가능한 공격의 존재와 암호학적 난해함(특히 EFID 쌍의 존재) 사이의 직접적인 연결을 확립했습니다. 이는 "완벽한" 강건함(전이 가능한 공격이 없는 상태)이 암호학적으로 계산하기 어려운 작업에서는 불가능함을 시사합니다.
4. 자원 할당 규칙(Rule of Thumb): 저자들은 실용적인 휴리스틱을 제안합니다: 만약 공격자의 계산 예산이 $T$라면, 방어자에게 $T^2$의 자원을 할당하는 것이 (방어가 존재한다면) 방어를 구축하기에 충분합니다. 반대로, $T^2$ 예산을 가진 방어가 실패한다면, 이는 해당 작업이 전이 가능한 공격을 허용함을 시사하며, 이는 다시 해당 프레임워크 내에서 보안 워터마크의 가능성을 배제합니다.

결론적으로, 이 논문은 워터마크, 방어, 공격 사이의 상호작용이 단순히 모델 아키텍처나 데이터셋의 문제가 아니라, 근본적으로 학습 작업의 계산 복잡도와 관련된 당사자 간의 자원 격차의 함수임을 밝히고 있습니다.