⚛️ quantum physics

A Simple and Efficient One-Shot Signature Scheme

이 논문은 키와 서명 크기를 세제곱 복잡도에서 이차 복잡도로 줄임으로써 Shmueli-Zhandry 구성을 크게 개선하고, 완벽한 정당성을 달성하며, 최근 관련 연구로부터의 교정 및 복구 응용 분야에 대한 강력한 서명 압축 불가능성을 가능하게 함으로써, 새롭고 단순하며 효율적인 원샷 서명 스킴을 제시한다.

원저자: Andrew Huang, Vinod Vaikuntanathan

게시일 2026-07-28

📖 4 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Andrew Huang, Vinod Vaikuntanathan

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

물리 법칙이 매우 특별한 종류의 디지털 잠금장치를 허용하는 세상을 상상해 보십시오. 현재의 세상에서는 금고 열쇠를 가지고 있다면 원하는 만큼 반복해서 열 수 있습니다. 하지만 미래의 양자 암호학이라는 기묘한 영역에서, 과학자들은 "원샷(one-shot)" 키를 만드는 방법을 발견했습니다. 이것은 마치 스스로 파괴되는 티켓과 같습니다. 이 티켓을 사용하여 문을 열고 당신이 그곳에 있었음을 증명할 수 있지만, 사용한 순간 티켓은 먼지로 변해버립니다. 다시 사용할 수 없으며, 나중에 사용하기 위해 복사본을 만들 수도 없습니다. 이것은 단순히 멋진 마술이 아닙니다. 이것은 깨지지 않는 디지털 화폐, 위조 불가능한 양자 권력 인증서, 그리고 심지어 디지털 비밀을 영원히 복구할 수 없도록 태워버릴 수 있는 방법으로 이어질 수 있는 강력한 도구입니다.

오랫동안 이러한 "원샷 서명(one-shot signatures)"을 구축하는 것은 마치 이쑤시개로 마천루를 짓는 것과 같았습니다. 이론적으로는 가능했지만, 설계가 매우 투박하여 엄청난 양의 양자 메모리(단 한 통의 편지에 서명하기 위해 책이 가득 찬 도서관이 필요한 수준)를 필요로 했고 작동하는 데도 오랜 시간이 걸렸습니다. 최근의 한 돌파구는 이것이 가능하다는 것을 보여주었지만, 결과물인 "키"는 거대했고 과정은 느렸습니다. 이제, MIT의 앤드류 황(Andrew Huang)과 비노드 바이쿤타나탄(Vinod Vaikuntanathan)의 새로운 논문이 매끄럽고 효율적인 재설계를 들고 왔습니다. 그들은 훨씬 적은 공간과 시간을 사용하여 이 자가 파괴되는 디지털 티켓을 만드는 방법을 알아냈으며, 이를 통해 이 아이디어를 실제 세계에서 실용적으로 만들었습니다.

자가 파괴되는 티켓

이 논문은 양자 암호학의 문제인 "원샷 서명(One-Shot Signatures, OSS)"을 다룹니다. 이 성취를 이해하기 위해, 당신이 비밀 메시지를 보내려는 스파이라고 상상해 보십시오. 예전의 투박한 버전의 스파이 게임에서 "서명"(당신가 메시지를 보냈다는 증거)은 거대하고 무거운 배낭과 같았습니다. 만약 짧은 쪽지에 서명하고 싶다면, 당신은 $\Theta(\lambda^4)$ 큐비트(양자 단위의 비트)가 담긴 배 backpack을 짊어져야 했습니다. 더 긴 메시지에 서명하고 싶다면 배낭은 더욱 커졌고, 서명하는 과정은 느리고 복잡했습니다. 종종 스파이가 일을 완수하기 위해 복잡한 양자 측정의 춤을 추어야 할 정도였습니다.

논문의 저자들은 "우리는 더 잘할 수 있다"라고 말합니다. 그들은 "배낭"이 훨씬 작아진 유선형 시스템을 설계했습니다. $\Theta(\lambda^4)$ 큐비트라는 거대한 짐 대신, 그들의 새로운 체계는 $\Theta(\lambda^2)$ 큐비트의 배낭만을 필요로 합니다. 이는 크기가 크게 줄어든 것입니다. 게다가 그들이 만들어내는 서명 또한 $\Theta(\lambda^3)$ 비트에서 $\Theta(\lambda^2)$ 비트로 줄어들어 더 작아졌습니다.

그들이 해낸 방법: "이미지(Image)" 기법

Shmueli와 Zandry가 만든 이전 방식은 마치 건초더미 속에서 특정 바늘을 찾기 위해 건초(역상, pre-image)를 뒤지는 것과 같았습니다. 그것은 마치 암호화된 결과로부터 역으로 추적하여 비밀번호를 추측하려는 것과 비슷했으며, 많은 시행착오와 많은 양자의 "되감기(rewinding, 계속 다시 시도하는 것)"를 요구했습니다. 이 과정은 비효율적이었고 때로는 유효한 서명을 생성하는 데 실패하여, 스파이가 쓸모없는 티켓을 가진 채 갇혀버릴 수도 있었습니다.

황과 바이쿤타나탄은 판을 뒤집었습니다. 건초더마 속에서 바늘을 찾는 대신, 그들은 바늘 속에서 건초를 찾기로 했습니다. 그들의 새로운 구조에서 "서명"은 함수의 "이미지(image)" 안에 직접 발견됩니다. 그들은 데이터 속에서 올바른 경로를 찾기 위해 영리한 양자 탐색 알고 알고리즘(그로버의 탐색, Grover's search)을 사용합니다. 이 접근 방식은 무작정 땅을 파는 대신, 보물로 바로 이어지는 지도를 가진 것과 같습니다. 올바른 곳을 찾고 있기 때문에, 이 과정은 "완벽하게 정확(perfectly correct)"합니다. 즉, 당신이 메시지에 서명할 때마다 시스템은 반드시 작동할 것임을 보장합니다. "앗, 티켓이 작동하지 않네"와 같은 실패의 순간은 없습니다.

이것이 중요한 이유: 양자 불꽃(Quantum Fire)

이 논문은 단순히 더 작은 배낭을 만드는 것에 그치지 않습니다. 저자들은 그들의 효율적인 서명이 "양자 불꽃(Quantum Fire)"이라 불리는 것을 구축하는 데 사용될 수 있음을 보여줍니다. 당신이 친구와 공유하고 싶은 디지털 문서를 가지고 있지만, 친구가 그것을 읽는 즉시 문서가 즉각적이고 영구적으로 파괴되어 아무도 복사본을 만들 수 없도록 하고 싶다고 상상해 보십시오. 이것이 "양자 불꽃"의 개념입니다.

이 불꽃을 만들기 위한 이전의 시도들은 오래되고 투박한 서명들에 의존했습니다. 저자들은 기존 방식에 치명적인 결함이 있었다고 지적합니다. 그것은 "압축 불가능(incompressible)"하지 않았습니다. 간단히 말해, 해커는 예전의 부피가 큰 서명을 가져가서 여전히 새로운 서명을 위조할 수 있을 만큼의 정보를 담고 있는 아주 작은 압축 파일로 줄일 수 있었습니다. 그것은 불을 껐다가 다시 붙일 수 있는 불꽃과 같았습니다.

새로운 체계는 이를 해결합니다. 그들의 서명은 구조적으로 다르게 설계되었기 때문에 "압축 불가능"합니다. 검증 능력을 잃지 않고는 데이터를 축소할 수 없습니다. 이는 그들이 구축한 "양자 불꽃"이 실제적이고 신뢰할 수 있음을 의미합니다. 일단 디지털 비밀이 타버리면, 그것은 영원히 타버린 상태로 남습니다. 그들은 또한 이 방식을 사용하여 Çakan, Goyal, Shmueli의 최근 논문에 나타난 버그를 수정하여, 안전하고 복제 불가능한 디지털 비밀을 생성하는 능력을 회복했습니다.

결론

저자들은 다음의 조건을 충족하는 원샷 서명 체계를 만드는 것이 가능하다는 것을 입증했습니다:

효율성: 이전의 최고치( $\Theta(\lambda^4)$ 및 $\Theta(\lambda^3)$ )와 비교했을 때, 훨씬 적은 양의 양자 메모리( $\Theta(\lambda^2)$ 큐비트)를 사용하며 더 작은 서명( $\Theta(\lambda^2)$ 비트)을 생성합니다.
단순성: 기존 방식이 느리고 이해하기 어렵게 만들었던 복잡한 다단계 양자 회로를 피합니다.
완벽함: 실패 가능성 없이 매번 완벽하게 작동합니다.
보안성: 해커가 데이터를 압축하여 시스템을 속는 것을 방지하여, "양자 불꽃" 및 기타 고급 보안 도구를 구축할 수 있게 합니다.

저자들은 향로(키를 훨씬 더 작게 만드는 것 등)에 여전히 개선의 여지가 있다고 언급했지만, 그들은 "이론적으로는 가능하지만 비실용적인" 단계에서 "효율적이며 차세대 양자 보안을 위한 준비가 된" 단계로 목표치를 끌어올렸습니다. 그들은 투박한 자가 파괴 벽돌을 매끄러운 자가 파괴 깃털로 바꾸어 놓았습니다.

기술 요약: 단순하고 효율적인 원샷 서명 스킴 (One-Shot Signature Scheme)

문제 정의

원샷 서명(one-shot signatures, OSS)은 사용자가 공개 검증 키($pk $)와 비밀 양자 서명 상태($ |sk\rangle$)를 생성할 수 있게 하는 독특한 양자 암호학적 프리미티브입니다. 서명 상태는 사용자가 선택한 단 하나의 메시지에 대해서만 유효한 서명을 생성할 수 있게 하며, 서명을 수행하면 상태가 "자기 파괴(self-destruct)"되어 두 번째 서명을 생성하는 것을 방지합니다. OSS는 양자 머니(quantum money), 양자 라이트닝(quantum lightning), 양자 파이어(quantum fire)와 같은 강력한 프리미티브를 함의하지만, 이를 효율적으로 구축하는 것은 여전히 과제로 남아 있습니다.

최근 Shmueli와 Zhandry(SZ) [SZ25]의 돌파구는 OSS의 첫 번째 구축 사례를 제공했습니다. 그러나 이들의 스킴은 다음과 같은 상당한 비효율성을 가집니다:

비트 단위 서명: SZ 구축 방식은 본질적으로 메시지를 한 번에 한 비트씩 서명합니다. $\lambda$ -비트 메시지를 서명하려면 병렬 반복(parallel repetition)이 필요하며, 이는 키와 서명 크기의 선형적 팽창을 초래합니다.
복잡한 증폭: 강력한 보안을 달려받기 위해, SZ는 복잡한 양자 리와인딩(quantum rewinding) 또는 양자 싱귤러 밸류 변환(QSVT) 회로(구체적으로 교대 투영/Marriott-Watrous 스타일 알고리즘)를 사용하는 Dall'Agnol과 Spooner(DS) [DS22]의 축소(reduction)에 의존합니다. 이는 서명 키 크기에 $\Theta(\lambda)$ 의 추가 오버헤드를 도입합니다.
불완전한 정확성: SZ 스킴은 무시할 수 있는 수준의 정확성 오류(correctness error)를 가집-는데, 즉 서명 알고리즘이 유효한 서명을 생성하는 데 실패할 수 있음을 의미합니다.
자원 비용: 오라클 모델에서 SZ 스킴은 $\Theta(\lambda^4)$ 큐비트 크기의 서명 키와 $\Theta(\lambda^3)$ 비트 크기의 서명을 생성합니다. 플레인 모델(plain model)에서는 이 파라미터들이 훨씬 더 커집니다.

나아가, Çakan, Goyal, Shmueli(CGS) [C¸GS25]의 후속 연구는 OSS를 사용하여 "공개 키 양자 파이어(public-key quantum fire)"를 구축하려고 시도했으나, SZ 스킴이 충족하지 못하는 압축 불가능성(incompressibility) 속성에 의존했습니다.

방법론

본 연구는 이전 방식들에서 요구되는 복잡한 축소와 병렬 반복을 피하는, 원샷 서명의 새로운 직접적인 구축법을 제안합니다. 핵심 방법론은 서명이 생성되는 방식에 대한 근본적인 변화를 포함합니다:

1. 그로버 탐색(Grover Search)을 통한 직접 구축

특정 비트로 시작하는 해시 함수의 전사(preimage)를 찾는 방식(이 경우 "합-바인딩(sum-binding)" 문제를 처리하기 위한 복잡한 증폭이 필요함)을 사용하는 SZ 방식 대신, 본 연구는 함수의 치역(image) 내에서 서명을 찾습니다.

설정: 이 스킴은 무작위 순열 $\Pi$ 와 행렬 $\mathbf{A}_y$ 및 벡터 $\mathbf{b}_y$ 로 정의된 부분 공간 패밀리를 활용합니다. 서명 상태 $|sk\rangle$ 는 이러한 파라미터들에 의해 정의된 아핀 부분 공간(affine subspace, coset) 위의 균등 중첩(uniform superposition)입니다.
서명 과정: 비트 $b$ 를 서명하기 위해, 알고리즘은 $b$ 로 시작하는 전사를 찾는 것이 아닙니다. 대신, 초기 중첩 상태를 보조 함수 $\mathcal{P}$ 의 치역 아래에서 코셋 벡터들이 특정 접두사(prefix) $b$ 를 갖도록 변환하기 위해 그로버 탐색 알고리즘을 사용합니다.
오라클 사용: 서명 알고리즘은 두 가지 반사 오라클을 반복적으로 적용합니다:
1. 이미지 접두사가 메시지 비트와 일치하는 상태를 표시하는 위상 오라클(phase oracle).
2. 부분 공간의 쌍대(dual)를 기준으로 반사하는 쌍대 오라클 $\mathcal{D}$ .
  이 과정을 $\ell$ 번(메시지 길이) 반복함으로써, 알고리즘은 상태를 전체 메시지에 대한 유효한 서명들의 중첩으로 회전시킵니다. 이 상태를 측정하면 유효한 서명을 얻을 수 있습니다.

2. 완전한 정확성 보장

저자들은 $\mathbf{A}_y$ 의 샘플링을 신중하게 설계함으로써 불완전한 정확성 문제를 해결합니다. $\mathbf{A}_y$ 의 첫 번째 열이 0이 아님을 보장하여, 어떤 공개 키 $y$ 에 대해서도 코셋이 0과 1로 시작하는 벡터를 모두 포함하도록 합니다. 이러한 구조적 보장은 그로버 탐색이 항상 성공하도록 하여 완전한 정확성(확률 1)을 달성합니다.

3. 다항 길이 메시지 처리

$\lambda$ 번 단일 비트 스킴을 반복하는 방식(이는 $\lambda$ 의 팽창을 일으킴) 대신, 이 스킴은 단 한 번의 실행으로 전체 $\lambda$ -비트 메시지를 서명합니다. 그로버 탐색은 단일 실행 내에서 비트 단위로 서명하도록 적응되어, $\lambda$ 개의 서명을 $\Theta(\lambda^2)$ 크기의 단일 서명으로 압축합니다. 임의의 다항 길이에 대해서는 표준 해시-앤-사인(hash-and-sign) 변환이 적용됩니다.

4. 압축 불가능성과 양자 파이어

본 논문은 SZ 스킴이 "강한 서명 압축 불가능성(strong signature incompressibility)"을 만족한다는 CGS [C¸GS25]의 주장에 결함이 있음을 식별합니다. SZ 스킴은 서명 알고리즘이 순방향 및 역방향 오라클( $\mathcal{P}$ 및 $\mathcal{P}^{-1}$ ) 모두에 접근해야 하므로, 압축된 목록 외부의 키에 대한 서명을 생성할 수 있게 되어 이 속성을 충족하지 못합니다.
새로운 구축 방식은 서명 시 오직 쌍대 오라클 $\mathcal{D}$ 만을 요구하고, 검증 시에는 별도의 오라클 $\mathcal{D}_0$ 를 사용하도록 수정합니다. 이러한 분리는 강한 서명 압축 불가능성의 증명을 가능하게 하여, CGS가 제안했던 양자 파이어 응용의 타당성을 회복합니다.

주요 기여 및 결과

효율성 개선

본 논문은 SZ 구축과 비교하여 자원 복잡도에서 상당한 감소를 달성했습니다:

서명 키 크기: $\Theta(\lambda^4)$ 큐비트에서 $\Theta(\lambda^2)$ 큐비트로 감소.
서명 크기: $\Theta(\lambda^3)$ 비트에서 $\Theta(\lambda^2)$ 비트로 감소.
공개 키 크기: 오라클 모델에서 $\Theta(\lambda^3)$ 비트, 플레인 모델에서 $\Theta(\lambda^5)$ 비트에서 각각 오라클 모델 $\Theta(\lambda^2)$ 비트, 플레인 모델 $\Theta(\lambda^4)$ 비트로 감소.
실행 시간: 서명 알고리즘은 훨씬 적은 수의 오라클 쿼리를 요구하며, QSVT/리와인딩 회로와 관련된 $\Theta(\lambda)$ 오버헤드를 피합니다.

보안 및 정확성

완전한 정확성: SZ와 달리, 새 스킴은 유효한 서명이 확률 1로 생성됨을 보장합니다.
강력한 보안: 이 스킴은 강한 불가변성(unforgeability)을 달성합니다. 즉, 다른 메시지에 대한 유효한 서명이나 동일한 메시지에 대한 다른 서명을 생성하는 것이 불가능합니다.
압축 불가능성: 이 스킴은 양자 파이어와 같은 고급 응용에 필요한 속성인 강한 서명 압축 불가능성을 만족합니다.

이론적 결과

본 논문은 이러한 개선 사항을 두 가지 주요 정리로 공식화합니다:

정리 1.1: 클래식 오라클 모델(무조건적) 및 플레인 모델(양자 내성 불식별 난독화 및 LWE 가정 하) 모두에서 완전한 정확성을 가진 효율적인 OSS 스킴의 존재를 확립합니다.
정리 1.2: 새로운 압축 불가능한 OSS 스킴이 완전한 정확성을 가진 공개 키 양자 파이어 및 키-파이어(key-fire) 구축을 가능하게 함을 입증하며, CGS [C¸GS25] 연구의 오류를 바로잡습니다.

의의

본 논문은 기존의 최첨단 원샷 서명 스킴에 대한 "단순하고 직접적이며 효율적인" 대안을 제공한다고 주장합니다. 이전 작업들에서 사용된 복잡한 축소(DS [DS22])와 병렬 반복 전략을 우회함으로써, 저자들은 키 및 서명 크기에서 이차적(quadratic) 개선을 달ach했습니다.

본 연구의 의의는 두 가지 측면에서 두드러집니다:

실제적 효율성: 큐비트 및 비트 요구 사항을 4차/3차 스케일에서 2차 스케일로 줄임으로써 양자 서명 스킴을 훨씬 더 실현 가능하게 만듭니다.
기초적 교정: OSS의 압축 불가능성에 관한 문헌의 결정적인 간극을 메웁니다. 압축 불가능성 속성을 수정함으로써, 본 논문은 이전에 SZ 스킴에 대한 결함 있는 가정을 바탕으로 가능하다고 주장되었던 "양자 파이어" 및 관련 프리미티브의 구축을 검증하고 가능하게 합니다.

저자들은 파라미터를 상당히 최적화했지만, 현재의 병목 현상이 쌍대-프리(dual-free) 케이스의 분석에 있기 때문에 오라클 모델에서 $\Theta(\lambda)$ 까지의 추가적인 개선을 위해서는 완전히 새로운 기술이 필요할 수 있다고 언급합니다. 마찬가지로, 플레인 모델의 파라미터를 개선하는 것도 여전히 미해결 과제로 남아 있습니다.