Cryptology ePrint Archive: Report 2015/866

Graded Encoding, Variations on a Scheme

Shai Halevi

Abstract: 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.

Category / Keywords: public-key cryptography / Cryptography Multilinear Maps, Graded Encoding, Multi-partite Key-Agreement, Zeroizing Attacks

Date: received 7 Sep 2015, last revised 9 Sep 2015

Contact author: shaih at alum mit edu

Available format(s): PDF | BibTeX Citation

Note: Fixed the subset structure in the key-agreement protocol

Version: 20150909:221338 (All versions of this report)

Short URL: ia.cr/2015/866

Discussion forum: Show discussion | Start new discussion