Cryptanalysis of GGH Map.

Abstract

Abstract. Multilinear map is a novel primitive which has many cryp-tographic applications, and GGH map is a major candidate of K-linear maps for K> 2. GGH map has two classes of applications, which are applications with public tools for encoding and with hidden tools for en-coding. In this paper, we show that applications of GGH map with public tools for encoding are not secure, and that one application of GGH map with hidden tools for encoding is not secure. On the basis of weak-DL attack presented by the authors themselves, we present several efficient attacks on GGH map, aiming at multipartite key exchange (MKE) and the instance of witness encryption (WE) based on the hardness of 3-exact cover (3XC) problem. First, we use special modular operations, which we call modified encoding/zero-testing to drastically reduce the noise. Such reduction is enough to break MKE. Moreover, such reduction negates K-GMDDH assumption, which is a basic security assumption. The pro-cedure involves mostly simple algebraic manipulations, and rarely needs