암호화 기법을 사용하면 어려운 문제를 좀 더 쉽게 만들 수 있습니다 | 콴타 매거진

어려운 문제를 해결하는 가장 좋은 방법은 무엇입니까? 이것이 바로 계산 복잡도 이론이라고 불리는 컴퓨터 과학의 하위 분야의 핵심 질문입니다. 대답하기 어려운 질문이지만 뒤집어 보면 더 쉬워집니다. 최악의 접근 방식은 거의 항상 시행착오이며, 성공할 때까지 가능한 솔루션을 연결하는 것입니다. 그러나 일부 문제의 경우 대안이 전혀 없는 것처럼 보입니다. 최악의 접근 방식이 최선의 접근 방식이기도 합니다.

연구자들은 그것이 정말로 사실인지 오랫동안 궁금해 해왔다고 말했다. 라훌 일랑고, 매사추세츠 공과대학에서 복잡성 이론을 공부하는 대학원생입니다. "'추측과 확인이 최적인 문제가 있나요?'라고 질문할 수 있습니다."

복잡성 이론가들은 많은 계산 문제를 연구했으며 심지어 어려운 문제조차도 순수한 시행착오보다 솔루션을 찾는 것을 조금 더 쉽게 만드는 일종의 영리한 절차나 알고리즘을 인정하는 경우가 많습니다. 몇 가지 예외 중에는 데이터 세트에 대한 가장 짧은 설명을 찾는 것이 목표인 압축 문제가 있습니다.

하지만 지난 11월 두 그룹의 연구자들이 독립하여 발견 압축 문제에 대한 또 다른 알고리즘 — 가능한 모든 답을 확인하는 것보다 약간 더 빠른 알고리즘입니다. 새로운 접근 방식은 다른 문제를 공격하기 위해 25년 전 암호학자들이 발명한 알고리즘을 적용함으로써 작동합니다. 한 가지 제한 사항이 있습니다. 데이터 세트의 크기에 맞게 알고리즘을 조정해야 한다는 것입니다.

“정말 아름답고 중요한 결과입니다.”라고 말했습니다. 에릭 알렌더, Rutgers University의 이론 컴퓨터 과학자입니다.

경도 정의

새로운 결과는 복잡성 이론이 출현하기 훨씬 이전인 소련에서 처음 연구된 문제를 조사한 최신 결과입니다. “내가 초등학교에 다니기 전에 러시아 사람들은 이것을 공식화했습니다.”라고 Allender는 말했습니다.

소련 연구자들이 연구한 최소 회로 크기 문제라고 불리는 특정 계산 문제는 컴퓨터 하드웨어 설계자가 항상 직면하는 문제와 유사합니다. 전자 회로가 어떻게 작동해야 하는지에 대한 완전한 사양이 주어진 경우 해당 작업을 수행할 수 있는 가장 간단한 회로를 찾을 수 있습니까? "perebor" 없이 이 문제를 해결하는 방법을 아는 사람은 아무도 없었습니다. 러시아어 단어는 "철저한 검색"과 거의 동일합니다.

최소 회로 크기 문제는 압축 문제의 예입니다. 긴 비트 문자열(0과 1)을 사용하여 회로의 동작을 설명하고 더 적은 비트를 사용하여 동일한 동작을 재현할 수 있는 방법이 있는지 물어볼 수 있습니다. 가능한 모든 회로 레이아웃을 확인하는 데는 문자열의 비트 수에 따라 기하급수적으로 늘어나는 시간이 걸립니다.

이러한 종류의 기하급수적 증가는 어려운 계산 문제를 정의하는 특징입니다. 그러나 모든 어려운 문제가 똑같이 어려운 것은 아닙니다. 일부는 철저한 검색보다 빠른 알고리즘을 가지고 있지만 실행 시간은 여전히 ​​기하급수적으로 늘어납니다. 현대적인 관점에서 볼 때, 근본적인 질문은 압축 문제에 대해 그러한 알고리즘이 존재하는지 여부입니다.

1959년에 Sergey Yablonsky라는 저명한 연구원은 철저한 검색이 실제로 최소 회로 크기 문제를 해결하는 유일한 방법임을 증명했다고 주장했습니다. 그러나 그의 증거는 몇 가지 허점을 남겼습니다. 일부 연구자들은 당시 결함을 발견했지만 Yablonsky는 대부분의 다른 연구자들이 페레보 문제에 대해 연구하는 것을 방해할 만큼 영향력이 있었습니다.

그 후 수십 년 동안 압축 문제를 연구한 연구자는 거의 없었으며, 페레보 문제는 복잡성 이론의 선사시대에 대부분 각주로 알려졌습니다. 이 질문에 대한 광범위한 관심은 연구자들이 압축 문제와 암호화의 기초 사이의 흥미로운 연관성을 발견한 이후에야 나타났습니다.

일방 통행

현대 암호화는 어려운 계산 문제를 사용하여 비밀 메시지를 보호합니다. 그러나 계산 견고성은 비대칭인 경우에만 유용합니다. 즉, 코딩된 메시지를 해독하기 어렵지만 처음에 메시지를 인코딩하는 것은 어렵지 않은 경우에만 유용합니다.

모든 암호화 체계에서 이러한 비대칭성의 기원은 입력 비트 문자열을 동일한 길이의 출력 문자열로 변환하는 단방향 함수라는 수학적 개체입니다. 단방향 함수에 대한 입력이 주어지면 출력을 계산하기는 쉽지만, 출력이 주어지면 함수를 역전(즉, 리버스 엔지니어링하고 입력을 복구)하는 것은 어렵습니다.

“암호학자들은 정말 매우 효율적으로 계산 가능하고 반전하기 어려운 단방향 함수를 갖고 싶어합니다.”라고 Allender는 말했습니다. 많은 수학적 함수가 이 속성을 갖고 있는 것으로 보이며 이러한 함수를 반전시키는 어려움은 다양한 계산 문제를 해결하는 데 따른 명백한 어려움에서 비롯됩니다.

불행하게도 암호학자들은 이러한 기능 중 실제로 반전하기 어려운 기능이 있는지 확실히 알지 못합니다. 실제로 진정한 단방향 기능이 존재하지 않을 수도 있습니다. 이러한 불확실성은 복잡성 이론가들이 50년 동안 고생했다 겉보기에 어려워 보이는 문제가 실제로는 어렵다는 것을 증명하기 위해서입니다. 그렇지 않고 연구자들이 이러한 문제에 대한 초고속 알고리즘을 발견한다면 이는 암호화에 재앙이 될 것입니다. 이는 일방 통행로에서 과속 차량을 갑자기 양방향으로 라우팅하는 것과 유사합니다.

계산 경도에 대한 포괄적인 이해가 여전히 어렵더라도 암호학자들은 최근 단방향 함수의 통합 이론을 향해 흥미로운 진전을 이루었습니다. 2020년에 텔아비브 대학의 암호학자가 큰 ​​발걸음을 내디뎠습니다. 라파엘 고개 그리고 그의 대학원생 리우 얀이 단방향 함수임을 증명했습니다. 밀접하게 연결되어 있다 시간 제한 Kolmogorov 복잡성 문제라고 하는 특정 압축 문제입니다.

이 문제 하나가 대부분의 입력에 대해 해결하기 어렵다면 Pass와 Liu의 결과는 입증하기 어려운 단방향 함수를 구성하는 방법에 대한 레시피를 제공합니다. 이 함수는 다른 계산 문제가 훨씬 쉬워지더라도 안전이 보장됩니다. 연구자들이 예상했던 것보다. 그러나 시간 제한이 있는 Kolmogorov 복잡성 문제를 해결하기 위한 빠른 알고리즘이 있다면 암호화는 불가능하고 모든 기능을 쉽게 반전시킬 수 있습니다. 이 문제의 어려움을 기반으로 한 단방향 함수는 가능한 가장 안전한 함수입니다. 즉, 모든 문제를 지배하는 단방향 함수입니다.

데이터 구조를 기반으로 구축

Pass와 Liu의 발견은 암호화의 기초를 더 잘 이해하기 위해 복잡성 이론을 사용하는 긴 연구 라인의 최신 장이었습니다. 그러나 이는 또한 그 관계를 뒤집는 방법도 제안했습니다. 시간 제한이 있는 Kolmogorov 복잡성 문제와 함수 역전 사이의 동등성은 두 문제에 대한 통찰력이 다른 문제에 대해 더 많은 것을 밝힐 수 있음을 의미합니다. 암호학자들은 암호화 방법의 약점을 더 잘 이해하기 위해 수십 년 동안 함수 반전 알고리즘을 연구해 왔습니다. 연구자들은 이러한 알고리즘이 복잡성 이론의 오래된 질문에 답하는 데 도움이 될 수 있는지 궁금해하기 시작했습니다.

많은 계산 문제와 마찬가지로 함수 반전도 철저한 검색을 통해 해결할 수 있습니다. 출력 문자열이 주어지면 올바른 답을 얻을 때까지 가능한 모든 입력을 함수에 연결하기만 하면 됩니다.

1980년에 암호학자 마틴 헬만(Martin Hellman)은 더 나은 결과를 얻을 수 있는지 연구하기 시작했습니다. 이는 수십 년 전에 소련 수학자들이 압축 문제에 대해 물었던 것과 동일한 질문이었습니다. 헬만 발견 그렇습니다. 가능합니다. 데이터 구조라는 수학적 개체를 사용하여 사전에 추가 작업을 수행할 의향이 있다면 가능합니다.

데이터 구조는 본질적으로 반전될 함수에 대한 정보를 저장하는 테이블이며, 이를 구성하려면 전략적으로 선택된 특정 입력에 대한 함수의 출력을 계산해야 합니다. 이러한 모든 계산은 "매우 오랜 시간이 걸릴 수 있습니다"라고 말했습니다. 라이언 윌리엄스, MIT의 복잡성 이론가. "그러나 아이디어는 이것이 단 한 번, 영원히 이루어진다는 것입니다." 다양한 출력이 제공되는 동일한 기능을 반전시키려는 경우(예: 동일한 방식으로 암호화된 다양한 메시지를 디코딩하려는 경우) 이 작업을 미리 수행하는 것이 좋습니다.

물론 추가 정보를 저장하려면 공간이 필요하므로 이 전략을 극단적으로 사용하면 어떤 컴퓨터에도 맞지 않는 빠른 프로그램이 될 수 있습니다. Hellman은 자신의 알고리즘이 더 많은 공간을 차지하지 않으면서 전체 검색보다 약간 더 빠르게 대부분의 기능을 반전할 수 있는 영리한 데이터 구조를 설계했습니다. 그러다가 2000년에 암호학자 Amos Fiat와 Moni Naor가 extended 모든 기능에 대한 Hellman의 주장.

2020년 Pass와 Liu의 획기적인 발전 이후 이러한 오래된 결과는 갑자기 새로운 의미를 갖게 되었습니다. Fiat-Naor 알고리즘은 철저한 검색보다 빠르게 임의의 기능을 반전시킬 수 있습니다. 압축 문제에도 효과가 있을 수 있나요?

제복을 벗어남

이 문제를 제기한 최초의 연구자는 복잡성 이론가였습니다. 라훌 산타남 옥스포드 대학의 대학원생이자 한린 렌. 그들은 한 번에 그렇게 했습니다. 2021 용지 이는 압축 문제와 기능 반전이 연구자들이 인식했던 것보다 훨씬 더 얽혀 있음을 증명했습니다.

Pass와 Liu는 시간 제한이 있는 Kolmogorov 복잡도 문제가 어렵다면 함수 반전도 어렵고 그 반대도 어렵다는 것을 증명했습니다. 그러나 문제는 어려울 수 있으며 철저한 검색보다 조금 더 나은 솔루션을 인정합니다. Santhanam과 Ren은 한 문제에 대해 철저한 검색이 필요한지 여부와 다른 문제에 대해 철저한 검색이 필요한지 여부 사이에 밀접한 연관성이 있음을 보여주었습니다.

그들의 결과는 연구자들이 자주 연구하는 "균일" 알고리즘과 "비균일" 알고리즘이라고 불리는 두 가지 광범위한 알고리즘 클래스에 대해 서로 다른 의미를 갖습니다. 균일 알고리즘은 모든 입력에 대해 동일한 절차를 따릅니다. 예를 들어 숫자 목록을 정렬하는 균일 프로그램은 목록에 항목이 20개이든 20,000개이든 동일한 방식으로 작동합니다. 대신 비균일 알고리즘은 길이가 다른 입력에 대해 다른 절차를 사용합니다.

Fiat-Naor 알고리즘에서 사용되는 데이터 구조는 항상 특정 기능에 맞게 조정됩니다. 10비트 문자열을 스크램블하는 함수를 반전하려면 스크램블이 비슷한 방식으로 수행되더라도 20비트 문자열을 스크램블하는 함수를 반전하는 데 필요한 데이터 구조와 다른 데이터 구조가 필요합니다. 이는 Fiat-Naor를 비균일 알고리즘으로 만듭니다.

Santhanam과 Ren의 결과는 Fiat-Naor 알고리즘을 압축 문제를 해결하기 위한 알고리즘으로 변환하는 것이 가능할 수 있음을 시사했습니다. 그러나 한 문제에서 다른 문제로 알고리즘을 적용하는 것은 간단하지 않았으며 더 이상 문제를 추구하지 않았습니다.

Pass는 1년 후 Naor의 암호화 기여를 축하하는 워크숍에서 Fiat가 고전 알고리즘에 대해 이야기하는 것을 듣고 같은 아이디어를 우연히 발견했습니다. “함수 반전을 사용한다는 아이디어는 그 이후로 내 마음속에 자리잡고 있었습니다.”라고 그는 말했습니다. 그는 이후 텔아비브대학교 연구원과 함께 본격적으로 이 문제를 연구하기 시작했다. 노암 메이저.

한편 Ilango는 캘리포니아 버클리에 있는 Simons Institute for the Theory of Computing을 방문하여 Santhanam을 포함한 다른 연구자들과 토론한 후 이 문제를 공격하도록 영감을 받았습니다. Santhanam은 “그냥 물건을 던지는 매우 우연한 대화 중 하나에서 나온 것입니다.”라고 말했습니다. Ilango는 나중에 Williams와 힘을 합쳤고 히라하라 슈이치, 도쿄 국립 정보학 연구소의 복잡성 이론가.

어려운 부분은 압축 문제를 해결하기 위해 Fiat-Naor 알고리즘의 핵심인 데이터 구조를 비균일 알고리즘에 삽입하는 방법을 알아내는 것이었습니다. 이러한 종류의 삽입을 수행하는 표준 절차가 있지만 알고리즘 속도가 느려지고 철저한 검색에 비해 장점이 없어집니다. 두 팀은 Fiat-Naor 데이터 구조를 통합하는 더 영리한 방법을 찾았고, 모든 입력에 대해 작동하고 철저한 검색보다 빠르게 유지되는 압축 문제에 대한 알고리즘을 얻었습니다.

두 알고리즘의 세부 사항은 약간 다릅니다. Ilango와 그의 공동 저자가 만든 방법은 검색을 가장 간단한 가능성으로 제한하더라도 철저한 검색보다 빠르며 시간 제한이 있는 Kolmogorov 복잡성, 최소 회로 크기 문제 등 모든 압축 문제에 적용됩니다. 그러나 핵심 아이디어는 두 알고리즘 모두 동일했습니다. 암호화 기술은 이 새로운 영역에서 그 가치가 입증되었습니다.

역전수렴

비균일 알고리즘에 대한 새로운 증명은 다음과 같은 자연스러운 질문을 제기합니다. 균일 알고리즘은 어떻습니까? 압축 문제를 사용하여 철저한 검색보다 빠르게 압축 문제를 해결할 수 있는 방법이 있습니까?

최근 일련의 결과는 그러한 알고리즘이 임의의 함수를 반전시키는 균일한 알고리즘과 동등하다는 것을 암시합니다. 이는 암호학자들이 수십 년 동안 성공적으로 추구하지 못한 것입니다. 그렇기 때문에 많은 연구자들은 가능성이 희박하다고 생각합니다.

Santhanam은 “매우 놀랄 것입니다.”라고 말했습니다. "완전히 새로운 아이디어가 필요합니다."

그러나 Allenender는 연구자들이 그 가능성을 무시해서는 안 된다고 말했습니다. “나에게 있어서 좋은 작업 가설은 어떤 일을 하는 데 균일하지 않은 방법이 있다면 균일한 방법도 있을 가능성이 매우 높다는 것입니다.”라고 그는 말했습니다.

어느 쪽이든, 이 연구는 복잡성 이론가들이 암호학의 오래된 질문에 새로운 관심을 갖도록 만들었습니다. 유발 이샤이이스라엘 하이파에 있는 Technion의 암호학자인 는 이것이 가장 흥미로운 점이라고 말했습니다.

“다양한 커뮤니티 간의 관심이 수렴되는 모습을 보게 되어 정말 기쁩니다.”라고 그는 말했습니다. “내 생각엔 그것이 과학에 아주 좋은 것 같아요.”