Abstract
We investigate the merits of altering the Garg, Gentry and Halevi (GGH13) graded encoding scheme to remove the presence of the ideal ⟨g⟩. In particular, we show that we can alter the form of encodings so that effectively a new gi is used for each source group 픾i, while retaining correctness. This would appear to prevent all known attacks on IO candidates instantiated using GGH13. However, when analysing security in a simplified branching program model, we present an IO distinguishing attack that does not use ⟨g⟩. 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 ⟨g⟩. Tangentially, we observe that our attack is prevented when considering all the added machinery of IO candidates.
Original language | English |
---|---|
Pages | 135-158 |
Number of pages | 24 |
DOIs | |
Publication status | Published - 2017 |
Event | IMA International Conference on Cryptography and Coding 2017 - St. Catherine's College, University of Oxford, Oxford, United Kingdom Duration: 12 Dec 2017 → 14 Dec 2017 https://www.qub.ac.uk/sites/CSIT/IMACC2017/ |
Conference
Conference | IMA International Conference on Cryptography and Coding 2017 |
---|---|
Abbreviated title | IMACC2017 |
Country/Territory | United Kingdom |
City | Oxford |
Period | 12/12/17 → 14/12/17 |
Internet address |
Keywords
- multilinear maps
- GGH13
- annihilation attacks
- Indistinguishability obfuscation
- branching programs