기술 요약: 치환된 퍼즐로부터의 개선된 의사 난수 코드(Pseudorandom Codes)

문제 정의

AI 생성 콘텐츠의 확산은 출처를 식별하기 위한 강력한 워터마킹 체계를 필요로 한다. 최근 연구는 **의사 난수 코드(Pseudorandom Codes, 이하 PRC)**가 강력한 강건성(robustness)과 품질 보증을 갖춘 워터마킹 체계와 동등하다는 것을 입증했다. PRC는 비밀 키 암호화 방식으로서, 암호문이 균등 분포(uniform distribution)와 계산적으로 구별 불가능하며(탐지 불가능성/품질 보장), 복호화 알고리즘이 높은 오류율을 허용하는(강건성 보장) 구조를 가진다.

그러나 기존의 PRC 구성 방식들은 세 가지 결정적인 한계점을 가지고 있다:

1. 취약한 보안성: 모든 기존 구성은 준다항 시간(quasipolynomial-time) 구별 공격에 취약하다. 이들은 $(\log n)$-희소 구조(sparse structures)를 숨기는 데 의존하는데, 이는 브루트 포스 탐색 공격을 허용한다.
2. 제한된 알파벳 강건성: 일부 구성은 편집 오류(edit errors)를 처리할 수 있지만, 다항 크기의 알파벳을 요구한다. 대규모 언어 모델(LLM)에서 나오는 실제 텍스트는 낮은 엔트로피(단어당 약 1비트)를 가지므로, 상수 크기(이상적으로는 이진) 알파벳에 대해서도 편집에 강건한 PRC가 필요하다.
3. 취약한 적대적 모델: 기존 연구들은 적대자가 계산적으로 유한하거나 탐지 키를 보유하지 않은 경우를 가정했다. PRCs가 탐지 키를 보유한 계산적으로 무제한인 적대자에 대해서도 강건성(강력-적응적 강건성, strongly-adaptive robustness)을 유지할 수 있는지 여부는 불분И명했다.

핵심적인 미결 과제는 단일 구성이 부서브지수적(subexponential) 보안, 이진 알파벳에 대한 편집 강건성, 그리고 키를 보유한 적대자에 대한 강건성을 동시에 달성할 수 있는가 하는 점이었다.

방법론

1. 치환된 코드 추측 (The Permuted Codes Conjecture)

저자들은 새로운 계산적 어려움 가정인 **치환된 코드 추측(Permuted Codes Conjecture)**을 도입한다. 이 추측은 "뒤섞인(scrambled)" 노이즈가 섞인 코드워드(codeword)의 분포가 균등 분포와 계산적으로 구별 불가능하다고 상정한다.

분포 $D_{n,\Sigma,C,\eta,T}$는 다음과 같이 생성된다:

1. 무작위 인덱스 치환 $\sigma \in S_n$과 알파벳 치환 $\pi_1, \dots, \pi_n \in S_\Sigma$를 샘플링한다.
2. 선형 코드 $C \subseteq \Sigma^n$로부터 $T$개의 코드워드 $c_1, \dots, c_T$를 균등하게 샘플링한다.
3. 각 코드워드에 대해 인덱스를 $\sigma$로 치환하고, 각 위치의 심볼을 $\pi_j$로 치환하여 $\hat{c}$를 생성한다.
4. $\hat{c}$에 치환 채널(substitution channel)과 노이즈율 $\eta$를 적용한다.

핵심 통찰: 저자들은 이 추측이 치환된 퍼즐 추측(Permuted Puzzles Conjecture)(이전에 이중 효율적 사적 정보 검색(PIR)을 위해 사용되었던 것)에 의해 함의됨을 증명한다. 저자들은 상수 크기의 알파벳과 높은 듀얼 거리(dual distance)를 가진 코드의 경우, 로그 개수의 샘플이 통계적으로 균등함을 보여주는 통계적 증거를 제공한다. 또한, 세 가지 구성 요소 모두(인덱스 치환, 알파벳 치환, 노이즈)가 필수적임을 입증한다. 만약 "토이(toy)" 버전처럼 알파벳 치환을 생략한다면, 저차 다항식 공격(low-degree polynomial attacks)을 통해 리드-솔로몬(Reed-Solomon) 코드가 구별 가능해진다.

2. 편집 강건한 PRC의 구성

이진 알파벳에 대한 편집 강건성을 달み하기 위해, 저자들은 폴디드 리드-솔로몬(Folded Reed-Solomon, FRS) 코드에 기반한 PRC를 구성한다.

• 인코딩: 비밀 키는 치환들과 원타임 패드(one-time pad)로 구성된다. 인코딩을 위해, 기저 코드로부터 무작위 코드워드를 추출하여 치환하고, 노이즈를 가한 뒤, 심볼의 일부를 선택한다. 결정적으로, 선택된 각 심볼은 심볼 값과 그 인덱스 모두를 포함하는 이진 문자열로 출력된다.
• 복호화: 복호기는 삽입/삭제에 의해 오염될 수 있는 문자열을 받는다. 복호기는 특정 길이의 모든 부분 문자열을 스캔하며, 잠재적인 $(index, symbol)$ 쌍을 복구하기 위해 편집 거리를 "브루트 포스" 방식으로 시도한다. 이러한 후보들은 각 위치에 대한 리스트를 형성한다. 그 후, 원래의 코드워드를 복구하기 위해 해당 리스트들에 대해 기저 코드의 **리스트 복구 알고리즘(list-recovery algorithm)**이 적용된다.
• 강건성 메커니즘: 출력에 인덱스를 포함함으로써, 복호기는 삽입이나 삭제에 의해 위치가 이동되더라도, 편집 수가 제한되어 있다면 올바른 심볼을 복구할 수 있다. FRS 코드를 사용하면 알파벳이 사실상 이진(변환을 통해)이더라도 상수 비율의 편집을 견딜 수 있다.

3. 워터마킹 변환

Christ와 Gunn(CRYPTO '24)이 확립한 프레임워크를 사용하여, 저자들은 자신들의 PRC를 자기회귀(autoregressive) 언어 모델을 위한 워터마킹 체계로 변환한다. 이 체계는 PRC 코드 비트에 따라 토큰 선택을 편향시켜 워터마크가 삽입된 텍스트를 생성한다. 편집에 대한 PRC의 강건성은 모델이 충분한 토큰당 엔트로피를 가질 때, 워터마크가 적대적인 텍스트 수정으로부터 살아남는 능력으로 직접 연결된다.

주요 기여 및 결과

1. 세 가지 속성을 갖춘 새로운 PRC 구성

본 논문은 다음 세 가지를 동시에 만족하는 최초의 PRC 구성을 제시한다:

• 그럴듯한 서브지수적 보안성: 치환된 코드 추측에 기반하며, 이는 준다항 시간 공격에 취약한 희소 구조를 피한다.
• 이진 알파벳 편집 강건성: 이 구성은 이진 알파벳 상에서의 상수 비율 최악의 경우 편집(삽입, 삭제, 치환)을 허용한다.
• 강력-적응적 강건성: 이 체계는 탐지 키를 알고 있는 계산적으로 무제한인 적대자에게도 강건성을 유지한다.

2. 이론적 보증

• 정리 5.6: 치환된 코드 추측 하에서, 서브지수적 보안을 가지며 상수 비율의 편집에 강력-적응적인 이진 알파벳 PRC가 존재한다.
• 정리 5.14: 폴디드 리드-솔로몬 코드를 위한 변형된 추측 하에서, 매우 낮은 상수 수준의 토큰당 엔트로피율 $\alpha$만을 필요로 하면서 상수 비율의 편집($\tilde{O}(\alpha^7)$)에 강건한, 탐지 불가능한 LLM 워터마크가 존재한다. 이는 현실적인 엔트로피 제약 조건 하에서 최악의 편집에 대해 탐지 불가능하면서도 강건한 최초의 워터마크이다.

3. 암호 분석 및 증거

• 알파벳 치환의 필요성: 저자들은 알파벳 치환이 없다면, 인덱스 치환과 노이즈가 있더라도 리드-솔로몬 코드가 균등 분포로부터 효율적으로 구별됨을 증명한다.
• 기존 연구에 대한 준다항 시간 공격: 저자들은 심하게 희소한 구조나 노이즈 허용 술어(noise-tolerant predicates)에 의존하는 광범위한 기존 PRC 구성들이 본질적으로 준다항 시간 공격에 취약함을 보여준다.
• 통계적 균등성: 저자들은 상수 크기의 알파벳에 대해, 소수의 치환된 코드워드들이 통계적으로 균등 분포와 구별 불가능함을 증명하여 추측의 타당성에 대한 증거를 제공한다.

의의

본 논문은 이전에 상호 배타적이거나 달성 불가능하다고 여겨졌던 PRC의 세 가지 바람직한 속성 사이의 긴장을 해결한다고 주장한다. 치환된 코드 추측을 공식화하고 폴디드 리드-솔로몬 코드를 활용함으로써, 저자들은 다음과 같은 워터마킹 체계의 이론적 토대를 마련했다:

1. 탐지 불가능함: 실제 언어 모델의 출력과 구별할 수 없다.
2. 강건함: 텍스트에 대한 적대적 편집(삽입/삭제)을 견뎌낼 수 있다.
3. 안전함: 탐지 키를 가진 공격자로부터도 강건성을 유지하여, 강건성을 해치지 않으면서 공적 검증(public verification)을 가능하게 한다.

이 연구는 이러한 속성을 달성하기 위해서는 희소 구조를 넘어, 치환되고 노이즈가 섞인 코드워드를 무작위 문자열과 구별하는 것의 어려움을 받아들여야 함을 보여준다. 비록 보안이 새로운 추측에 의존하고 있으나, 저자들은 이 추측의 타당성에 대한 강력한 증거를 제공하며, 이를 통해 실제적인 AI 생성 텍스트를 위한 강건한 워터마크의 존재를 입증한다.