Paper 2018/011

Graded Encoding Schemes from Obfuscation

Pooya Farshim, Julia Hesse, Dennis Hofheinz, and Enrique Larraia


We construct a graded encoding scheme (GES), an approximate form of graded multilinear maps. Our construction relies on indistinguishability obfuscation, and a pairing-friendly group in which (a suitable variant of) the strong Diffie--Hellman assumption holds. As a result of this abstract approach, our GES has a number of advantages over previous constructions. Most importantly: a) We can prove that the multilinear decisional Diffie--Hellman (MDDH) assumption holds in our setting, assuming the used ingredients are secure (in a well-defined and standard sense). In particular, and in contrast to previous constructions, our GES does not succumb to so-called ``zeroizing'' attacks. Indeed, our scheme is currently the only GES for which no known cryptanalysis applies. b) Encodings in our GES do not carry any noise. Thus, unlike previous GES constructions, there is no upper bound on the number of operations one can perform with our encodings. Hence, our GES essentially realizes what Garg et al.~(EUROCRYPT 2013) call the ``dream version'' of a GES. Technically, our scheme extends a previous, non-graded approximate multilinear map scheme due to Albrecht et al.~(TCC 2016-A). To introduce a graded structure, we develop a new view of encodings at different levels as polynomials of different degrees.

Available format(s)
Publication info
Published by the IACR in PKC 2018
Multilinear mapsgraded encoding schemesindistinguishability obfuscation
Contact author(s)
julia hesse @ crisp-da de
2018-04-12: revised
2018-01-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Pooya Farshim and Julia Hesse and Dennis Hofheinz and Enrique Larraia},
      title = {Graded Encoding Schemes from Obfuscation},
      howpublished = {Cryptology ePrint Archive, Paper 2018/011},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.