Controlled alternate quantum walk-based block hash function

Dan Li, Panpan Ding, Yuqian Zhou, Yu-Guang YangQuantum Inf. Process 2023 · DOI

TL;DR

This paper introduces a novel "Controlled Alternate Quantum Walk-based Block Hash Function" (CAQWBH) that significantly speeds up hash processing by handling messages in batches. By leveraging time-position-dependent quantum walks on complete graphs with self-loops, CAQWBH offers enhanced efficiency while maintaining security and flexibility.

What Problem Does This Paper Address?

The field of cryptography faces a significant challenge from the advancement of quantum computing. Shor's algorithm and Grover's algorithm threaten the security of many current cryptographic protocols. While post-quantum cryptography is one approach, quantum cryptography itself offers a promising path forward. Quantum walks, as the quantum counterparts of classical random walks, provide a powerful mathematical model for quantum computation and have found applications in various areas, including cryptography.

Existing quantum walk-based hash functions, while offering security based on the irreversibility of quantum measurement rather than complex mathematical problems, often process messages one bit at a time. This sequential processing is inefficient, especially for large amounts of data, and poses a bottleneck for practical applications on quantum computers. The paper aims to address this efficiency gap by developing a hash function that can process messages in larger chunks, thereby accelerating the hashing process.

Methods

The core innovation of this paper is the introduction of a time-position-dependent Controlled Alternate Quantum Walk (CAQW) on complete graphs with self-loops. This approach allows for the processing of messages in "batch amounts," a significant improvement over previous methods that handled messages bit-by-bit.

Here's a breakdown of the key methodological aspects:

  • Controlled Alternate Quantum Walk (CAQW): This is an extension of quantum walks where the evolution of the walker is controlled by external information, in this case, the message being hashed. The "alternate" aspect likely refers to a specific type of quantum walk evolution.
  • Time-Position-Dependent: The coin operators (which dictate the walker's movement) are not static but change based on both the step in time and the current position of the walker. This adds complexity and potentially enhances the hashing properties.
  • Complete Graphs with Self-Loops: The quantum walk is performed on a specific type of graph structure. Complete graphs ensure high connectivity, and self-loops can introduce additional dynamics. These structures are chosen to satisfy the "avalanche characteristic," meaning small changes in the input lead to large changes in the output.
  • Block Hash Function: Unlike previous bit-by-bit processing, CAQWBH processes messages in blocks. This is achieved by using the time-position-dependent CAQW where the coin operator is controlled by an N-bit message in each step, allowing for parallel processing of message bits.
  • Post-processing: After the quantum walk evolves, the resulting probability distribution is post-processed. This involves multiplying the probabilities by $10^k$ and taking the remainders modulo $2^k$ to generate a binary string as the hash value. This step is crucial for irreversibility and security.

Datasets

Not discussed in the paper. The paper focuses on the theoretical construction and performance analysis of the CAQWBH algorithm, using simulated or theoretical data for evaluation rather than specific named datasets.

Key Insights and Ideas

  • Batch Processing for Quantum Hash Functions: The most significant insight is the demonstration that quantum walk-based hash functions can be made significantly more efficient by processing messages in batches, rather than bit-by-bit. This directly addresses a practical bottleneck for quantum cryptographic primitives.
  • Time-Position-Dependent Walks Enhance Security and Efficiency: The use of time-position-dependent coin operators in the CAQW not only contributes to the efficiency of batch processing but also likely enhances the security by introducing more complex and dynamic state evolutions.
  • Complete Graphs with Self-Loops are Ideal for Hashing: The choice of this specific graph structure is motivated by its ability to satisfy the avalanche characteristic, a fundamental requirement for secure hash functions.
  • Irreversibility Through Measurement and Modulo Arithmetic: The security of CAQWBH is rooted in two key principles: the inherent irreversibility of quantum measurement and the many-to-one nature of the modulo arithmetic used in post-processing. This makes it computationally infeasible to reverse-engineer the original message from the hash.
  • Practicality on Current Hardware: The authors emphasize that CAQWBH is practical even on classical computers, which is a crucial consideration given the current state of quantum computing commercialization.

Key Results

The paper presents several key findings regarding the performance of CAQWBH:

  • High Efficiency: CAQWBH dramatically accelerates hash processing by handling messages in batch amounts.
  • Security: The hash function is demonstrated to be secure due to the irreversibility of measurement and modulo arithmetic, making it impossible to backtrack the message from the hash value.
  • Flexibility: The hash value length can be easily adjusted by changing parameters N and k, allowing for the construction of hash functions of varying lengths.
  • Statistical Performance:
    • Sensitivity to Message: Tiny modifications to the input message result in substantial changes in the output hash value, indicating good diffusion.
  • Diffusion and Confusion: Statistical tests show that the mean changed bit number and probability are close to ideal values (64 and 50% respectively), with low standard deviations, demonstrating stable diffusion and confusion properties.
  • Uniform Distribution: The hash values are distributed uniformly across the hash space, indicating resistance to statistical attacks.
  • Collision Resistance: While a formal proof is difficult for chaotic hash functions, experimental tests suggest that birthday attacks are practically impossible for CAQWBH, especially with its flexible key space.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that while CAQWBH is efficient, achieving accurate probability distributions for the quantum walk requires multiple runs, which can still be computationally intensive, especially on classical simulators.
  • The theoretical security relies on the assumption of ideal quantum computers.
  • Future Work:
    • The paper introduces extensions of CAQWBH for Message Authentication Codes (MAC) and Pseudo-Random Number Generators (PRNG), suggesting these as avenues for further development and application.
  • The authors suggest that CAQWBH could be used in designing cryptographic protocols, implying future research into its integration into broader security frameworks.
  • Further exploration of the impact of different graph structures and quantum walk variations on performance and security is implied.

Summary updated

BibTeX
@article{li2023controlled,
  author = {Dan Li and Panpan Ding and Yuqian Zhou and Yu-Guang Yang},
  title = {{Controlled alternate quantum walk-based block hash function}},
  journal = {Quantum Inf. Process.},
  year = {2023},
  doi = {10.1007/s11128-023-04123-w},
}
Figure