기술 요약: 전처리 모델에서의 인증된 삭제를 포함한 하이브리드 암호화

문제 정의

본 논문은 인증된 삭제(Certified Deletion, CD)를 포함한 암호화의 근본적인 과제를 다룬다. 표준적인 아웃소싱 시나리오에서, 앨리스(Alice)는 밥(Bob, 또는 클라우드 서버)을 위해 데이터를 암호화하지만, 고전적 정보 이론에 따르면 디지털 데이터는 완벽하게 복제될 수 있다. 결과적으로, 나중에 암호 키가 노출되거나 암호 체계가 깨질 경우, 서버가 암호문(ciphertext)을 삭제했다고 주장하더라도 공격자는 평문(plaintext)을 복구할 수 있다.

Broadbent와 Islam(BI)은 정보 이론적 인증된 삭제를 달eric하기 위해 양자 정보(구체적으로 Wiesner 코딩 및 복제 불가능성 정리)를 사용하는 대칭 키 솔루션을 제안했으나, 이들의 방식은 일회용 사용으로 제한되며 메시지 길이만큼 긴 비밀 키를 필요로 한다. 이후의 공개키 인증된 삭제(PKE-CD) 방식들은 키 재사용을 허용하지만, 이는 미래의 컴퓨팅 발전(양자 컴퓨터 등)에 취und vulnerable한 **계산적 난해성 가정(computational hardness assumptions)**에 의존한다. 저자들은 공백을 식별하였다: 계산적 난해성 가정을 피하면서 임의의 메시지 길이를 지원하고 키 재사용이 가능한 인증된 삭제 암호화의 필요성이다.

방법론

저자들은 **전처리 모델에서의 하이브리드 암호화 인증된 삭제(pHE-CD)**라고 불리는 프레임워크를 제안한다. 이 접근 방식은 앨리스와 밥이 암호화 단계 이전에 사전에 공유된 상관 관계가 있는 무작위 문자열(공용 분포 $P(X, Y, Z)$를 통해 생성됨)을 공유하는 **상관 관계 무작위성 모델(correlated randomness model)**을 활용한다.

이 방법론은 두 가지 구별되는 암호학적 프리미티브의 결합에 의존한다:

1. 정보 이론적 키 캡슐화 메커니즘(iKEM): 이 구성 요소는 앨리스와 밥이 그들의 상관 관계 무작위성을 사용하여 공유 비밀 키를 구축한다. 이는 난해성 가정에 의존하지 않고 계산 능력이 무한한 공격자에 대해서도 보안을 제공한다.
2. 인증된 삭제를 포함한 데이터 캡슐화 메커니즘(DEM-CD): 이 구성 요소는 iKEM에서 유도된 키를 사용하여 실제 메시지를 암호화한다. DEM-CD는 인증된 삭제 속성을 담당한다.

이 결합된 시스템의 보안은 두 유형의 공격자에 대해 분석된다:

• 계산적으로 제한된 공격자: 양자 다항 시간(QPT) 내로 제한된 공격자.
• 계산적으로 무제한인 공격자: 무제한의 계산 능력을 가진 공격자.

논문은 **영속적 인증된 삭제 보안(Everlasting Certified Deletion Security, EV-CD)**을 정의하는데, 여기서 기밀성은 삭제 증명서 검증 전에는 계산적이지만, 유효한 증명서가 발행되면 정보 이론적으로 변한다.

주요 기여

1. pHE-CD의 형식화

저자들은 전처리 모델에서의 인증된 삭제를 포함한 하이브리드 암호화 패러다임을 확장하여 pHE-CD 스킴을 도입하고 형식화하였다. 이들은 이 환경에 적합한 암호화(IND-qe-CPA) 및 인증된 삭제(EV-qe-CD)에 대한 보안 개념을 정의한다.

2. 두 가지 구성(Constructions)

논문은 서로 다른 보안 트레이드오프를 제공하는 pHE-CD 프레임워크 기반의 두 가지 구체적인 구성을 제시한다:

• 구성 1 (완전 정보 이론적 방식):

  • 구성 요소: 정보 이론적 iKEM과 정보 이론적으로 안전한 DEM-CD(Broadbent-Islam의 일회용 SKE-CD를 사용하여 인스턴스화됨)를 결합한다.
  • 특징: 암호화 및 인증된 삭제 모두에 대해 정보 이론적 보안을 제공한다.
  • 한계: 각 암호화마다 새로운 키를 필요로 한다(OTP와 유사함). 비트 단위 반복 없이도 임의의 긴 메시지를 직접 지원할 수는 있으나, 전통적인 의미의 키 재사용은 지원하지 않는다.

• 구성 2 (계산적 암호화, 영속적 삭제):

  • 구성 요소: 정보 이론적 iKEM과 인증된 삭제를 위해 적응된 (AES와 같은 대칭 프리미티브를 사용하는) 계산적으로 안전한 DEM을 결합한다.
  • 특징:
    • 암호화: QPT 공격자에 대해 계산적 보안(양자 내성)을 제공한다.
    • 인증된 삭제: **영속적 보안(everlasting security)**을 제공한다. 삭제 증명서 검증 전에는 보안이 계산적이지만, 성공적인 검증 후에는 보안이 정보 이론적이 되어, 공격자가 복호화 키를 얻더라도 평문을 학습할 수 없음을 보장한다.
  • 효율성: 이 구성은 상수 길이의 키를 사용하는 키 효율적(key-efficient) 방식이다. 각 비트를 독립적으로 암호화하고 암호문을 연결함으로써 임의의 긴 메시지를 지원한다.

3. 보안 증명

저자들은 pHE-CD의 보안이 구성 요소의 보안으로 환원됨을 입증하는 엄격한 결합 정리(composition theorems)를 제공한다:

• 암호화 보안: iKEM이 IND-qe-CEA 보안이고 DEM-CD가 IND-OT 보안이면, 결과물인 pHE-CD는 IND-qe-CPA 보안이다.
• 삭제 보안: iKEM이 IND-qe-CEA 보안이고 DEM-CD가 일회용 EV-CD 보안이면, 결과물인 pHE-CD는 EV-qe-CD 보안이다.
  증명은 하이브리드 게임 논법(hybrid-game argument)을 사용하여, pHE-CD를 깨는 공격자가 iKEM 또는 DEM-CD를 깨는 공격자로 변환될 수 있음을 보여준다.

결과

• 실현 가능성: 본 논문은 계산적 난해성 가정에 의존하지 않고 전처리 모델에서 인증된 삭제를 포함한 하이브리드 암호화가 가능하다는 것을 입증한다.
• 보안 보장:
  • 구성 1은 암호화와 삭제 모두에 대해 무조건적(정보 이론적) 보안을 달성한다.
  • 구성 2는 암호화에 대해서는 계산적 보안을, 영속적(everlasting) 삭제에 대해서는 정보 이론적 보안을 달성한다. 이는 삭제 검증이 성공하면, 설령 공격자가 나중에 복호화 키를 획득하더라도 데이터가 공격자의 관점에서 정보 이론적으로 제거되었음을 의미한다.
• 구현: 구성 방식은 BB84 QKD 프로토콜과 밀접하게 연관된 Wiesner conjugate coding을 활용하며, 이는 현재의 양자 기술로 구현 가능하다.
• 확장성: 두 스킴 모두 임의의 길이의 메시지 암호화를 지원한다.

의의 및 주장

저자들은 자신들의 연구가 기존 PKE-CD 방식에서 발견되는 계산적 난해성 가정에 대한 의존을 양자 정보 이론의 근본 원칙으로 대체한다고 주장한다. 상관 관계 무작위성을 활용함으로써 다음을 달성한다:

1. 미래의 발전에 대한 견고성: 보안이 미래의 알고리즘이나 양자 컴퓨터에 의해 깨질 수 있는 수학적 문제(예: 인수 분해 또는 격자 문제)의 어려움에 의존하지 않는다.
2. 영속적 기밀성: 특히 구성 2의 경우, 성공적인 삭제 검증 시 기밀성이 계산적 보안에서 정보 이론적 보안으로 전환되는 독특한 특성을 강조한다. 이는 암호 체계가 미래에 깨지더라도, 검증된 삭제 데이터는 안전하게 유지됨을 보장한다.
3. 실용성: Wiesner 코딩의 사용은 이들이 일부 이론적인 양자 암호 제안들과 달리 현재의 양자 기술로 구현 가능함을 시사한다.

결론적으로, 저자들은 iKEM 구성 요소가 상관 관계 무작위성(QKD로부터 유도될 수 있음)에 의존한다는 점을 언급하며, qKEM의 보안을 캡슐화 오라클 접근을 가진 공격자까지 확장하는 것이 향후 연구 과제임을 밝힌다. 저자들은 모든 양자 암호학의 미해결 문제를 해결하려는 것이 아니라, 계산적 가정이 없는 인증된 삭제 분야를 진전시키는 공식적인 프레임워크와 구체적인 구성을 제공했다는 점을 명시한다.