Paper 2015/866

Graded Encoding, Variations on a Scheme

Shai Halevi


In this note we provide a more-or-less unified framework to talk about the functionality and security of graded encoding schemes, describe some variations of recent schemes, and discuss their security. In particular we describe schemes that combine elements from both the GGH13 scheme of Garg, Gentry and Halevi (EUROCRYPT 2013) and the GGH15 scheme of Gentry, Gorbunov and Halevi (TCC 2015). On one hand, we show how to use techniques from GGH13 in the GGH15 construction to enable encoding of arbitrary plaintext elements (as opposed to only small ones) and to introduce "levels/subsets" (e.g., as needed to implement straddling sets). On the other hand, we show how to modify the GGH13 scheme to support graph-induced constraints (either instead of, or in addition to, the levels from GGH13). Turning to security, we describe zeroizing attacks on the GGH15 scheme, similar to those described by Cheon et al. (EUROCRYPT 2015) and Coron et al. (CRYPTO 2015) on the CLT13 and GGH13 constructions. As far as we know, however, these attacks to not break the GGH15 multi-partite key-agreement protocol. We also describe a new multi-partite key-agreement protocol using the GGH13 scheme, which also seems to resist known attacks. That protocol suggests a relatively simple hardness assumption for the GGH13 scheme, that we put forward as a target for cryptanalysis.

Note: Update (Oct 2015): The key-agreement protocols that are described (or alluded to) in sections 6,7 are broken. Thanks to Yupu Hu and Jean-Sébastien Coron for pointing out to me various attacks, these attacks (and their extensions) will be described in separate reports in the coming weeks/months.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Cryptography Multilinear MapsGraded EncodingMulti-partite Key-AgreementZeroizing Attacks
Contact author(s)
shaih @ alum mit edu
2015-10-30: last of 3 revisions
2015-09-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shai Halevi},
      title = {Graded Encoding, Variations on a Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2015/866},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.