Compressed Permutation Oracles Revisited

디지털 세계에서 보안은 종종 완벽하고 예측 불가능한 기계라는 개념에 의존합니다. 암호학자들은 어떤 입력값이든 받아들여 완전히 무작위처럼 보이는 출력을 내놓되, 한 가지 결정적인 규칙을 가진 장치를 상상합니다. 즉, 동일한 입력을 두 번 넣으면 매번 동일한 출력이 나와야 한다는 것입니다. 이는 무작위 치환(random permutation)이라고 알려져 있습니다. 이것은 비밀번호 저장 방식부터 통신의 무결성을 검증하는 알고리즘에 이르기까지, 우리가 데이터를 안전하게 지키기 위해 사용하는 많은 도구의 보이지 않는 엔진입니다. 이러한 도구들이 진정으로 안전한지 테스트하기 위해, 과학자들은 이 기계에 질문을 던질 수 있는 강력한 공격자를 상상합니다. 고전적인 세계에서 공격자는 한 번에 하나의 질문을 던집니다. 하지만 양자 세계에서 공격자는 한꺼번에 많은 질문을 던질 수 있으며, 마치 가능한 모든 질문을 동시에 던지는 것처럼 질문들을 중첩(superposition)시킬 수 있습니다. 이렇게 중첩 상태로 쿼리를 보내는 능력은 보안을 증명하는 일을 믿기 힘들 정도로 어렵게 만듭니다. 왜냐하면 공격자가 우리의 일반적인 직관을 거스르는 방식으로 정보를 얻기 때문입니다.

수년 동안 연구자들은 양자 공격자가 이러한 질문으로부터 무엇을 배우는지 추적하기 위한 수학적 모델을 구축하려고 노력해 왔습니다. '압축 오라클(compressed oracle)'이라 불리는 한 유망한 방법은 간략화된 공책과 같은 역할을 합니다. 이 공책은 거대하고 복잡한 기계 전체를 추적하는 대신, 공격자가 지금까지 물어본 입력과 출력의 특정 쌍만을 기록합니다. 이 덕분에 수학적 계산이 관리 가능한 수준이 되어, 과학자들이 특정 보안 시스템이 안전하다는 것을 증证明할 수 있게 해줍니다. 그러나 이 방법에는 심각한 문제 하나가 발목을 잡았습니다. 바로 이 공책이 완벽하게 정확하지 않다는 점이었습니다. 이 방법은 공격자가 상대적으로 적은 수의 질문을 던질 때만 제대로 작동한다는 것이 증명되었습니다. 만약 공격자가 너무 많은 질문을 던지면, 공책의 예측은 현실에서 벗어나기 시작하며 보안 증명의 신뢰성을 떨어뜨릴 수 있었습니다. 이러한 한계로 인해, 많은 현대 암호 시스템들이 결연한 양자 적대자 앞에서 버텨낼 수 있을지 확신할 수 없었습니다.

한 연구팀이 이제 이 방법을 재검토하여 가장 결정적인 결함을 해결했습니다. 그들은 압축된 공책이 기존에 생각했던 것보다 훨씬 더 신뢰할 수 있다는 것을 입증했습니다. 그들의 새로운 분석은 공격자가 이전보다 훨씬 더 많은 수의 질문, 구체적으로 전체 가능한 입력값의 제곱근만큼의 질문을 던지더라도 이 방법이 올바르게 작동함을 증명합니다. 이는 기존의 제한치가 그 숫자의 아주 작은 부분에 불과했던 것에 비하면 엄청난 개선입니다. 연구진은 실제의 복잡한 기계와 간략화된 공책 사이의 연결을 구축하는 방식을 변경함으로써 이를 달성했습니다. 복잡하고 간접적인 구조 대신, 그들은 공책을 기계의 기저 상태(underlying state)에 대한 직접적인 측정값으로 볼 수 있음을 보여주었습니다. 이 새로운 관점은 수학적 과정을 더 깔고 명확하게 만들 뿐만 아니라, 공격자가 질문을 던질 수 있는 인위적인 천장을 제거했습니다.

이러한 개선의 영향은 즉각적이고 구체적입니다. 연구진은 이 새로운, 더 정교해진 증명을 현대 암호학의 두 가지 중요한 구조인 스펀지 구조(sponge construction)와 데이비스-마이어 압축 함수(Davies-Meyer compression function)에 적용했습니다. 이들은 SHA-3 표준을 포함하여 우리의 디지털 세계를 보호하는 해시 함수의 설계도입니다. 정교해진 방법을 사용하여, 연구팀은 공격자가 이러한 시스템을 깨뜨리기 위해 정확히 몇 번의 양자 쿼리가 필요한지 계산했습니다. 그들은 충돌(collision)을 찾는 데 있어 이러한 시스템의 보안이 시스템 크기의 제곱근에 따라 증가하는 운영 횟수를 필요로 하며, 프리이미지(pre-image)를 찾는 데는 그보다 더 많은 연산이 필요하다는 점에서 매우 견고하다는 것을 발견했습니다. 그들의 결과는 네 가지 주요 SHA-3 변형에 대한 보안에 대해 명시적이고 구체적인 수치를 제공하며, 하부 설계의 특정 구조적 약점을 이용하는 방법을 찾지 않는 한 이 시스템들이 양자 컴퓨터에 대해서도 안전함을 보여줍니다.

연구진은 수학적 모델의 보안을 증명하는 것과 실제 하드웨어의 보안을 구분하는 데 주의를 기울였습니다. 그들의 작업은 만약 기초가 되는 무작위 치환이 예상대로 작동한다면, 그 위에 구축된 암호 구조가 안전하다는 것을 확인해 줍니다. 그들은 실제 SHA-3 표준에서 사용되는 특정 치환이 완벽하다고 주장한 것이 아니라, 설계 자체가 건실하다는 것을 주장한 것입니다. 이 구분은 매우 중요합니다. 즉, 시스템의 실패는 치환의 특정 구현상의 결함에서 비롯될 가능성이 높으며, 시스템이 구축된 근본적인 방식의 결함 때문이 아니라는 것을 의미합니다. 수학적 경계를 강화함으로써, 연구진은 미래의 시스템을 분석할 수 있는 더 강력한 도구를 암호학자들에게 제공하였으며, 이를 통해 차세대 디지털 보안이 직면할 양자 위협을 명확하고 정확한 이해를 바탕으로 설계할 수 있도록 보장했습니다.

그들 발견의 핵심은 공격자의 쿼리와 알려진 답변 데이터베이스 사이의 관계를 어떻게 다루느냐에 있습니다. 기존 방식에서는 실제 기계와 공책 사이의 연결이 다소 느슨하여, 질문의 수가 늘어남에 따라 오류가 누적되었습니다. 새로운 접근 방식은 공책을 기계의 상태에 대한 직접적이고 일관된 반영으로 취급합니다. 그들은 두 대상 사이의 가교를 구축하여 정확한 수학적 관계를 보존하며, 이를 통해 공책이 질문의 수와 상관없이 시스템의 실제 상태를 놓치지 않도록 보장합니다. 이 가교는 정보를 마치 도서관을 층별로 정리하듯 별도의 단계로 분리한 다음, 그들 사이의 연결을 신중하게 정규화(normalization)하는 기술을 사용하여 구축됩니다. 이 정규화는 공책에서 계산된 확률이 실제 세계의 확률과 일치하도록 보장하여, 기존의 유용성을 제한했던 '표류(drift)' 현상을 제거합니다.

이 연구는 단일 증명을 개선하는 것에 그치지 않고, 대칭 암호의 양자 보안 분석을 위한 전체 토대를 강화합니다. 압축 오라클의 한계를 가능한 입력값의 아주 작은 부분에서 제곱근까지 밀어 올림으로써, 연구진은 이전에 분석이 불가능했던 시스템들을 분석할 수 있는 문을 열었습니다. 결과는 이러한 유형의 암호 시스템을 깨뜨리는 데 있어 양자 이득(quantum advantage)이 우려만큼 크지 않을 수 있음을 시사하며, 이는 시스템이 충분한 용량을 갖추고 설계되었을 때 그러합니다. 연구팀이 명시적인 상수와 구체적인 경계값을 제공할 수 있게 됨에 따라, 엔지니어들은 이제 막연한 추정치에 의존하는 대신 시스템이 제공하는 보안 수준을 정확히 계산할 수 있게 되었습니다. 이러한 명확성은 미래의 디지털 인프라를 구축하는 데 필수적이며, 양자 컴퓨터가 현실이 되어가는 시대에 우리의 데이터가 보호받을 수 있도록 보장합니다.

또한 이 연구는 많은 암호화 체계의 구성 요소인 이상적인 사이퍼(ideal ciphers)로 그 결과를 확장합니다. 이 모델에서 보안은 서로 다른 키에 의해 제어되는 치환 패밀리에 달려 있습니다. 연구진은 공격자가 서로 다른 키들에 대해 중첩 상태로 시스템을 쿼리할 수 있는 경우에도 개선된 방법이 동일하게 잘 작동함을 보여주었습니다. 이는 매우 중요한 결과인데, 왜냐하면 많은 키가 관여한다고 해서 이러한 시스템의 보안이 저하되지 않음을 의미하기 때문입니다. 이 분석은 키의 수와 관계없이 견고하게 유지되며, 이러한 암호 설계의 근본적인 구조가 양자 공격에 대해 건실하다는 생각을 뒷받침합니다.

궁극적으로, 이 논문은 양자 보안을 이해하기 위해 사용되는 도구들의 성숙을 나타냅니다. 이는 한때 엄격한 증명을 수행하기에는 너무 취약하다고 여겨졌던 방법을 신뢰할 수 있는 도구로 강화시킨 것입니다. 연구진은 압축 오라클이 단순한 휴리스틱 근사가 아니라, 양자 정보를 추적하는 수학적으로 타당한 방법임을 보여주었습니다. 이를 통해 그들은 암호학계에 더 명확한 전망을 제공하였으며, 이를 통해 가장 진보된 위협에 맞서 증명 가능한 보안을 갖춘 시스템을 설계할 수 있게 하였습니다. 이 작업은 복잡한 양자 세계의 실제를 더 잘 반영하기 위해 우리의 수학적 모델을 정교화하는 일이 얼마나 강력한 힘을 갖는지 보여주는 증거입니다.