International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 06 April 2015

Yupu Hu, Huiwen Jia
ePrint Report ePrint Report
Multilinear map is a novel primitive which has many cryptographic applications, and GGH map is a major candidate of multilinear maps. GGH map has two classes of applications, which are respectively applications for public tools of encoding and hidden tools of encoding. In this paper we show that applications of GGH map for public tools of encoding are not secure. We present an efficient attack on GGH map, aiming at multi-party key exchange (MPKE) and the instance of witness encryption (WE) based on the hardness of 3-exact cover problem. First, for the secret of each user, we obtain an equivalent secret, which is the sum of original secret and a noise. The noise is an element of the specific principal ideal, but its size is not small. To do so, we use weak-DL attack presented by authors of GGH map. Second, we use special modular operations, which we call modified encoding/decoding, to filter the decoded noise much smaller. Such filtering is enough to break MPKE. Moreover, such filtering negates K-GMDDH assumption, which is the security basis of an ABE. The procedure almost breaks away from those lattice attacks and looks like an ordinary algebra. The key point is our special tools for modular operations. Finally, we break the instance of WE based on the hardness of 3-exact cover problem. To do so, we not only use modified encoding/decoding, but also (1) introduce and solve \"combined 3-exact cover problem\", which is a problem never hard to be solved; and (2) compute Hermite normal form of the specific principal ideal. The attack on the instance of WE is under an assumption, which seems at least nonnegligible.

Expand

Additional news items may be found on the IACR news page.