(In)security of concrete instantiation of Lin17’s functional encryption scheme from noisy multilinear maps

Functional encryption (FE) is a novel cryptographic paradigm. In comparison to conventional encryption schemes, FE allows producing secret keys sk_f corresponding to a function f that decrypt encryptions of x to f(x). Recently, Lin proposed FE for arbitrary degree polynomials from the SXDH assumption to an exact multilinear map (CRYPTO’17). However, there is no concrete instantiation of the scheme in the absence of an exact multilinear map. Although Lin’s FE can be instantiated by noisy multilinear maps such as the GGH13, CLT13, and GGH15 schemes, the security of FE instantiated by noisy multilinear maps is unclear. In this paper, we point out the weakness of the Lin’s FE when it is instantiated by well-known candidates of noisy multilinear maps. In other words, we present a polynomial time attack of the FE on each noisy multilinear map. In the proposed method, our attack captures Lin’s FE for arbitrary degree polynomials instantiated by GGH13 and CLT13 and is also applicable to FE for polynomials of degree O(log ₂λ) when instantiated by GGH15 under the current parameters where λ is the security parameter.