Paper 2012/168

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

Valérie Gauthier, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
cryptanalysishomomorphic encryptiondistinguisherReed-Solomon codes
Contact author(s)
jean-pierre tillich @ inria fr
History
2012-03-30: received
Short URL
https://ia.cr/2012/168
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/168,
      author = {Valérie Gauthier and Ayoub Otmani and Jean-Pierre Tillich},
      title = {A Distinguisher-Based Attack of a Homomorphic Encryption   Scheme Relying on Reed-Solomon Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2012/168},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/168}},
      url = {https://eprint.iacr.org/2012/168}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.