Right Divisibility in Erasing Semi-Thue Systems: A Minimal View of Intruder Deduction

당신이 특정 금고를 도둑이 열 수 있을지 파악하려는 숙련된 열쇠 기술자라고 상상해 보십시오. 디지털 보안의 세계에서 메시지는 잠긴 상자와 같습니다. 그리고 '도둑'(또는 침입자)은 그들에게 도구 상치가 있습니다: 그들은 두 상자를 하나로 묶거나, 열쇠로 잠그거나, 혹은 그것들을 지문(해시) 형태로 만들 수 있습니다. 보안 전문가들의 큰 질문은 이것입니다: "도둑이 이미 훔친 상자들을 가지고, 오직 그들의 도구만을 사용하여 새로운 특정한 상자(예: 비밀 키)를 만들어낼 수 있는가?" 이것을 **침입자 연역 문제(intruder deduction problem)**라고 부릅니다.

이 문제를 해결하기 위해, 과학자들은 종종 이 복잡한 상자들을 단순히 글자들의 문자열이라고 가정합니다. 만약 당신이 그 화려한 모양들을 모두 벗겨내고 오직 글자의 순서만을 본다면, 이 문제는 단어 퍼즐 게임이 됩니다. 당신에게는 시작 단어와 목표 단어가 있고, 단어의 일부를 잘라내거나 재배열하는 규칙 목록이 있습니다. 질문은 이것입니다: "나는 시작 단어에서 목표 단어로 잘라 붙이며 나아갈 수 있는가?" 이 논문은 이 게임의 매우 구قت적인, 축소된 버전을 깊이 파고들어, 규칙이 문제를 해결 가능하게 만드는 지점이 어디인지, 그리고 언제 답을 아는 것이 불가능해지는지를 정확히 살펴봅니다.

---

거대한 단어 게임: 자르고 붙이기, 그리고 논리의 한계

이 논문에서 저자인 라자 O. P. 다마니크(Raja O. P. D. Damanik)와 알웬 티우(Alwen Tiu)는 복잡한 3D 형태의 암호화 메시지를 보는 것을 멈추고, 대신 그것들을 단순한 단어로 바라보기로 합니다. 모든 메시지가 목걸이에 꿰어진 긴 구슬 줄이라고 상상해 보십시오. "규칙"이란 침입자가 따르는 도구로, 목걸이의 앞부분이나 뒷부분을 싹둑 잘라낼 수는 있지만 중간은 절대 건드릴 수 없는 마법 가위와 같습니다.

저자들은 간단한 질문을 던집니다. 만약 내가 목걸이 ABC를 가지고 있고 이를 Z로 만들고 싶다면, 앞쪽에 구슬을 추가한 뒤 앞부분을 잘라내는 방식으로 가능할까? 이것을 **우측 분할 문제(right-divisibility problem)**라고 부릅니다. 듣기에는 쉬워 보이지만, 논리의 세계에서는 지뢰밭과 같습니다. 때때로 규칙이 너무 까다로워서, 아무리 빠른 컴퓨터라도 답이 "예"인지 "아니오"인지 결코 말할 수 없는 경우가 있습니다. 이 논문은 어떤 종류의 가위(규칙)가 게임을 풀 수 있게 만들고, 어떤 것이 게임을 완전히 망가뜨리는지를 보여주는 지도입니다.

"접두사 제거(Prefix-Erasing)" 가위: 쉬운 모드

먼저, 저자들은 접두사 제거라고 불리는 특정한 유형의 규칙을 살펴봅니다. 예를 들어, "만약 단어 시작 부분에 'BA'라는 글자가 보이면 그것을 잘라내라!"라는 규칙이 있다고 가정해 봅시다. 즉, BA-RED는 RED가 됩니다. 만약 당신에게 이런 규칙들이 있고, 그것들이 "수렴적"(meaning convergent, 즉 어떤 순서로 가위를 적용하더라도 항상 동일한 최종 단어에 도ك달함)이라면, 저자들은 놀라운 사실을 증명합니다: 당신은 이 퍼즐을 풀 수 있습니다.

그들은 단순히 가능하다고 말하는 데 그치지 않고, 초고속 알고리즘을 구축했습니다. 만약 당신이 두 단어를 준다면, 그들의 방식은 단어의 길이에 비례하는 시간(구체적으로는 단어의 길이에 비례하는 시간) 내에 한 단어가 다른 단어로 변할 수 있는지 순식간에 알려줄 수 있습니다. 이는 마치 특정 순서의 절단 작업이 작동할지 즉시 알려주는 마법 지팡이를 가진 것과 같습니다. 이는 이러한 "앞부분을 자르는" 규칙들에 대해 침입자의 연역 문제가 안전하고 해결 가능하다는 것을 확인해 줍니다.

"접미사 제거(Suffix-Erasing)" 가위: 까다로운 모드

다음으로, 그들은 상황을 뒤집습니다. 만약 가위가 단어의 뒷부분만을 자른다면 어떻게 될까요? 이것을 접미사 제거라고 합니다. 예를 들어, "단어가 'ED'로 끝나면 그것을 잘라내라!"라는 규칙이 있다고 가정해 봅시다. 즉, RED는 R이 됩니다.

여기서 게임은 훨씬 어려워집니다. 저자들은 이 문제를 여전히 풀 수는 있지만, 앞부분을 자르는 버전만큼 쉽지는 않다는 것을 보여줍니다. 그들이 찾아낸 방법은 출구에서부터 역방향으로 미로를 헤매는 것과 같습니다. 당신은 많은 가능한 경로를 탐색해야 하며, 최악의 경우 경로의 수가 기하급수적으로 늘어납니다(마치 눈덩이가 언덕을 굴러 내려가며 엄청나게 커지는 것처럼). 하지만 좋은 소식은, 이것이 해결 가능하다는 점입니다. 논문은 이러한 "뒷부분을 자르는" 규칙들에 대해서는, 비록 계산 능력이 조금 더 필요할지라도 답을 알아낼 방법이 항상 존재함을 증명합니다.

"동시 변수 리프팅(Simultaneous Variable-Lifting)" 함정: 게임 오버

하지만 그다음, 저자들은 반전을 도입합니다. 만약 침입자가 초강력 도구를 가지고 있다면 어떨까요? 예를 들어, "단어의 중간 부분을 잘라내되 앞과 뒤는 유지하고, 동시에 두 개의 서로 다른 부분에 대해 이 작업을 수행하라"라는 규칙이 있다고 가정해 봅시다. 이것을 동시 변수 리프팅이라고 합니다.

이것은 작은 변화처럼 들리지만, 게임을 완전히 망가뜨립니다. 저자들은 만약 이러한 동시 절단 규칙을 허용한다면, 이 문제가 **결정 불가능(undecidable)**해진다는 것을 증명합니다. 이것은 매우 중요한 일입니다. 이는 특정 유형의 규칙에 대해, 답을 보장할 수 있는 알고리즘이 존재하지 않는다는 것을 의미합니다. 컴퓨터에게 아무리 많은 시간을 주더라도, 침입자가 목표 단어를 만들 수 있는지 알지 못한 채 영원히 실행될 수도 있습니다.

이를 증명하기 위해, 그들은 단순히 추측한 것이 아니라, 이 단어 퍼즐을 푸는 것이 MPCP(Modified Post Correspondence Problem)라고 불리는 유명하고 해결 불가능한 문제를 푸는 것과 정확히 같음을 보여주었습니다. 수학자들이 이미 MPCP는 해결 불가능하다는 것을 알고 있기에, 그들은 이 버전의 침입자 연역 문제 또한 해결 불가능함을 증명한 것입니다.

이것이 왜 중요한가

"단어를 자르는 것이 누구와 무슨 상관인가?"라고 의문을 가질 수 있습니다. 답은 이렇습니다: 암호화를 사용하는 모든 이들과 상관이 있습니다. 실제 세계의 보안 프로토콜은 이러한 단어 게임과 유사한 복잡한 수학을 사용합니다. 문제를 가장 기초적인 뼈대(단어와 단순한 절단)로 축소함으로써, 저자들은 "해결 가능한" 영역과 "불가능한" 영역 사이의 정확한 경계선을 찾아냈습니다.

그들은 만약 보안 규칙이 단순한 앞부분 절단이나 뒷부분 절단 가위와 같다면, 해커가 침입할 수 있는지 자동으로 확인할 수 있는 도구를 만들 수 있음을 보여주었습니다. 하지만 만약 규칙이 너무 화려해져서—여러 곳을 동시에 잘라내는 것을 허용한다면—우리는 현재의 도구로는 답을 알 수 없는 벽에 부딪히게 됩니다. 이는 보안 전문가들이 어떤 종류의 암호화 시스템이 자동 분석에 안전하고, 어떤 것이 현재의 도구로 다루기에는 너무 혼란스러운지를 알 수 있게 해줍니다.

요컨대, 이 논문은 논리의 경계에 대한 가이드북입니다. 침입자의 퍼즐 중 많은 것을 풀 수 있지만, 답을 결코 알 수 없는 특정한 종류의 복잡성이 존재한다는 것을 알려줍니다. 그리고 그 선이 어디에 그려져 있는지 아는 것이 더 안전한 디지털 잠금장치를 만드는 첫걸음입니다.