Quantum Periodic Distinguisher Construction: Symbolization Method and Automated Tool

Qun Liu, Haoyang Wang, Jinliang Wang, Boyun Li, Meiqin Wang

TL;DR

This paper introduces a novel, automated framework for constructing quantum periodic distinguishers, a crucial tool for breaking symmetric-key ciphers using Simon's algorithm. By developing a generalized method and a symbolic representation, the authors have created the first fully automated SMT-based search model, leading to improved quantum distinguishers for several ciphers and opening new avenues for quantum cryptanalysis.

What Problem Does This Paper Address?

Simon's algorithm is a powerful quantum algorithm capable of efficiently finding the period of periodic functions. However, its practical application in cryptanalysis has been hampered by the difficulty of constructing suitable periodic functions, especially for complex symmetric-key ciphers. Existing methods are often manual, lack generality, or struggle with unknown differences within the cipher's structure. This paper tackles the challenge of creating a unified, automated approach to discover these periodic distinguishers, thereby enhancing the quantum threat to symmetric cryptography and potentially influencing future cipher design.

Methods

The authors propose a two-pronged approach:

  1. Generalized Method for Periodic Distinguisher Construction: They introduce a more generalized method that accounts for input differences and differences after round functions, overcoming limitations of prior work. This includes a polynomial-time distinguisher and a probabilistic distinguisher that leverages collisions of differences.
  2. Automated SMT-based Search Model: A key innovation is a novel symbolic representation of cipher states. This allows for the translation of the complex problem of finding periodic functions into a format solvable by Satisfiability Modulo Theories (SMT) solvers. This fully automated model significantly simplifies the search process, especially for complex structures.

Datasets

Not discussed in the paper. The paper focuses on theoretical advancements and applying them to existing cryptographic primitives.

Key Insights and Ideas

  • Symbolic Representation is Key: The paper highlights how abstracting cipher states into a limited set of symbols dramatically simplifies the search for periodic properties, making complex structures tractable.
  • Automation is the Future: The development of a fully automated SMT-based search model is a significant step towards making quantum cryptanalysis more accessible and efficient.
  • Probabilistic Distinguishers Broaden the Scope: By incorporating probabilistic approaches, the method can uncover periodic distinguishers that might be missed by purely deterministic methods.
  • New Quantum Weaknesses Found: The automated model successfully identified improved quantum distinguishers for several ciphers, demonstrating its practical effectiveness.

Key Results

The paper reports several significant findings:

  • Improved Quantum Distinguishers: The authors discovered new quantum distinguishers with improved round counts for:
  • GFS-4F: 10 rounds (1 round improvement)
    • LBlock: 10 rounds (2 rounds improvement)
    • TWINE: 10 rounds (2 rounds improvement)
    • Skipjack-B: 16 rounds (3 rounds improvement)
  • First Distinguishers for SKINNY: The model identified the first 7/8/9-round periodic distinguishers for SKINNY, a cipher previously lacking such quantum attacks.
  • Classical Performance: The proposed distinguishers also show competitive or superior performance compared to existing classical distinguishers in terms of data complexity.
  • Broad Applicability: The framework was successfully applied to various cipher structures, including Generalized Feistel Structures (GFS) and Substitution-Permutation Networks (SPN), demonstrating its versatility.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • MDS Matrices: Developing more precise analytical models for ciphers incorporating MDS matrices remains a challenge. The current approach uses an approximate strategy.
  • Scalability with Initial Values: For an increased number of initial values, exploring more precise models to ensure correctness without extensive testing is an open problem.
  • Future Cryptographic Design: The findings suggest that periodic distinguishers should be a key consideration in the design of future cryptographic primitives to ensure their quantum resistance. The authors anticipate that this work will influence future cipher design and analysis.

Summary updated

BibTeX
@article{liu2025quantum,
  author = {Qun Liu and Haoyang Wang and Jinliang Wang and Boyun Li and Meiqin Wang},
  title = {{Quantum Periodic Distinguisher Construction: Symbolization Method and Automated Tool}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2025},
}

Loading related content...

Figure