IACR News item: 16 February 2016
Jung Hee Cheon, Jinhyuck Jeong, Changmin Lee
ePrint Report
We describe a polynomial time algorithm to solve the Computational Small Polynomial Ratio Problem in current parameter, which is to find a short element of an ideal
<g>\subset Z[X]/\langle X^n+1 \rangle when |g| is smaller than
some constant B ( in Q[X]/\langle X^n+1 \rangle) and a somewhat small multiple of g^{-1} ( in R_q) is given.
In GGH scheme, which is the first candidate of a (approximate) multilinear map, the algorithm, using any encodings, can be directly applied to obtain the any secret elements. Recently, the GGH scheme was known to be insecure by so called zeroizing attack {HJ15}, when an encoding of zero is published. Hence, this work leads to showing that GGH scheme without an encoding of zero is also insecure.
In GGH scheme, which is the first candidate of a (approximate) multilinear map, the algorithm, using any encodings, can be directly applied to obtain the any secret elements. Recently, the GGH scheme was known to be insecure by so called zeroizing attack {HJ15}, when an encoding of zero is published. Hence, this work leads to showing that GGH scheme without an encoding of zero is also insecure.
Additional news items may be found on the IACR news page.