Paper 2023/248

Unique-Path Identity Based Encryption With Applications to Strongly Secure Messaging

Paul Rösler, FAU Erlangen-Nürnberg
Daniel Slamanig, Austrian Institute of Technology
Christoph Striecks, Austrian Institute of Technology

Hierarchical Identity Based Encryption (HIBE) is a well studied, versatile tool used in many cryptographic protocols. Yet, since the performance of all known HIBE constructions is broadly considered prohibitive, some real-world applications avoid relying on HIBE at the expense of security. A prominent example for this is secure messaging: Strongly secure messaging protocols are provably equivalent to Key-Updatable Key Encapsulation Mechanisms (KU-KEMs; Balli et al., Asiacrypt 2020); so far, all KU-KEM constructions rely on adaptive unbounded-depth HIBE (Poettering and Rösler, Jaeger and Stepanovs, both CRYPTO 2018). By weakening security requirements for better efficiency, many messaging protocols dispense with using HIBE. In this work, we aim to gain better efficiency without sacrificing security. For this, we observe that applications like messaging only need a restricted variant of HIBE for strong security. This variant, that we call Unique-Path Identity Based Encryption (UPIBE), restricts HIBE by requiring that each secret key can delegate at most one subordinate secret key. However, in contrast to fixed secret key delegation in Forward-Secure Public Key Encryption, the delegation in UPIBE, as in HIBE, is uniquely determined by variable identity strings from an exponentially large space. We investigate this mild but surprisingly effective restriction and show that it offers substantial complexity and performance advantages. More concretely, we generically build bounded-depth UPIBE from only bounded-collusion IBE in the standard model; and we generically build adaptive unbounded-depth UPIBE from only selective bounded-depth HIBE in the random oracle model. These results significantly extend the range of underlying assumptions and efficient instantiations. We conclude with a rigorous performance evaluation of our UPIBE design. Beyond solving challenging open problems by reducing complexity and improving efficiency of KU-KEM and strongly secure messaging protocols, we offer a new definitional perspective on the bounded-collusion setting.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
UPIBEHIBEIBEMessagingKU-KEMUnique PathIdentity Based EncryptionKey-Updatable KEM
Contact author(s)
paul roesler @ fau de
daniel slamanig @ ait ac at
christoph striecks @ ait ac at
2023-02-21: approved
2023-02-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Paul Rösler and Daniel Slamanig and Christoph Striecks},
      title = {Unique-Path Identity Based Encryption With Applications to Strongly Secure Messaging},
      howpublished = {Cryptology ePrint Archive, Paper 2023/248},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.