Cryptology ePrint Archive: Report 2016/200

An Alternative View of the Graph-Induced Multilinear Maps

Yilei Chen

Abstract: In this paper, we view multilinear maps through the lens of ``homomorphic obfuscation". In specific, we show how to homomorphically obfuscate the kernel-test and affine subspace-test functionalities of high dimensional matrices. Namely, the evaluator is able to perform additions and multiplications over the obfuscated matrices, and test subspace memberships on the resulting code. The homomorphic operations are constrained by the prescribed data structure, e.g. a tree or a graph, where the matrices are stored. The security properties of all the constructions are based on the hardness of Learning with errors problem (LWE). The technical heart is to ``control" the ``chain reactions'' over a sequence of LWE instances.

Viewing the homomorphic obfuscation scheme from a different angle, it coincides with the graph-induced multilinear maps proposed by Gentry, Gorbunov and Halevi (GGH15). Our proof technique recognizes several ``safe modes" of GGH15 that are not known before, including a simple special case: if the graph is acyclic and the matrices are sampled independently from binary or error distributions, then the encodings of the matrices are pseudorandom.

Category / Keywords:

Date: received 24 Feb 2016, last revised 1 Mar 2016

Contact author: chenyl at bu edu

Available format(s): PDF | BibTeX Citation

Version: 20160301:125529 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]