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

This paper proposes a highly collision-resistant quantum hash function based on discrete-time quantum walks on Hanoi networks, where message bits control probability amplitude flow and shift operators to enable effective hashing even for small message lengths.

The Gist

Imagine you have a magical machine that takes any story you tell it—whether it's a single word or a whole novel—and turns it into a unique, unchangeable fingerprint. In the digital world, we call this a Hash Function. It's like a digital seal of authenticity. If you change even a single letter in your story, the fingerprint should look completely different.

For decades, we've used classical machines to do this, but as computers get faster (especially quantum computers), old seals are starting to crack. That's why scientists are building new, quantum-powered seals.

This paper introduces a new, super-strong quantum seal based on a concept called a Quantum Walk on a special map called the Hanoi Network. Here is how it works, explained simply:

1. The Quantum Walker (The Coin Flipper)

Imagine a tiny, invisible ghost (a quantum particle) walking around a circular track made of stepping stones.

• In a normal walk: The ghost flips a coin. Heads, it steps left; Tails, it steps right.
• In a Quantum Walk: The ghost is in a "superposition," meaning it is walking both left and right at the same time. It spreads out like a wave, exploring the whole track simultaneously.

2. The Problem with the Old Tracks

Most previous quantum hash machines used a simple circular track (a ring).

• The Flaw: If the ring has an even number of stones, the ghost gets stuck in a predictable pattern. It's like a dancer who always lands on the same foot at the same time. This makes it easy for hackers to guess the pattern, leading to "collisions" (where two different stories get the same fingerprint).
• The Limitation: These old machines also needed very long stories (messages) to work properly. If you gave them a short note, the ghost didn't have enough time to spread out, and the fingerprint was weak.

3. The Hanoi Network: Adding "Teleportation" Doors

The authors of this paper decided to upgrade the track. Instead of just a simple ring, they built a Hanoi Network.

• The Metaphor: Imagine the circular track, but now there are secret teleportation tunnels connecting stones that are far apart.
• Why it helps: These tunnels break the predictable rhythm. The ghost can now jump across the track instantly. This creates a chaotic, unpredictable spread of the ghost's path, making it incredibly hard to guess where it will end up.

4. The Secret Sauce: Controlling the Walk with Your Message

This is where the magic happens. In older machines, your message (the story) only controlled the coin flip (Left or Right).

• The Innovation: In this new system, your message controls two things:
  1. The Coin: Which direction to step.
  2. The Teleportation: Whether to take the normal path or jump through the secret tunnel.

Think of it like a video game level where your password doesn't just tell the character which way to turn, but also decides which magic portals open up. Because the message controls both the steps and the shortcuts, the final path is unique to that specific message.

5. Why This is a Big Deal

• Short Messages Work: Because of the teleportation tunnels, the ghost spreads out fast. You can use this machine for very short messages (like a 4-digit PIN), whereas old machines needed long paragraphs to work.
• Unbreakable Seals: The paper shows that if you change just one bit of your message (like changing a '1' to a '0'), the final fingerprint changes completely. It's like changing one ingredient in a cake recipe and ending up with a completely different dish.
• Collision Resistance: The chance of two different messages producing the same fingerprint is astronomically low (about 0.05% in their tests, which is incredibly good). It's like trying to find two snowflakes that are identical, but with a much higher guarantee of uniqueness.

The Bottom Line

The authors have built a new type of digital fingerprint machine. By using a special map with "teleportation" shortcuts and letting the message control both the walking and the jumping, they created a system that is:

1. Faster for short messages.
2. More secure against hackers trying to fake fingerprints.
3. Robust enough to handle the noisy, imperfect nature of real-world quantum computers.

It's a significant step toward a future where our digital signatures and passwords are protected by the laws of quantum physics rather than just complex math.

Technical Summary

Here is a detailed technical summary of the paper "Quantum hash function using discrete-time quantum walk on Hanoi network" by Pulak Ranjan Giri.

1. Problem Statement

Classical hash functions (e.g., SHA-256, MD5) are vulnerable to attacks, particularly as quantum computing advances (e.g., Shor's and Grover's algorithms). While quantum hash functions have been proposed to leverage quantum properties like superposition and entanglement for enhanced security, existing schemes based on Discrete-Time Quantum Walks (DTQW) face specific limitations:

• Graph Constraints: Most existing schemes rely on simple one-dimensional periodic lattices (cycles). These often suffer from predictable zero-probability distributions for even-length lattices, leading to high collision rates.
• Message Length Limitations: Many cycle-based schemes require message bit-lengths to exceed the number of vertices in the graph to function effectively, limiting their utility for short messages.
• Control Mechanism: In most prior works, the message bits only control the coin operator of the quantum walk, leaving the shift operator static. This limits the complexity and diffusion of the resulting hash.

2. Methodology

The authors propose a novel quantum hash function utilizing a DTQW on a Hanoi Network of degree four (HN4).

A. The Underlying Graph: HN4

• Structure: The HN4 is a one-dimensional periodic lattice of $N_v = 2^n$ vertices with added long-range edges.
• Topology: Each vertex connects to two nearest neighbors (regular edges) and two long-range edges (connecting to $|i, j-1\rangle$ and $|i, j+1\rangle$ in a hierarchical coordinate system).
• Advantage: The long-range edges break the periodic zero-probability distribution found in simple cycles, allowing the use of even-length lattices and enabling efficient probability spreading even for short messages.

B. The Quantum Walk Mechanism

The evolution of the quantum state is governed by the operator $U = S(C \otimes I)$, where $C$ is the coin operator and $S$ is the shift operator.

• Dual Control: Uniquely, the message bits control both the coin operator ($C$) and the shift operator ($S$).
  • Bit = 0: Uses evolution operator $U_0 = S_0(C_0 \otimes I)$.
  • Bit = 1: Uses evolution operator $U_1 = S_1(C_1 \otimes I)$.
• Operators:
  • Coin ($C$): Uses Grover operators ($2|\psi\rangle\langle\psi| - I$) with specific coin states$|\psi_0\rangle$and$|\psi_1\rangle$determined by parameters ($l_{00}, \tilde{l}_{00}$, etc.) associated with the long-range edges.
  • Shift ($S$): Composed of three parts:
    1. Regular flip-flop shift (nearest neighbors).
    2. Long-range flip-flop shift (hierarchical connections).
    3. Self-loops for specific boundary vertices.
• Process: For a message $m = b_s \dots b_0$, the final state is $|\psi_f\rangle = U_{b_0} U_{b_1} \dots U_{b_s} |\psi_{in}\rangle$.

C. Hash Generation

1. Initialization: Start with a specific initial state $|\psi_{in}\rangle$ (equal superposition of coin states at vertex 0).
2. Evolution: Apply the sequence of operators based on the message bits.
3. Measurement: Measure the probability distribution $P(x_v, m)$ over the vertices.
4. Post-processing: Convert probability amplitudes to integers by multiplying by $10^l$and taking modulo$2^k$(where$k=16$). Concatenating these values for all$N_v$vertices yields a hash of length$L = N_v \times 16$ bits.

3. Key Contributions

1. HN4 Network Integration: First application of the Hanoi Network (HN4) for quantum hash functions, leveraging long-range edges to eliminate periodic zero-probability artifacts.
2. Dual-Operator Control: A novel scheme where message bits control both the coin and shift operators, significantly increasing the complexity of the state evolution and resistance to collision.
3. Short Message Efficiency: The scheme works effectively for messages with bit-lengths smaller than the number of vertices ($N_v$), a significant improvement over cycle-based schemes that typically require $s > N_v$.
4. Robustness to Parameter Variation: The system maintains low collision rates even with random variations in the long-range edge weights and initial coin state amplitudes.

4. Results and Performance Analysis

The authors conducted extensive statistical simulations ($N=10,000$ trials) to validate the scheme:

• Collision Resistance:
  • Experimental Collision Rate: 0.05%.
  • Theoretical Collision Rate: 0.02%.
  • Comparison: Significantly lower than other quantum walk schemes (e.g., Ref [24] at 23.12%, Ref [30] at 10.18%).
• Sensitivity (Avalanche Effect): Small changes in the input message (bit flips, insertions, deletions) result in massive changes in the output hash (high Hamming distance), satisfying the strict sensitivity requirement.
• Diffusion and Confusion:
  • The distribution of flipped bits between two hash values is uniform and close to the ideal mean ($N/2$).
  • Standard deviation is low, indicating high randomness.
• Uniform Distribution: The bit distribution in the hash space is uniform, with no statistical signatures of the original message remaining.
• Birthday Attack Resistance: With a 256-bit hash output, the scheme requires $2^{128}$ trials to find a collision with 50% probability, offering strong resistance.
• Scalability: The collision rate remains low and close to theoretical values as the number of vertices ($N_v$) increases (tested up to 512 vertices).

5. Significance

• Security: The scheme offers a high level of security based on the Holevo theorem (quantum information limits) rather than just computational hardness, making it potentially more robust against future quantum attacks than classical hash functions.
• NISQ Compatibility: The HN4 network requires only 2 qubits to represent the coin space and has a structure suitable for implementation on Noisy Intermediate-Scale Quantum (NISQ) devices.
• Practicality: By supporting short messages and even-length lattices, this method expands the applicability of quantum hash functions to a wider range of cryptographic protocols.
• Future Outlook: While the current analysis assumes noiseless conditions, the authors acknowledge that noise mitigation (e.g., reducing iteration steps or using error correction) will be a critical area for future research to ensure practical deployment.

In conclusion, this paper presents a highly efficient, collision-resistant quantum hash function that overcomes the structural limitations of previous lattice-based quantum walk schemes by utilizing the unique topology of the Hanoi Network and a dual-control evolution mechanism.