기술 요약: 고전적 임대인(Lessor)을 사용하는 양자 키 리싱(Quantum Key Leasing)에 대한 통합적 접근 방식

문제 정의

보안 키 리싱(Secure Key Leasing, SKL)은 임대인(Lessor)이 임차인(Lessee)에게 양자 비밀 키를 대여하여, 임차인이 특정 암호 기능(예: 복호화, 서명 또는 PRF 평가)을 수행할 수 있도록 하는 암호학적 프리미티브이다. 결정적으로, 임대인은 나중에 이 능력을 검증 가능한 방식으로 철회(Revoke)할 수 있어야 한다. 임차인은 자신이 키를 파기했음을 증명하는 삭제 인증서(Deletion Certificate)를 반환해야 하며, 그 이후에는 해당 기능을 수행할 수 없어야 한다.

기존 연구들은 다양한 프리미티브(PKE, FHE, PRF, 서명)에 대해 SKL을 구현해 왔으나, 다음과 같은 두 가지 주요 한계점을 갖는다:

1. 모듈성 부족: 구성 방식이 통합된 프레임워크에서 도출되기보다는 특정 프리미티브에 맞춤화된 임시방편(Ad-hoc)적인 경우가 많다.
2. 양자 임대인 요구 사항: 기존 방식은 일반적으로 임대인(클라이언트)이 양자 상태를 준비하고 전송할 수 있는 완전한 양자 능력을 갖출 것을 요구한다. 실제 클라우드 컴퓨팅 시나리오에서는 클라이언트가 요구하는 양자 자원을 최소화하는 것이 필수적이다. 고전적 임대인을 지원하는 유일한 알려진 방식(Chardouvelis et al., Eurocrypt 2025)은 공개키 암호(PKE)와 완전 동형 암호(FHE)로 제한되어 있으며, 특정 LWE 구조에 크게 의존하기 때문에 다른 프리미티브로의 일반화가 어렵다.

본 연구가 다루는 핵심 질문은 다음과 같다: 고전적 임대인을 지원하면서 광범위한 암호 기능들을 아우르는 모듈형 SKL 프레임워크를 개발할 수 있는가?

방법론

저자들은 범용 암호 프리미티브를 고전적 임대인을 위한 SKL 스킴으로 "업그레이드"하는 모듈형 프레임워크를 제안한다. 이 구성은 세 가지 핵심 구성 요소에 기반한다:

1. 노이지 트랩도어 클로-프리(Noisy Trapdoor Claw-Free, NTCF) 생성기: Broadbent 등의 연구와 Mahadev의 연구에 기반한 NTCF는 고전적 클라이언트가 양자 서버가 특정 "클로 상태(Claw state)"(즉, $f(a_0)=f(a_1)=y$를 만족하는 두 전사(Pre-image) $|0\rangle|a_0\rangle + |1\rangle|a_1\rangle$의 중첩)를 준비했는지 검증할 수 있게 한다. 보안은 *적응적 하드코어 비트 속성(Adaptive Hardcore Bit Property)*에 의존하며, 이는 서버가 Hadamard 기저(삭제를 증명하기 위함)로 상태를 측정하면 계산 기저에서의 전사를 회복할 능력을 상실함을 보장한다.
2. 특수 이중 모드 보안 함수 평가(Special Dual-Mode SFE): 저자들은 학습 기반 오류(LWE) 가정에 기반한 새로운 SFE 스킴을 구축한다. 이 SFE는 프레임워크에 필요한 특정 속성들을 갖는다:
   • 이중 모드(Dual-Mode): 입력 메시지를 추출할 수 있는 추출 가능 모드(Extractable mode) 또는 입력을 통계적으로 숨기는 *은닉 모드(Hiding mode)*로 동작한다.
   • 상태 회복 가능성(State Recoverability): 은닉 모드에서, 수신자가 보유한 상태 정보는 사이퍼텍스트와 입력을 사용하여 트랩도어를 통해 회복될 수 있다.
   • 효율적인 중첩 생성: 수신자는 사용된 무작위성과 얽힘(Entanglement)을 남기지 않고도 SFE 상태를 중첩 상태로 생성할 수 있다.
   • 분해 가능성(Decomposability): 수신자의 상태는 개별 비트에 의존하는 블록들로 분해될 수 있으며, 이는 보안 환원(Security Reduction)에 결정적인 속성이다.
3. 병렬 추출을 이용한 워터마킹(Watermarking with Parallel Extraction): 프레임워크는 대상 프리미티브(PKE, PRF, 서명)의 워터마크 적용 가능한 버전을 활용한다. 워터마크 적용 가능한 스킴은 "마크(Mark, 비밀 문자열)"를 키에 삽嵌入할 수 있게 한다. 보안 개념은 만약 공격자가 올바르게 작동하는 기능적 프로그램(예: 복호기 또는 서명기)을 생성한다면, "병렬 추출기(Parallel Extractor)"가 공격자의 양자 상태로부터 삽입된 마크를 회복할 수 있음을 요구한다.

핵심 메커니즘:
프레임워크는 NTCF 클로 상태와 얽힘으로써 표준 키를 양자 상태로 변환한다.

• 임대인(고전적)은 NTCF 공공 파라미터와 SFE CRS를 임차인에게 보낸다.
• 임차인은 클로 상태를 준비하고 SFE의 첫 번째 라운드를 실행한다.
• 임대인은 NTCF 전사(Pre-images)를 실제 비밀 키(예: 워터마크 적용 가능한 PKE 키)로 매핑하는 회로 $C$를 정의한다. 이 회로는 SFE를 통해 동형적으로 실행된다.
• 임차인은 결과물을 받으며, 결과적으로 비밀 키가 중첩 내에 임베딩된 양자 상태 $|0\rangle|sk_0\rangle + |1\rangle|sk_1\rangle$를 얻게 된다.
• 삭제(Deletion): 키를 철회하기 위해, 임대인은 임차인에게 Hadamard 기저로 상태를 측정할 것을 요청한다. NTCF와 SFE의 특성 덕분에, 유효한 측정 인증서는 임차인이 계산 기저의 정보(전사와 그에 따른 비밀 키)를 상실했음을 증명한다.
• 보안 환원(Security Reduction): 만약 공격자가 삭제 검증을 통과했음에도 여데 암호 작업을 수행할 능력을 유지한다면, 환원은 워터마킹 스킴의 병렬 마크 추출 속성을 사용하여 NTCF 전사를 추출한다. 이는 삭제 인증서(Hadampad 기저 측정을 제공함)와 결합되어 NTCF의 Cut-and-choose 적응적 하드코어 비트 속성을 깨뜨린다.

주요 기여 및 결과

1. 통합된 고전적 임대인 SKL 프레임워크

본 논문은 병렬 추출 가능한 워터마킹을 갖춘 모든 포스트 퀀텀 보안 프리미티브를 고전적 임대인용 SKL 스킴으로 변환하는 일반적인 컴파일러를 제시한다. 이 프레임워크는 모듈식이며, 임시방편적인 구성이 아닌 표준적인 가정(LWE)에 기반한다.

2. 특정 스킴들

이 프레임워크를 바탕으로 저자들은 다음을 구축한다:

• 고전적 임대인용 PKE-SKL: 이전의 LWE 기반 구성(Chardouvelis et al., Eurocrypt 2025)에서 PKE 자체를 위한 특정 LWE 구조에 대한 의존성을 제거함으로써 이를 개선하였다. 기초가 되는 PKE는 어떤 IND-CPA 보안 포스트 퀀텀 스킴이든 될 수 있다.
• 고전적 임대인용 PRF-SKL: 고전적 임대인을 가진 보안 키 리싱을 갖춘 PRF의 첫 번째 구성이다. 이는 LWE에 기반하며 워터마크 적용 가능한 예측 불가능 함수(UPF)를 활용한다.
• 고전적 임대인용 DS-SKL: 고전적 임대인을 가진 디지털 서명의 첫 번째 구성이다. 이를 위해서는 기초가 되는 서명 스킴이 결맞은 서명 가능성(Coherent Signability)(상태를 붕괴시키지 않고 중첩된 키를 사용하여 서명할 수 있는 능력)을 가져야 하며, 저자들은 이를 LWE/SIS로부터 구축한다.

3. 보안 개념

모든 스킴은 **VRA 보안(Verification Key Revealing Attacks에 대한 보안)**을 만족한다. 이는 매우 강력한 보안 개념으로, 공격자가 유효한 삭제 인증서를 제출한 후에 삭제 검증 키를 부여받더라도 스킴이 안전하게 유지됨을 의미한다. 이는 공격자가 사후에 검증 키를 사용하여 속임수를 쓰거나 키에 대한 정보를 학습하는 것을 방지한다.

4. 비대화형 키 생성

저자들은 PKE-SKL에 대해 **비대화형 키 생성(Non-interactive Key Generation)**을 달성하기 위해 구성을 정교화하였으며(PRF/DS의 경우 상수 라운드 달성), 이후에도 이를 유지한다. 표준 프로토콜에서는 키 생성을 위해 임대인과 임차인이 상호작용해야 한다. 개선된 버전은 임대인이 공공 파라미터를 한 번 게시하면, 그 후 임차인이 비대화형으로 키를 생성할 수 있게 한다. 전체 키 생성은 암호화/서명 단계로 유예되며, 여기서 임차인은 사이퍼텍스트로부터 얻은 보조 정보를 사용하여 키 준비를 완료한다.

5. 보조 구성

이 과정에서 논문은 다음을 구축한다:

• 병렬 추출 속성을 가진 PKE, UPF 및 디지털 서명을 위한 워터마킹 스킴.
• 표준 SFE 정의에는 없는 고유한 상태 회복 가능성 및 분해 가능성 속성을 만족하는 특수 이중 모드 SFE 스킴.

의의 및 주장

본 논문은 광범위한 암호 기능(PKE, PRF, 서명)에 걸쳐 고전적 임대인을 지원하는 최초의 모듈형 보안 키 리싱 프레임워크를 제공한다고 주장한다.

• 모듈성: 특정 프리미티브에 맞춰 제작된 이전 연구들과 달리, 이 접근 방식은 병렬 추출 가능한 워터마킹을 갖춘 모든 프리미티브에 작동하는 컴파일러로 문제를 추상화한다.
• 실용성: 고전적 임대인을 허용함으로써, 이 프레임워크는 양자 능력이 부족한 클라이언트가 존재하는 실제 클라우드 컴퓨팅 시나리오와 부합한다.
• 보안 강도: 스킴들은 VRA 보안을 달성하며, 이는 삭제 후 검증 키가 유출되더라도 견고함을 보장하는 더 강력한 보증이다.
• 기초적 개선: 특수 이중 모드 SFE와 병렬 추출을 갖춘 워터마킹 스킴의 구축은 독립적인 관심사를 가진 기여로 제시된다.

저자들은 자신들의 PKE-SKL 구성이 LWE에 의존하지만, 기초가 되는 PKE 스킴 자체는 반드시 LWE 기반일 필요는 없음을 명시하며, 이는 이전의 LWE 구조적 PKE-SKL 스킴보다 더 큰 유연성을 제공한다. 또한, 서명에 대한 접근 방식은 '결맞은 서명 가능성'이라는 특정 속성을 필요로 하며, 이를 LWE/SIS로부터 구축한다는 점을 밝힌다.