Certified Randomness with Optimal Rate

디지털 세계에서 신뢰는 매우 취약한 상품입니다. 우리가 온라인으로 투표하거나, 뱅킹을 위한 비밀 코드를 생성하거나, 탈중앙화 네트워크를 위한 리더를 선출할 때, 우리는 진정으로 예측 불가능한 무작위성에 의존합니다. 만약 이 무작위성이 예측 가능하거나 편향되어 있다면, 시스템 전체가 붕괴됩니다. 수십 년 동안 과학자들은 기계에 의존하지 않고도 그러한 무작위성을 생성하는 방법을 모색해 왔습니다. 이상적인 시나리오는 비트(0과 1)의 문자열을 생성하는 장치인데, 이 장치가 생성하는 결과가 너무나 혼돈스럽고 균일하여 장치 소유자조차도 결과를 미리 예측할 수 없는 상태를 의미합니다. 이것이 바로 "인증된 무작위성(certified randomness)"의 성배입니다. 즉, 사전에 존재하는 비밀 시드(seed) 없이도 누구나 검증할 수 있는, 진정으로 무작위적이라는 수학적 보증입니다.

기존의 방법들은 무작위성이 약해 쉽게 조작될 수 있거나, 작은 무작위 시작 숫자를 제공할 신뢰할 수 있는 인간이 필요하다는 한계가 있었습니다. Siddhartha Jain, Saachi Mutreja, Bhaskar Roberts의 새로운 연구는 이러한 근본적인 한계를 다룹니다. 그들은 양자 컴퓨터가 (심지어 악의적인 컴퓨터라 할지라도) 완벽에 가까운 무작위성을 가진 비트 문자열을 생성했음을 증명할 수 있는 프로토콜을 개발했습니다. 이때 확인하는 사람은 완전히 결정론적이며 자신만의 무작위 숫자를 전혀 가지고 있지 않은 상태여야 합니다. 이 돌파구는 어떠한 신뢰할 수 있는 시작점도 필요로 하지 않으며, 이론적으로 가능한 최고 수준의 무작위성 비율을 달着했습니다.

연구진은 모든 당사자가 유니버설 해시처럼 작동하는 공공의 완벽하게 무작위적인 함수에 접근할 수 있는 이론적 설정인 '양자 랜덤 오라클 모델(quantum random oracle model)' 내에서 작업했습니다. 이 환경에서 그들은 양자 증명자(prover)가 긴 비트 문자열을 생성하고, 그 문자열이 진정으로 무작위적이라는 짧은 증명을 제공할 수 있는 시스템을 구축했습니다. 핵심적인 혁신은 증명을 확인하는 검증자(verifier)가 스스로 무작위적일 필요가 없다는 점입니다. 즉, 검증자는 고정된 결정론적 알고리즘일 수 있습니다. 이와 같은 성과를 달성하려 했던 이전의 시도들은 높은 품질의 무작위성을 보장하는 데 실패했거나, 프로세스를 시작하기 위해 검증자가 작은 신뢰할 수 있는 무작위 시드를 보유해야 했습니다. 새 프로토콜은 그 시드를 완전히 제거함으로써, 결정론적인 검증자가 신뢰할 수 없는 양자 장치로부터 생성된 긴 문자열의 무작위성을 여전히 확신할 수 있음을 입증했습니다.

그 중요성을 이해하려면 시스템이 완벽하게 무작위적이지 않을 때 어떤 일이 발생하는지를 살펴보아야 합니다. 만약 비트 문자열이 "약하게" 무작위적이라면, 겉보기에는 혼돈스러워 보일지라도 특정 패턴으로 편향될 수 있어 예측에 취약해질 수 있습니다. 연구진은 자신들의 방법이 거의 최대치에 가까운 엔트로피(무질서도)를 보장한다는 것을 증명했습니다. 실질적인 관점에서 이는 특정 길이의 문자열에 대해, 진정으로 예측 불가능한 비트의 수가 전체 길이에 거의 육박함을 의미합니다. 무작위성의 손실은 로그량만큼 아주 미미하며, 이는 물리 법칙과 계산의 본질상 피할 수 없는 것입니다. 이는 무작위성이 보장되는 양이 전체 길이의 아주 작은 부분에 불과했던 기존 방식들에 비해 엄청난 발전입니다.

프로토콜은 두 가지 주요 단계로 작동합니다. 첫째, 양자 장치는 양자 공격에 대해 안전하다고 입증된 특정 수학적 구조를 사용하여 "약하게" 무작위적인 소스를 생성합니다. 이 소스는 아직 고도의 보안이 필요한 애플리케이션에 사용하기에는 충분하지 않습니다. 둘째 단계에서, 장치는 이 소스를 필터 역할을 하는 압축 함수에 통과시킵니다. 이 필터는 약한 소스를 더 짧고 훨씬 강력한 비트 문자열로 응축합니다. 연구진은 공격자가 특정 입력을 선택하거나 함수의 동작을 관찰함으로써 과정을 조작하려 하더라도, 최종 출력을 예측 가능하도록 강제할 수 없음을 입 demonstrated했습니다. 최종 문자열은 공격자가 전체 상호작용의 이력을 모두 보았더라도 가장 가능성 높은 결과를 맞히기 어렵게 만드는 척도인 '최소 엔트로피(min-entropy)'를 높은 수준으로 유지합니다.

이 연구의 핵심 요소는 "조건부" 최소 엔트로피 개념입니다. 매 시간마다 새로운 무작위 숫자를 방송하는 공공 무작위 비콘(randomness beacon)과 같은 많은 실제 응용 분야에서, 현재 숫자의 보안은 공격자가 이전의 숫자들을 모두 알고 있더라도 현재 숫자를 예측할 수 없다는 사실에 달려 있습니다. 연구진은 자신들의 프로토콜이 이전의 모든 메시지와 데이터에 조건 지어진 상태에서도 각 새로운 무작위 펄스가 예측 불가능함을 보장한다는 것을 보여주었습니다. 이는 블록체인 네트워크의 리더 선출이나 암호화 프로토콜을 위한 공통 무작위 문자열 생성과 같이, 현재 라운드의 무결성이 과거의 예측 불가능성에 기반하는 애플리케팅에 필수적입니다.

연구팀은 자신들의 연구가 가진 한계에 대해서도 엄격하고 정직하게 다루었습니다. 공격자가 다항 시간(polynomial time) 동안 실행될 수 있다면 결정론적 검증자와 함께 완벽하고 균일한 무작위성을 달성하는 것은 불가능하다고 그들은 증명했습니다. 공격자는 이론적으로 '거부 샘플링(rejection sampling)'이라는 기술을 사용하여 출력의 적은 수의 비트를 고정함으로써, 시스템을 교묘하게 조작하여 약간 편향된 결과를 만들어낼 수 있습니다. 그러나 연구진은 자신들의 프로토콜이 이러한 제약 조건 하에서 최선의 결과를 달성한다고 보여주었습니다. 즉, 공격자가 고정할 수 있는 비트의 수가 매우 적어서 남은 무작위성이 모든 실질적인 암호학적 목적에 충분하다는 것을 보장합니다. 손실은 무시할 수 있는 수준이며, 보안은 현실적인 컴퓨팅 능력을 가진 어떤 공격자에게도 유효합니다.

이 연구는 보안 통신과 탈중앙화 시스템의 미래에 즉각적인 함의를 갖습니다. 신뢰할 수 있는 시드가 필요하지 않도록 함으로써, 이 프로토콜은 단일한 신뢰할 수 없는 양자 장치에서 실행될 수 있는 무작위성 비콘을 생성할 수 있게 합니다. 이러한 비콘은 누구나 검증할 수 있는 신선하고 예측 불가능한 무작위 숫자를 주기적으로 게시할 수 있습니다. 이 숫자의 보안은 장치 운영자의 정직함이 아니라 양자 역학의 법칙과 프로토콜의 수학적 구조에 달려 있습니다. 현재 구현은 이론적 모델에 의존하고 있지만, 실질적인 적용으로 가는 길은 그 어느 때보다 명확하며, 기계를 신뢰할 필요 없이 현대 디지털 사회가 절실히 필요로 하는 신뢰할 수 있는 무작위성을 생성하는 방법을 제시합니다.

이 연구는 초기 연구자들이 제기했던 인증된 무작위성의 한계에 대한 결정적인 답변을 제시합니다. 이는 결정론적 검증자와 함께 완벽한 균일성을 달성하는 것이 수학적으로 도달 불가능할지라도, 완벽한 것과 구별할 수 없을 정도의 무작위성은 달성 가능하다는 것을 확인시켜 줍니다. 연구진은 단순히 무작위성 비율을 개선한 것이 아니라, 신뢰할 수 없는 환경에서의 가능성의 경계를 재정의했습니다. 그들의 구조는 양자 랜덤 오라클 모델에서 보안에 대한 견고하고 무조건적인 보증을 제공하며, 양자 시대의 무작위성을 바라보는 새로운 표준을 세웁니다. 결과적으로 이 프로토콜은 이론적으로 건실하면서도 실질적으로 유의미하며, 추상적인 양자 이론과 안전한 디지털 인프라의 구체적인 요구 사이의 간극을 메우고 있습니다.