Welcome to the resource topic for 2012/168
Title:
A Distinguisher-Based Attack of a Homomorphic Encryption Scheme Relying on Reed-Solomon Codes
Authors: Valérie Gauthier, Ayoub Otmani, 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.
ePrint: https://eprint.iacr.org/2012/168
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .