Paper 2021/222

Quantum-safe HIBE: does it cost a Latte?

Raymond K. Zhao, Sarah McCarthy, Ron Steinfeld, Amin Sakzad, and Máire O’Neill

Abstract

The UK government is considering advanced primitives such as identity-based encryption (IBE) for adoption as they transition their public-safety communications network from TETRA to an LTE-based service. However, the current LTE standard relies on elliptic curve based IBE, which will be vulnerable to quantum computing attacks, expected within the next 20--30 years. Lattices can provide quantum-safe alternatives for IBE. These schemes have shown promising results in terms of practicality. To date, several IBE schemes over lattices have been proposed but there has been little in the way of practical evaluation. This paper provides the first complete C implementation and benchmarking of Latte, a promising Hierarchical IBE scheme proposed by the United Kingdom (UK) National Cyber Security Centre (NCSC) in 2017 and endorsed by European Telecommunications Standards Institute (ETSI). We propose optimisations for the KeyGen, Delegate, Extract and Gaussian sampling components of Latte thereby increasing attack costs, reducing decryption key lengths by 2x--3x, ciphertext sizes by up to 33% and improving speed. In addition, we conduct a precision analysis, bounding the Rényi divergence of the Gaussian sampling procedures from the ideal distribution, in corroboration of our claimed security levels. Our resulting implementation of the Delegate function takes 0.4 seconds at 80-bit security level on a desktop machine at 4.2GHz, significantly faster than the order of minutes estimated in the ETSI technical report. Furthermore, our optimised Latte Encrypt/Decrypt implementation reaches speeds up to 5.8x faster than the ETSI implementation.