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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2016/200}},
      url = {https://eprint.iacr.org/2016/200}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.