A Distinguisher-Based Attack of a Homomorphic Encryption Scheme Relying on Reed-Solomon Codes

Abstract

Bogdanov and Lee suggested a homomorphic public-key encryption scheme based on error correcting codes. The underlying public code is a modified Reed-Solomon code obtained from inserting a zero submatrix in the Vandermonde generating matrix defining it. The columns that define this submatrix are kept secret and form a set \(L\). We give here a distinguisher that detects if one or several columns belong to \(L\) or not. This distinguisher is obtained by considering the code generated by component-wise products of codewords of the public code (the so called "square code"). This operation is applied to punctured versions of this square code obtained by picking a subset \(I\) of the whole set of columns. It turns out that the dimension of the punctured square code is directly related to the cardinality of the intersection of \(I\) with \(L\). This allows an attack which recovers the full set \(L\) and which can then decrypt any ciphertext.