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

Persichetti, Edoardo; Randrianarisoa, Tovohery Hajatiana; Santini, Paolo

doi:10.2478/tmmp-2022-0018

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

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

Abstract

Paradigm

My account