International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

New SAT-based Model for Quantum Circuit Decision Problem: Searching for Low-Cost Quantum Implementation

Authors:
Jingwen Chen , School of Cyber Science and Technology, Shandong University, Qingdao, Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan
Qun Liu , School of Cyber Science and Technology, Shandong University, Qingdao, Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan
Yanhong Fan , School of Cyber Science and Technology, Shandong University, Qingdao, Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan
Lixuan Wu , School of Cyber Science and Technology, Shandong University, Qingdao, Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan
Boyun Li , School of Cyber Science and Technology, Shandong University, Qingdao, Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan
Meiqin Wang , Quan Cheng Shandong Laboratory, Jinan, School of Cyber Science and Technology, Shandong University, Qingdao, Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan
Download:
DOI: 10.62056/anmmp-4c2h
URL: https://cic.iacr.org//p/1/1/31
Search ePrint
Search Google
Abstract:

In recent years, quantum technology has been rapidly developed. As security analyses for symmetric ciphers continue to emerge, many require an evaluation of the resources needed for the quantum circuit implementation of the encryption algorithm. In this regard, we propose the quantum circuit decision problem, which requires us to determine whether there exists a quantum circuit for a given permutation f using M ancilla qubits and no more than K quantum gates within the circuit depth D. Firstly, we investigate heuristic algorithms and classical SAT-based models in previous works, revealing their limitations in solving the problem. Hence, we innovatively propose an improved SAT-based model incorporating three metrics of quantum circuits. The model enables us to find the optimal quantum circuit of an arbitrary 3 or 4-bit S-box under a given optimization goal based on SAT solvers, which has proved the optimality of circuits constructed by the tool, LIGHTER-R. Then, by combining different criteria in the model, we find more compact quantum circuit implementations of S-boxes such as RECTANGLE and GIFT. For GIFT S-box, our model provides the optimal quantum circuit that only requires 8 gates with a depth of 31. Furthermore, our model can be generalized to linear layers and improve the previous SAT-based model proposed by Huang et al. in ASIACRYPT 2022 by adding the criteria on the number of qubits and the circuit depth.
BibTeX
@article{cic-2024-34114,
  title={New SAT-based Model for Quantum Circuit Decision Problem: Searching for Low-Cost Quantum Implementation},
  journal={cic},
  publisher={International Association for Cryptologic Research},
  volume={1, Issue 1},
  url={https://cic.iacr.org//p/1/1/31},
  doi={10.62056/anmmp-4c2h},
  author={Jingwen Chen and Qun Liu and Yanhong Fan and Lixuan Wu and Boyun Li and Meiqin Wang},
  year=2024
}