An Alternative View of the Graph-Induced Multilinear Maps

Yilei Chen

Paper 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.

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Contact author(s): chenyl @ bu edu
History: 2016-03-01: last of 3 revisions; 2016-02-25: received; See all versions
Short URL: https://ia.cr/2016/200
License: CC BY

BibTeX

@misc{cryptoeprint:2016/200,
      author = {Yilei Chen},
      title = {An Alternative View of the Graph-Induced Multilinear Maps},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/200},
      year = {2016},
      url = {https://eprint.iacr.org/2016/200}
}