{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,1]],"date-time":"2024-12-01T01:40:17Z","timestamp":1733017217420,"version":"3.30.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,12,1]],"date-time":"2024-12-01T00:00:00Z","timestamp":1733011200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,12,1]],"date-time":"2024-12-01T00:00:00Z","timestamp":1733011200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"the Key Research Program of the Chinese Academy of Sciences","award":["ZDRW- XX-2022-1"],"award-info":[{"award-number":["ZDRW- XX-2022-1"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cybersecurity"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The 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 <jats:italic>QSCD<\/jats:italic><jats:sub>ff<\/jats:sub> 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 circuit implementations, we propose two error-correction strategies and provide a theoretical feasibility analysis within a specified range in the ion-trap quantum computation environment, adhering to the theoretical limits of quantum computation. Rigorous proofs are presented to demonstrate the correctness and reliability of the proposed methods. Our contribution provides a theoretical foundation for the physical feasibility analysis of quantum cryptographic algorithms, offering insights into the challenges and prospects of implementing these algorithms in quantum computation environments.<\/jats:p>","DOI":"10.1186\/s42400-024-00257-1","type":"journal-article","created":{"date-parts":[[2024,12,1]],"date-time":"2024-12-01T00:01:36Z","timestamp":1733011296000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The quantum circuit implementation and feasibility analysis of quantum public-key cryptosystem based on the $$QSCD_{ff}$$ problem"],"prefix":"10.1186","volume":"7","author":[{"given":"Anyi","family":"Li","sequence":"first","affiliation":[]},{"given":"Qiqing","family":"Xia","sequence":"additional","affiliation":[]},{"given":"Qianru","family":"Zhu","sequence":"additional","affiliation":[]},{"given":"Li","family":"Yang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,12,1]]},"reference":[{"key":"257_CR4","doi-asserted-by":"publisher","unstructured":"Ajtai M, Dwork C (1997) A public-key cryptosystem with worst-case\/average-case equivalence. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing - STOC \u201997, pp. 284\u2013293. ACM Press, El Paso, Texas, United States . https:\/\/doi.org\/10.1145\/258533.258604","DOI":"10.1145\/258533.258604"},{"key":"257_CR7","doi-asserted-by":"publisher","unstructured":"Albrecht, M.R., Faug\u00e9re, J.-C., Fitzpatrick, R., Perret, L., Todo, Y., Xagawa, K.: Practical Cryptanalysis of a Public-Key Encryption Scheme Based on New Multivariate Quadratic Assumptions. In: Krawczyk, H. (ed.) Public-Key Cryptography - PKC 2014. Lecture Notes in Computer Science, pp. 446\u2013464. Springer, Berlin, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54631-0_26","DOI":"10.1007\/978-3-642-54631-0_26"},{"key":"257_CR33","unstructured":"Artin, M.: Algebra. Pearson (2018)"},{"key":"257_CR10","doi-asserted-by":"publisher","unstructured":"Bardet M, Chaulet J, Dragoi V, Otmani A, Tillich JP (2016). Cryptanalysis of the McEliece Public Key Cryptosystem Based on Polar Codes. In: Takagi, T. (ed.) Post-Quantum Cryptography. Lecture Notes in Computer Science, pp. 118\u2013143. Springer International Publishing, Cham https:\/\/doi.org\/10.1007\/978-3-319-29360-8_9","DOI":"10.1007\/978-3-319-29360-8_9"},{"key":"257_CR35","doi-asserted-by":"crossref","unstructured":"Benenti, G., Casati, G., Strini, G.: Principles Of Quantum Computation And Information - Volume I: Basic Concepts. World Scientific (2004)","DOI":"10.1142\/9789812794796"},{"key":"257_CR11","doi-asserted-by":"publisher","unstructured":"Berlekamp, E., McEliece, R., van Tilborg, H. (1978)On the inherent intractability of certain coding problems (Corresp.). IEEE Trans. Inf. Theory 24(3), 384\u2013386 https:\/\/doi.org\/10.1109\/TIT.1978.1055873","DOI":"10.1109\/TIT.1978.1055873"},{"key":"257_CR24","doi-asserted-by":"publisher","unstructured":"Chailloux A, Naya-Plasencia M, Schrottenloher, A. An Efficient Quantum Collision Search Algorithm and Implications on Symmetric Cryptography. In: Takagi, T., Peyrin, T. (eds.) Advances in Cryptology - ASIACRYPT 2017. Lecture Notes in Computer Science, pp. 211\u2013240. Springer International Publishing, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70697-9_8","DOI":"10.1007\/978-3-319-70697-9_8"},{"issue":"2","key":"257_CR40","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1016\/j.ic.2004.04.001","volume":"192","author":"R Cleve","year":"2004","unstructured":"Cleve R (2004) The query complexity of order-finding. Inf. Comput. 192(2):162\u2013171. https:\/\/doi.org\/10.1016\/j.ic.2004.04.001","journal-title":"Inf. Comput."},{"key":"257_CR38","doi-asserted-by":"publisher","unstructured":"Cruz, P.M.Q., Murta, B.: Shallow Unitary Decompositions of Quantum Fredkin and Toffoli Gates for Connectivity-Aware Equivalent Circuit Averaging. arXiv (2023). https:\/\/doi.org\/10.48550\/arXiv.2305.18128","DOI":"10.48550\/arXiv.2305.18128"},{"issue":"4","key":"257_CR2","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","volume":"31","author":"T Elgamal","year":"1985","unstructured":"Elgamal T (1985) A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31(4):469\u2013472. https:\/\/doi.org\/10.1109\/TIT.1985.1057074","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3\u20134","key":"257_CR13","first-page":"181","volume":"12","author":"H Fujita","year":"2012","unstructured":"Fujita H (2012) Quantum McEliece public-key cryptosystem. Quantum Inf. Comput. 12(3\u20134):181\u2013202","journal-title":"Quantum Inf. Comput."},{"key":"257_CR20","doi-asserted-by":"publisher","unstructured":"Grassl M, Langenberg B, Roetteler M, Steinwandt, R (2016). Applying Grover\u2019s Algorithm to AES: Quantum Resource Estimates. In: Takagi, T. (ed.) Post-Quantum Cryptography. Lecture Notes in Computer Science, pp. 29\u201343. Springer International Publishing, Cham https:\/\/doi.org\/10.1007\/978-3-319-29360-8_3","DOI":"10.1007\/978-3-319-29360-8_3"},{"key":"257_CR34","unstructured":"Grillet, P.A.: Abstract Algebra. Springer (2007)"},{"key":"257_CR23","doi-asserted-by":"publisher","unstructured":"Huang, Z., Sun, S.: Synthesizing Quantum Circuits of\u00a0AES with\u00a0Lower T-depth and\u00a0Less Qubits. In: Advances in Cryptology - ASIACRYPT 2022: 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5- 9, 2022, Proceedings, Part III, pp. 614\u2013644. Springer-Verlag, Berlin, Heidelberg (2023). https:\/\/doi.org\/10.1007\/978-3-031-22969-5_21","DOI":"10.1007\/978-3-031-22969-5_21"},{"key":"257_CR22","doi-asserted-by":"publisher","unstructured":"Jaques, S., Naehrig, M., Roetteler, M., Virdia, F.: Implementing Grover Oracles for Quantum Key Search on AES and LowMC. In: Canteaut, A., Ishai, Y. (eds.) Advances in Cryptology - EUROCRYPT 2020. Lecture Notes in Computer Science, pp. 280\u2013310. Springer International Publishing, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45724-2_10","DOI":"10.1007\/978-3-030-45724-2_10"},{"key":"257_CR5","doi-asserted-by":"publisher","unstructured":"Katsumata S, Nishimaki R, Yamada S, Yamakawa T (2020) Adaptively Secure Inner Product Encryption from LWE. In: Moriai, S., Wang, H. (eds.) Advances in Cryptology - ASIACRYPT 2020 vol. 12493, pp. 375\u2013404. Springer International Publishing, Cham . https:\/\/doi.org\/10.1007\/978-3-030-64840-4_13","DOI":"10.1007\/978-3-030-64840-4_13"},{"key":"257_CR27","doi-asserted-by":"publisher","unstructured":"Kawachi A, Koshiba T, Nishimura H, Yamakami T Computational Indistinguishability Between Quantum States and Its Cryptographic Application. In: Cramer, R. (ed.) Advances in Cryptology - EUROCRYPT 2005. Lecture Notes in Computer Science, pp. 268\u2013284. Springer, Berlin, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11426639_16","DOI":"10.1007\/11426639_16"},{"issue":"177","key":"257_CR3","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1090\/S0025-5718-1987-0866109-5","volume":"48","author":"N Koblitz","year":"1987","unstructured":"Koblitz N (1987) Elliptic Curve Cryptosystems. Math. Comput. 48(177):203\u2013209. https:\/\/doi.org\/10.1090\/S0025-5718-1987-0866109-5","journal-title":"Math. Comput."},{"key":"257_CR21","doi-asserted-by":"publisher","unstructured":"Langenberg B, Pham H, Steinwand, R: Reducing the Cost of Implementing the Advanced Encryption Standard as a Quantum Circuit. IEEE Trans. Quantum Eng. 1, 1\u201312 (2020) https:\/\/doi.org\/10.1109\/TQE.2020.2965697","DOI":"10.1109\/TQE.2020.2965697"},{"issue":"9","key":"257_CR14","doi-asserted-by":"publisher","first-page":"1618","DOI":"10.1007\/s11433-011-4806-y","volume":"55","author":"M Liang","year":"2012","unstructured":"Liang M, Yang L (2012) Public-key encryption and authentication of quantum information. Sci. China Phys. Mech. Astron. 55(9):1618\u20131629. https:\/\/doi.org\/10.1007\/s11433-011-4806-y","journal-title":"Sci. China Phys. Mech. Astron."},{"key":"257_CR25","doi-asserted-by":"publisher","unstructured":"Liu X, Yang H, Yang L Feasibility Analysis of Cracking RSA with Improved Quantum Circuits of the Shor\u2019s Algorithm. Secur. commun. netw 2023, 2963110 (2023) https:\/\/doi.org\/10.1155\/2023\/2963110","DOI":"10.1155\/2023\/2963110"},{"issue":"1","key":"257_CR26","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1186\/s42400-023-00181-w","volume":"6","author":"X Liu","year":"2023","unstructured":"Liu X, Yang H, Yang L (2023) Minimizing CNOT-count in quantum circuit of the extended Shor\u2019s algorithm for ECDLP. Cybersecur. 6(1):48. https:\/\/doi.org\/10.1186\/s42400-023-00181-w","journal-title":"Cybersecur."},{"key":"257_CR31","doi-asserted-by":"publisher","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press (2010). https:\/\/doi.org\/10.1017\/CBO9780511976667","DOI":"10.1017\/CBO9780511976667"},{"issue":"3","key":"257_CR15","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.77.032348","volume":"77","author":"GM Nikolopoulos","year":"2008","unstructured":"Nikolopoulos GM (2008) Applications of single-qubit rotations in quantum public-key cryptography. Phys. Rev. A 77(3):032348. https:\/\/doi.org\/10.1103\/PhysRevA.77.032348","journal-title":"Phys. Rev. A"},{"key":"257_CR32","doi-asserted-by":"publisher","unstructured":"Preskill, J. (1998) Fault-tolerant quantum computation. In: Introduction to Quantum Computation and Information, pp. 213\u2013269. https:\/\/doi.org\/10.1142\/9789812385253_0008","DOI":"10.1142\/9789812385253_0008"},{"key":"257_CR8","doi-asserted-by":"publisher","unstructured":"Raviv N, Langton B, Tamo I (2021) Multivariate Public Key Cryptosystem from Sidon Spaces. In: Garay, J.A. (ed.) Public-Key Cryptography - PKC 2021. Lecture Notes in Computer Science, pp. 242\u2013265. Springer International Publishing, Cham . https:\/\/doi.org\/10.1007\/978-3-030-75245-3_10","DOI":"10.1007\/978-3-030-75245-3_10"},{"issue":"6","key":"257_CR12","doi-asserted-by":"publisher","first-page":"1279","DOI":"10.1007\/s10623-021-00861-z","volume":"89","author":"J Renner","year":"2021","unstructured":"Renner J, Puchinger S, Wachter-Zeh A (2021) LIGA: A cryptosystem based on the hardness of rank-metric list and interleaved decoding. Des. Codes Cryptogr. 89(6):1279\u20131319. https:\/\/doi.org\/10.1007\/s10623-021-00861-z","journal-title":"Des. Codes Cryptogr."},{"issue":"2","key":"257_CR6","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10623-012-9732-0","volume":"71","author":"R Sepahi","year":"2014","unstructured":"Sepahi R, Steinfeld R, Pieprzyk J (2014) Lattice-based completely non-malleable public-key encryption in the standard model. Des. Codes Cryptogr. 71(2):293\u2013313. https:\/\/doi.org\/10.1007\/s10623-012-9732-0","journal-title":"Des. Codes Cryptogr."},{"issue":"2","key":"257_CR1","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"RL Rivest","year":"1978","unstructured":"Rivest RL, Shamir A, Adleman L (1978) A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2):120\u2013126. https:\/\/doi.org\/10.1145\/359340.359342","journal-title":"Commun. ACM"},{"key":"257_CR37","doi-asserted-by":"publisher","unstructured":"Shor, P.W.: Fault-tolerant quantum computation. In: Proceedings of 37th Conference on Foundations of Computer Science, pp. 56\u201365 (1996). https:\/\/doi.org\/10.1109\/SFCS.1996.548464","DOI":"10.1109\/SFCS.1996.548464"},{"issue":"4","key":"257_CR28","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.91.042306","volume":"91","author":"A Souto","year":"2015","unstructured":"Souto A, Mateus P, Ad\u00e3o P, Paunkovi\u0107 N (2015) Bit-string oblivious transfer based on quantum state computational distinguishability. Phys. Rev. A 91(4):042306. https:\/\/doi.org\/10.1103\/PhysRevA.91.042306","journal-title":"Phys. Rev. A"},{"issue":"5","key":"257_CR36","doi-asserted-by":"publisher","first-page":"793","DOI":"10.1103\/PhysRevLett.77.793","volume":"77","author":"AM Steane","year":"1996","unstructured":"Steane AM (1996) Error Correcting Codes in Quantum Theory. Phys. Rev. Lett. 77(5):793\u2013797. https:\/\/doi.org\/10.1103\/PhysRevLett.77.793","journal-title":"Phys. Rev. Lett."},{"issue":"8","key":"257_CR19","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s11128-022-03628-0","volume":"21","author":"Z Sun","year":"2022","unstructured":"Sun Z, Gao W, Dong H, Xie H, Yang L (2022) A new post-quantum voting protocol based on physical laws. QIP 21(8):289. https:\/\/doi.org\/10.1007\/s11128-022-03628-0","journal-title":"QIP"},{"key":"257_CR30","doi-asserted-by":"publisher","unstructured":"Xiao M, Tao X (2023) Research on quantum cheque based on the resolution of quantum state computing. In: International Conference on Cryptography, Network Security, and Communication Technology (CNSCT 2023), vol. 12641, pp. 247\u2013252 . https:\/\/doi.org\/10.1117\/12.2678871","DOI":"10.1117\/12.2678871"},{"issue":"8","key":"257_CR29","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s11128-020-02736-z","volume":"19","author":"X Xin","year":"2020","unstructured":"Xin X, Yang Q, Li F (2020) Quantum public-key signature scheme based on asymmetric quantum encryption with trapdoor information. QIP 19(8):233. https:\/\/doi.org\/10.1007\/s11128-020-02736-z","journal-title":"QIP"},{"key":"257_CR16","doi-asserted-by":"publisher","unstructured":"Yang L, Liang M A Note on Quantum McEliece Public-Key Cryptosystem. arXiv (2013). https:\/\/doi.org\/10.48550\/arXiv.1212.0725","DOI":"10.48550\/arXiv.1212.0725"},{"issue":"11","key":"257_CR17","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/s11128-020-02912-1","volume":"19","author":"L Yang","year":"2020","unstructured":"Yang L, Yang B, Xiang C (2020) Quantum public-key encryption schemes based on conjugate coding. QIP 19(11):415. https:\/\/doi.org\/10.1007\/s11128-020-02912-1","journal-title":"QIP"},{"issue":"10","key":"257_CR39","doi-asserted-by":"publisher","DOI":"10.1007\/s11432-019-2689-4","volume":"63","author":"B Yang","year":"2020","unstructured":"Yang B, Yang L (2020) Effect on ion-trap quantum computers from the quantum nature of the driving field. Sci. China Inf. Sci. 63(10):202501. https:\/\/doi.org\/10.1007\/s11432-019-2689-4","journal-title":"Sci. China Inf. Sci."},{"key":"257_CR18","doi-asserted-by":"publisher","unstructured":"Yang L, Zhou RR (2013) On the Post-Quantum Security of Encrypted Key Exchange Protocols. arXiv . https:\/\/doi.org\/10.48550\/arXiv.1305.5640","DOI":"10.48550\/arXiv.1305.5640"},{"key":"257_CR9","doi-asserted-by":"publisher","unstructured":"Yang, B.-Y., Chen, J.-M. (2005) Building Secure Tame-like Multivariate Public-Key Cryptosystems: The New TTS. In: Boyd, C., Gonz\u00e1lez\u00a0Nieto, J.M. (eds.) Information Security and Privacy. Lecture Notes in Computer Science, pp. 518\u2013531. Springer, Berlin, Heidelberg . https:\/\/doi.org\/10.1007\/11506157_43","DOI":"10.1007\/11506157_43"}],"container-title":["Cybersecurity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-024-00257-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s42400-024-00257-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-024-00257-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,1]],"date-time":"2024-12-01T01:02:51Z","timestamp":1733014971000},"score":1,"resource":{"primary":{"URL":"https:\/\/cybersecurity.springeropen.com\/articles\/10.1186\/s42400-024-00257-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,1]]},"references-count":40,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["257"],"URL":"https:\/\/doi.org\/10.1186\/s42400-024-00257-1","relation":{},"ISSN":["2523-3246"],"issn-type":[{"type":"electronic","value":"2523-3246"}],"subject":[],"published":{"date-parts":[[2024,12,1]]},"assertion":[{"value":"15 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 May 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 December 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interest"}}],"article-number":"63"}}