A NISQ-friendly Coined Quantum Walk Algorithm for Chaos-based Cryptographic Applications

논문 개요

이 논문은 NISQ(Noisy Intermediate-Scale Quantum, 잡음이 있는 중간 규모 양자) 장치 환경에서 실행 가능한 새로운 양자 보행 알고리즘인 게으른 교대 양자 보행 (Lackadaisical Alternating Quantum Walk, LAQW) 을 제안합니다. 연구진은 이 알고리즘을 기반으로 한 혼돈 기반 (Chaos-based) 대칭 키 생성 체계를 설계하고, 기존 CAQW(Controlled Alternating Quantum Walk) 모델 대비 회로 깊이 (Circuit Depth) 를 획기적으로 줄이면서도 암호학적 무작위성과 재현성을 유지함을 입증했습니다.

1. 문제 제기 (Problem Statement)

• NISQ 환경의 한계: 기존 암호학에 적용된 이산 시간 양자 보행 (DTQW), 특히 교대 양자 보행 (AQW) 및 제어된 교대 양자 보행 (CAQW) 은 $n \times n$ 격자에서 $t$ 시간 단계에 대해 회로 깊이가 $O(n^2t)$로 스케일링됩니다. 이는 현재의 잡음이 많은 양자 프로세서 (QPU) 에서는 너무 깊어 오류가 누적되어 결과를 재현할 수 없게 만듭니다.
• 홀수 크기 격자의 제약: 암호학적 응용을 위해 홀수 크기 (Odd-sized) 의 주기적 그래프를 사용해야 하는 CAQW 모델은, 양자 푸리에 변환 (QFT) 기반의 효율적인 회로 구현이 불가능하여 회로 깊이가 비효율적으로 증가하는 문제가 있었습니다.
• 재현성 문제: 양자 잡음으로 인해 측정된 확률 분포가 매번 달라지면, 암호화/복호화에 필요한 동일한 키를 생성하는 것이 불가능해집니다.

2. 방법론 (Methodology)

2.1 LAQW 알고리즘 제안

• 자기 루프 (Self-loop) 도입: 기존 CAQW 모델의 각 노드에 **자기 루프 (Self-loop)**를 추가하여 '게으른 양자 보행 (Lackadaisical Quantum Walk, LQW)'의 특성을 교대 보행에 적용했습니다.
  • 이로 인해 보행자는 이동 (좌/우) 하거나 제자리에 머무를 수 있게 되어, 홀수 크기 격자에서도 모든 노드에 0 이 아닌 확률을 가질 수 있게 되었습니다.
  • 이 구조적 변경은 QFT 기반의 회로 구현을 가능하게 하여, 증감 (Increment/Decrement) 연산자를 효율적으로 처리할 수 있게 했습니다.
• 회로 깊이 최적화: 제안된 LAQW 모델의 회로 깊이는 $O(n^2 + nt)$로 스케일링되어, 기존 CAQW 의 $O(n^2t)$에 비해 $t$가 클 때 훨씬 얕은 깊이를 가집니다.

2.2 대칭 키 생성 체계

1. 비트열 생성 (Bitstring Generation):
   • LAQW 의 확률 분포를 샘플링하여 측정 횟수를 수집합니다.
   • 반올림 (Rounding): 측정된 카운트를 정수 구간으로 반올림하여 실험 간 재현성을 확보합니다.
   • 소수 모듈러스 매핑 (Prime-modulus Mapping): 반올림된 값을 8 비트 바이트로 변환할 때, 단순 모듈 256 연산 대신 **소수 (Prime numbers)**를 모듈로로 사용하여 출력 바이트의 균일성 (Uniformity) 을 높이고 편향을 줄입니다.
2. 비트 추출 (Bit Extraction):
   • **Leftover Hash Lemma (LHL)**를 적용하여 최소 엔트로피 (Min-entropy) 를 보수적으로 추정합니다.
   • 초기 파라미터 (특히 코인 상태 $\alpha$) 에 가중치를 둔 결정론적 추출 방식을 사용하여, 최종적으로 128 비트의 암호 키를 생성합니다.

3. 주요 기여 (Key Contributions)

1. 새로운 알고리즘 (LAQW): 암호학적 응용에 적합한 얕은 회로 깊이를 가진 LAQW 모델과 그 양자 회로 구현을 최초로 제안했습니다.
2. NISQ 친화성: CAQW 대비 약 88% 의 회로 깊이 감소를 달성하여, 현재의 IBM FakeTorino 와 같은 실제 양자 하드웨어 (또는 그 시뮬레이션) 에서의 실행 가능성을 입증했습니다.
3. 암호학적 유효성 검증: 생성된 키의 무작위성 (NIST 통계 테스트), 재현성 (Hamming 거리 분석), 그리고 잡음 내성 (Noise Resilience) 을 종합적으로 평가했습니다.

4. 결과 (Results)

4.1 회로 깊이 비교

• 깊이 감소: GenericBackendV2(잡음 없음) 및 FakeTorino(IBM Torino QPU 시뮬레이션) 에서 LAQW 는 CAQW 대비 평균 88.28% 및 **87.81%**의 회로 깊이 감소를 보였습니다.
• 구체적 수치: $t=20$일 때, CAQW 는 5064 의 깊이를 가진 반면 LAQW 는 550 의 깊이만 필요로 했습니다.

4.2 파라미터 민감도 (혼돈 특성)

• 초기값 민감성: $\theta_0, \theta_1, \alpha$ 파라미터를 1% 변경했을 때, LAQW 는 CAQW 보다 평균 헬링거 거리 (Hellinger Distance) 가 각각 30.12%, 29.63%, 18.98% 더 크게 변화하여 더 높은 민감도 (혼돈 특성) 를 보였습니다.
• 시간 단계 민감성: 반면, 시간 단계 $t$의 변화에 대해서는 CAQW 가 더 민감하게 반응했습니다.

4.3 통계적 무작위성 (NIST 테스트)

• 생성된 키의 품질: LAQW 로 생성된 128 비트 키는 NIST SP 800-22 테스트 (Frequency, Block Frequency, Runs, Longest Run, Spectral, Cumulative Sums) 에서 모든 테스트를 통과했습니다.
• CAQW 대비 우위: CAQW 는 Block Frequency 테스트에서 실패 ($p=0.004$) 하는 등 국소적 불균형을 보인 반면, LAQW 는 전반적으로 더 균일한 무작위성을 보였습니다.

4.4 재현성 및 잡음 내성

• 재현성: 동일한 초기 파라미터로 100 회 실험 시, 최종 128 비트 키의 정규화된 해밍 거리는 0.0003으로 거의 0 에 가까웠습니다 (단 한 번의 4 비트 차이 발생).
• 잡음 내성: IBM FakeTorino 백엔드에서 실제 잡음을 시뮬레이션했을 때도, 추출 가능한 비트 수와 키의 재현성이 잡음이 없는 시뮬레이션과 거의 동일하게 유지되었습니다.

5. 의의 및 결론 (Significance)

• 실용적 암호화 구현: 이 연구는 양자 보행 기반의 암호학이 이론적 모델을 넘어, 현재의 NISQ 하드웨어에서 실제로 구현 가능한 단계로 나아갔음을 보여줍니다.
• 효율성과 안전성의 균형: CAQW 모델의 높은 계산 비용 (깊은 회로) 을 줄이면서도, 오히려 더 나은 무작위성과 재현성을 확보했습니다.
• 미래 전망: 제안된 LAQW 기반 키 생성 체계는 이미지 암호화, 해시 함수 등 다양한 혼돈 기반 암호 응용 분야에서 CAQW 를 대체할 수 있는 강력한 후보로 평가받습니다. 특히, 초기 파라미터에 대한 높은 민감성과 잡음 내성은 양자 키 분배 및 대칭 키 암호화 시스템의 보안성을 강화하는 데 기여할 것입니다.

요약하자면, 이 논문은 양자 보행의 회로 깊이를 획기적으로 줄여 NISQ 장치에서 실행 가능한 새로운 암호 키 생성 알고리즘을 개발하고, 이를 통해 고품질의 암호학적 무작위성과 재현성을 달성했음을 입증한 중요한 연구입니다.