### Abstract

The GGH Graded Encoding Scheme[9], based on ideal lattices, is the first plausible approximation to a cryptographic multilinear map. Unfortunately, using the security analysis in[9], the scheme requires very large parameters to provide security for its underlying "encoding re-randomization" process. Our main contributions are to formalize, simplify and improve the efficiency and the security analysis of the re-randomization process in the GGH construction. This results in a new construction that we call GGHLite. In particular, we first lower the size of a standard deviation parameter of the re-randomization process of[9] from exponential to polynomial in the security parameter. This first improvement is obtained via a finer security analysis of the "drowning" step of re-randomization, in which we apply the Rényi divergence instead of the conventional statistical distance as a measure of distance between distributions. Our second improvement is to reduce the number of randomizers needed from Ω(n log n) to 2, where n is the dimension of the underlying ideal lattices. These two contributions allow us to decrease the bit size of the public parameters from O(λ^{5} log λ) for the GGH scheme to O(λ log^{2}λ) in GGHLite, with respect to the security parameter λ (for a constant multilinearity parameter κ).

Original language | English |
---|---|

Title of host publication | Advances in Cryptology |

Subtitle of host publication | EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings |

Editors | Phong Q. Nguyen, Elisabeth Oswald |

Place of Publication | Heidelberg |

Publisher | Springer, Springer Nature |

Pages | 239-256 |

Number of pages | 18 |

Volume | 8441 LNCS |

ISBN (Electronic) | 9783642552205 |

ISBN (Print) | 9783642552199 |

DOIs | |

Publication status | Published - 2014 |

Event | 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2014 - Copenhagen, Denmark Duration: 11 May 2014 → 15 May 2014 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 8441 LNCS |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Other

Other | 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2014 |
---|---|

Country | Denmark |

City | Copenhagen |

Period | 11/05/14 → 15/05/14 |

## Fingerprint Dive into the research topics of 'GGHLite: more efficient multilinear maps from ideal lattices'. Together they form a unique fingerprint.

## Cite this

*Advances in Cryptology: EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings*(Vol. 8441 LNCS, pp. 239-256). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8441 LNCS). Heidelberg: Springer, Springer Nature. https://doi.org/10.1007/978-3-642-55220-5_14