Paper 2017/906
Notes On GGH13 Without The Presence Of Ideals
Martin R. Albrecht, Alex Davidson, Enrique Larraia, and Alice Pellet--Mary
Abstract
We investigate the merits of altering the Garg, Gentry and Halevi (GGH13) graded encoding scheme to remove the presence of the ideal \(\langle g \rangle\). In particular, we show that we can alter the form of encodings so that effectively a new \(g_i\) is used for each source group \(\mathbb{G}_i\), while retaining correctness. This would appear to prevent all known attacks on indistinguishability obfuscation (IO) candidates instantiated using GGH13. However, when analysing security in simplified branching program and obfuscation security models, we present branching program (and thus IO) distinguishing attacks that do not use knowledge of \(\langle g \rangle\). This result opens a counterpoint with the work of Halevi (EPRINT 2015) which stated that the core computational hardness problem underpinning GGH13 is computing a basis of this ideal. Our attempts seem to suggest that there is a structural vulnerability in the way that GGH13 encodings are constructed that lies deeper than the presence of \(\langle g \rangle\).
Note: Added extra attack from Alice Pellet--Mary and include as author
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Major revision. IMACC 2017
- Keywords
- multilinear mapsGGH13annihilation attacksindistinguishability obfuscationbranching programs
- Contact author(s)
- alex davidson 2014 @ rhul ac uk
- History
- 2017-11-24: revised
- 2017-09-24: received
- See all versions
- Short URL
- https://ia.cr/2017/906
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2017/906,
author = {Martin R. Albrecht and Alex Davidson and Enrique Larraia and Alice Pellet--Mary},
title = {Notes On {GGH13} Without The Presence Of Ideals},
howpublished = {Cryptology {ePrint} Archive, Paper 2017/906},
year = {2017},
url = {https://eprint.iacr.org/2017/906}
}
