Cryptanalysis Of GGH Map And Its Applications

Mutilinear maps is a novel primitive,which has too numerous cryptographic applications and new services to name.GGH(derived from the initial letters of Garg,Gentry and Halevi)map is the first and the most important candidate construction of multilinear maps,whose appearance marked the beginning of the research fever on multilinear maps.A large number of excellent research results,including various advanced cryptographic applications and new candidate schemes,have ever since come to the fore.Though Garg et al.fully discussed GGH map's security by doing a great deal of cryptographic analysis and pointed out that GGH map is secure against almost all lattice attacks,due to the lack of security proof,there is a somewhat scepticism about the security of GGH map and its all kinds of applications.This dissertation focus mainly on the security aspect of the GGH map and its manifold applications(with public/hidden tool for encoding).By introducing several innovative techniques,such as the modified encoding/zerotesting,weakening a specific NPC problem and constructing alternative encoding tools,this work obtains the following main results.1.Breaking the the multipartite non-interactive key exchange protocol from GGH map(Eurocrypt 2013): above all,by using the weak discrete logarithm attack,an “equivalent secret” of a use's secret can be obtained from the public information;then,by means of our first new technique,called modified encoding/zerotesting,the noise term in the “equivalent secret” can be reduced to small enough,thus getting the shared secret among users.Due to the fact that the GGH analogue of the graded decisional Diffie–Hellman assumption serves as the security foundation of the protocol,our attack makes the assumption untenable as well.2.Breaking the GGH analogue of the graded computational Diffie–Hellman assumption(Eurocrypt 2013)as well as two representative cryptographic applications from GGH map–the identity-based aggregate signature scheme(Crypto 2013)and attribute-based encryption scheme(Crypto 2013): by improving the first new technique,a high level encoding can be reduced to a level-1 encoding,which means that the “division”operation can be performed in the graded encoding system,thus destroying the “not division but multiplication” algebraic structure.This permission of the “division” operation makes it successful for us to break directly the GGH analogue of the graded computational Diffie–Hellman assumption.Moreover,for the identity-based aggregate signature scheme from GGH map,we can efficiently figure out any user's private key given only the public keys,thus to forge a valid signature on any message.As for the attribute-based encryption scheme from GGH map,any user can decrypt arbitrary valid ciphertext,including those he/she has no authority to decrypt,which completely destroys the access control characteristics in the attribute-based encryption.3.Breaking the witness encryption scheme based on GGH map and the exact-3-cover problem(STOC 2013): on the basis of the modified encoding/zero-testing above,by introducing our second new technique,which can weaken the exact-3-cover problem,an NPC problem,to an easy one,called combined exact-3-cover problem,we can break the witness encryption with public tools for encoding;furthermore,on the basis of the two techniques mentioned above,by introducing our third new technique,which is constructing alternative encoding tools,we can break the witness encryption with hidden tools for encoding as well.4.Breaking two kinds of simple revisions of GGH map: these two kinds of revisions,proposed by ourselves,basically cover almost all the simple revisions.By extending our first new technology and a further analysis,the two fixed schemes can be broken as well under the assumption that 2?is polynomially large.Our work is a negation of GGH map and its applications.We claim that: with public tools for encoding,no cryptographic application of GGH map is secure;with hidden tools for encoding,at least one such application is insecure;GGH map with simple revisions can hardly avoid our attack.