IACR News item: 02 January 2015
Moon Sung Lee
ePrint Reportwhich is claimed to be the most efficient among the additive homomorphic encryption schemes.
The security is proved based on the hardness of a new problem, the (decisional) co-approximate common divisor problem.
In this paper,
we cryptanalyze the scheme and investigate the hardness of an aforementioned problem.
Our first result
shows that
Cheon et al.\'s scheme is insecure for the range of parameters considered in the original paper~\\cite{CLSCCS14}.
Experiments show that the message can be recovered in seconds for the proposed parameters.
We also analyze the condition of the parameters to thwart the proposed attack.
As a second result,
we show that the co-approximate common divisor problem
is easy for the similar range of parameters,
in condition that the modulus is known and is a product of two primes.
In our estimate, to thwart the proposed attack,
the parameters should be enlarged many times.
Apart from the scheme,
the co-approximate common divisor problem itself is interestingly related
to the well-known hard problem, an approximate common divisor problem.
And further investigation on this relationship would be desirable.
Additional news items may be found on the IACR news page.