Cryptology ePrint Archive: Report 2021/499

Optimizing Registration Based Encryption

Kelong Cong and Karim Eldefrawy and Nigel P. Smart

Abstract: The recent work of Garg et al. from TCC'18 introduced the notion of registration based encryption (RBE). The principal motivation behind RBE is to remove the key escrow problem of identity based encryption (IBE), where the IBE authority is trusted to generate private keys for all the users in the system. Although RBE has excellent asymptotic properties, it is currently impractical. In our estimate, ciphertext size would be about 11 terabytes in an RBE deployment supporting 2 billion users. Motivated by this observation, our work attempts to reduce the concrete communication and computation cost of the current state-of-the-art construction. Our contribution is two-fold. First, we replace Merkle trees with crit-bit trees, a form of PATRICIA trie, without relaxing any of the original RBE efficiency requirements introduced by Garg et al. This change reduces the ciphertext size by 15% and the computation cost of decryption by 30%. Second, we observe that increasing RBE's public parameters by a few hundred kilobytes could reduce the ciphertext size by an additional 50%. Overall, our work decreases the ciphertext size by 57.5%.

Category / Keywords: public-key cryptography /

Date: received 18 Apr 2021

Contact author: kelong cong at esat kuleuven be, karim eldefrawy@sri com, nigel smart@kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20210419:061143 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]