Cryptology ePrint Archive: Report 2012/168

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

Val\'erie Gauthier and Ayoub Otmani and Jean-Pierre Tillich

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.

Category / Keywords: public-key cryptography / cryptanalysis, homomorphic encryption, distinguisher, Reed-Solomon codes

Date: received 29 Mar 2012

Contact author: jean-pierre tillich at inria fr

Available formats: PDF | BibTeX Citation

Version: 20120330:134808 (All versions of this report)

Discussion forum: Show discussion | Start new discussion