당신이 모르는 사람에게 수학 문제를 대신 풀어달라고 요청할 수 있지만, 당신의 비밀 숫자는 절대 보여줄 필요가 없는 세상을 상상해 보십시오. 당신은 당신의 데이터를 깨지지 않는 마법의 상자에 담아 잠근 뒤 전달하고, 그 사람은 상자 자체에 대해 계산을 수행합니다. 그들이 상자를 돌려주면, 당신은 그것을 열어 답을 찾아내지만, 그 사람은 당신의 원래 데이터에 있는 단 하나의 숫자도 보지 못했습니다. 이것이 바로 현대 암호학의 초능력인 **동형 암호(Homomorphic Encryption, HE)**가 약속하는 바입니다. 이는 마치 편지의 주소를 읽기 위해 봉투를 열지 않고도 편지를 분류하고, 도장을 찍고, 경로를 지정할 수 있는 우체국에 밀봉된 편지를 보내는 것과 같습니다.

하지만 여기 문제가 있습니다. 그 편지가 당신의 손을 떠난 후, 그 안에 담긴 작업물의 소유권은 누구에게 있을까요? 만약 어떤 회사가 당신의 암호화된 데이터를 사용하여 모델을 학습시키거나 의료 스캔을 처리한다면, 최종 결과물은 새로운 가치 있는 디지털 자산이 됩니다. 그렇다면 당신의 데이터가 사용되었다는 것을, 혹은 그들의 특정 알고리즘이 작업을 수행했다는 것을 어떻게 증명할 수 있을까요? 디지털 세계에서 우리는 보통 사진이나 노래에 소유권을 증명하기 위해 워터마크를 입힙니다. 하지만 잠긴 상자에는 워터마크를 그냥 그려 넣을 수 없습니다. 표면에 흠집을 내면 마법이 깨져서 상자가 열리지 않을 수도 있기 때문입니다. 게다가 상자가 여러 번 전달되고 처리되다 보면, 단순한 흠집은 완전히 지워질 수도 있습니다. 과학자들은 이 마법의 상자 안에서 잠금장치를 망가뜨리지 않으면서도 여정을 견뎌낼 수 있는 비밀스러운 '서명'을 숨기는 방법을 찾아내기 위해 노력해 왔습니다.

"How to Watermark the RLWE Homomorphic Ciphertexts"라는 제목의 이 논문은 정확히 그 퍼즐을 다룹니다. 저자들(Yufei Zhou가 이끄는 팀)은 이 암호화된 상자의 수학적 노이즈(noise) 안에 작고 보이지 않는 '워터마크'를 숨기는 방법을 제안합니다. 그들은 단순히 막연한 아이디어를 제시하는 것이 아니라, 두 가지 구체적인 작동 방식을 구축하고 그것이 작동함을 수학적으로 증명합니다. 이것은 마치 라디오 신호의 정전기 노이즈 속에 비밀 메시지를 숨기는 것과 같습니다. 메시지는 존재하지만, 일반적인 청취자에게는 그저 잡음처럼 들릴 뿐입니다. 저자들은 신호가 증폭되거나, 다른 신호와 섞이거나, 노이즈 필터를 통과한 후에도 그 비밀 메시지를 여전히 찾아낼 수 있음을 보여줍니다.

이 논문은 이 작업을 위한 두 가지 서로 다른 도구를 소개하며, 각 도구는 서로 다른 종류의 수학 문제에 맞게 설계되었습니다. 첫 번째 도구인 ARWMark는 튼튼하고 유연한 스티커와 같습니다. 이는 암호화된 숫자들을 더하는 작업(덧셈)에는 뛰어나지만, 암호화된 상자들을 곱하려고 하면 스티커가 갈갈이 찢겨 나갑니다. 두 번째 도구인 MRWMark는 더 복잡하게 맞물리는 퍼즐 조각과 같습니다. 이것은 훨씬 더 강력합니다. 암호화된 데이터의 덧셈과 곱셈을 모두 견뎌낼 수 있습니다. 하지만 사용하기 더 어렵고, 메시지를 숨기기 위해 노이즈 안에 훨씬 더 많은 "공간"을 필요로 합니다. 저자들은 단순히 꿈만 꾼 것이 아니라, 코드를 작성하고 강력한 컴퓨터로 수천 번의 시뮬레이션을 실행하여, 복잡한 계산의 풍파를 겪은 후에도 워터마크가 여전히 숨겨져 있고 탐지 가능하다는 것을 보여주었습니다.

"잠긴 상자"의 마법

이것이 어떻게 작동하는지 이해하기 위해 재료를 살펴보겠습니다. 이 논문은 RLWE(Ring Learning with Errors)라고 불리는 암호화 방식에 의존합니다. 당신이 비밀 레시피(데이터)를 가지고 있고, 낯선 사람의 주방에서 케이크(결과)를 굽고 싶다고 가정해 봅시다. 레시피를 안전하게 지키기 위해, 당신은 재료를 주는 대신 아주 미세하고 보이지 않는 양의 모래가 섞인 밀가루 봉지를 줍니다. 낯선 사람은 이 "노이즈가 섞인" 밀가루를 사용하여 케이크를 굽습니다. 그들이 당신에게 케이크를 건네줄 때, 당신은 밀가루에 모래가 정확히 얼마나 들어 있었는지 알 수 있으므로, 모래를 빼내어 완벽한 케이크를 얻을 수 있습니다. 여기서 "모래"가 바로 노이즈입니다. 실제 세계에서 이 노이즈는 암호를 안전하게 유지하기 위한 수학적 필수 요소입니다. 노이즈가 없다면 비밀 레시피를 추측할 수 있기 때문입니다.

문제는 이 노이즈가 워터마크를 숨기기에 완벽한 장소라는 점입니다. 저자들은 만약 특정 패턴의 "모래"를 노이즈 안에 숨길 수 있다면, 특정 상자가 자신의 것임을 증명할 수 있다는 점을 깨달았습니다. 하지만 위험도 따릅니다. 모래를 너무 많이 넣으면 케이크가 무너질 수 있고(복호화 실패), 너무 적게 넣으면 나중에 패턴을 찾을 수 없을 수도 있습니다. 또한, 만약 낯선 사람이 두 개의 밀가루 봉지를 섞거나(동형 덧셈) 곱한다면(동형 곱셈), 모래 패턴이 뒤섞이거나 씻겨 내려갈 수 있습니다.

두 가지 해결책: 스티커와 퍼즐

저자들은 "낯선 사람"이 어떤 종류의 수학을 수행하느냐에 따라 두 가지 해결책을 제안합니다.

1. ARWMark: "덧셈 방지" 스티커
이 방법은 투표를 집계하거나 의료 통계를 합산하는 것처럼 암호화된 데이터가 주로 더해지는 상황을 위해 설계되었습니다. 저자들은 워터마크를 정전기 속에 숨겨진 비밀 신호처럼 취급합니다. 그들은 무작위 "키"(특정한 모래 패턴)를 선택하고, 상자의 노이즈에 그것을 조금 더합니다.

• 작동 방식: 무작위 모래가 든 밀가루 봉지가 있다고 상상해 보십시오. 여기에 약간의 특정한 "파란색 모래"를 추가합니다. 이 봉지가 당신의 것인지 확인하고 싶을 때, 당신은 파란색 모래를 찾습니다.
• 함정: 이 방식은 밀가루 봉지들을 단순히 더할 때는 매우 잘 작동합니다. 파란색 모래가 약간 희석될 뿐, 여전히 존재하기 때문입니다. 하지만 봉지들을 곱하려고 한다면(훨씬 더 복잡한 연산), 파란_색 모래는 너무 철저하게 뒤섞여 패턴이 사라지게 됩니다. 논문은 이 방법이 덧셈에는 강하지만 곱셈에는 실패한다는 것을 수학적으로 증명합니다.
• 결과: 저자들은 초기 파란색 모래의 양이 충분히 강하다면, 많은 암호화된 숫자를 더한 후에도 파란색 모래 패턴을 높은 정확도로 탐지할 수 있음을 보여주었습니다.

2. MRWMark: "곱셈 방지" 퍼즐
이것은 핵심적인 역할을 하는 도구입니다. AI 모델을 실행하거나 딥러닝 추론을 수행하는 것과 같이 데이터가 곱해지는 시나리오를 위해 설계되었습니다. 이는 곱셈이 노이즈를 혼돈스럽게 만들기 때문에 훨씬 더 어렵습니다.

• 작동 방식: 단순히 패턴을 더하는 대신, 저자들은 "선형 방정식 시스템"을 이용한 영리한 트릭을 사용합니다. 특정 숫자 세트만이 풀 수 있는 규칙(수수께끼와 같은)이 있다고 가정해 봅시다. 그들은 이 수수께끼를 푸는 숫자 세트를 노이즈 안에 숨깁니다.
• 마법: 암호화된 상자들을 곱할 때, 곱셈의 수학적 성질이 이 수수께끼의 해답을 실제로 보존합니다. 이는 마치 퍼즐 조각들이 서로 맞물려 있는데, 상자를 흔들더라도 조각들이 여전히 똑같은 방식으로 맞물리는 것과 같습니다.
• 함정: 곱셈은 엄청난 혼돈을 만들어내기 때문에, 이 방법은 메시지를 숨기기 위해 훨씬 더 많은 "공간"(임베딩 강도)을 필요로 합니다. 논문은 이 메시지가 수학적 폭풍 속에서 길을 잃지 않도록 하기 위해 필요한 노이즈의 양이 엄청나다는 점을 언급합니다. 때로는 임베딩 강도가 수백만 단위에 달해야 합니다.
• 결과: 저자들은 이 방법이 덧셈과 곱셈을 모두 견딜 수 있음을 입증했지만, 이는 "제로 비트(zero-bit)" 시스템(단순히 워터마크의 존재 여부만 증명할 뿐 긴 메시지를 전달하지는 못함)이며 많은 자원을 필요로 한다는 점을 보여주었습니다.

수치가 말해주는 것

저자들은 단순히 추측한 것이 아니라, 이 아이디어들을 엄격하게 테스트했습니다. 그들은 Intel Xeon Gold CPU와 502 GB RAM을 갖춘 강력한 컴퓨터에서 Python을 사용하여 시뮬레이션을 구축했습니다. 그들은 다항식 크기($N$) 2048과 평문 모듈러스($p$) 65537을 사용하여 128비트 보안 수준을 충족하도록 암호화 파라미터를 설정했습니다.

ARWMark의 경우, 적절한 임베딩 강도($I_w$)가 7일 때 비밀 키 암호화에서 워터마크를 명확히 구별할 수 있음을 발견했습니다. 그러나 공용 키 암호화(노이즈가 더 많은 경우)에서는 동일한 신호를 얻기 위해 강도를 100까지 높여야 했습니다. 그들은 공격자가 워터마크를 지우려고 시도하는 상황(무작위 노이즈 추가)을 테스트했습니다. 그 결과, 원래의 임베딩이 충분히 강하게 만들어지지 않는 한, 노이즈가 너무 거대하지 않다면 워터마크가 생존한다는 것을 발견했습니다. 하지만 공격자가 충분한 노이즈를 추가하면 워터마크를 잃을 수 있었습니다.

MRWMark의 경우, 판돈이 더 컸습니다. 낮은 임베딩 강도에서는 워터마크가 노이즈 속에서 사라지는 경우가 많았습니다. 하지만 강도를 34로 높였을 때, 워터마크를 찾는 성공률이 거의 100%로 급등했습니다. 곱셈을 테스트했을 때 요구 사항은 치솟았습니다. 리사이즈(resize, 노이즈 감소 단계) 없이 단 한 번의 곱셈 연산을 견뎌내려면 최소 782,327의 강도가 필요했습니다. 리사이즈 연산을 추가하면 그 숫자는 거의 9,600만까지 뛰었습니다. 이 수치들은 이 방법이 작동하기는 하지만, 워터마크의 "크기" 측면에서 막대한 비용이 따른다는 것을 보여줍니다.

결론

이 논문은 우리가 이러한 마법 같은 암호화 상자 안에 워터마크를 숨길 수 있다는 것을 증명합니다. 이는 단순히 "계산할 수 있는가?"를 넘어 "그 계산의 결과를 추적하고 보호할 수 있는가?"의 단계로 나아갔다는 점에서 중요한 진전입니다.

저자들은 한계점을 명확히 짚고 있습니다. 그들의 "스티커"(ARWMark)는 단순한 덧셈에는 훌륭하지만 곱셈 앞에서는 무너집니다. 그들의 "퍼즐"(MRWMark)은 곱셈을 처리할 수 있지만 비용이 많이 들고 사용하기 어렵습니다. 그들은 모든 가능한 시나리오에 대한 해결책을 제시했다고 주장하는 것이 아니라, 견고한 토대와 두 가지 작동하는 프로토타입을 제공한 것입니다.

향arian(미래)에 저자들은 두 세계의 장점을 결합하여, 작으면서도 어떤 수학 연산도 견뎌낼 수 있는 강력한 워터마크를 만들기를 희망합니다. 그때까지 그들의 연구는 프라이버시를 보호하는 세상에 새로운 보안 계층을 제공하여, 우리가 비밀을 클라우드에 전달할 때도 그 작업의 주인이 누구이고 결과의 소유자가 누구인지 증명할 수 있게 해줄 것입니다. 그것은 노이즈의 바다 속에 숨겨진 작고 보이지 않는 서명이지만, 디지털 시대에 그 서명은 신뢰와 혼돈을 가르는 차이가 될 수 있습니다.