An Attack on a Non-Interactive Key Exchange from Code Equivalence

Edoardo Persichetti; Tovohery Hajatiana Randrianarisoa; Paolo Santini

doi:10.2478/tmmp-2022-0018

.blurhash-client-img { display: none !important; }

An Attack on a Non-Interactive Key Exchange from Code Equivalence

Tatra Mountains Mathematical Publications

Volume 82 (2022): Issue 2 (December 2022)

By: Edoardo Persichetti, Tovohery Hajatiana Randrianarisoa and Paolo Santini

Open Access

|Feb 2023

Abstract

A recent paper by Zhang and Zhang claims to construct the first code-based non-interactive key exchange protocol, using a modified version of the Code Equivalence Problem. In this paper we explain why this approach is flawed. Namely, we describe an attack which involves only linear algebra and completely breaks the protocol with overwhelming probability. A simple Magma script confirms our results.

References

[1] 2017. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography
Search in Google Scholar Back to article
[2] ALBRECHT, M. R. — BERNSTEIN, D. J. — CHOU, T.—CID, C. — GILCHER, J. — —LANGE, T. — MARAM, V. — VON MAURICH, I. — MISOCZKI, R.—NIEDERHAGEN, R. — PATERSON, K. G. — PERSICHETTI, E. — PETERS, C. — SCHWABE, P.— —SENDRIER, N.—SZEFER, J.—TJHAI, C. J.—TOMLINSON, M.—WANG, W.: Classic McEliece: conservative code-based cryptography, NIST Post-Quantum Standardization, 3rd Round, 2021.
Search in Google Scholar Back to article
[3] ARAGON, N.—BARRETO, P.S.L.M.—BETTAIEB, S.—BIDOUX, L.—BLAZY, O.– DENEUVILLE J. C. — GABORIT, P. — GUERON, S. — GÜNEYSU, T. — MELCHOR, C. A. — MISOCZKI, R. — PERSICHETTI, E. — SENDRIER, N. — TILLICH, J. - P. — VASSEUR, V. — ZÉMOR, G.: BIKE: Bit Flipping Key Encapsulation, NIST Post--Quantum Standardization, 3rd Round, 2021.
Search in Google Scholar Back to article
[4] BARENGHI, A.—BIASSE, J.-F.—PERSICHETTI, E.—SANTINI, P.: LESS-FM: Fine--tuning signatures from the code equivalence problem. In: International Conference on Post-Quantum Cryptography, (Jung Hee Cheon, Jean-Pierre Tillich, eds.) Lecture Notes in Comput. Sci. vol. 12841, Springer, Cham, Switzerland, 2021, pp. 23–43.10.1007/978-3-030-81293-5_2
Search in Google Scholar Back to article
[5] BARENGHI, A.—BIASSE, J.-F.—PERSICHETTI, E.—SANTINI, P.: On the computational hardness of the code equivalence problem in cryptography, Adv. Math. Commun. (2022), Cryptology ePrint Archive. https://eprint.iacr.org/2022/967
Search in Google Scholar Back to article
[6] BARENGHI, A.—BIASSE, J.-F.—NGO, T.—PERSICHETTI, E.—SANTINI, P.: Advanced signature functionalities from the code equivalence problem, Int. J. Comput. Math.: Computer Systems Theory 7 (2022), no. 2, 102–128.10.1080/23799927.2022.2048206
Search in Google Scholar Back to article
[7] BEULLENS, W.: Not Enough LESS: An proved algorithm for solving code equivalence problems over 𝔽_q. In: Selected Areas in Cryptography: 27th International Conference, Halifax, NS, Canada (Virtual Event), October 21–23, 2020, Revised Selected Papers. Springer, Cham, 2021, pp. 387–403.10.1007/978-3-030-81652-0_15
Search in Google Scholar Back to article
[8] BIASSE, J.-F.—MICHELI, G.—PERSICHETTI, E.—SANTINI, P.: LESS is More: Code-based Signatures Without Syndromes. Progress in cryptology—AFRICACRYPT 2020, (A. Nitaj, A. Youssef, eds.), Lecture Notes in Comput. Sci. Vol. 12174, Springer, Cham, Switzerland, 2020, pp. 45–65.10.1007/978-3-030-51938-4_3
Search in Google Scholar Back to article
[9] CASTRYCK, W.—DECRU, T.: An efficient key recovery attack on SIDH (preliminary version), Cryptology ePrint Archive, 2022.10.1007/978-3-031-30589-4_15
Search in Google Scholar Back to article
[10] CASTRYCK, W.—LANGE, T.—MARTINDALE, C.—PANNY, L.—RENES, J.: CSIDH: an efficient post-quantum commutative group action, In: ASIACRYPT ’18, Lecture Notes in Comput. Sci. Vol. 11274, Springer, Cham, Switzerland, 2018, pp. 395–427.10.1007/978-3-030-03332-3_15
Search in Google Scholar Back to article
[11] JAO, D.—FEO, L. D.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: International Workshop on Post-Quantum Cryptography, Lecture Notes in Comput. Sci. Vol. 7071, Springer, Switzerland, Heidelberg, 2011, pp. 19–34.10.1007/978-3-642-25405-5_2
Search in Google Scholar Back to article
[12] LEON, J.: Computing automorphism groups of error-correcting codes, IEEE Trans. Inform. Theory 28 (1982), no. 3, 496–511.10.1109/TIT.1982.1056498
Search in Google Scholar Back to article
[13] SAMARDJISKA, S.—SANTINI, P.—PERSICHETTI, E.—BANEGAS, G.: A reaction attack against cryptosystems based on LRPC codes. In: International Conference on Cryptology and Information Security in Latin America, Progress in cryptology—LATINCRYPT 2019. Lecture Notes in Comput. Sci. Vol. 11774, Springer, Cham, 2019, pp. 197–216.10.1007/978-3-030-30530-7_10
Search in Google Scholar Back to article
[14] SENDRIER, N.: Finding the permutation between equivalent linear codes: The support splitting algorithm, IEEE Trans. Inform. Theory 46 (2000), no. 4, 1193–1203.10.1109/18.850662
Search in Google Scholar Back to article
[15] ZHANG, Z.—ZHANG, F.: Code-based non-interactive key exchange can be made. Cryptology ePrint Archive, Report 2021/1619, 2021. https://ia.cr/2021/1619.
Search in Google Scholar Back to article

Articles in this issue

DOI: https://doi.org/10.2478/tmmp-2022-0018 | Journal eISSN: 1338-9750 | Journal ISSN: 1210-3195

Journal RSS Feed

Language: English

Page range: 53 - 64

Submitted on: Jul 19, 2022

Published on: Feb 15, 2023

Published by: Slovak Academy of Sciences, Mathematical Institute

In partnership with: Paradigm Publishing Services

Publication frequency: 1 issue per year

Keywords:

Related subjects:

© 2023 Edoardo Persichetti, Tovohery Hajatiana Randrianarisoa, Paolo Santini, published by Slovak Academy of Sciences, Mathematical Institute
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Volume 82 (2022): Issue 2 (December 2022)