💻 computer science

Quantum Hash Function Based on Spectral Properties of Graphs and Discrete Walker Dynamics

이 논문은 메시지를 토로이드 격자 위의 가중치 그래프로 매핑하고 양자 위상 추정(Quantum Phase Estimation)을 활용하여 구조적 및 동적 특성을 모두 포착하는 스펙트럼 특징을 추출함으로써 256비트 지문을 생성하는 새로운 양자 해싱 알고리즘인 QGH-256을 소개하며, Qiskit 시뮬레이션을 통해 강력한 암호학적 민감도와 실현 가능성을 입증한다.

원저자: Mohana Priya Thinesh Kumar, Pranavishvar Hariprakash

게시일 2026-06-30

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Mohana Priya Thinesh Kumar, Pranavishvar Hariprakash

원본 논문은 CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

개요: 새로운 디지털 지문

당신이 긴 소설 같은 복잡한 이야기를 하나의 고유한 지문으로 변환해야 한다고 상상해 보세요. 디지털 세계에서 우리는 보통 이를 위해 "해시 함수"(SHA-256 등)를 사용합니다. 하지만 이 논문의 저자들은 미래의 양자 컴퓨터가 이러한 오래된 지문들을 깨뜨릴 수 있다고 우려합니다.

그래서 그들은 QGH-256이라는 새로운 종류의 지문을 만들었습니다. 단순히 숫자로 수학 계산을 하는 대신, 이 방법은 당신의 메시지를 하나의 지도로 바꾸고, 그 지도를 가로지르는 **보행자(Walker)**를 보낸 뒤, 양자 물리학을 사용하여 지도의 "진동"을 측정하여 최종 지문을 만들어냅니다.

1단계: 단어를 지도로 바꾸기 (보행자)

비유: 작은 로봇이 격자판(체커보드와 같은) 위를 걷고 있다고 상상해 보세요. 이 격자판은 스스로 연결되어 있습니다(오른쪽 끝으로 나가면 왼쪽에서 다시 나타납니다). 이를 "토로이드 격자(Toroidal grid)"라고 부릅니다.

작동 방식: 메시지(예: "Hello")를 가져와 이진 코드(0과 1)로 변환합니다.
걷기: 로봇은 무작위로 걷지 않습니다. 로봇은 메시지를 비트 단위로 읽습니다.
- 00을 보면 북쪽으로 걷습니다.
- 01을 보면 남쪽으로 걷습니다.
- 10을 보면 동쪽으로 걷습니다.
- 11을 보면 서쪽으로 걷습니다.
지도: 로봇이 걸으면서 길 위에 흔적을 남깁니다. 로봇이 선(에지)을 통과할 때마다, 메시지에 포함된 숫자에 따라 그 선에 "가중치(Weight)"를 더합니다.
결과: 당신은 독특하고 가중치가 부여된 지도를 얻게 됩니다. 메시지에서 글자 하나만 바뀌어도(예: "Hello"에서 "Hella"로), 로봇은 완전히 다른 경로를 걷게 되어 완전히 다른 지도를 만들어냅니다.

이것이 중요한 이유: 논문에 따르면, 이 지도는 방향성이 없기 때문에(로봇이 어느 방향을 보고 있었는지는 기록하지 않고, 단지 선을 몇 번 통과했는지만 기록함), 지도를 보고 원래의 메시지를 알아내는 것은 매우 어렵습니다. 이는 마치 등산객이 어디서 시작해서 어디로 끝났는지 모르는 상태에서, 그저 닳아버린 풀밭의 흔적만 보고 정확한 경로를 추측하려는 것과 같습니다.

2단계: 지도의 "음악" 듣기 (스펙트럼 지문 채취)

이제 이 독특한 지도를 얻었으니, 어떻게 지문으로 바꿀까요? 저자들은 **스펙트럼 분석(Spectral Analysis)**이라는 물리 개념을 사용합니다.

비유: 당신의 지도가 거대한 드럼이라고 상상해 보세요. 드럼을 치면 진동이 발생합니다. 모든 드럼은 그 형태와 가죽의 팽팽함에 따라 연주할 수 있는 특정한 "음표"(주파수) 세트를 가지고 있습니다.

수학에서 이 "음표"들은 **고윳값(Eigenvalues)**이라고 불립니다.
지도의 "팽팽함"과 "형태"는 그래프 라플라시안(Graph Laplacian)(지도의 연결성과 가중치를 설명하는 복잡한 수학 행렬)에 의해 결정됩니다.

양자 기술의 도입:
보통 이 음표들을 들으려면 복잡한 방정식을 풀어야 합니다. 하지만 이 논문은 양자 위상 추정(Quantum Phase Estimation, QPE) 알고리즘을 사용합니다.

QPE를 아주 민감한 마이크라고 생각하면 쉽습니다. 이 마이크는 드럼의 소리를 즉각적으로 "들어서" 어떤 음표들이 연주되고 있는지 정확히 알려줍니다.
핵심 세부 사항: 저자들은 단순히 한 가지 음표만 듣는 것이 아닙니다. 그들은 "중첩"(모든 가능한 시작점의 혼합 상태와 같은 양자 상태)을 시스템에 보냅니다. 이는 양자 컴퓨터가 지도의 전체 노래, 즉 음표들이 서로 어떻게 상호작용하는지까지 포함하여 한꺼번에 듣는다는 것을 의미합니다.

이것이 특별한 이유:
두 개의 서로 다른 지도가 우연히 같은 음표 세트를 가질 수도 있습니다(이를 "공통 스펙트럼/co-spectral"이라고 합니다). 하지만 저자들은 음표들이 지도의 특정한 구조(고유벡터)와 어떻게 상호작용하는지를 듣기 때문에, 소리는 비슷하지만 모양이 다른 두 지도를 구별해 낼 수 있습니다. 이는 "충돌(Collision)"(두 개의 서로 다른 메시지가 동일한 지문을 생성하는 현상)을 방지합니다.

3단계: 열 흔적 (최종 지문)

양자 컴퓨터가 "음표"(고윳값)를 식별하면, 저자들은 **열 흔적(Heat Trace)**이라는 것을 계산합니다.

비유: 당신의 지도 위에 뜨거운 물을 붓는다고 상상해 보세요. 열은 격자를 따라 퍼져 나갑니다(확산).

"열 흔적"은 열이 얼마나 빨리 퍼지는지를 측정합니다.
이 과정을 다양한 시간대별로 측정함으로써, 지도가 어떻게 생겼는지에 대한 고유한 서명을 얻습니다.
이 서명은 다시 256비트 코드(0과 1로 이루어진 문자열)로 압축됩니다. 이것이 당신의 최종 QGH-256 해시입니다.

왜 안전한가? ("눈사태 효과")

논문은 이 새로운 방식이 좋은 자물쇠의 규칙들을 충족하는지 테스트합니다.

결정론(Determinism): "Hello"를 두 번 입력하면, 항상 똑같은 지문을 얻습니다.
눈사태 효과(Avalanche Effect): 글자 하나만 바꿔도(예: "Hello" $\rightarrow$ "Hella"), 로봇은 완전히 다른 경로를 걷습니다. 이는 지도를 바꾸고, "음표"를 바꾸고, "열의 확산"을 바꾸어, 결과적으로 완전히 다른 256비트 지문을 만들어냅니다.
역상 저항성(Pre-image Resistance): 만약 누군가 지문을 훔치더라도, 원래의 메시지를 역추적하여 찾아낼 수 없습니다. 수학적 과정이 너무 어렵고, 지도는 걷기 과정의 방향 정보를 잃어버리기 때문입니다.

한계: 시뮬레이션임

이 논문은 현재 이 기능을 실제로 실행할 만큼 크고 조용한 양자 컴퓨터가 존재하지 않는다는 점을 인정합니다.

문제점: 실제 양자 컴퓨터는 "노이즈(잡음)"가 많습니다(마치 잡음이 섞인 라디오와 같습니다). 만약 노이즈가 있는 기계에서 지도의 "음표"를 들으려고 하면 결과가 틀려질 수 있고, 실행할 때마다 지문이 바뀔 수 있습니다.
논문의 해결책: 저자들은 시뮬레이터(완벽한 양자 컴퓨터를 흉내 내는 컴퓨터 프로그램)에서 테스트를 수행했습니다. 이는 이론적으로 수학이 완벽하게 작동함을 증명했습니다.
미래: 그들은 양자 컴퓨터가 더 발전하고 노이즈가 줄어듦에 따라, 이 방법이 해커들에 대한 강력한 방어 수단이 될 것이라고 믿습니다.

요약

저자들은 새로운 디지털 자물쇠를 만들었습니다.

메시지를 격자 위의 독특한 걷기 경로로 변환합니다.
양자 컴퓨터를 사용하여 그 경로의 진동을 듣습니다.
그 진동을 256비트 코드로 변환합니다.

그들은 이 방식이 그래프가 진동하는 복잡한 물리 법칙에 의존하기 때문에, 미래의 양자 컴퓨터조차 원래의 메시지를 추측하거나 두 메시지가 동일한 코드를 생성하도록 만드는 것이 훨씬 더 어렵다고 주장합니다.

기술 요약: 그래프의 스펙트럼 특성 및 이산 워커 역학에 기반한 양자 해시 함수

문제 정의
본 논문은 고전적 암호 해시 함수(예: SHA-256, MD5)가 양자 컴퓨팅 위협에 직면해 있는 상황을 다룹니다. 구체적으로, 쇼어(Shor) 알고리즘과 그로버(Grover) 알고리즘은 거대 정수를 효율적으로 인수분해하고 구조화되지 않은 탐색을 가속화함으로써 현재의 표준에 실존적 위험을 초래합니다. NIST(미국 국립표준기술연구소)가 양자 내성 암호(PQC)를 표준화하고 있으나, 양자 및 고전적 공격 모두를 견뎌낼 수 있는 양자 네이티브(quantum-native) 또는 양자 탄력적 해싱 체계에 대한 필요성이 존재합니다. 기존의 접근 방식들은 선형 비트 연산에 의존하는 경우가 많은데, 이는 양자 가속에 대한 충분한 저항력을 제공하지 못하거나 동일한 고유값 스펙트럼을 공유하는 구조적으로 다른 그래프(공스펙트럼 그래프, co-spectral graphs)를 구별하지 못할 수 있습니다.

방법론
저자들은 고전적 이산 워커 역학(discrete walker dynamics)과 양자 스펙트럼 그래프 분석을 통합한 새로운 스펙트럼 해싱 알고리즘인 QGH-256을 제안합니다. 워크플로우는 다음 단계로 진행됩니다:

메시지 유도 그래프 구축:
- 입력 메시지는 UTF-8 바이너리로 변환된 후 블록 단위로 분할됩니다.
- 고전적 이산 워커(discrete walker)가 고정된 $4 \times 4$ 토로이드 격자(toroidal grid) 위에서 작동합니다. 무작위 보행(random walk)과 달리, 각 단계에서 워커의 방향은 메시지 비트에 의해 결정론적으로 결정됩니다(구체적으로, 각 블록의 첫 번째와 마지막 비트가 북, 남, 동, 서 방향을 결정함).
- 각 블록의 십진수 값은 통과하는 엣지(edge)의 가중치 역할을 합니다.
- 이 과정을 통해 모든 입력 메시지에 대해 고유하고 재현 가능한 가중치 부과 무방향 그래프 $G = (V, E, W)$ 가 생성됩니다. 저자들은 방향 정보가 무방향 엣지 가중치에서 손실되고 순회 시퀀스를 재구성하는 복잡성 때문에, 그래프로부터 원래의 메시지를 복구하는 것이 계산적으로 매우 어렵다고 명시합니다.
양자 위상 추정(QPE)을 통한 스펙트럼 핑거프린팅:
- 그래프의 구조는 라플라시안 행렬 $L = D - A$ (차수 행렬 $D$ 에서 인접 행렬 $A$ 를 뺀 것)로 인코딩됩니다.
- 양자 알고리즘을 활용하기 위해, $L$ 은 행렬 지수 함수를 통해 유니터리 연산자 $U = e^{iLt}$ 로 변환됩니다.
- **양자 위상 추정(QPE)**은 $U$ 에 적용됩니다. 결정적으로, QPE 회로의 입력은 단일 고유벡터가 아니라 그래프의 노드 기저(node basis)로 정의된 중첩 상태( $|\psi\rangle = \sum \alpha_i |i\rangle$ )입니다.
- 입력 상태가 라플라시안의 고유벡터들의 중첩 상태이기 때문에, QPE 과정은 스펙트럼 분석기 역할을 수행하여 해당 상태를 주파수(위상) 성분으로 분해합니다. 특정 위상을 측정할 확률은 입력 상태와 해당 고유벡터 사이의 중첩(overlap)의 제곱에 비례합니다.
열 흔적(Heat Trace) 및 해시 생성:
- 저자들은 여러 시간 척도에 걸쳐 열 흔적 값 $h(t) = \sum |c_k|^2 e^{-t\tilde{\lambda}_k}$ 를 평가함으로써 "스펙트럼 핑거프린트"를 계산합니다. 이 메트릭은 고유값 정보와 고유벡터의 기여도(계수 $c_k$ 를 통해)를 모두 포착합니다.
- 이 특징 벡터는 후처리 과정을 거쳐 고정된 256비트 이진 해시로 압축됩니다.

주요 기여

공스펙트럼 충돌 해결: 본 방법의 주요 이론적 기여는 동일한 고유값 스펙트럼을 가지나 구조는 다른 공스펙트럼 그래프를 구별하는 능력입니다. QPE에 중첩 상태를 입력으로 사용함으로써, 결과적인 스펙트럼 핑거프린트는 고유값뿐만 아니라 고유벡터의 중첩( $|c_k|^2$ )에도 의존하게 됩니다. 이를 통해 비동형(non-isomorphic) 그래프들이 동일한 스펙트럼을 공유하더라도 서로 다른 핑거프린트를 생성하도록 보장합니다.
고정 단계 효율성: 저자들은 워커의 단계를 10,000단계로 고정하고 메시지 길이에 따라 블록 크기를 조정함으로써 이전의 워커 기반 알고리즘을 개선했습니다. 이는 그래프 생성 단계의 계산 비용이 입력 메시지의 크기와 무관하게 유지되도록 보장합니다.
양자 네이티브 설계: 이 알고리즘은 양자 역학의 본질적 특성(중첩 및 위상 추정)을 활용하여 고엔트로피 핑거프린트를 생성하며, 이를 통해 포스트 퀀텀 보안의 후보로서 자리매김합니다.

결과 및 평가
본 논문은 노이즈 없는 결정론적 결과를 보장하기 위해 **시드 기반 Qiskit 상태 벡터 시뮬레이터(seeded Qiskit Statevector Simulator)**를 사용하여 QGH-256을 평가하였으며, 이는 현재의 노이즈가 있는 중간 규모 양자(NISQ) 하드웨어가 결정론성에 영향을 미칠 수 있는 변동을 유발할 수 있음을 인정한 것입니다.

결정론(Determinism): 동일한 입력은 일관되게 동일한 256비트 해시를 생성했습니다.
아발란체 효과(Avalanche Effect): 입력의 단일 비트 변화(예: "Hello" vs "Hella")는 출력에서 현저히 높은 해밍 거리(Hamming distance)를 나타냈으며, 이는 입력 섭동에 대한 민감도를 확인시켜 줍니다.
역상 저항성(Pre-image Resistance): 저자들은 그래프 역 고유값 문제(graph inverse eigenvalue problem)의 복잡성과 무방향성으로 인한 모호성 때문에 해시를 역산하는 것이 불가능하다고 주장합니다.
계산 시간: 고정된 격자 크기와 고정된 워커 단계 덕분에 실행 시간은 메시지 길이에 관계없이 거의 일정하게 유지되는 것으로 관찰되었습니다.

의의 및 주장
본 논문은 QGH-25로써 위상적 및 역학적 그래프 특성을 통합하여 고전적 해싱의 강력한 대안을 제공한다고 주장합니다.

양자 탄력성: 저자들은 알고리즘이 복잡한 비선형 스펙트럼 계산(행렬 지수 함수 및 심층 QPE 회로 포함)에 의존함으로써 "헤비 오라클(heavy oracle)"을 생성한다고 주장합니다. 이는 그로버 기반의 역상 공격을 시도하는 공격자의 반복당 비용을 크게 증가시켜, 그로버 알고리즘이 제공하는 이차적 속도 향상을 상쇄할 수 있게 합니다.
NIST PQC 준수: 이 스킴은 보안(양자 공격에 대한 저항성), 성능(메시지 길이에 대한 상수 시간), 상호 운용성(256비트 출력의 기존 인프라 호환성) 측면에서 NIST PQC 기준을 충족하는 것으로 제시됩니다.
향atic 전망: 저자들은 현재의 하드웨어 제한(노이즈, 결맞음)으로 인해 시뮬레이션을 통한 검증이 필수적이지만, 이 접근 방식이 양자 오류 정정과 큐비트 안정성이 성숙해짐에 따라 견고한 암호 프리미티브를 개발하기 위한 유망한 경로를 제공한다고 결론짓습니다.

본 논문은 QGH-256의 즉각적인 실제 양자 하드웨어 배포를 주장하는 것이 아니라, 시뮬레이션으로 검증된 개념 증거로서의 이론적 프레임워크를 제시하는 데 목적이 있습니다.