Non-Local Search-to-Decision Reduction over F2

암호학의 영역에서, 비밀의 보안은 종종 하나의 근본적인 원칙에 의존한다: 정보는 취약하다는 것이다. 만약 당신이 양자 정보를 복사하려고 시도한다면, 복사하는 행위 자체가 원래의 정보를 교란하여 도난의 흔적을 남기게 된다. 노 클로닝 정리(no-cloning theorem)로 알려진 이 개념은, 고전 물리학으로는 보호할 수 없는 방식으로 데이터를 보호하기 위해 설계된 차세대 보안 프로토콜의 근간이다. 한 딜러가 무작위 비트 문자열—긴 비밀번호—을 가져와 이를 두 조각으로 나누어, 한 조각은 밥(Bob)에게 주고 다른 한 조각은 찰리(Charlie)에게 건네주는 상황을 상상해 보라. 이 둘은 서로 떨어져 있으며 서로 통신할 수 없다. 그 후 그들은 무작위 질문, 즉 숫자의 벡터를 받고, 자신들이 가진 비밀의 조각과 그 질문을 바탕으로 특정 답을 계산하라는 요청을 받는다. 과제는 그들이 전체 비밀번호를 실제로 재구성하지 않고도, 순수한 운이 허용하는 것보다 더 자주 정답을 맞히도록 답변을 조정할 수 있는지 확인하는 것이다.

비국소적 탐색-결정 문제(non-local search-to-decision problem)로 알려진 이 시나리오는 정보의 본질에 대한 심오한 질문을 던진다. 만약 밥과 찰리가 무작위 질문에 대해 정답을 일관되게 예측할 수 있다면, 그것은 그들이 어떻게든 숨겨진 전체 문자열을 복구해냈음을 의미하는가? 고전적인 세계에서 답은 '예'이다. 만약 당신이 비밀의 무작위 부분을 충분히 잘 예측할 수 있다면, 결국 전체를 재구성할 수 있다. 이는 알려진 수학적 사실이다. 그러나 정보가 상태의 중첩으로 존재할 수 있는 양자 세계에서는 규칙이 덜 명확하다. 두 당사자가 비밀을 완전히 복구하지 못하더라도, 양자 역학의 기묘한 특성을 사용하여 그들의 추측을 완벽하게 조정할 수 있을까? 만약 그럴 수 있다면, 이는 단일 정보의 예측이 전체 메시지를 복구하는 것만큼 어렵다는 가정에 기반한 많은 제안된 양자 암호 체계의 보안을 깨뜨릴 것이다.

한 연구자가 이제 이 구체적이고 중요한 사례에 대해 이 질문을 해결했다. 그는 만약 밥과 찰리가 무작위 질문에 대한 정답을 확률적으로 우연보다 유의미하게 높게 예측할 수 있다면, 그들은 또한 자신들의 조각에 대한 국소적 측정만을 사용하여 전체 숨겨진 문자열을 복구할 수 있어야 함을 증명했다. 즉, 두 당사자가 비밀 자체를 찾는 더 어려운 문제를 먼저 해결하지 않고서는 답을 맞힐 수 있는 양자 지름길은 존재하지 않는다. 연구자는 그들이 정답을 맞힐 확률이 전체 문자열을 성공적으로 복구할 확률과 밀접하게 결합되어 있음을 입증했다. 만약 문자열을 복구할 확률이 무시할 수 있을 정도로 작다면, 즉 사실상 불가능하다면, 그들이 정답을 맞힐 확률 또한 무작위 추측의 50대 50 기준선 근처에서 아주 약간 높은 수준에 머물게 된다.

이 증명은 컴퓨터 시뮬레이션이 아닌 양자 역학의 법칙에 기초한 엄격하고 수학적인 논증이다. 연구자는 이를 테스트하기 위해 물리적인 장치를 만든 것이 아니라, 성공적인 추측을 허용하는 전략은 본질적으로 전체 비밀을 추출하는 기제(machinery)를 포함하고 있다는 논리적 논거를 구축했다. 그는 두 당사자가 공유하는 양자 상태를 분석하였고, 만약 그 상태가 높은 성공률의 추측을 허용한다면, 그것은 반드시 높은 성공률의 복구를 허용해야 함을 보여주었다. 결과는 확정적이다: 양자 세계에서는, 완전한 지식을 얻는 대가를 치르지 않고서는 올바른 추측이라는 혜택을 누릴 수 없다. 이 발견은 디지털 키가 감지 없이 복사되거나 도난될 수 없도록 설계된 기술인 복제 불가능 암호화(unclonable encryption)의 이론적 토대를 강화한다. 이는 이러한 시스템의 보안이 특정 계산의 난이도가 아니라, 정보가 완전히 드러나지 않고서는 공유될 수 없다는 근본적인 물리 법칙에 달려 있음을 확인시켜 준다.

연구자는 또한 자신의 작업에 한계가 있음을 언급했다. 그는 추측하는 능력이 비밀을 복구하는 능력을 함의한다는 것을 증명했지만, 그의 증명은 실제로 그 복구를 수행하기 위한 빠르고 효율적인 방법을 제공하지는 않는다. 이는 이론적으로 복구가 가능하다는 것을 보여줄 뿐, 컴퓨터에서 이를 빠르게 수행하는 단계별 레시피를 제공하는 것은 아니다. 이 구분은 실제 응용 분야에서 중요하다. 만약 복구 과정이 사용하기에 너무 느리다면, 비록 이론적 보장이 성립하더라도 강력한 컴퓨터를 가진 해커로부터 보호하지 못할 수도 있기 때문이다. 그러나 양자 정보의 근본적인 한계를 설정하는 목적에 있어서는, 이 결과는 완전하다. 이는 양자 추측에서 '공짜 점심'이 가능하다는 가능성에 문을 닫아버리며, 결정 문제의 난이도가 탐색 문제의 난이도와 불가분하게 연결되어 있음을 확인해 준다.

이 연구는 표준 컴퓨터의 세계에서 추측과 복구 사이의 유사한 연결 고리를 확립한 고전적 결과인 골드라이히-레빈(Goldreich-Levin) 정리의 오랜 연구 역사를 계승한다. 새로운 연구는 이 논리를 양자 영역, 특히 두 당사자가 비밀을 공유하고 동일한 무작위 도전에 직면하는 시나리오로 확장한다. 이 문제를 해결하려는 이전의 시도들은 당사자들이 서로 다른 도전을 받거나 비밀이 더 복잡한 방식으로 공유되는 경우에 집중했었다. 연구자는 두 당사자가 정확히 동일한 도전을 받는 경우를 다룸으로써 양자 보안에 대한 이해의 중요한 공백을 메웠다. 그의 연구 결과는 이 설정을 기반으로 한 양자 암호 체계의 보안이, 근본적인 탐색 문제가 어렵다는 전제하에 견고함을 시사한다.

이 증명의 함의는 단 하나의 특정 암호 방식에만 국한되지 않는다. 이는 정보가 여러 당사자 사이에 분산된 양자 시스템의 보안을 분석하기 위한 새로운 도구를 제공한다. 성공적인 예측 전략이 성공적인 복구 전략을 함의한다는 것을 증명함으로써, 연구자는 암호학자들에게 그들의 시스템을 테스트할 수 있는 방법을 제시했다. 만약 어떤 시스템이 추측 공격에 의해 뚫릴 수 있다면, 그것은 복구 공격에 의해서도 뚫릴 수 있다. 이는 보안 분석의 과업을 단순화하여, 전문가들이 시스템의 안전을 보장하기 위해 더 어려운 문제인 복구 문제에 집중할 수 있게 해준다. 또한 이 작업은 현재의 기술적 한계가 아닌 물리 법칙에 의존하는 정보 이론적 보안의 힘을 강조한다. 미래의 컴퓨터가 무한히 빨라지더라도, 이러한 원칙에 의해 보호되는 시스템을 깰 수는 없다. 왜냐하면 정보는 흔적을 남기지 않고서는 추출될 수 없기 때문이다.

결국, 이 논문은 양자 보안의 미래를 향해 명확하고 안심할 수 있는 메시지를 전달한다. 그것은 양자 세계가 탐지 없이 비밀을 훔칠 수 있는 루프홀(loophole)을 제공하지 않는다는 것을 확인해 준다. 만약 떨어진 두 당사자가 무작위 질문에 대해 우연보다 더 잘 협력하여 답을 낼 수 있다면, 그들은 사실상 전체 비밀을 손에 쥐고 있는 것이다. 하나를 가지면서 다른 하나를 갖지 않을 방법은 없다. 이 결과는 양자 역학이 그 기묘하고 반직관적인 특징들에도 불구하고, 궁극적으로 정보가 어떻게 공유되고 보호되는지에 대해 엄격한 규율을 강요한다는 점을 재확인해 준다. 이는 양자 영역에서, 아는 행위는 소유하는 행위만큼이나 강력하며, 시스템을 우회하려는 시도는 오직 그 시도를 드러낼 뿐이라는 사실을 상기시킨다.