Verified Pythagorean Composition for Adaptive Cryptographic Games: Noise Flooding in Homomorphic Encryption

당신이 친구에게 비밀 메시지를 보내려고 하는데, 메시지를 훔쳐보는 것을 좋아하는 장난꾸러기 고블린이 운영하는 우체국을 통해 메시지를 보내야 한다고 상상해 보세요. 옛날에는 편지를 상자에 넣고 잠갔지만, 고블린이 상자를 열어 메시지를 읽는 순간 비밀은 사라져 버렸습니다. 그러다 **동형 암호(Homomorphic Encryption)**라는 마법 같은 발명이 등장했습니다. 이것은 마치 특수한 잠금 상자와 같아서, 고블린이 잠긴 편지 속의 숫자를 직접 보지 않고도 그 숫자들을 더하거나, 곱하거나, 분류하는 등의 수학 연산을 할 수 있게 해줍니다. 고블린이 계산 결과물을 돌려주면, 당신은 그것을 열어봅니다. 그러면 그 안에는 정답이 들어 있습니다. 고블린은 그 안에 어떤 숫자가 들어 있었는지 전혀 알지 못했음에도 말이죠.

하지만 여기에는 함정이 하나 있습니다. 가장 대중적인 버전인 CKKS에서는 수학이 완벽하지 않습니다. 숫자들이 너무 복잡하기 때문에, 결과물이 선명한 사진이 아닌 약간 흐릿한 사진처럼 "불투명"하거나 근사치로 나타나기 때문입니다. 보통 이 정도의 흐릿함은 괜찮습니다. 아주 미세한 노이즈 수준이니까요. 하지만 교활한 고블린(공격자)은 수많은 수학 문제를 던진 뒤, 그 흐릿한 결과들을 자신이 예상한 답과 비교하여, 그 미세한 차이를 이용해 당신의 비밀 키를 천천히 재구성할 수 있습니다. 이는 마치 고블린이 당신의 상자를 흔들었을 때 상자가 얼마나 흔들리는지를 정확히 알아내어, 그 흔들림을 통해 비밀번호를 알아내는 것과 같습니다. 이를 막기 위해 암호학자들은 **노이즈 플러딩(Noise Flooding)**이라는 방어 기법을 고안했습니다. 답변을 보내기 전에 거대한 무작위 노이즈(정적)를 추가하여, 고블린이 사용하려던 미세한 단서들을 덮어버리는 것입니다.

여기서 핵심적인 질문은 다음과 같습니다: 얼마만큼의 노이즈를 추가해야 하는가? 노이즈를 너무 적게 넣으면 고블린이 비밀을 알아낼 수 있고, 너무 많이 넣으면 답변이 너무 흐릿해져서 쓸모없게 됩니다. 까다로운 점은, 고블린이 한 번에 하나씩 질문을 던지며 이전 답변에 따라 전략을 바꿀 수 있다는 것입니다. 만약 질문마다 개별적으로 노이즈를 추가한다면, 노이즈의 "비용"이 빠르게 누적되어 결국 답변을 극도로 흐릿하게 만들어야 합니다. 하지만 하나의 영리한 수학적 아이디어는, 게임 전체를 한꺼번에 바라본다면 그 비용이 훨씬 느리게 증가할 수 있다고 제안했습니다. 즉, 질문의 횟수($q$)에 비례하는 것이 아니라, 질문 횟수의 제곱근($\sqrt{q}$)만큼만 증가한다는 것입니다. 이 논문은 이 영리한 아이디가 실제로 작동함을 증명하고, 컴퓨터가 모든 단계를 검증할 수 있는 방식으로 이를 입증하는 내용입니다.

---

이 논문의 거대한 발견: "피타고라스"의 비밀

"Verified Pythagorean Composition for Adaptive Cryptographic Games"라는 제목의 이 논문은 형식 검증(Formal Verification) 분야의 거대한 성취입니다. 형식 검증이란, 수학적 증명의 오류를 확인하기 위해 초지능 컴퓨터를 사용하는 것을 말합니다. 저자들(연구팀)은 노이즈 플러딩에 관한 유명한 보안 논거를 컴퓨터가 이해할 수 있는 언어로 번역했습니다. 그런 다음, 컴퓨터가 모든 논리적 단계를 검증하도록 하여, 가장 엄격한 조사 하에서도 수학이 성립함을 확인했습니다.

이들의 핵심 연구는 공격자가 많은 질문을 던질 때 오류가 어떻게 누적되는지에 대한 새로운 방식의 사고법입니다.

"흐릿한 사진" 문제

사진에 약간의 노이즈를 추가하여 비밀을 숨기려 한다고 상상해 보세요. 노이즈를 아주 조금만 넣으면 사진은 여전히 선명하지만, 눈썰미 좋은 고블린이 비밀을 찾아낼 수 있습니다. 반대로 노이즈를 너무 많이 넣으면 비밀은 안전해지지만, 사진은 엉망이 되어 버립니다.
암호의 세계에서 이 "정적"은 **노이즈(Noise)**라고 불립니다. 이 논문은 공격자가 메시지의 복호화된 결과를 최대 $q$번 요청하는 시나리오를 다룹니다. 이때 방어자는 비밀을 숨기기 위해 매번 노이즈를 추가합니다.

• 기존 방식 (선형 손실): 각 질문을 별개의 사건으로 취급하면, 모든 질문에 대해 안전할 만큼 충분한 노이즈를 추가해야 합니다. 만약 공격자가 100번의 질문을 던진다면, 노이즈를 100배 더 많이 넣어야 하며, 이는 최종 결과물을 완전히 쓸모없게 만듭니다.
• 새로운 방식 (제곱근 손로스): 이 논문은 더 똑똑한 전략을 확인해 줍니다. 공격자의 질문들이 서로 연결되어 있기 때문에(즉, "적응적(adaptive)"이기 때문에), 필요한 총 노이즈는 질문 횟수의 제곱근($\sqrt{q}$)만큼만 증가한다는 것을 보여줍니다. 따라서 100번의 질문을 던지더라도, 100배가 아닌 10배의 노이즈만 있으면 됩니다. 이는 우리가 훨씬 더 선명한 답변을 유지하면서도 안전을 지킬 수 있다는 점에서 엄청난 승리입니다.

"피타고라스"의 비유

왜 "피타고라스"라고 부를까요? 직각삼각형을 생각해 보세요. 두 변의 길이가 각각 3과 4라면, 가장 긴 변(빗변)의 길이는 $3 + 4 = 7$이 아닙니다. 그것은 $\sqrt{3^2 + 4^2} = 5$입니다. 전체 길이는 단순히 두 변을 더한 것보다 짧습니다.
이 논문에서 "변"은 공격자의 각 질문으로부터 발생하는 미세한 위험(또는 "비용")입니다.

• 잘못된 생각: 위험을 그냥 더해버리면($3 + 4$), 매우 크고 무서운 숫자가 나옵니다.
• 실제 상황: 저자들은 이러한 위험들이 삼각형의 변처럼 결합된다는 것을 증명합니다. 즉, 위험 요소들이 서로 관련되어 있어 어느 정도 "상쇄"된다는 것입니다. 전체 위험은 제곱의 합의 제곱근이 됩니다.
  논문은 이러한 위험들을 개별적으로 추적할 수 있으며(전문 용어로 "조건부 쿨백-라이블러 거리(Conditional Kullback-Leibler costs)", 즉 답변이 어떻게 달라 보이는지를 의미함), 마지막에 단 한 번만 최종적인 "안전 점수"로 변환할 수 있음을 증명합니다. 이를 통해 수학적 효율성을 유지하면서도 노이즈를 낮게 유지할 수 있습니다.

컴퓨터의 역할: "로봇 변호사"

"왜 컴퓨터가 필요할까요? 수학은 그냥 수학 아닌가요?"라고 물을 수 있습니다.
문제는 이러한 증명들이 믿기 힘들 정도로 복잡하다는 점입니다. 확률, 난수, 그리고 자신의 생각을 계속 바꾸는 교활한 공격자의 행동을 다루는 수천 단계의 과정이 포함됩니다. 인간은 아주 작은 세부 사항을 놓치거나, 전체 논리를 무너뜨릴 수 있는 작은 가정을 범하기 쉽습니다.
저자들은 Rocq(증명 보조 도구)와 SSProve(라이브러리)를 사용했습니다. 그들은 단순히 종이 위에 증명을 적은 것이 아니라, 암호 게임의 디지털 모델을 구축했습니다.

1. 논리: 그들은 이러한 "피타고라스적" 위험 조합을 처리하는 방법(프로그램 로직)을 알려주는 새로운 규칙 세트를 만들었습니다.
2. 컴파일러: 그들은 공격자의 프로그램을 감시하는 "트레이스 컴파일러(Trace Compiler)"를 만들었습니다. 이 컴파일러는 공격자를 잠시 멈추고, 다음 움직임을 살핀 뒤, 비밀을 안전하게 유지하면서 공격을 계속 진행하게 할 수 있습니다.
3. 검증: 컴퓨터는 모든 코드 라인과 모든 수학적 단계를 체크했습니다. 만약 기초가 되는 암호 체계가 안전하다면, 이 노이즈 플러딩 방어 기법을 적용했을 때 "제곱근"의 효율성을 가지며 안전하다는 것을 확인했습니다.

이것이 당신에게 의미하는 바

이 논문은 새로운 암호화 방식을 발명하거나 새로운 공격법을 제시하는 것이 아닙니다. 대신, 알려진 방어 기법(노이즈 플러딩)을 가져와서, 그것이 똑똑한 "피타고라스" 이론이 예측한 대로 정확히 작동한다는 것을 수학적 확실성을 가지고 증명한 것입니다.

• 이 논문은 적응적 공격자로부터 안전하기 위해 반드시 엄청난 양의 노이즈를 추가해야 한다는 생각(선형 성장)이 틀렸음을 입증합니다.
• 또한 기초 암호 체계가 이미 안전하다면, "제곱근" 성장이 실질적으로 안전하다는 것을 증명합니다.
• 더불어 이 방어 기법 뒤에 숨겨진 복잡한 수학에 빈틈이 없음을 확인해 줍니다.

저자들은 이것이 특정 암호 소프트웨어의 완벽함을 보장하는 것이 아니라, 논리에 대한 검증된 증명임을 매우 신중하게 밝히고 있습니다. 그들은 만약 좋은 암호 체계를 가지고 있고 이 노이즈 플러딩을 올바르게 적용한다면, 수학적으로 안전하다는 것을 증명한 것입니다. 또한, 가장 대중적인 암호 체계인 CKKS 자체의 구체적인 세부 사항을 검증한 것이 아니라, 노이즈 방어의 '논리'를 검증했다는 점을 명시했습니다. 하지만 디지털 프라이버시를 지키는 사람들에게 이것은 큰 진전입니다. 공격자가 똑똑하고 끈질기더라도, 우리의 비밀을 지켜주는 수학을 신뢰할 수 있게 되었기 때문입니다.

요약하자면, 이 논문은 수년간의 논쟁 끝에 설계된 다리의 구조가 튼튼한지 확인하기 위해 로봇 검사팀을 투입한 숙련된 건축가와 같습니다. 그들은 다리를 짓기 위해 우리가 생각했던 것만큼 많은 강철이 필요하지 않다는 것을 증명했습니다. 설계의 영리한 기하학적 구조(피타고라스 법칙)만으로도 충분히 무게를 견딜 수 있으며, 그 덕분에 경로는 명확하게 유지되고 비밀은 숨겨질 수 있습니다.