IACR News item: 13 October 2015
Jinsu Kim, Sungwook Kim, Jae Hong Seo
ePrint ReportIn this paper, we propose a new integer-based multilinear map that has several advantages over previous schemes. In terms of security, we expect that our construction is resistant to the zeroizing attack. In terms of efficiency, the bit-size of an encoding grows sublinearly with $\\kappa$, more precisely $O((\\log_2\\kappa)^2)$.
To this end, we essentially utilize a technique of the multiplication procedure in {\\em scale-invariant} fully homomorphic encryption (FHE), which enables to achieve sublinear complexity in terms of multilinearity and at the same time security against the zeroizing attacks (EUROCRYPT 2015, IACR-Eprint 2015/934, IACR-Eprint 2015/941), which totally broke Coron, Lepoint, and Tibouchi\'s integer-based construction (CRYPTO 2013, CRYPTO2015). We find that the technique of scale-invariant FHE is not very well harmonized with previous approaches of making GES from (non-scale-invariant) FHE. Therefore, we first devise a new approach for approximate multilinear maps, called {\\em Ring Encoding System (RES)}, and prove that a multilinear map built via RES is generically secure. Next, we propose a new efficient scale-invariant FHE with special properties, and then construct a candidate RES based on a newly proposed scale-invariant FHE.
It is worth noting that, contrary to the CLT multilinear map (CRYPTO 2015), multiplication procedure in our construction does not add hidden constants generated by ladders of zero encodings, but mixes randoms in encodings in non-linear ways without using ladders of zero encodings. This feature is obtained by using the scale-invariant FHE and essential to prevent the Cheon et al.\'s zeroizing attack.
Additional news items may be found on the IACR news page.