Quantum circuit implementations of SM4 block cipher based on different gate sets | Quantum Information Processing Skip to main content

Advertisement

Springer Nature Link
Log in

Quantum circuit implementations of SM4 block cipher based on different gate sets

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

In recent years, the quantum implementation of symmetric ciphers has received much attention. In this paper, we investigate the construction of quantum circuits based on different gate sets for the SM4 block cipher, which is the national standard of commercial cryptography of China and is standardized in ISO/IEC. First, we construct reversible circuits using Pauli-X gates, CNOT gates and Toffoli gates (i.e., the NCT gate set) for the SM4 S-box, based on which we design two circuits for the SM4 S-box with Clifford+T gates by applying the quantum And gate and existing decomposition scheme of the Toffoli gate, respectively. In addition, we propose a new in-place 1 implementation for the linear transformation in the SM4 round function. Finally, taking the qubit consumption and the \(T{\cdot } M\) value (the product of qubit consumption and nonlinear gate depth of a quantum circuit) as metrics, we investigate the application of various circuits we designed to the construction of quantum circuits for SM4. The results show that we can always construct a subroutine/stand-alone circuit based on the NCT gate set, or based on Clifford+T gates for SM4 with fewer qubits or lower \(T {\cdot } M\) value than existing state-of-the-art implementations.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Data availability

The datasets generated during and/or analyzed during the current study are available at https://github.com/Supporting-Material/The-SM4-Sbox-in-quantum.

Notes

  1. Note that the qubit cannot be copied. The operation of coping the value stored in a qubit can be completed by introducing an ancilla qubits \(|0\rangle \) and then utilizing the CNOT gate that takes \(|0\rangle \) as the target qubit.

References

  1. Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Gary L. Miller, (ed), In: Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pp. 212–219. ACM (1996)

  2. Simon, D.R.: On the power of quantum computation. SIAM J. Comput. 26(5), 1474–1483 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  3. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  4. Daemen, J., Rijmen, V.: The Design of Rijndael: AES—The Advanced Encryption Standard. Information Security and Cryptography. Springer, Berlin (2002)

    Book  MATH  Google Scholar 

  5. Almazrooie, M., Samsudin, A., Abdullah, R., Mutter, K.N.: Quantum reversible circuit of AES-128. Quantum Inf. Process. 17(5), 112 (2018)

    Article  ADS  MathSciNet  MATH  Google Scholar 

  6. Grassl, M., Langenberg, B., Roetteler, M., Steinwandt, R.: Applying Grover’s algorithm to AES: quantum resource estimates. In: Takagi, T., (eds.), Post-Quantum Cryptography—7th International Workshop, PQCrypto 2016, Fukuoka, Japan, February 24-26, 2016, Proceedings, vol. 9606 of Lecture Notes in Computer Science, pp. 29–43. Springer, (2016)

  7. Huang, Z., Sun, S.: Synthesizing quantum circuits of aes with lower t-depth and less qubits. In: Agrawal, S., Lin, D. (eds.), 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, volume 13793 of Lecture Notes in Computer Science, pp. 614–644. Springer (2022)

  8. Jang, K., Baksi, A., Song, G., Kim, H., Seo, H., Chattopadhyay, A.: Quantum analysis of aes. IACR Cryptol. ePrint Arch. 2022, 683 (2022)

  9. 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 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part II, volume 12106 of Lecture Notes in Computer Science, pp. 280-310. Springer (2020)

  10. Kim, P., Han, D., Jeong, K.C.: Time-space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2. Quantum Inf. Process. 17(12), 1–39 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  11. Langenberg, B., Pham, H., Steinwandt, R.: Reducing the cost of implementing the advanced encryption standard as a quantum circuit. IEEE Trans. Quantum Eng. 2020(1), 1–12 (2020)

    Article  Google Scholar 

  12. Li, Z., Cai, B., Sun, H., Liu, H., Wan, L., Qin, S., Wen, Q., Gao, F.: Novel quantum circuit implementation of Advanced Encryption Standard with low costs. Sci. China Phys. Mech. Astron. 65(9), 290311 (2022)

    Article  ADS  Google Scholar 

  13. Li, Z., Gao, F., Qin, S., Wen, Q.: New record in the number of qubits for a quantum implementation of AES. IACR Cryptol. ePrint Arch. 2023, 018 (2023)

  14. Lin, D., Xiang, Z., Xu, R., Zhang, S., Zeng, X.: Optimized Quantum Implementation of AES. IACR Cryptol. ePrint Arch. 2023, 146 (2023)

  15. Wang, Z., Wei, S., Long, G.: A quantum circuit design of AES requiring fewer quantum qubits and gate operations. Front. Phys. 17(4), 1–7 (2022)

    Article  Google Scholar 

  16. Zou, J., Wei, Z., Sun, S., Liu, X., Wu, W.: Quantum circuit implementations of AES with fewer qubits. In: Moriai, S., Wang, H. (eds.), Advances in Cryptology - ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part II, volume 12492 of Lecture Notes in Computer Science, pp. 697–726. Springer (2020)

  17. Standardization Administration of the P. R. China: GB/T32907-2016. In: Information Security Technology-SM4 Block Cipher Algorithm (2016)

  18. Lin, D., Xiang, Z., Zhang, R., Zhang, S., Zeng, X.: Quantum implementation of SM4 (in Chinese). J. Cryptol. Res. 8(6), 999–1018 (2021)

    Google Scholar 

  19. Zou, J., Li, L., Wei, Z., Luo, Y., Liu, Q., Wu, W.: New quantum circuit implementations of SM4 and SM3. Quantum Inf. Process. 21(5), 1–38 (2022)

    Article  ADS  MathSciNet  MATH  Google Scholar 

  20. Abbasi, I., Afzal, M.: A compact S-Box design for SMS4 block cipher. In: IT Convergence and Services, Lecture Notes in Electrical Engineering, pp. 641–658. Springer (2011)

  21. Bai, X., Xu, Y., Guo, L.: Securing SMS4 cipher against differential power analysis and its VLSI implementation. In: 2008 11th IEEE Singapore International Conference on Communication Systems, Guangzhou, China, November 19-21, 2008, pp. 167–172. IEEE Xplore (2008)

  22. Martínez-Herrera, A.F., Mex-Perera, C., Nolazco-Flores, J.: Merging the camellia, SMS4 and AES s-boxes in a single s-box with composite bases. In: Desmedt, Y. (eds.), 16th International Conference, ISC 2013, Dallas, Texas, November 13-15, 2013, Proceedings, volume 7807 of Lecture Notes in Computer Science, pp. 209–217. Springer (2013)

  23. Wei, Z., Sun, S., Hu, L., Wei, M., Boyar, J., Peralta, R.: Scrutinizing the Tower Field Implementation of the \(\mathbb{F} _{2^8}\) Inverter-with Applications to AES, Camellia, and SM4. IACR Cryptol. ePrint Arch. 2019, 738 (2019)

  24. Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. In: Oswald, E., Fischlin, M. (eds.), Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, volume 9056 of Lecture Notes in Computer Science, pp. 430-454. Springer (2015)

  25. Zou, J., Wei, Z., Sun, S., Luo, Y., Liu, Q., Wu, W.: Some efficient quantum circuit implementations of camellia. Quantum Inf. Process. 21(4), 1–27 (2022)

    Article  ADS  MathSciNet  MATH  Google Scholar 

  26. Xiang, Z., Zeng, X., Lin, D., Bao, Z., Zhang, S.: Optimizing implementations of linear layers. IACR Trans. Symmetric Cryptol. 2020(2), 120–145 (2020)

    Article  Google Scholar 

  27. Shende, V.V., Prasad, A.K., Markov, I.L., Hayes, J.P.: Synthesis of reversible logic circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 22(6), 710–722 (2003)

    Article  Google Scholar 

  28. Jean, J., Peyrin, T., Sim, S.M., Tourteaux, J.: Optimizing implementations of lightweight building blocks. IACR Trans. Symmetric Cryptol. 2017(4), 130–168 (2017)

    Article  Google Scholar 

  29. Amy, M., Maslov, D., Mosca, M., Roetteler, M.: A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 32(6), 818–830 (2013)

    Article  Google Scholar 

Download references

Funding

This work was supported by the National Key Research and Development Program of China (Grant No.2021YFA1000600), the National Natural Science Foundation of China (Grant No.62272147) and the Wuhan Science and Technology Bureau (Grant No.2022010801020328).

Author information

Authors and Affiliations

  1. Faculty of Mathematics and Statistics, Hubei Key Laboratory of Applied Mathematics, Hubei University, Wuhan, 430062, China

    Da Lin & Xiangyong Zeng

  2. State Key Laboratory of Cryptology, P. O. Box 5159, Beijing, 100878, China

    Zejun Xiang

  3. School of Cyber Science and Technology, Hubei University, Wuhan, 430062, China

    Zejun Xiang, Runqing Xu & Shasha Zhang

Authors
  1. Da Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zejun Xiang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Runqing Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Xiangyong Zeng
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Shasha Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

Da Lin and Zejun Xiang derived the methodology. Runqing Xu simulated the theoretical results. Xiangyong Zeng and Shasha Zhang provided data and format analysis. All authors contributed to the preparation of the manuscript. All authors read and approved the final manuscript.

Corresponding author

Correspondence to Zejun Xiang.

Ethics declarations

Conflict of interest

The authors have no competing interests to declare that are relevant to the content of this article.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendices

Appendix A: NCT-based circuit of the SM4 S-box

1.1 A.1 The reversible circuit of \(H_1\)

$$\begin{aligned} \begin{array}{llllll} {{\mathtt {\#Toffoli~depth~1:~step~9-12}}}\\ {1}&{}\mathtt {x_{4} = \overline{x_{4} \oplus x_{5} \oplus x_{3} \oplus x_{2}}},&{}{6}&{}\mathtt {x_{2} = \overline{x_{2} \oplus x_{7} \oplus x_{1}}},&{}{11}&{}\mathtt {a_1 = a_1 \oplus x_{3}\cdot x_{2}}\\ {2}&{}\mathtt {x_{5} = x_{5} \oplus x_{3} \oplus x_{1} \oplus x_{0}},&{}{7}&{}\mathtt {x_{0} = \overline{x_{0}}},&{}{12}&{}\mathtt {a_4 = a_4 \oplus x_{0}\cdot x_{1}},\\ {3}&{}\mathtt {x_{7} = x_{7} \oplus x_{4} \oplus x_{3} \oplus x_{1}},&{}{8}&{}\mathtt {x_{1} = x_{5} \oplus x_{1}},&{}{13}&{}\mathtt {a_2 = a_2 \oplus a_4},\\ {4}&{}\mathtt {x_{6} = \overline{x_{6} \oplus x_{7}}},&{}{9}&{}\mathtt {a_2 = a_2 \oplus x_{4}\cdot x_{5}},&{}{14}&{}\mathtt {a_3 = a_3 \oplus a_2},\\ {5}&{}\mathtt {x_{3} = x_{3} \oplus x_{5}},&{}{10}&{}\mathtt {a_3 = a_3 \oplus x_{7}\cdot x_{6}},&{}{15}&{}\mathtt {a_0 = a_0 \oplus a_3\oplus a_4},\\ {{\mathtt {\#Toffoli~depth~2:~step~7-10}}}\\ {1}&{}\mathtt {x_{4} = x_{7} \oplus x_{4} \oplus x_{3} \oplus x_{0}},&{}{5}&{}\mathtt {x_{7} = x_{7} \oplus x_{4} \oplus x_{3}},&{}{9}&{}\mathtt {a_1 = a_1 \oplus x_{7}\cdot x_{6}},\\ {2}&{}\mathtt {x_{1} = x_{6} \oplus x_{5} \oplus x_{2} \oplus x_{1}},&{}{6}&{}\mathtt {x_{6} = x_{6} \oplus x_{2} \oplus x_{1}},&{}{10}&{}\mathtt {a_3 = a_3 \oplus x_{3}\cdot x_{2}},\\ {3}&{}\mathtt {x_{0} = x_{4} \oplus x_{3} \oplus x_{0}},&{}{7}&{}\mathtt {a_0 = a_0 \oplus x_{4}\cdot x_{1}},&{}{11}&{}\mathtt {a_1 = a_1 \oplus a_2},\\ {4}&{}\mathtt {x_{5} = x_{6} \oplus x_{5}},&{}{8}&{}\mathtt {a_2 = a_2 \oplus x_{0}\cdot x_{5}},&{}&{}\\ {{\mathtt {\#Toffoli~depth~3:~step~7-10}}}\\ {1}&{}\mathtt {x_{0} = x_{4} \oplus x_{3} \oplus x_{0}},&{}{8}&{}\mathtt {a_0 = a_0 \oplus x_{7}\cdot x_{6}},&{}{15}&{}\mathtt {x_{4} = x_{5} \oplus x_{4} \oplus x_{3} \oplus x_{1}},\\ {2}&{}\mathtt {x_{2} = x_{5} \oplus x_{2} \oplus x_{1}},&{}{9}&{}\mathtt {a_1 = a_1 \oplus x_{4}\cdot x_{1}},&{}{16}&{}\mathtt {a_1 = a_1 \oplus x_{4}},\\ {3}&{}\mathtt {x_{4} = x_{7} \oplus x_{4}},&{}{10}&{}\mathtt {a_2 = a_2 \oplus x_{3}\cdot x_{5}},&{}{17}&{}\mathtt {x_{7} = x_{7} \oplus x_{5} \oplus x_{3}},\\ {4}&{}\mathtt {x_{1} = x_{6} \oplus x_{1}},&{}{11}&{}\mathtt {a_0 = a_0 \oplus a_2},&{}{18}&{}\mathtt {a_2 = a_2 \oplus x_{7}},\\ {5}&{}\mathtt {x_{3} = x_{3} \oplus x_{0}},&{}{12}&{}\mathtt {x_{7} = x_{7} \oplus x_{6} \oplus x_{5} \oplus x_{3}},&{}{19}&{}\mathtt {x_{4} = x_{4} \oplus x_{2} \oplus x_{0}},\\ {6}&{}\mathtt {x_{5} = x_{6} \oplus x_{5} \oplus x_{1}},&{}{13}&{}\mathtt {x_{7} = x_{7} \oplus x_{2} \oplus x_{0}},&{}{20}&{}\mathtt {a_3 = a_3 \oplus x_{4}}.\\ {7}&{}\mathtt {a_4 = a_4 \oplus x_{0}\cdot x_{2}},&{}{14}&{}\mathtt {a_0 = a_0 \oplus x_{7}},&{}&{}\\ \end{array} \end{aligned}$$

1.2 A.2 The reversible circuit of \(H_2\) with Toffoli depth 6

$$\begin{aligned} \begin{array}{lll} {1}&{} \mathtt {a_1 = a_1 \oplus a_0 \cdot a_2},&{}{\mathtt {\#Toffoli~depth~1}}\\ {2}&{} \mathtt {a_0 = a_0 \oplus a_1},&{}\\ {3}&{} \mathtt {a_2 = a_2 \oplus a_0 \cdot a_3},&{}{\mathtt {\#Toffoli~depth~2}}\\ {4}&{} \mathtt {a_0 = a_0 \oplus a_1 \cdot a_2},&{}{\mathtt {\#Toffoli~depth~3}}\\ {5}&{} \mathtt {a_1 = a_1 \oplus a_0}~(t_{33}),&{}\\ {6}&{} \mathtt {a_2 = a_2 \oplus a_3}~(t_{41}),&{}\\ {7}&{} \mathtt {a_3 = a_3 \oplus a_0 \cdot a_2},&{}{\mathtt {\#Toffoli~depth~4}}\\ {8}&{} \mathtt {a_4 = a_4 \oplus a_2 \cdot a_1},&{}{\mathtt {\#Toffoli~depth~5}}\\ {9}&{} \mathtt {a_0 = a_0 \oplus a_4 \cdot a_3}~(t_{44}),&{}{\mathtt {\#Toffoli~depth~6}}\\ {10}&{} \mathtt {a_3 = a_3 \oplus a_2}~(t_{37}).&{}\\ \end{array} \end{aligned}$$

1.3 A.3 The reversible circuit of \(H_2\) with Toffoli depth 5

$$\begin{aligned} \begin{array}{lll} {1}&{}\mathtt {a_1 = a_1 \oplus a_0 \cdot a_2},&{}{\mathtt {\#Toffoli~depth~1}}\\ {2}&{}\mathtt {a_0 = a_0 \oplus a_1},&{}\\ {3}&{}\mathtt {a_2 = a_2 \oplus a_0 \cdot a_3},&{}{\mathtt {\#Toffoli~depth~2}}\\ {4}&{}\mathtt {a_0 = a_0 \oplus a_1 \cdot a_2},&{}{\mathtt {\#Toffoli~depth~3}}\\ {5}&{}\mathtt {a_1 = a_1 \oplus a_0}~(t_{33}),&{}\\ {6}&{}\mathtt {a_2 = a_2 \oplus a_3}~(t_{41}),\\ {7}&{}\mathtt {a_5 = a_5 \oplus a_2},&{}\\ {8}&{}\mathtt {a_3 = a_3 \oplus a_0 \cdot a_5},&{}{\mathtt {\#Toffoli~depth~4}}\\ {9}&{}\mathtt {a_4 = a_4 \oplus a_2 \cdot a_1},&{}{\mathtt {\#Toffoli~depth~4}}\\ {10}&{}\mathtt {a_0 = a_0 \oplus a_4 \cdot a_3}~(t_{44}),&{}{\mathtt {\#Toffoli~depth~5}}\\ {11}&{}\mathtt {a_3 = a_3 \oplus a_2}~(t_{37}).\\ \end{array} \end{aligned}$$

1.4 A.4 The reversible circuit of \(H_3\)

Appendix B: Binary matrix corresponds to L

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lin, D., Xiang, Z., Xu, R. et al. Quantum circuit implementations of SM4 block cipher based on different gate sets. Quantum Inf Process 22, 282 (2023). https://doi.org/10.1007/s11128-023-04002-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11128-023-04002-4

Keywords

Search

Navigation