On the security of subspace subcodes of Reed-Solomon codes for public key encryption

2020/09/12 by Couvreur, Alain, Lequesne, Matthieu · 1 citation
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.2009.05826

Abstract

This article discusses the security of McEliece-like encryption schemes using subspace subcodes of Reed-Solomon codes, i.e. subcodes of Reed-Solomon codes over \mathbbF_q^m whose entries lie in a fixed collection of \mathbbF_q-subspaces of \mathbbF_q^m. These codes appear to be a natural generalisation of Goppa and alternant codes and provide a broader flexibility in designing code based encryption schemes. For the security analysis, we introduce a new operation on codes called the twisted product which yields a polynomial time distinguisher on such subspace subcodes as soon as the chosen \mathbbF_q-subspaces have dimension larger than m/2. From this distinguisher, we build an efficient attack which in particular breaks some parameters of a recent proposal due to Khathuria, Rosenthal and Weger.

Cited by

• Quasi-twisted codes: decoding and applications in code-based cryptography

Related

• Generalized subspace subcodes with application in cryptology
• A Distinguisher-Based Attack on a Variant of McEliece's Cryptosystem Based on Reed-Solomon Codes
• Distinguisher-Based Attacks on Public-Key Cryptosystems Using\n Reed-Solomon Codes
• On the structure of the Schur squares of Twisted Generalized Reed-Solomon codes and application to cryptanalysis
• A Distinguisher-Based Attack of a Homomorphic Encryption Scheme Relying on Reed-Solomon Codes