🔢 mathematics

LLM-Text Watermarking based on Lagrange Interpolation

이 논문은 적대적 공격으로 인해 텍스트가 심하게 삭제되더라도 암호화 해시 함수로 생성된 $x$ 좌표와 임베딩된 $f(x)$ 값을 활용하여 라그랑주 보간법을 기반으로 한 최대 공선점 (MCP) 문제를 해결함으로써 LLM 생성 텍스트에서 다중 비트 저자 신원을 효과적으로 복원하는 워터마킹 기법을 제안합니다.

원저자: Jarosław Janas, Paweł Morawiecki, Josef Pieprzyk

게시일 2026-02-27

📖 3 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Jarosław Janas, Paweł Morawiecki, Josef Pieprzyk

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

이 논문은 **"거대 언어 모델 (LLM, 예: 챗봇) 이 쓴 글이 진짜 인간이 쓴 것인지, 아니면 AI 가 쓴 것인지, 그리고 누가 썼는지 증명하는 새로운 방법"**을 소개합니다.

기존의 방법들은 글 속에 보이지 않는 '디지털 지문'을 심는 방식이었는데, 이 논문은 그 지문을 **수학적인 '직선'**으로 만들어 심는 아주 똑똑한 방식을 제안합니다.

이해하기 쉽게 세 가지 핵심 비유로 설명해 드릴게요.

1. 핵심 아이디어: "보이지 않는 직선을 그리다"

상상해 보세요. AI 가 글을 쓸 때, 그 글자 하나하나에 아주 미세한 신호를 숨깁니다. 이 신호는 마치 수학 문제의 답과 같습니다.

비유: AI 가 글을 쓸 때, 보이지 않는 직선을 그리는 중이라고 생각하세요.
작동 원리:
1. 우리는 미리 정해진 직선 하나를 생각합니다. (예: $y = 2x + 1$ )
2. AI 가 글을 쓰면서, 글자 (토큰) 들을 선택할 때 이 직선 위에 있는 점들을 모으도록 유도합니다.
3. 예를 들어, 1 번째 글자는 $x=1$ 일 때의 점, 10 번째 글자는 $x=10$ 일 때의 점처럼, 글자 순서에 따라 직선 위의 특정 좌표 $(x, y)$ 를 선택하게 됩니다.
4. 결과적으로, AI 가 쓴 글자 속에 이 직선을 구성하는 점들이 숨겨져 있는 것입니다.

2. 왜 '라그랑주 보간법'이 필요한가요? (점 퍼즐 맞추기)

문제는 AI 가 글을 쓸 때, 혹은 누군가 글을 수정할 때 이 점들이 실수나 고의적인 변조로 인해 직선에서 벗어날 수 있다는 것입니다.

상황: 직선 위에 있어야 할 점 100 개가 있는데, 30 개는 원래 자리에 있고, 70 개는 엉뚱한 곳에 흩어져 있습니다.
해결책 (라그랑주 보간법):
- 이 논문은 라그랑주 보간법이라는 수학적 도구를 사용합니다.
- 비유: 흩어진 점들 중에서 **"가장 많은 점들이 일직선으로 이어져 있는 구간"**을 찾아내는 게임입니다.
- 수학적으로 이 문제를 '최대 공선점 (Maximum Collinear Points)' 문제라고 부릅니다.
- 만약 흩어진 점들 중 30 개가 여전히 완벽한 직선을 이루고 있다면, 우리는 그 직선의 방정식을 다시 계산해 낼 수 있습니다. 그 직선의 방정식 (예: $y=2x+1$ ) 이 바로 **수신자 (Watermark)**입니다.

3. 적의 공격을 막는 '강한 방패'

악당 (해커) 이 이 지문을 지우려고 글을 수정한다고 가정해 봅시다.

단어 바꾸기 (치환): 악당이 글자를 몇 개 바꾸더라도, 직선 위의 점들이 조금씩 흔들릴 뿐, 직선 전체를 망가뜨리기는 어렵습니다. 여전히 직선을 찾을 수 있습니다.
글자 추가/삭제 (동기화 파괴): 악당이 글자를 중간에 끼워 넣거나 지우면, 점들의 순서가 깨져서 직선이 무너질 수 있습니다. 하지만 이 논문은 오류 수정 기술을 추가했습니다.
- 비유: 점들이 조금 흔들려도, "아마도 원래는 여기 있었을 거야"라고 추측해서 점들을 다시 맞춰주는 과정을 거칩니다.
- 덕분에 악당이 글을 조금만 건드리더라도, 직선을 찾아내어 "이 글은 AI 가 썼다"는 것을 증명할 수 있습니다.

요약: 이 기술이 왜 중요한가요?

진실 확인: "이 뉴스 기사는 AI 가 쓴 거야, 인간이 쓴 거야?"를 쉽게 가려낼 수 있습니다.
저작권 보호: "이 글은 내가 AI 를 통해 썼어"라고 증명할 수 있어 표절이나 가짜 뉴스 확산을 막을 수 있습니다.
강력함: 글을 조금씩 수정하거나 다듬더라도 (예: 요약, 번역, 오타 수정), 숨겨진 직선 (지문) 은 살아남아 발견됩니다.
간단함: AI 모델 자체를 다시 훈련시킬 필요 없이, 글을 생성할 때만 살짝 조절하면 됩니다.

한 줄 결론:
이 논문은 AI 가 쓴 글 속에 수학적인 '직선'을 숨겨두고, 나중에 그 직선을 찾아내어 AI 의 흔적을 증명하는 똑똑한 '디지털 지문' 기술을 개발했습니다. 마치 보이지 않는 실로 꿰어진 구슬들 중에서 가장 긴 직선 부분을 찾아내어 비밀을 해독하는 것과 같습니다.

1. 문제 제기 (Problem Statement)

대규모 언어 모델 (LLM) 의 급속한 발전으로 인해 생성된 텍스트의 출처를 추적하고, 허위 정보 (misinformation), 가짜 뉴스, 표절, 그리고 AI 가 작성한 내용을 인간이 작성한 것처럼 속이는 행위를 식별하는 것이 시급한 과제가 되었습니다. 기존 워터마킹 기술들은 주로 이진 신호 (워터마크 유무) 에 국한되거나, 모델 학습 단계에서 개입해야 하는 등 실용성에 한계가 있었습니다. 특히, 적대적 공격 (텍스트 편집, 삭제, 삽입 등) 이 가해졌을 때 워터마크를 복원하는 것은 여전히 큰 도전 과제입니다.

2. 제안된 방법론 (Methodology)

이 논문은 라그랑주 보간 (Lagrange Interpolation) 과 유한체 (Finite Field, GF(2^n)) 산술을 활용한 새로운 다중 비트 (multi-bit) 워터마킹 기법을 제안합니다.

핵심 아이디어

수학적 표현: 워터마크 $W$ 를 유한체 $GF(2^n)$ 위의 직선 $f(x) = a_1x + a_0$ 의 계수 $(a_0, a_1)$ 로 인코딩합니다.
임베딩 (Embedding):
- 사전 정의된 시크릿 키와 해시 함수를 사용하여 생성된 토큰 시퀀스 내에서 의사난수 $x$ 좌표를 생성합니다.
- 해당 $x$ 에 대해 $y = f(x)$ 를 계산하여 $n$ 비트의 $y$ 좌표를 얻습니다.
- 생성된 $y$ 의 각 비트에 따라 어휘 (Vocabulary) 를 두 집합 ( $V_0, V_1$ ) 으로 나누고, LLM 의 로짓 (logit) 값을 편향시켜 해당 비트에 해당하는 토큰을 선택되도록 유도합니다.
- 이 과정을 반복하여 직선 위에 있는 점들 $(x, f(x))$ 의 시퀀스를 텍스트에 숨깁니다.
추출 (Extraction):
- 텍스트에서 토큰을 재구성하여 $x$ 좌표를 복원하고, 토큰 분포를 분석하여 $y$ 좌표를 추정합니다.
- 이때 생성 과정의 확률적 변동이나 적대적 편집으로 인해 일부 점은 오차 (Spurious points) 를 포함하게 됩니다.
- 최대 공선점 문제 (Maximum Collinear Points, MCP): 추출된 점들 중에서 가장 많은 수의 점들이 지나는 직선을 찾는 문제를 해결합니다.
- 해당 직선을 통해 라그랑주 보간을 적용하여 원래의 다항식 $f(x)$ 와 계수 $(a_0, a_1)$ 를 복원하여 워터마크를 획득합니다.

주요 특징

모델 무관성 (Model-agnostic): LLM 의 내부 가중치를 변경하지 않고, 추론 (Inference) 단계의 로짓 편향 (Logit Bias) 만을 조정하므로 기존 모델에 적용 가능합니다.
학습 불필요 (Training-free): 모델을 재학습시킬 필요가 없습니다.
내구성: 일부 점이 손상되거나 제거되더라도, 나머지 점들이 직선을 이루고 있다면 워터마크를 복원할 수 있습니다.

3. 주요 기여 (Key Contributions)

다중 비트 워터마킹: 단순한 이진 신호가 아닌, 다중 비트 정보를 효율적으로 인코딩하고 복원하는 체계 제시.
알고리즘적 효율성: MCP 문제를 해결하기 위해 해싱 기반 알고리즘을 사용하여 $O(N^2)$ 시간 복잡도로 효율적으로 처리하며, 추출 시간이 매우 짧음.
이론적 분석: 유한체 $GF(2^n)$ 상에서 무작위 점들이 직선을 형성할 확률에 대한 상한선 (Theorem 1) 을 증명하여, 오탐지 (False Positive) 확률을 제어하기 위한 파라미터 (필드 크기, 임계값 등) 설계 가이드 제공.
비트 보정 메커니즘: 추출 시 발생하는 비트 오류를 보정하기 위해 해밍 거리 (Hamming radius) 내의 후보들을 탐색하는 경량 보정 단계 도입.

4. 실험 결과 (Experimental Results)

성능 비교: Llama 2-7B 및 Mistral 7B 등 다양한 모델과 Essays, HC3 데이터셋을 사용하여 실험했습니다.
- 정확도: 16 비트에서 32 비트까지의 워터마크 크기에 대해 85%~98% 의 높은 일치율 (Match Rate) 을 기록했습니다.
- 비교: 기존 최첨단 방법 (Fernandez et al., Wang et al., Qu et al. 등) 과 유사하거나 더 나은 성능을 보였으며, 특히 24 비트 이상에서 기존 방법들이 실용적이지 않거나 (NA) 성능이 급격히 떨어지는 것과 대조적으로 안정적이었습니다.
- 속도: 추출 시간은 수백 토큰의 텍스트에 대해 1 초 미만으로 매우 빠릅니다.
적대적 공격 저항성:
- 치환 (Substitution): 토큰 길이가 유지되므로 동기화가 깨지지 않아 가장 낮은 영향.
- 삽입/삭제 (Insertion/Deletion): 토큰 시퀀스 길이가 변해 블록 정렬이 깨지므로 (Desynchronization) 가장 큰 영향을 미치나, 10% 의 토큰 변경에도 부분적인 복원 가능성을 보임.
- 전체적으로 제안된 방식은 임의의 편집에 완전히 견고하지는 않지만, 상당 수준의 적대적 조작을 견딜 수 있음.

5. 의의 및 결론 (Significance and Conclusion)

실용성: 이 방식은 LLM 의 가중치를 수정하지 않고도 적용 가능하여, 오픈소스 모델이나 상용 API 기반 시스템에도 쉽게 도입할 수 있습니다.
확장성: 직선 (1 차 다항식) 을 사용하는 것을 넘어, 고차 다항식 (Higher-degree polynomials) 을 사용하여 더 긴 워터마크를 인코딩하거나, 여러 직선을 조합하는 방식으로 확장 가능합니다.
미래 방향: 텍스트 편집 공격에 대한 내성을 강화하고, 고차 다항식 기반의 최적화 및 하이브리드 방식을 연구할 필요가 있음을 제시합니다.

요약하자면, 이 논문은 수학적 구조 (라그랑주 보간 및 유한체) 를 활용하여 LLM 생성 텍스트에 강인한 다중 비트 워터마크를 삽입하고, 적대적 편집이 있더라도 이를 복원할 수 있는 효율적이고 실용적인 프레임워크를 제시한 연구입니다.