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 format(s): PDF | BibTeX Citation
Version: 20120330:134808 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]