⚛️ quantum physics

Constant-Rate Certified Deletion

본 논문은 추가적인 가정 없이 플레인 모델(plain model)에서 상수율 인증된 삭제(constant-rate certified deletion)를 지원하도록 광범위한 암호학적 프리미티브를 업그레이드하는 통합 프레임워크를 제시하며, 영구적 보안을 보존하고 표준적인 난해성 가정 하에 공적 검증 가능성을 가능하게 하는 최초의 구성을 달성한다.

원저자: Kai-Min Chung, Tzu-Hsiang Huang, Wei-Hsiang Hung, Shota Yamada

게시일 2026-10-05

📖 3 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Kai-Min Chung, Tzu-Hsiang Huang, Wei-Hsiang Hung, Shota Yamada

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

현대 디지털 세상에서 '잊힐 권리'는 단순히 파일을 삭제하는 것 그 이상을 요구하는 법적 개념이며, 데이터가 진정으로 사라졌다는 증거를 필요로 합니다. 이는 근본적인 도전 과제인데, 텍스트 메시지나 사진과 같은 고전적 정보는 무한히 복제될 수 있기 때문입니다. 설령 파일이 비밀 코드로 잠겨 있더라도, 미래의 컴퓨팅 기술의 비약적 발전이나 유출된 키가 있다면 공격자가 이를 해독하여 원래의 내용을 복구할 수 있습니다. 데이터를 완전히 지웠음을 보장하는 유일한 방법은 물리학의 법칙, 구체적으로 양자 역학의 기묘한 규칙에 의존하는 것입니다. 양자 영역에서 정보는 다르게 작동합니다. 정보는 완벽하게 복제될 수 없으며, 이를 측정하는 행위는 필연적으로 정보를 교란시킵니다. 이러한 파괴적 특성은 독특한 기회를 제공합니다. 만약 데이터가 양자 상태로 저장되어 있다면, 사용자가 특정 방식으로 이를 측정하도록 강제함으로써 원래의 정보를 복구할 수 있는 길을 완전히 차단하고 삭제를 증명할 수 있습니다.

수년 동안 연구자들은 사용자가 비밀 정보를 삭제했음을 증명하는 인증서를 생성할 수 있게 해주는 '인증된 삭제(certified deletion)'라는 방법론을 연구해 왔습니다. 그러나 주요한 장애물은 항상 효율성이었습니다. 기존 방식들은 아주 적은 양의 데이터를 보호하기 위해서도 방대한 양의 양자 저장 공간을 필요로 했습니다. 단 1비트의 정보를 암호화하기 위해, 기존의 방식들은 보안 수준에 따라 선형적으로 증가하는 수많은 양자 입자를 필요로 했기에 대규모 메시지에 적용하기에는 비실용적이었습니다. 이는 마치 엽서 한 장을 보내려는데 종이 위의 잉크를 보호하기 위해 화물 컨테이너가 가득 찬 창고를 통째로 빌려야 하는 것과 같았습니다. 이러한 비효율성 때문에 이 개념은 이론적으로는 타당했지만, 보안 메시징이나 클라우드 스토리지와 같은 실제 응용 분야에서 사용하기에는 너무 무거웠습니다.

연구진은 이제 '상수율 인증된 삭제(constant-rate certified deletion)'를 달성하는 새로운 프레임워크를 개발함으로써 이 문제를 해결했습니다. 이는 메시지의 크기에 따라 필요한 양자 저장 공간이 폭발적으로 늘어나는 것이 아니라, 메시지 크기에 직접적으로 비례하여 성장함을 의미합니다. 새로운 시스템에서 오버헤드는 최소화됩니다. 대규모 메시지의 경우, 필요한 양자 데이터는 메시지 자체보다 약간 더 큰 수준에 불과하며, 이를 통해 이전의 표준 설정에서는 불가능하다고 여겨졌던 효율적인 비율을 달라성했습니다. 연구진은 공개키 암호화, 속성 기반 액세스, 그리고 암호화된 데이터에 대한 연산을 허용하는 완전 동형 암호(fully homomorphic encryption)를 포함한 다양한 암호 도구에 적용 가능한 통합된 방법을 만들어냄으로써 이를 달성했습니다.

연구진은 자신들의 접근 방식이 두 가지 서로 다른 유형의 양자 인코딩 방식에서 작동함을 입증했습니다. 첫 번째 유형은 보안 키 분배에 사용되는 유명한 BB84 프로토콜과 유사한 방법에 기반합니다. 두 번째 유형은 블라인드 위임(blind delegation) 및 보안 소프트웨어 리싱(secure software leasing)과 같은 더 고급 기능을 가능하게 하는 서브스페이스 코셋 상태(subspace coset states)라는 더 복잡한 구조를 사용합니다. 두 경우 모두, 새로운 프레임워크를 통해 메시지를 암호화한 후, 삭제를 수행하는 사람을 신뢰할 필요 없이 인증서를 검증하며 삭제할 수 있습니다. 결정적으로, 이러한 효율성은 수학적 문제의 난해함에 대한 어떠한 새로운 미증명 가설도 도입하지 않고, 원래의 암호 체계가 사용했던 것과 동일한 토대에만 의존하여 달성되었습니다.

연구진은 단순히 과정을 더 빠르고 가볍게 만드는 것을 넘어, 삭제 검증을 공공화(public)하는 방법 또한 보여주었습니다. 많은 보안 시나리오에서 단순히 송신자만이 데이터가 사라졌음을 아는 것으로는 부족하며, 제3자나 공공 감사인이 비밀 키에 접근할 필요 없이 삭제를 검증할 수 있어야 합니다. 기존의 시도들은 이러한 공공 검증 기능을 추가할 때 선형적인 양의 추가 데이터를 요구하여 효율성 이점을 상쇄해 버렸습니다. 연구진은 특정 조건 하에서만 생성될 수 있고 누구나 검증할 수 있는 디지털 서명의 일종인 '제한된 서명(constrained signatures)' 기술을 사용하여 이 문제를 극복했습니다. 이 기술을 상수율 프레임워크와 결합함으로써, 연구진은 누구나 데이터가 삭제되었음을 검증할 수 있으면서도 대규모 메시지를 처리할 수 있을 만큼 충분히 효율적인 시스템을 만들어냈습니다.

이 연구는 광범위한 암호 프리미티브(cryptographic primitives)를 고효율의 검증 가능한 삭제를 지원하도록 업그레이드하는 통합 솔루션을 제공합니다. 양자 데이터를 통해 메시지를 보호하는 데 필요한 양이 메시지 자체와 거의 비슷하면서도, 데이터가 증명 가능하게 삭제될 수 있음을 보장하는 시스템을 갖추는 것이 처음으로 가능해졌습니다. 이 획기적인 성과는 인증된 삭제를 비실용적으로 만들었던 막대한 오버헤드를 제거하여, 이러한 양자 보안 기능들이 미래의 프라이버시 보호 기술에 통합될 수 있는 길을 열어주었습니다. 연구진은 삭제 인증서가 성공적으로 검증된다는 전제하에, 이 결과가 무한한 계산 능력을 가진 공격자에게도 유효함을 입증하였으며, 이를 통해 고전적 시스템은 결코 달성할 수 없는 방식으로 데이터가 영원히 사라졌음을 보장했습니다.

기술 요약: 상수율 인증 삭제 (Constant-Rate Certified Deletion)

1. 문제 정의

본 논문은 암호학의 근본적인 과제인 인증 삭제 (Certified Deletion, CD) 문제를 다룬다. CD는 사용자가 데이터가 이전에 암호화되었더라도 해당 데이터를 삭제했음을 제3자에게 증명할 수 있게 해준다. 이는 개인정보 보호 규정(예: GDPR)의 "잊힐 권리"에 의해 동기 부여된다.

고전적인 세계에서 CD는 불가능하다. 고전 정보는 임의로 복사될 수 있기 때문에, 공격자가 암호문을 보유하고 있다가 나중에 비밀키가 유출되었을 때 이를 복호화할 수 있기 때문이다. 양자 정보는 **복제 불가능 정리 (no-cloning theorem)**와 **불확정성 원리 (uncertainty principle)**를 통해 해결책을 제시한다. 이 원리들은 공격자가 상태를 복사한 뒤 서로 호환되지 않는 두 가지 기저(basis)에서 동시에 측정하는 것을 방지한다.

그러나 **플레인 모델 (plain model, 무작위 오라클이 없는 모델)**에서의 기존 CD 구성 방식은 치명적인 비효율성을 겪고 있다. 즉, 단 하나의 클래식 비트를 암호화하기 위해 선형 개수의 큐비트 ( $\Theta(\lambda)$ )가 필요하다. 이는 $n$ 비트 메시지에 대해 $\Theta(n\lambda)$ 의 총 통신 비용을 발생시켜, 서브콘스턴트 비율 (subconstant rate) ( $O(\log \lambda)/\Theta(\lambda)$ )을 초래한다. 상수율 (constant-rate) CD (메시지 크기에 비례하는 $O(n)$ 개의 큐비트를 사용하는 경우)를 달성하는 데 있어 주요 장벽은 이전 연구(특히 [BK23])에서 사용된 증명 기법이다. 해당 기법은 실제 메시지에 대한 의존성을 늦추기 위해 전체 메시지 문자열을 "추측(guessing)"하는 방식에 의존하는데, 이 추측 단계는 메시지 길이에 따라 지수적인 보안 손실을 발생시켜 긴 메시지에는 적용이 불가능하게 만든다.

2. 방법론

저자들은 지수적 보안 손실의 장벽을 극복하여, BB84 상태 기반 및 부분 공간 코셋 상태 (subspace coset states) 기반이라는 두 가지 광범위한 프리미티브 클래스에 대해 상수율 CD를 가능하게 하는 통합 프레임워크를 제안한다.

핵심 기술 혁신

선형 추출기를 이용한 위치별 추측 (Position-Wise Guessing with Linear Extractors):
전체 메시지 문자열을 추측하는 대신 (이는 지수적 손실을 유발함), 저자들은 위치별 추측 전략을 채택한다. [BK23]에서 사용된 단순 XOR 추출기를 유한체 $\mathbb{F}$ 상의 최대 거리 분리 (MDS) 코드에 기반한 고율 선형 추출기로 대체한다.
- 메시지 $m$ 은 양자 상태에 적용된 선형 맵 $R$ 과 무작위 패드 $r$ 을 사용하여 마스킹된다.
- 보안 증명은 한 번에 하나의 필드 원소를 추측하며 진행된다. 공격자가 추측되지 않은 나머지 메시지 비트에 대한 정보를 얻는 것을 방지하기 위해, 저자들은 남은 메시지의 누설을 계산적으로 일회용 패드(one-time pad) 처리하는 새로운 무작위 패드 $r$ 을 도입한다.
지연된 샘플링 및 순수화 (Deferred Sampling and Purification):
상수율 설정에서도 "컷 앤 츄즈 (cut-and-choose)" 논증을 복구하기 위해, 저자들은 공격자가 삭제 증명서(deletion certificate)를 출력한 이후에 기저 문자열 $\theta$ (또는 부분 공간 파라미터)의 샘플링을 지연시킨다.
- 저자들은 양자 상태를 챌린저와 공격자 사이의 얽힌 EPR 쌍으로 취급하기 위해 순수화 (purification) 기법을 활용한다.
- 무작위 패드 $r$ 을 도입함으로써, 저자들은 전체 분포를 변경하지 않고도 $\theta$ 의 선택을 지연시킬 수 있다. 이를 통해 챌린저는 증명서를 검증한 후에만 올바른 기저로 상태를 측정할 수 있으며, 결과적으로 공격자가 관련 비트에 대해 잘못된 기저로 측정하도록 보장한다.
효율적으로 검증 가능한 술어 (Efficiently Checkable Predicates):
증명의 결정적인 단계는 보안 논증을 "이상적인 세계"(암호화가 사소한 경우)에서 "실제 세계"(암호화가 계산적 가정을 따르는 경우)로 전이하는 것이다. 저자들은 공격자의 잔여 상태가 특정 구조적 조건(예: 에러가 희소한 상태)을 만족하는지 검증하는 효율적으로 검검 가능한 술어를 정의한다.
- BB84 상태의 경우, 푸리에 변환을 적용하고 MDS 코드의 오류 정정 능력을 사용하여 에러 벡터를 복구한다.
- 부분 공간 코셋 상태의 경우, 코셋 상태에 이 기술을 적용할 때 문제가 되었던 얽힘 문제를 우회하기 위해 영리한 순수화 전략을 사용하여 상태의 누설과 얽힌 부분을 분리한다.
제약된 서명을 통한 공개 검증 가능성 (Public Verifiability via Constrained Signatures):
상수율을 희생하지 않으면서 **공개 검증 가능한 삭제 (PVD)**를 달성하기 위해, 저자들은 최단 정수 솔루션 (Shortest Integer Solution, SIS) 가정에 기반한 **제약된 서명 (Constrained Signatures, CS)**을 통합한다.
- 개별 큐비트에 서명하는 대신 (이는 선형 오버헤드를 추가함), 양자 상태의 전체 중첩(superposition)에 코히어런트하게 서명한다.
- 저자들은 양자 인코딩에 의해 정의된 유효 집합(예: $T_{x,\theta}$ )에 속하는지 확인하는 술어와 연관된 제약된 서명 키를 사용한다.
- CS의 **함수 프라이버시 (function privacy)**와 4-wise 독립 해시 함수(무작위 오라클을 시뮬레이션하기 위함)를 활용하여, 중첩에 서명하는 것이 밑바탕이 되는 메시지나 기저에 대한 정보를 누설하지 않으면서도, 메시지 길이 $n$ 과는 독립적이고 보안 파라미터 $\lambda$ 에 대해서는 다항식 크기인 서명 크기를 유지하도록 한다.

3. 주요 기여 및 결과

A. BB84 상태를 위한 상수율 인증 삭제

저자들은 모든 $\epsilon > 0$ 에 대해 $(1-\epsilon)$ 의 비율을 달리는 BB84 상태 기반 CD에 대한 정리를 확립한다.

범위: 커밋먼트 스킴(Commitment Schemes), 비밀키 암호화(SKE), 공개키 암호화(PKE), 속성 기반 암호화(ABE), 완전 동형 암호(FHE), 타임 릴리스 암호화(Timed-Release Encryption), 위트니스 암호화(Witness Encryption)를 포함한 "All-or-nothing" 프리미티브에 적용된다.
메커니즘: 유한체 상의 MDS 코드와 위치별 추측 기법을 사용한다.
결과: 통신 비용은 $n$ 비트 메시지에 대해 $O(n)$ 큐비트이며, 이는 $\Theta(n\lambda)$ 였던 기존 방식보다 크게 개선된 것이다.

B. 부분 공간 코셋 상태를 위한 상수율 인증 삭제

저자들은 프레임워크를 부분 공간 코셋 상태로 확장하여 $1/4$ 의 비율을 달성한다.

범위: 블라인드 위임(Blind Delegation), 보안 소프트웨어 리싱(Secure Software Leasing), 기능 암호화(FE), 차등 입력 구별 불가능성 난독화(diO), CCA-PKE 등 "All-or-nothing"을 넘어선 프리미티브에 적용된다.
메커니즘: BB84 기반 증명을 코셋 상태에 적용할 때 발생하는 얽힘 장벽을 피하는 새로운 순수화 기법을 활용한다.
결과: 이는 플레인 모델에서 이러한 고급 프리미티브를 위한 최초의 상수율 구성이다.

C. 공개 검증 가능한 인증 삭제 (PVD)

SIS 가정 하에서, 저자들은 상수율 특성을 유지하는 PVD 스킴을 구축한다.

의의: 기존 PVD 구성은 선형 오버헤드가 필요하여 비율을 파괴하거나, 난독화(iO)와 같은 강력한 가정을 필요로 했다.
결과: 본 논문은 SIS만을 가정하여 BB84 및 코셋 상태 기반 프리미티브 모두에 대해 최초의 상수율 PVD 스킴을 제공한다.

4. 의의 및 주장

본 논문은 양자 암호학의 오랜 미해결 과제인, 플레인 모델에서 상수율을 유지하면서 영구적 보안 (everlasting security) (삭제 후 무제한 공격자에 대한 보안)을 보장하는 인증 삭제 스킴을 구축하는 문제를 해결했다고 주장한다.

장벽 극복: 이 연구는 이전에 메시지 길이를 로그 스케일로 제한했던 [BK23] 증명 기법의 "추측 장벽(guessing barrier)"을 명확히 식별하고 극복했다.
통합 프레임워크: 기초 프리미티브에 필요한 가정(PVD를 위한 SIS 제외) 외에 새로운 가정을 추가하지 않고도 광범위한 암호학적 프리미티브를 인증 삭제가 가능하도록 업그레이드하는 범용 컴파일러를 제공한다.
실질적 효율성: 큐비트 오버헤드를 보안 파라미터에 대한 선형에서 상수 계수로 줄임으로써, 인증 삭제를 대규모 데이터 애플리케이션에 이론적으로 실행 가능하게 만들었다.
한계 인정: 저자들은 상수율을 달달성했지만, BB84 상태의 경우 비율이 약 $1/3$ (또는 불균형한 파라미터 시 $1-\epsilon$ )이고 코셋 상태의 경우 $1/4$ 임을 언급하며, 1에 접근하지는 못했다는 점을 밝힌다. 또한, 부분 공간 코셋 상태를 위한 PVD 컴파일러가 클래식 기능 내에서 코히어런트하게 언컴퓨팅(uncomputing)하는 데 어려움이 있어 현재는 모든 "All-or-nothing 너머"의 프리미티브(예: diO 또는 FE)까지 확장되지는 않는다는 점을 인정한다.

요약하자면, 이 연구는 표준 격자 가정(lattice assumptions)을 사용하여 높은 효율성(상수율)과 강력한 보안 보장(영구적 보안 및 공개 검증 가능성)을 갖춘 인증 삭제를 구현함으로써, 양자 보안 데이터 삭제의 실용성을 높이는 중요한 진전을 이루었다.