당신이 탐정이 되어 미스터리를 풀고 있다고 상상해 보십시오. 하지만 당신의 단서는 지문이나 발자국이 아니라 숫자로 이루어져 있습니다. 당신은 암호학, 즉 비밀 코드를 다루는 과학의 세계에서 일하고 있습니다. 이 세계에서 "코드"란 단순히 비밀 메시지가 아닙니다. 그것은 정보를 보호하기 위해 설계된, 격자(grid) 안에 배열된 특정한 숫자 패턴입니다. 수십 년 동안 과학자들은 초강력 양자 컴퓨터(아직 존재하지 않지만 곧 다가올 미래의 기술)가 이러한 코드들을 순식간에 깨뜨릴 수 있을까 봐 걱정해 왔습니다. 안전을 지키기 위해, 암호학자들은 양자 기계조차 풀기 매우 어려운 수학 문제에 기반한 새로운 자물쇠를 만들고 있습니다.

이 중 가장 유망한 유형의 자물쇠는 "코드 등가성(Code Equivalence)"이라는 퍼즐에 의존합니다. 두 개의 숫자 격자가 있다고 상상해 보십시오. 이 퍼즐은 다음과 같이 묻습니다: "이 두 격자는 비밀리에 동일한 것인가, 단지 순서가 바뀌거나 형태가 변형된 것뿐인가?" 당신은 열(column)의 순서를 바꿀 수 있고(마치 책장에 있는 책을 재배치하는 것처럼), 숫자의 크기를 조절할 수 있지만(마치 글꼴 크기나 색상을 바꾸는 것처럼), 숫자들이 말하는 근본적인 이야기는 바꿀 수 없습니다. 만약 그들이 동일하다는 것을 증명할 수 있다면, 당신은 자물쇠를 푼 것입니다. 만약 증명할 수 없다면, 비밀은 안전하게 유지됩니다. 이것이 우리의 미래 인터넷을 보호할 수 있는 차세대 디지털 서명의 토대입니다.

오랫동안, 이 퍼즐을 해결하는 방법에 대한 이해에는 공백이 있었습니다. 우리에게는 "결정(decision)" 도구가 있었습니다. 즉, "두 격자가 동등한가?"라는 질문에 단순히 "예" 또는 "아니오"라고 답할 수 있는 마법 같은 오라클(oracle)이었습니다. 하지만 현실 세계에서 우리에게 필요한 것은 단순한 예/아니오 이상의 것입니다. 우리는 실제로 어떻게 순서가 바뀌었는지, 그리고 숫자가 얼마나 변형되었는지 정확히 알아야 합니다. 이것을 "탐색(search)" 문제라고 부릅니다. 지금까지 우리는 "예/아니오" 답변을 해결책으로 바꿀 수 있는 방법을 가장 단순한 버전의 퍼즐(순서만 바뀌는 경우)에 대해서는 알고 있었지만, 더 복잡한 버전(숫자를 변형하거나 숫자 체계 자체의 규칙을 바꾸는 경우)에 대해서는 여전히 미스터리로 남아 있었습니다.

Abhinaba Mazumder가 작성한 이 논문은 이 미스터리를 해결합니다. 저자는 "예/아니오" 오라클을 완전한 탐정으로 탈바꿈시켜 가장 복잡한 버전의 퍼즐에 대한 정확한 해답을 찾아내는 영리하고 단계적인 방법을 제시합니다. 이 논문은 두 코드가 동등한지 결정할 수 있다면, 그 두 코드를 일치시키는 구체적인 순서 변경과 변형 지침을 효율적으로 찾아낼 수 있음을 증명합니다. 이는 "탐색" 문제가 "결정" 문제만큼 어렵지 않다는 것을 보여주는 중요한 진전입니다. 저자는 "예/아니오" 답변으로부터 비밀 키를 합리적인 시간 내에 재구성할 수 있음을 입증하는 명확하고 결정론적인 레시피(알고리즘)를 제공합니다.

탐정의 도구 상자: 셔플링(Shuffling)과 스트레칭(Stretching)

이 논문이 어떻게 작동하는지 이해하기 위해, 간단한 비유를 사용하여 퍼즐 조각들을 나누어 보겠습니다. 당신이 카드 덱을 가지고 있다고 상상해 보십시오. 하지만 카드에는 문양이나 숫자가 아니라 점의 패턴이 그려져 있습니다.

퍼즐: 당신은 덱 A와 덱 B라는 두 개의 덱을 가지고 있습니다. 당신은 덱 B가 다음과 같은 과정을 거친 덱 A라고 의심합니다:

1. 셔플링(Shuffling): 카드의 순서가 바뀌었습니다.
2. 스트레칭(Stretching): 어떤 카드들의 점들이 비밀스러운 숫자에 의해 곱해졌습니다(마치 이미지를 확대하는 것처럼).
3. 트위스트(Twisted): (가장 복잡한 버전의 경우) 점들이 상호작용하는 규칙이 "체 확대 자기동형 사상(field automorphism)"에 의해 약간 변경되었습니다. 이는 '2'를 '3'으로, '3'을 '2'로 바꾸는 특정 패턴을 가진 비밀 규칙과 같습니다.

"결정" 문제는 심판에게 "이 두 덱이 같은가?"라고 묻는 것과 같습니다. 심판은 단지 "예" 또는 "아니오"라고 답합니다.
"탐색" 문제는 "덱 A를 덱 B로 만들기 위한 정확한 이동 목록을 보여달라"고 요청하는 것과 같습니다.

마법의 기술: 셔플링 고정하기

이 논문의 첫 번째 큰 돌파구는 "예/아니오" 심판만을 사용하여 **셔플(permutation)**을 찾아내는 방법을 알아낸 것입니다.

당신이 덱 A의 첫 번째 카드(이를 "에이스"라고 부릅시다)가 덱 B의 5번째 위치로 이동했는지 알고 싶다고 가정해 봅시다. 당신은 심판에게 "에이스가 5번 위치에 있습니까?"라고 직접 물을 수 없습니다. 왜냐하면 다른 방식으로도 덱을 일치시킬 수 있기 때문에, 에이스가 실제로는 6번 위치에 있더라도 심판이 "예"라고 답할 수도 있기 때문입니다.

그래서 저자는 **"사영 클래스(Projective Classes)"**라고 불리는 영리한 트릭을 사용합니다. 이것을 색상만 다를 뿐 똑같이 보이는 카드들을 그룹화하는 것으로 생각하십시오. 만약 에이스와 킹이 (크기만 다를 뿐) 동일한 점 패턴을 가지고 있다면, 그들은 같은 "클래스"에 속합니다.

탐정의 전략은 카드를 **고정(pinning)**하는 것입니다.

1. 탐정은 덱 A의 첫 번째 카드를 가져와서 100개의 복사본을 만들어 덱의 끝에 모두 붙입니다.
2. 그런 다음, 덱 B의 후보 카드(예를 들어 5번째 위치에 있는 카드)를 가져와서 100개의 복사본을 만들어 덱 B의 끝에 붙입니다.
3. 그리고 심판에게 묻습니다: "이 새로운 거대한 덱들이 동등한가?"

만약 심판이 **"아니오"**라고 한다면, 이는 후보 카드(5번 위치)가 잘못된 선택이었음을 의미합니다. "에이스"가 그 위치로 이동하지 않았다는 뜻입니다.
만약 심서이 **"예"**라고 한다면, 이는 "에이스"가 5번 위치로 이동했다는 강력한 힌트가 됩니다.

이것이 왜 작동할까요? 왜냐하면 심판은 전체 구조가 일치할 때만 "예"라고 답할 수 있기 때문입니다. 100개의 동일한 복사본을 추가함으로써, 당신은 속이기 어려운 거대한 "지문(fingerprint)"을 만드는 것입니다. 후보가 틀리면 지문이 일치하지 않아 심판이 "아니오"라고 할 것이고, 후보가 맞으면 지문이 정렬되어 심판이 "예"라고 할 것입니다.

이 논문은 이 과정을 모든 카드에 대해 하나씩 수행함으로써 전체 셔플 목록을 재구성할 수 있음을 증명합니다. 이것은 마치 퍼즐 조각을 하나씩 끼워 맞춰보는 것과 같지만, 조각을 끼우려고 시도하는 대신 마법 거울에게 그림이 제대로 보이는지 묻는 것과 같습니다.

두 번째 단계: 스트레칭 찾기

셔플을 알고 나면 퍼즐은 훨씬 쉬워집니다. "스트레칭"(대각 행렬) 부분은 각 카드의 비밀 곱수를 찾는 것과 같습니다.

저자는 셔플(순서)을 알고 나면 더 이상 마법 심판이 필요하지 않다는 것을 보여줍니다. 당신은 표준 수학(선형 대수학)을 사용하여 각 카드가 얼마나 스트레칭되었는지 정확히 알아낼 수 있습니다. 이 논문은 엔겔-슈나이더(Engel-Schneider) 알고리즘을 사용합니다.

당신이 다음과 같은 방정식 세트를 가지고 있다고 상상해 보십시오: "카드 A(2만큼 스트레칭됨)는 카드 B와 같다." 만약 당신이 카드 A와 카드 B를 알고 있다면, 단순히 나누어서 "2"를 찾을 수 있습니다. 이 논문은 이 과정이 여기서도 똑같이 일어난다고 설명합니다. 저자는 이 문제를 단서들의 네트워크(그래프)로 변환하고, 이를 따라가며 비밀 곱수를 찾아냅니다. 이 단계는 빠르고 결정론적이며, 더 이상의 "예/아니오" 질문을 요구하지 않습니다.

최종 보스: "트위스트(Twist)" (체 확대 자기동형 사상)

가장 복잡한 버전의 퍼즐은 체의 규칙 자체가 변하는 "트위스트"를 포함합니다(체 확대 자기동형 사상). 이는 만약 덱 B에서 숫자 2가 실제로 3을 의미하게 되기로 심판이 갑자기 결정한 것과 같습니다.

이 논문은 이 트위스트가 "사영 클래스"(유사한 카드들의 그룹화)를 망가뜨리지 않는다는 것을 보여줍니다. 그룹화가 그대로 유지되기 때문에, 탐정은 첫 번째 단계의 "고정" 트릭을 사용하여 트위스트가 포함된 상황에서도 셔플을 찾을 수 있습니다.

셔플을 찾은 후, 탐정은 가능한 모든 "트위스트"를 시도하기만 하면 됩니다(트위스트의 개수는 $\log_p q$개로 매우 적습니다). 각 가능한 트위스트에 대해 두 번째 단계의 "스트레칭" 수학을 실행합니다. 만약 수학적 결과가 완벽하게 맞아떨어진다면, 비밀 트위스트를 찾은 것입니다. 그렇지 않다면 다음 트위스트를 시도합니다. 시도해야 할 트위스트의 수가 매우 적기 때문에, 이 과정은 여전히 매우 빠릅니다.

이것이 의미하는 바

이 논문은 두 가지 주요 사실을 증명합니다:

1. 선형 코드 등가성(Linear Code Equivalence, LCE)에 대하여: 두 코드가 동등한지에 대해 "예/아니오"라고 말할 수 있는 도구가 있다면, 합리적인 시간 내에 정확한 해답을 찾는 도구를 구축할 수 있습니다.
2. 일반화된 코드 등가성(Generalized Code Equivalence, GCE)에 대하여: "트위스트"가 포함된 가장 복잡한 버전에서도 이 방식은 작동합니다.

저자는 이 문제들(search)이 결정 문제(decision)보다 근본적으로 더 어렵다는 아이디어를 명시적으로 배제합니다. 이 논문은 "탐색" 문제가 "결정" 문제와 별개의 더 높은 산이 아니라, 자연스럽게 이어지는 경로임을 증명합니다.

여기서 신뢰도가 높은 이유는 저자가 단순히 추측이나 시뮬레이션을 제공한 것이 아니라 증명을 제공했기 때문입니다. 이 방법은 **결정론적(deterministic)**입니다. 즉, 항상 작동하며 "아마도" 맞을 것이 아니라 항상 정답을 줍니다. 또한 이 논문은 이 특정 코드들에 대해서는 문제를 해결했지만, 다른 시스템에서 사용되는 다른 유형의 코드인 "행렬 코드 등가성(Matrix Code Equivalence)"에 대한 유사한 해결책은 여전히 누락되어 있어, 미래의 탐정들에게 과제로 남아 있다고 언급합니다.

요약하자면, 이 논문은 우리에게 마스터 키를 건네줍니다. "예/아니오" 오라클이 전체 비밀을 풀기에 충분히 강력하며, 모호한 확인을 정밀하고 실행 가능한 솔루션으로 바꿀 수 있음을 보여줍니다. 이는 우리의 미래를 위한 보안성이 높은 양자 내성 디지털 서명을 구축하는 데 있어 매우 중요한 조각입니다.