Quantum hash function using discrete-time quantum walk on Hanoi network

이 논문은 메시지의 비트가 확률 진폭의 흐름을 제어하는 한나 네트워크 기반의 이산 시간 양자 보행을 활용하여, 기존 순환 그래프 기반 양자 해시 함수의 단점을 극복하고 짧은 메시지 길이에서도 높은 충돌 저항성을 갖는 새로운 양자 해시 함수를 제안합니다.

핵심

이 논문은 **"양자 컴퓨팅을 이용해 더 안전하고 빠른 '디지털 지문' (해시 함수) 을 만드는 새로운 방법"**을 소개합니다.

기존의 컴퓨터가 사용하는 암호 기술은 해킹 기술이 발전하면 뚫릴 위험이 있지만, 이 연구는 양자 역학의 신비로운 성질을 이용해 그 어떤 해커도 뚫기 어려운 새로운 자물쇠를 제안합니다.

이 복잡한 내용을 일상적인 비유로 쉽게 설명해 드릴게요.

---

1. 해시 함수란 무엇일까요? (디지털 지문)

우리가 물건을 보관할 때, 그 물건의 특징을 요약한 '지문'이나 '바코드'를 붙여놓습니다.

• 원리: 어떤 복잡한 문서 (메시지) 가 들어오면, 이를 아주 짧고 고정된 형태의 숫자 (해시 값) 로 바꿉니다.
• 특징: 이 숫자를 보고 원래 문서를 다시 만들어내는 것은 불가능에 가깝습니다. 마치 커피를 갈아내면 원두를 다시 합칠 수 없는 것과 같습니다.
• 문제점: 기존 컴퓨터 (고전 컴퓨터) 가 사용하는 암호는 해커들이 계산 능력을 키우면 언젠가 뚫릴 수 있습니다.

2. 양자 보행 (Quantum Walk) 이란? (미로 속의 유령)

이 연구의 핵심은 **'양자 보행'**이라는 기술을 사용합니다.

• 비유: imagine you are a ghost walking in a maze.
  • 고전 보행: 유령이 미로에서 한 번에 한 칸씩 이동합니다. (왼쪽? 오른쪽? 하나만 선택)
  • 양자 보행: 유령은 동시에 여러 길로 이동할 수 있습니다 (중첩). 또한, 여러 경로가 만나서 서로 간섭하며 (간섭) 특정 길은 사라지고 특정 길은 더 강해집니다.
• 장점: 이 '유령'이 미로를 돌아다니는 패턴은 매우 복잡하고 예측하기 어렵습니다. 이 패턴을 이용해 암호를 만드는 것입니다.

3. 이 연구의 혁신: '하노이 네트워크'라는 특별한 미로

기존 연구들은 주로 단순한 원형 미로 (고리) 를 사용했습니다. 하지만 이 논문은 **'하노이 네트워크 (Hanoi Network)'**라는 더 복잡한 미로를 사용합니다.

• 비유:
  • 기존 미로 (원형): 한 바퀴 돌고 돌아오는 단순한 길입니다. 여기서는 '유령'이 특정 시간에 특정 곳에 있을 확률이 0 이 되는 규칙적인 패턴이 생겨, 해커가 이를 예측하기 쉽습니다.
  • 새로운 미로 (하노이 네트워크): 단순한 고리 길에 **멀리 떨어진 곳으로 바로 연결되는 '비행기'나 '터널' (장거리 연결선)**이 추가된 미로입니다.
  • 효과: 이 터널들 덕분에 '유령'이 이동할 수 있는 경로가 훨씬 다양해지고, 규칙적인 패턴이 깨집니다. 덕분에 **짧은 메시지 (짧은 입력)**에서도 매우 강력한 암호를 만들 수 있습니다. (기존 방식은 메시지가 길어야만 안전했습니다.)

4. 어떻게 암호를 만들까요? (비밀 번호로 미로를 조작하다)

이 시스템은 입력받은 메시지 (비트열, 0 과 1 의 나열) 를 이용해 미로의 규칙을 실시간으로 바꿉니다.

• 비유:
  • 메시지의 각 숫자 (0 또는 1) 는 미로의 **문 (Coin)**과 **이동 규칙 (Shift)**을 바꾸는 열쇠입니다.
  • 0 이 나오면: 유령이 왼쪽으로 갈 때 문이 열리고, 오른쪽으로 갈 때 문이 닫힙니다.
  • 1 이 나오면: 반대로 문이 열리거나 닫힙니다.
  • 핵심: 기존 연구는 '문'만 바꿨다면, 이 연구는 '문'과 '이동 규칙'을 모두 메시지대로 바꿉니다.
  • 결과: 아주 작은 입력 (메시지) 의 변화도, 유령의 최종 위치를 완전히 엉뚱한 곳으로 보내버립니다. (작은 변화가 큰 결과를 낳음)

5. 왜 이 방법이 더 안전할까요?

이 논문은 이 방법이 기존 양자 해시 함수보다 훨씬 **충돌 (Collision)**이 적다고 증명했습니다.

• 충돌이란? 서로 다른 두 문서가 똑같은 '지문' (해시 값) 을 갖는 경우입니다. 해커가 이걸 이용하면 위조가 가능합니다.
• 이 연구의 성과:
  • 충돌 확률: 기존 방식들은 충돌 확률이 1%~20% 에 달했지만, 이 방식은 0.05% 수준으로 압도적으로 낮습니다.
  • 비유: 10,000 번의 시도를 해도 거의 같은 지문이 나올 확률이 거의 없다는 뜻입니다.
  • 작은 메시지에도 강력: 보통 양자 암호는 입력이 길어야 안전했지만, 이 '하노이 네트워크'는 입력이 짧아도 안전합니다.

6. 결론: 미래의 디지털 자물쇠

이 논문은 **"양자 보행"**이라는 기술을 **"하노이 네트워크"**라는 복잡한 미로에 적용하여, 기존 암호보다 훨씬 강력하고 빠른 디지털 지문을 만들 수 있음을 보여줍니다.

• 핵심 메시지: "단순한 고리 길에 터널을 추가하고, 유령의 이동 규칙을 더 정교하게 조작함으로써, 해커가 예측할 수 없는 완벽한 암호를 만들었다."

이 기술은 양자 컴퓨터 시대가 왔을 때, 우리의 개인정보와 금융 자산을 지키는 새로운 표준이 될 가능성이 매우 높습니다.

기술 요약

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

• 양자 해시 함수의 필요성: 기존 고전 해시 함수 (SHA-1, MD5 등) 는 양자 컴퓨팅의 발전 (특히 쇼어 알고리즘 등) 으로 인해 보안 위협에 노출될 수 있습니다. 양자 역학의 중첩과 얽힘 특성을 활용한 양자 해시 함수는 이러한 위협에 대한 강력한 대안으로 주목받고 있습니다.
• 기존 양자 보행 기반 해시 함수의 한계:
  • 대부분의 기존 연구는 1 차원 주기 격자 (1D periodic lattice) 를 기반으로 합니다.
  • 짧은 메시지 처리 불가: 1 차원 격자 기반 해시 함수는 일반적으로 메시지의 비트 길이가 그래프의 정점 수보다 길어야만 작동합니다. 짧은 메시지는 해시 값 생성에 적합하지 않습니다.
  • 충돌 (Collision) 문제: 짝수 길이의 1 차원 격자에서는 특정 시간 단계에서 확률 분포가 0 이 되는 예측 가능한 주기적 특성이 발생하여 해시 충돌률이 매우 높아집니다.
  • 제어 방식의 단순성: 기존 방식은 주로 메시지의 비트가 '동전 연산자 (Coin operator)'만 제어하며, '이동 연산자 (Shift operator)'는 제어하지 않습니다. 이는 해시 함수의 복잡성과 충돌 저항성을 제한합니다.

2. 제안된 방법론 (Methodology)

이 논문은 하노이 네트워크 (Hanoi Network, HN4) 위에서 작동하는 이산 시간 양자 보행 (Discrete-time Quantum Walk) 을 기반으로 한 새로운 양자 해시 함수를 제안합니다.

• 하노이 네트워크 (HN4) 구조:
  • 1 차원 주기 격자에 특수한 형태의 장거리 연결 (Long-range edges) 이 추가된 구조입니다.
  • 정점 $x_v$는 $2^i(2j+1)$ 형태로 표현되며, 각 정점은 두 개의 정규 엣지 (이웃 연결) 와 두 개의 장거리 엣지를 가집니다.
  • 이 장거리 엣지는 '작은 세상 (Small-world)' 구조를 형성하여, 짝수 길이의 격자에서도 예측 불가능한 확률 분포를 생성하고 충돌을 방지합니다.
• 메시지 제어 방식 (핵심 혁신):
  • 기존과 달리 메시지의 비트 값 (0 또는 1) 에 따라 동전 연산자 (Coin operator, $C$) 와 이동 연산자 (Shift operator, $S$) 를 모두 제어합니다.
  • 비트 0: $U_0 = S_0 (C_0 \otimes I)$ 사용. (그로버 연산자 $C_0$와 플립 - 플롭 이동 연산자 $S_0$ 적용)
  • 비트 1: $U_1 = S_1 (C_1 \otimes I)$ 사용. (그로버 연산자 $C_1$와 표준 이동 연산자 $S_1$ 적용)
  • 이를 통해 메시지의 작은 변화가 양자 상태의 진화에 큰 영향을 미치도록 설계되었습니다.
• 해시 값 생성 과정:
  1. 초기 상태 $|\psi_{in}\rangle$ 설정 (동전 공간과 정점 공간의 중첩 상태).
  2. 메시지 비트에 따라 $U_0$ 또는 $U_1$을 반복 적용하여 최종 양자 상태 $|\psi_f\rangle$ 도출.
  3. 최종 상태의 확률 분포 $P(x_v, m)$ 측정.
  4. 사후 처리 (Post-processing): 확률 진폭을 정밀도 계수 $10^l$로 곱하고$2^k$로 나눈 나머지 (Modulo) 를 취하여 16 비트 (또는 그 이상) 의 이진 문자열로 변환. 이를 모두 연결하여 최종 해시 값 생성.

3. 주요 기여 및 결과 (Key Contributions & Results)

• 높은 충돌 저항성 (Collision Resistance):
  • 실험 결과, 제안된 방식의 충돌률은 약 0.05% (이론적 값 0.02%) 로 나타났습니다.
  • 기존 다른 양자 해시 함수들 (참고문헌 [24], [30], [26] 등) 의 충돌률 (1.46% ~ 23.12%) 에 비해 월등히 낮습니다 (표 V 참조).
  • 장거리 엣지의 가중치 파라미터 ($l_{00}, \tilde{l}_{00}$ 등) 를 적절히 조절함으로써 1 차원 격자의 주기적 0 확률 문제를 해결했습니다.
• 짧은 메시지 처리 능력:
  • 기존 1 차원 격자 방식은 메시지의 비트 길이가 정점 수보다 커야 했지만, HN4 네트워크를 사용하면 비트 길이가 정점 수보다 짧은 메시지에서도 효과적으로 작동합니다 (그림 6 참조).
• 통계적 성능 분석:
  • 민감도 (Sensitivity): 메시지의 1 비트 변경만으로도 해시 값이 극적으로 변화하는 것을 확인했습니다.
  • 확산 및 혼란 (Diffusion & Confusion): 해시 값 내 비트의 변경 횟수 (햄밍 거리) 가 이상적인 값에 가깝게 분포하여 확산과 혼란 특성이 우수함을 입증했습니다 (표 II).
  • 균일 분포 (Uniform Distribution): 해시 공간 내 비트 분포가 균일하게 나타났으며, 통계적 편차가 매우 작았습니다 (표 III).
  • 생일 공격 (Birthday Attack) 저항성: 256 비트 해시 값을 생성하므로, 충돌을 찾을 확률이 0.5 가 되기 위해 $2^{128}$번의 시도가 필요하여 매우 강력합니다.
• NISQ 장치 적합성:
  • HN4 네트워크는 2 큐비트만 사용하여 구현 가능하므로, 현재의 제한된 큐비트 수와 연결성을 가진 NISQ (Noisy Intermediate-Scale Quantum) 장치에서도 구현 가능성이 높습니다.

4. 의의 및 결론 (Significance)

• 보안성 강화: 메시지가 동전 연산자와 이동 연산자 모두를 제어함으로써 양자 보행의 복잡성을 극대화하고, 해시 함수의 일방향성 (One-way property) 을 강화했습니다.
• 실용성: 짧은 메시지도 처리할 수 있고, 1 차원 격자의 구조적 결함을 장거리 엣지로 보완하여 실제 양자 컴퓨팅 환경에 적용 가능한 고효율 해시 함수를 제시했습니다.
• 향후 과제: 현재 연구는 이상적인 (Noise-free) 환경에서 수행되었으나, 실제 양자 장치의 노이즈 (Decoherence) 가 해시 함수의 결정론적 특성과 보안에 미치는 영향에 대한 추가 연구가 필요하다고 언급했습니다. 노이즈를 완화하기 위해 메시지 비트 2 개를 하나의 연산자로 제어하는 등의 최적화 방안이 제시되었습니다.

요약하자면, 이 논문은 하노이 네트워크의 독특한 구조와 메시지 기반의 이중 제어 (Coin & Shift) 메커니즘을 결합하여, 기존 양자 해시 함수의 단점 (짧은 메시지 불가, 높은 충돌률) 을 극복하고 매우 높은 충돌 저항성을 가진 새로운 양자 해시 함수를 제안한 획기적인 연구입니다.