Amplifying Randomized Encodings & Applications

현대 암호학의 광활한 풍경 속에는 보안과 효율성 사이의 근본적인 긴장이 존재한다. 우리는 매우 강력한 보안을 갖추면서도 일상적인 기기에서 실행될 수 있을 만큼 단순한 시스템을 원한다. 이를 달기 위해 암호학자들은 종종 '일방향 함수(one-way functions)'에 의존하는데, 이는 한 방향으로는 수행하기 쉽지만 비밀 키 없이는 역방산하는 것이 거의 불가능한 수학적 연산을 의미한다. 이러한 함수의 존재는 디지털 프라이버시의 근간이지만, 수십 년 동안 수학자들은 컴퓨터 과학에서 가장 어려운 문제들을 바탕으로 이들의 존재를 증명하기 위해 고군투쟁해 왔다. 특정하고 잠재적으로 취약할 수 있는 가정에 의존하는 대신, 연구자들은 일방향 함수가 존재해야 하는 이유가 단순히 특정 유형의 문제들이 본질적으로 해결하기 어렵기 때문이라는 것을 보여주고자 오랫동안 노력해 왔다. 이러한 어려운 문제의 범주 중에는 '영지식 증명(zero-knowledge proofs)'과 관련된 문제들이 있다. 영지식 증명이란 한 당사자가 비밀에 대한 세부 정보를 전혀 드러내지 않으면서도 자신이 그 비밀을 알고 있다는 사실을 상대방에게 확신시키는 방법이다. 질문은 여전히 남아 있다: 만약 이러한 영지식 문제들이 최악의 경우(worst-case)에 해결하기 어렵다면, 그것이 안전한 암호화를 위해 필요한 일방향 함수의 존재를 보장하는가?

연구팀은 '무작위 인코딩(randomized encodings)'의 신뢰성을 증폭시키는 새로운 방법을 개발함으로써 이 질문에 답하기 위한 중요한 진전을 이루었다. 무작위 인코딩을 복잡한 문제를 더 단순하고 뒤섞인 버전으로 변환하는 방법이라고 상상해 보라. 목표는 원래의 문제에 대한 정보는 최종 결과 외에는 아무것도 드러내지 않으면서, 원래 문제보다 훨씬 계산하기 쉬운 변환을 만드는 것이다. 연구진은 이러한 변환 중에서도 보안 보장이 '예(yes)'라는 답변에 대해서만 성립하는 특정 유형, 즉 '일방향 인코딩(one-sided encoding)'이라 불리는 시나리오에 집중했다. 그들은 이러한 인코딩이 초기에는 불완전하더라도(즉, 약간의 정보를 유출하거나 가끔 틀린 답을 내놓더라도) 체계적으로 개선될 수 있음을 발견했다. 변환 과정에서 정보가 얼마나 버려지는지를 측정하는 '손실 감소(lossy reductions)' 개념에 기반한 새로운 기술을 적용함으로써, 연구팀은 이러한 결함이 있는 인코딩이 오류와 정보 유출이 무시할 수 있을 정도로 작아질 때까지 효과적으로 증폭될 수 있음을 증명했다.

이 증폭 과정은 컴퓨터 과학의 더 깊은 연결 고리를 여는 열쇠이다. 연구진은 어떤 문제가 적당한 수준의 프라이버시와 정확성을 가지고 인코딩될 수 있다면, 그것을 거의 완벽한 버전으로 변환할 수 있음을 보여주었다. 그들은 비대화형 영지식 증명을 다루는 NISZK라는 문제 범주에 이 결과를 적용했다. 수년 동안, 이러한 증명들의 영지식 특성을 약한 역다항식(inverse-polynomial) 보장에서 강한 무시 가능한(negligible) 보장으로 강화할 수 있는지 여부는 미해결 과제로 남아 있었다. 연구팀은 이를 증명하여 1990년대 후반부터 해결되지 않았던 문제를 풀었다. 이는 어떤 문제가 약한 영지식 증명을 가질 수 있다면, 해당 문제가 충분히 어렵다는 전제하에 이를 거의 완벽한 영지식 보장을 가진 것으로 변환할 수 있음을 의미한다.

이 연구의 함의는 일방향 함수의 존재로 직접 연결된다. 연구진은 만약 이러한 영지식 문제들의 최악의 경우 버전이 실제로 풀기 어렵다면, 특정한 일방향 인코딩에 대한 오류 제거 절차가 확립될 수 있다는 조건하에 일방향 함수가 반드시 존재해야 함을 입증했다. 그들은 일방향 인코딩으로부터 오류를 제거하는 능력이 이러한 특정 문제들의 어려움과 안전한 암호 도구 생성 사이의 간극을 메우기에 충분하다는 것을 보여줌으로써 이를 달성했다. 본 논문은 이러한 오류 제거 알고리즘을 만드는 것이 충분하다는 점은 확립하였으나, 그러한 오류 제거 알고리즘의 구축을 향후 연구를 위한 미해결 과제로 명시적으로 남겨두었다. 나아가, 그들은 양자 영역을 탐구하여 유사한 원리가 양자 인코딩에도 적용됨을 보여주었으며, 이는 결과적으로 일방향 함수의 양자 버전인 '일방향 상태 생성기(one-way state generators)'의 존재를 시사한다. 이는 이러한 문제들의 근본적인 난해함이 고전 및 양자 암호 모두를 지원할 만큼 견고함을 나타낸다.

또한, 이 연구는 컴퓨터 프로그램의 내부 작동 방식을 숨기면서 그 기능은 유지하는 강력한 암호 도구인 '비식별성 난독화(indistinguishability obfuscation)'의 성격을 다루었다. 이전 연구들은 프로그램이 완벽하게 숨겨져 있거나 오류가 매우 낮은 매우 엄격한 조건 하에서만 난독화가 일방향 함수를 함의한다는 것을 보여주었다. 새로운 연구는 난독화가 약하고 불완전하여 상당한 정보를 유출하고 빈번한 오류를 발생시키더라도, 컴퓨터 과학의 주요 이론적 구조인 '다항식 계층(Polynomial Hierarchy)'이 붕괴하지 않는 한 여전히 일방형 함수의 존재를 함의한다는 것을 증명했다. 이 발견은 우리가 안전한 암호화가 가능하다는 확신을 가질 수 있는 조건을 크게 넓혔으며, 이를 구축하기 위한 장벽이 이전에 생각했던 것보다 더 낮고 견고하다는 것을 시사한다.

이러한 연결 고리를 확립함으로써, 연구진은 암호학의 이론적 토대에 대한 더 명확한 지도를 제공했다. 그들은 특정 광범위한 문제들을 해결하는 어려움이 단지 추상적인 수학적 호기심이 아니라, 우리 디지털 세계에 필요한 보안의 직접적인 원천임을 보여주었다. 그들의 작업은 만약 우리가 이러한 복잡한 문제들이 최악의 경우에 풀기 어렵다는 것을 신뢰할 수 있고, 또한 일방향 인코딩의 오류 제거에 관한 미해결 과제가 해결된다면, 우리가 데이터를 안전하게 지켜주는 일방향 함수의 존재에 의존할 수 있음을 확인시켜 주었다. 이 결과는 단순히 가능성을 제시하는 것이 아니라, 오류를 제거하기 위한 인코딩 기술의 성공적인 정교화에 달려 있다는 조건하에, 어려운 문제로부터 안전한 암호화로 가는 경로가 열려 있다는 엄밀한 증명을 제공한다. 이는 이론적 커뮤니티가 왜 암호학이 작동하는지, 그리고 그것을 구축하기 위해 진정으로 무엇이 필요한지에 대한 결정적인 이해에 더 가까이 다가가게 한다.