The quantum circuit implementation and feasibility analysis of quantum public-key cryptosystem based on the $$QSCD_{ff}$$ problem

AbstractThe development of quantum computation enables exponential time complexity problems on classical computers to be solved in polynomial time on quantum computers. However, it also poses a threat to the security of classical cryptographic schemes based on integer factorization and discrete logarithms. In response to this challenge, quantum cryptographic schemes based on quantum computation and quantum communication environments have become a focal point of research. The quantum public-key cryptosystem based on the QSCDff problem stands as one of the influential schemes in the realm of quantum public-key cryptography, yet its feasibility remains unexplored in current literature. Our specific focus lies in the quantum circuit implementations and fault-tolerant construction, which serve as essential prerequisites for the physical feasibility of quantum cryptographic schemes. We provide quantum circuit implementations along with rigorous theoretical proofs for the computation of the permutation product operation and the permutation sign operation in quantum public-key cryptographic schemes. Based on the fault-tolerant quantum computation process of the aforementioned quantum circu