From Bits to Mixed-Radix Keys: Horner Decomposition, Uniform Sampling, and the Information-Theoretic QKD Interface of the MR-OTP

기술 요약: 비트에서 혼합 기수 키로(From Bits to Mixed-Radix Keys)

문제 정의
이전 연구[1]에서 소개된 혼합 기수 일회용 패드(Mixed-Radix One-Time Pad, MR-OTP)는 클래식한 이진 일회용 패드를 비균일한 기수(base)를 가진 자릿수 공간으로 일반화한다. 이는 중간 단계의 이진 변환 없이도 이질적인 데이터 알파벳(예: DNA 서열, 라틴 텍스트)을 네이티브하게 인코딩할 수 있게 하며, 섀넌의 완전 비밀성(perfect secrecy)을 보존한다. 그러나 실제 배포를 위해서는 양자 키 분배(QKD) 소스의 가공되지 않은 이진 엔트로피 출력을 혼합 기수 키 공간상에 균등하게 분포하는 키 튜플로 변환하는 메커니즘이 필요하다.

단순한 접근 방식인 $k = \lceil \log_2 P \rceil$ 비트를 읽어($P$는 기수들의 곱) 그 결과 정수를 $P$로 나머지 연산(modulo) 하는 방식은 "모듈로 편향(modulo bias)"이라는 통계적 왜곡을 초래한다. 정보 이론적 설정에서, 키 분포의 비균일성은 완전 비밀성 정리의 가설을 위반하며, 이는 편향의 크기와 관계없이 시스템을 불안전하게 만든다. 본 논문은 이러한 편향을 도입하지 않으면서 균등한 이진 스트림을 균등한 혼합 기수 키 튜플로 변환하는 알고리즘적 과제를 다룬다.

방법론
본 논문은 혼합 기수 위치 가중치와 다항식 평가의 중첩된 형태 사이의 구조적 동등성을 확립한다.

1. 대수적 대응: 저자들은 **호너의 방법(Horner's method)**과 그 역함수가 이 변환을 위한 정형적인 대수적 쌍을 이룬다는 점을 식별하였다. 순방향 맵(호너 평가)은 자릿수 튜플을 하나의 정수로 합성하며, 역방향 맵(역 호너 분해)은 연속적인 나머지 연산을 통해 정수로부터 자릿수를 복구한다. 이는 키 공간 $\mathcal{K}$와 정수 구간 $\{0, \dots, P-1\}$ 사이의 전단사 함수(bijection)를 확립한다.
2. 거부 샘플링(Rejection Sampling): 모듈로 편향을 제거하기 위해, 본 논문은 거부 샘플링 알고리즘(알고리즘 1)을 제안한다. 알고리즘은 $k$ 비트를 추출하여 정수 $V$를 형성한다. 만약 $V \ge P$이면 샘플을 폐기하고 과정을 반복한다. 만약 $V < P$이면, 역 호너 분해를 적용하여 키 튜플을 생성한다.
3. 보안 분석 프레임워크: 본 논문은 단일 및 다중 세션에 걸쳐 전체 파이프라인(QKD $\to$ 키 추출 $\to$ MR-OTP 암호화)을 분석한다. 각 세션의 키와 기수 시퀀스를 위해 QKD 스트림의 서로 소인 블록을 사용하는 분할 키 롤링(partition key-rolling) 방식을 채택한다.
4. 적대자 분류: 보안 분석은 테스트 기반(testing-based), 대수적(algebraic), 무제한(unbounded), 그리고 암호문 전용(ciphertext-only)의 네 가지 적대자 클래스를 구분한다. 또한 "계산적 비밀(computational secret)"(기수 시퀀스 $B$)과 "정보 이론적 비밀(information-theoretic secret)"(패드 $K$)을 분리한다.

주요 기여 및 결과

• 균등 키 샘플링: 본 논문은 단순한 모듈로 연산이 완전 비밀성을 깨뜨린다는 것을 증명한다(명제 3.1). 거부 샘플링과 역 호너 분해를 결합하면 키 공간에 대한 균등 분포가 복원됨을 입증한다(정리 3.4). 이 과정의 기대 비트 비용은 $2\lceil \log_2 P \rceil$로 제한되며, 기대 거부 횟수는 최대 2회이다(명제 3.5).
• 엔드 투 엔드 보안: 이상적인 QKD 소스, 거부 샘플링 알고리즘, 그리고 MR-OTP의 결합은 단일 세션(정리 4.2) 및 분할 키 롤링 방식 하의 $N$개 세션(정리 6.2)에 대해 섀넌의 완전 비밀성을 달성한다. 이는 계산적 가정을 전제로 하지 않는다.
• 표현 효율성: 본 논문은 자연 알파벳에 대한 MR-OTP의 이진 OTP 대비 효율성 이득을 정량화한다. 네이티브 심볼 공간에서 작동함으로써, MR-OTP는 이진 인코딩에 내재된 "이진 오버헤드"($\lceil \log_2 b \rceil - \log_2 b$)를 제거한다. 예를 들어, 십진 숫자의 경우 약 $16.9\%$, 라틴 알파벳의 경우 약 $6.0\%$의 키 재료 감소 효과를 제공한다(명제 5.3).
• 기수 복구 문제(Base Recovery Problem, BRP):
  • 암호문 전용: 본 논문은 암호문만으로부터 기수 시퀀스 $B$를 복구하는 것이 정보 이론적으로 불가능함을 증명한다(결론 8.2). 암호문은 제약 조건 $b_i > c_i$ 외에는 $B$에 대한 어떠한 정보도 제공하지 않는다.
  • 기지 평문(Known-Plaintext): 기지 평문 설정에서, 본 논문은 테스트 기반 적대자에 대한 쿼리 복잡도의 무조건적 하한을 설정하며, $B$를 식별하기 위해서는 최소 $|F_T| - 1$회의 쿼리가 필요함을 보여준다. 여기서 작은 $T$에 대해 $|F_T|$는 메시지 길이 $L$에 대해 지수적으로 남는다(정리 8.10).
  • 보안의 불변성: 핵심 결과(정리 8.15)는 적대자(유계 또는 무계)가 기지 평문 데이터를 통해 기수 시퀀스 $B$를 성공적으로 복구하더라도, 새로운 키로 암호화된 미래의 메시지에 대해서는 어떠한 정보도 얻을 수 없음을 증명한다. 이는 패드의 정보 이론적 보안이 기수 복구 문제의 계산적 상태와 무관하게 유지됨을 의미한다.
• 배치 추출(Batched Extraction): 본 논문은 $N$개의 키 자릿수를 동시에 생성하기 위해 하나의 큰 정수를 추출하는 배치 키 추출 알고리즘(섹션 9)을 도입한다. 이는 순차적 샘플링에 비해 거부 오버헤드를 줄이며, $N \to \infty$일 때 심볼당 $\log_2 b$ 비트의 이론적 엔트로피 한계에 근접한다(정리 9.2).
• 비이상적 소스: 본 논문은 총 변동 거리(total variation distance) 측면에서 균등 분포에 $\epsilon$-가까운 비이상적 QKD 소스로 보안 보장을 확장한다. $N$개 세션에 대한 엔드 투 엔드 보안 저하는 $2N\epsilon$으로 제한됨을 보여준다(정리 10.3).

의의 및 주장
본 논문은 엄격한 정보 이론적 보안을 유지하면서 QKD 소스를 사용하여 MR-OTP를 배포하기 위한 완전한 알고리즘적 토대를 제공한다고 주장한다. 주요 의의는 다음과 같다:

1. 편향 문제 해결: 이진 엔트로피를 완전 비밀성의 균등성 요구 사항을 위반하지 않고 혼합 기수 키로 변환하는 검증된 방법(거부 샘플링 + 호너 역산)을 제공한다.
2. 무조건적 시간적 보안: 미래 메시지의 보안은 기수 시퀀스를 복구하는 계산적 난이도와 독립적임을 확립한다. 즉, 기수가 복구되더라도 시스템은 새로운 암호화에 대해 완전 비밀성을 유지한다. 이는 계산적 계층(기수를 숨김)과 정보 이론적 계층(메시지를 숨김)이 독립적인 "이중 레이어" 보안 구조를 생성한다.
3. 효율성: MR-OTP가 2의 거듭제곱이 아닌 알파벳에 대해 이론적으로 타당할 뿐만 아니라, 보안을 희생하지 않으면서 키 소비를 줄이는 데 있어 이진 OTP보다 실질적으로 더 효율적임을 입증한다.
4. 적대자 분류: 적대자의 능력을 엄격히 구분하여, 기지 평문 설정에서 정보 이론적 보장이 모든 적대자 클래스에 대해 무조건적으로 유효함을 증명하는 한편, 계산적 어려움 결과는 특정 하위 집합(테스트 vs 대수적)에만 적용됨을 명시한다.

본 논문은 동적 키 롤링 변형(기수 시퀀스가 이전 암호문에 의존하는 경우) 및 대수적 적대자에 대한 기수 복구 문제의 평균 사례 계산적 난이도와 관련된 향후 과제를 제시하며 마무리된다.