Registered Attribute-Based Encryption with Publicly Verifiable Certified Deletion, Everlasting Security, and More

이 논문은 중앙 권한 기관 없이도 사용자의 키 등록과 세밀한 접근 제어를 지원하면서도 공개적으로 검증 가능한 인증 삭제 및 영구적 보안을 보장하는 최초의 등록 속성 기반 암호화 (RABE) 체계를 제안합니다.

핵심

이 논문은 **"디지털 데이터의 영구적이고 검증 가능한 삭제"**를 가능하게 하는 새로운 암호화 기술을 제안합니다.

기존의 암호화는 "열쇠를 잃어버리면 열 수 없다"는 원리지만, 이 기술은 **"열쇠를 주더라도, 이미 데이터를 영구히 파기했음을 증명할 수 있다"**는 더 강력한 개념을 다룹니다. 특히 이 기술은 중앙 관리자 (예: 구글, 아마존 같은 거대 기업) 에 의존하지 않고, 사용자 스스로가 권한을 관리할 수 있는 분산형 시스템에서 작동합니다.

이 복잡한 내용을 일상적인 비유로 쉽게 설명해 드리겠습니다.

---

1. 문제 상황: "지우개 없는 디지털 세상"

우리가 컴퓨터나 스마트폰에 파일을 지우면, 실제로는 하드디스크에서 단순히 '지우기' 표시만 할 뿐 데이터는 남아있습니다. 나중에 해커가 열쇠 (비밀번호) 를 훔치거나, 미래에 슈퍼컴퓨터가 개발되면 그 '지워진' 데이터도 다시 복구할 수 있습니다.

• 비유: 종이 문서에 쓴 글을 지우개로 지우면, 잉크 자국이 남아서 확대경으로 보면 다시 읽을 수 있는 것과 같습니다. 디지털 세상에서는 '완전한 삭제'가 거의 불가능했습니다.

2. 해결책: "양자 지우개 (Certified Deletion)"

이 논문은 **양자 역학 (Quantum Mechanics)**의 원리를 이용합니다. 양자 물리학에는 **"복제 불가 정리"**라는 법칙이 있습니다. 즉, 양자 상태의 정보는 완벽하게 복사할 수 없습니다.

• 비유: 마법 같은 잉크를 상상해 보세요. 이 잉크로 글을 쓰면, 한 번 읽거나 지우려고 하면 잉크가 스스로 변색되어 원래 글자를 읽을 수 없게 됩니다.
  • 이 기술을 **'인증된 삭제 (Certified Deletion)'**라고 합니다.
  • 사용자가 데이터를 삭제할 때, "내가 정말로 이 데이터를 영구히 파괴했습니다"라는 **증명서 (Certificate)**를 발급받습니다. 이 증명서가 있으면, 나중에 열쇠를 훔친 해커라도 그 데이터는 절대 복구할 수 없습니다.

3. 새로운 도전: "중앙 관리자가 없는 세상 (RABE)"

기존의 이 기술은 대부분 '중앙 관리자'가 열쇠를 나눠주고 삭제 증명을 확인하는 방식이었습니다. 하지만 중앙 관리자가 해킹당하면 모든 시스템이 무너집니다.

이 논문은 **등록형 속성 기반 암호화 (RABE)**라는 기술을 도입하여 중앙 관리자 없이도 작동하게 만들었습니다.

• 비유:
  • 기존 방식 (중앙 집중형): 모든 사람이 은행 (중앙 관리자) 에 가서 열쇠를 발급받고, 은행이 "이 사람이 문서를 지웠습니다"라고 확인해 줍니다. 은행이 망하면 모두 위험합니다.
  • 새로운 방식 (분산형 RABE): 각자가 자신의 열쇠를 직접 만듭니다. 그리고 서로의 공개 열쇠만 '공유 게시판'에 등록합니다. 중앙 관리자는 그 목록만 정리할 뿐, 누구의 열쇠도 알지 못합니다.
  • 이 논문은 바로 이 분산된 시스템에서도 '영구 삭제'가 가능하도록 세계 최초로 기술을 개발했습니다.

4. 이 기술의 두 가지 핵심 기능

이 논문은 크게 두 가지 버전의 기술을 제시합니다.

A. 개인 검증 가능 버전 (Privately Verifiable)

• 상황: 보낸 사람 (송신자) 만이 삭제 여부를 확인할 수 있습니다.
• 비유: 친구가 보낸 편지를 받았는데, 친구에게만 "이 편지를 태웠습니다"라는 확인서를 보여줄 수 있습니다. 제 3 자는 그 확인서의 진위를 알 수 없습니다.
• 용도: 민감한 개인 간 통신에 적합합니다.

B. 공개 검증 가능 버전 (Publicly Verifiable)

• 상황: 누구든 (심지어 제 3 자나 규제 기관) 삭제 증명을 확인할 수 있습니다.
• 비유: 친구가 편지를 태웠다는 것을 증명하는 '소각 증명서'를 공공장소에 붙여놓습니다. 지나가는 사람 누구나 "아, 이 친구가 정말로 편지를 태웠구나"라고 확인할 수 있습니다.
• 용도: 법적인 규제 준수나 투명성이 필요한 기업 간 거래에 적합합니다.

5. "영구적 보안 (Everlasting Security)"이란 무엇인가?

이 기술의 가장 놀라운 점은 **'영구적 보안'**입니다.

• 일반 암호화: "지금의 컴퓨터로는 해독할 수 없지만, 100 년 후의 슈퍼컴퓨터 앞에서는 무너질 수 있다."
• 이 기술 (Certified Everlasting): "삭제 증명서가 발급되면, 미래의 어떤 슈퍼컴퓨터나 천재 해커가 등장해도 절대 복구할 수 없다."
• 비유: 데이터를 지우기 위해 '양자 폭탄'을 터뜨린 것과 같습니다. 폭탄이 터진 후, 그 자리에 남아있는 것은 아무것도 없습니다. 미래의 기술이 아무리 발전해도, '없던 것'을 다시 만들 수는 없기 때문입니다.

6. 요약: 왜 이 논문이 중요한가?

1. 중앙 관리자 불필요: 거대 기업이 열쇠를 쥐고 있을 필요 없이, 사용자 스스로가 안전을 지킬 수 있습니다.
2. 완벽한 삭제: 데이터를 지우면, 열쇠를 훔쳐도 절대 복구할 수 없습니다.
3. 검증 가능: 삭제 사실을 스스로 증명하거나, 누구나 확인할 수 있습니다.
4. 미래 대비: 양자 컴퓨터가 등장해도, 일단 삭제된 데이터는 영원히 안전합니다.

한 줄 요약:

"이 기술은 디지털 세상에서 **'지우개'**가 실제로 작동하도록 만들었으며, 그 지우기가 **'누구나 볼 수 있는 증명서'**로 남게 하여, 중앙 관리자 없이도 데이터를 영원히 안전하게 파기할 수 있게 해줍니다."

기술 요약

1. 연구 배경 및 문제 정의 (Problem)

• 인증된 삭제 (Certified Deletion) 의 한계: 기존 인증된 삭제 기술은 양자 역학의 '복제 불가 정리 (No-cloning theorem)'를 활용하여 암호화된 데이터를 물리적으로 복구 불가능하게 삭제할 수 있음을 보장합니다. 그러나 대부분의 기존 연구 (ABE, FHE 등) 는 **중앙 집중형 신뢰 기관 (Trusted Authority)**에 의존합니다. 이 기관이 키를 생성하고 분배하기 때문에, 기관이 해킹되거나 악의적으로 작동할 경우 전체 시스템의 보안이 붕괴되는 키 은닉 (Key Escrow) 취약점이 존재합니다.
• 등록 기반 암호화 (RBE) 의 필요성: 키 은닉 문제를 해결하기 위해 '등록 기반 암호화 (RBE)'가 제안되었습니다. RBE 는 사용자가 자신의 키 쌍을 생성하고 공개키만 등록하는 탈중앙화 모델을 제공합니다. 하지만 기존 RABE(등록 기반 속성 기반 암호화) 는 인증된 삭제 기능을 지원하지 못했습니다.
• 핵심 연구 질문: "중앙 신뢰 기관 없이 탈중앙화된 RABE 프레임워크에서 인증된 삭제 (Certified Deletion) 를 구현할 수 있는가?" 그리고 더 나아가 "삭제 후에도 무제한 계산 능력을 가진 적대자로부터도 정보가 보호되는 **인증된 영구 보안 (Certified Everlasting Security)**을 달성할 수 있는가?"

2. 주요 방법론 및 기술적 접근 (Methodology)

저자들은 RABE 와 인증된 삭제를 결합하기 위해 다음과 같은 계층적 구조와 새로운 원시 (Primitive) 를 도입했습니다.

A. 핵심 구성 요소: Shadow Registered ABE (Shad-RABE)

• 개념: 기존 RABE 에 '시뮬레이션 (Simulation)' 기능을 추가한 새로운 원시입니다. 보안 증명 과정에서 실제 키 대신 시뮬레이션된 키와 암호문을 생성할 수 있게 하여, 적대자가 삭제 증명 후에도 키를 획득하더라도 메시지를 복호화할 수 없음을 증명하는 데 필수적입니다.
• 구현:
  • 구분 불가능성 오비퓨케이션 (iO): 암호화 회로를 숨깁니다.
  • 영지식 증명 (ZKA): 증명자가 특정 속성을 만족함을 증명하되 정보를 노출하지 않습니다.
  • 등록 기반 ABE (RABE): 탈중앙화 키 관리의 기반이 됩니다.
  • 격자 기반 (Lattice-based): 양자 내성 (Post-Quantum) 보안을 위해 LWE(Learning With Errors) 가정과 그 변형 (ℓ-succinct LWE, Plain LWE, Equivocal LWE) 을 기반으로 구현되었습니다.

B. 인증된 삭제 (Certified Deletion, CD) 구현

두 가지 검증 모델을 제안합니다.

1. 개인 검증 가능 (Privately Verifiable, PriVCD):
   • 하이브리드 암호화: Shad-RABE 를 사용하여 대칭키를 암호화하고, 실제 메시지는 인증된 삭제가 가능한 대칭키 암호 (SKE-CD) 로 암호화합니다.
   • 검증: 삭제 증명 (Certificate) 은 송신자 (공개키 소유자) 만이 검증할 수 있습니다.
2. 공개 검증 가능 (Publicly Verifiable, PubVCD):
   • One-Shot Signature (OSS) 와 Witness Encryption (WE) 활용:
     • 수신자는 양자 비밀키로 0 또는 1 중 하나만 서명할 수 있는 'One-Shot Signature' 키 쌍을 생성합니다.
     • 송신자는 "0 에 대한 유효한 서명이 존재함"을 증언 (Witness) 으로 하는 Witness Encryption 을 사용하여 메시지를 암호화합니다.
     • 삭제는 수신자가 "1 에 대한 서명"을 생성하여 증명합니다. OSS 의 특성상 0 과 1 을 동시에 서명할 수 없으므로, 1 을 서명하면 0 을 해독할 수 있는 키가 파괴되어 영구적으로 삭제됩니다.
     • 장점: 제 3 자가 서명을 검증하여 삭제가 이루어졌음을 공개적으로 확인할 수 있습니다.

C. 인증된 영구 보안 (Certified Everlasting Deletion, CED)

• 개념: 삭제 증명 후, 적대자가 무제한의 계산 능력을 갖게 되더라도 (정보이론적 보안) 메시지를 복원할 수 없음을 보장합니다.
• 기반: BB84 양자 상태와 **Certified Everlasting Lemma (CEL)**를 활용합니다.
  • 개인 검증 (PriVCED): 무작위 기저 (Basis) 로 인코딩된 BB84 양자 상태를 암호화합니다. 삭제 시 잘못된 기저로 측정하면 정보가 파괴됩니다.
  • 공개 검증 (PubVCED): BB84 상태에 '일회용 서명 (One-time unforgeable signature for BB84 states)'을 적용하여, 공개적으로 삭제 증명을 검증하면서도 양자 상태의 파괴를 보장합니다.

3. 주요 기여 (Key Contributions)

1. 최초의 탈중앙화 RABE-CD/CED 제안: 중앙 권한 없이 인증된 삭제 및 영구 삭제를 지원하는 첫 번째 격자 기반 (Lattice-based) 키 정책 RABE 스킴을 설계했습니다.
2. Shad-RABE 원시 개발: RABE 프레임워크 내에서 시뮬레이션 가능한 새로운 원시인 Shad-RABE 를 제안하고, 이를 iO, ZKA, RABE 를 조합하여 구성했습니다. 이는 향후 인증된 삭제 스킴의 핵심 빌딩 블록이 됩니다.
3. 다양한 검증 모델의 구현:
   • RABE-PriVCD: SKE-CD 와 Shad-RABE 를 결합한 개인 검증 가능 스킴.
   • RABE-PubVCD: Witness Encryption 과 One-Shot Signature 를 결합한 공개 검증 가능 스킴.
   • RABE-PriVCED & RABE-PubVCED: BB84 상태와 Certified Everlasting Lemma 를 활용하여 정보이론적 보안을 제공하는 영구 삭제 스킴.
4. 양자 내성 (Post-Quantum) 보장: 모든 스킴을 격자 기반 (Lattice-based) 가정 (LWE 등) 위에 구축하여 양자 컴퓨터 공격에도 안전한 것을 증명했습니다.

4. 결과 및 성능 (Results)

• 보안 증명: 모든 제안된 스킴은 양자 다항 시간 (QPT) 적대자에 대해 안전하며, 인증된 삭제 및 영구 삭제 보안 정의를 만족함을 하이브리드 증명을 통해 rigorously 증명했습니다.
• 구현 가능성:
  • Shad-RABE 는 Champion et al. 의 RABE, Bitansky et al. 의 ZKA, Cini et al. 의 iO 를 격자 기반으로 구체화하여 구현 가능합니다.
  • RABE-PubVCD 는 VWW22/Tsa22 의 Witness Encryption 과 OSS 스킴을 결합하여 격자 기반 구현을 제시했습니다.
• 효율성: RABE 의 특성상 키 크기와 암호문 크기가 사용자 수에 비례하지 않고 로그 (log) 수준으로 유지되어 확장성이 우수합니다.

5. 의의 및 중요성 (Significance)

• 신뢰 모델의 혁신: 기존 암호학의 '중앙 집중형 신뢰 기관' 의존성을 완전히 제거하고, 탈중앙화된 환경에서도 데이터의 영구적 삭제를 보장할 수 있음을 입증했습니다. 이는 클라우드 스토리지, 규제 준수 (GDPR 등) 가 필요한 분산 시스템에 매우 중요합니다.
• 양자 보안의 확장: 인증된 삭제가 단순한 PKE 나 ABE 를 넘어, 복잡한 접근 제어 (Attribute-Based) 와 결합되어 탈중앙화 환경에서도 작동할 수 있음을 보여주었습니다.
• 영구 보안의 실용화: 계산적 보안을 넘어 정보이론적 보안을 제공하는 '영구 삭제'를 RABE 에 도입함으로써, 미래의 기술 발전 (양자 컴퓨터 등) 으로 인한 데이터 유출 위험까지 차단하는 새로운 패러다임을 제시했습니다.
• 공개 검증 가능성: 삭제 증명을 제 3 자가 검증할 수 있게 함으로써, 규제 기관이나 감사자가 데이터 삭제를 투명하게 확인할 수 있는 환경을 조성했습니다.

결론적으로, 이 논문은 탈중앙화 암호화와 양자 기반 데이터 삭제 기술을 융합하여, 중앙 권한 없이도 강력하고 검증 가능한 데이터 생명주기 관리를 가능하게 하는 획기적인 암호학적 프레임워크를 제시했습니다.