The Research And Improvement Of Multi-linear Maps Over Integers

It is a long-standing open problem that extending bilinear elliptic curve pairings to multi-linear maps.In 2003 Boneh and Silverberg showed two in-teresting applications of multi-linear maps [9], namely multipartite Diffie-Hellman and very efficient broadcast encryption; however they were pessimistic about the existence of such maps from the realm of algebraic geometry. Cryp-tographic multi-linear maps have proved their tremendous potential as building blocks for new constructions in last few years. Garg, Gentry and Halevi put forward the first candidate construction (GGH) [16] based on ideal lattices, a second construction over the integers was described by Coron, Lepoint and Ti-bouchi (CLT) [13]. However the CLT scheme was recently broken by Cheon et al.; the attack works by computing the eigenvalues of a diagonalizable matrix over Q derived from the multi-linear map.The definition of the procedures for manipulating encodings what we recall are:Instance generation, Sampling level-zero encoding, Encodings at higher levels, Re-randomization, Adding and Multiplying Encodings, Zero Testing, and Extraction.By using Weil and Tate pairings, Joux [25] constructed the first one-round 3-way secret key exchange protocol. If multi-linear maps existed,Boneh and Silverberg [9] showed how this result could be extended to get a one-round N-way secret key exchange protocol. Our encoding schemes easily support the Boneh-Silverberg construction, with one subtle difference:Since our public parameters hide some secrets (i.e., the elements g, h, z) then we get a one- round N-way secret key exchange protocol in the common reference string model. A one-round N-way key exchange scheme consists of three randomized probabilistic polynomial-time algorithms.But the CLT scheme was recently broken by Cheon et al.; the attack works by computing the eigenvalues of a diagonalizable matrix over Q derived from the multi-linear map. The draft [18] was updated, to propose a candidate immunization against our attack [18] after the attack was published. Another candidate immunization was proposed in [10]. Both immunizations have been showed insecure in [12].Regarding the modifying of programme CLT, an important idea is to re-duce the public disclosure information of parameters. In this paper, we mod-ified the zero-testing parameter of the aforementioned programme, that is to say, give out the general form of zero-testing parameter, to ensure that after the test, when zero-testing parameter shows in public, a matrix equation can-not be constructed as zero-testing parameter, and all the relevant parameters cannot be recovered by zero-testing parameter neither.