International Association for Cryptologic Research

International Association
for Cryptologic Research


David Derler


Bloom Filter Encryption and Applications to Efficient Forward-Secret 0-RTT Key Exchange
Forward secrecy is considered an essential design goal of modern key establishment (KE) protocols, such as TLS 1.3, for example. Furthermore, efficiency considerations such as zero round-trip time (0-RTT), where a client is able to send cryptographically protected payload data along with the very first KE message, are motivated by the practical demand for secure low-latency communication. For a long time, it was unclear whether protocols that simultaneously achieve 0-RTT and full forward secrecy exist. Only recently, the first forward-secret 0-RTT protocol was described by Günther et al. ( Eurocrypt , 2017). It is based on puncturable encryption. Forward secrecy is achieved by “puncturing” the secret key after each decryption operation, such that a given ciphertext can only be decrypted once (cf. also Green and Miers, S&P 2015). Unfortunately, their scheme is completely impractical, since one puncturing operation takes between 30 s and several minutes for reasonable security and deployment parameters, such that this solution is only a first feasibility result, but not efficient enough to be deployed in practice. In this paper, we introduce a new primitive that we term Bloom filter encryption (BFE), which is derived from the probabilistic Bloom filter data structure. We describe different constructions of BFE schemes and show how these yield new puncturable encryption mechanisms with extremely efficient puncturing. Most importantly, a puncturing operation only involves a small number of very efficient computations, plus the deletion of certain parts of the secret key, which outperforms previous constructions by orders of magnitude. This gives rise to the first forward-secret 0-RTT protocols that are efficient enough to be deployed in practice. We believe that BFE will find applications beyond forward-secret 0-RTT protocols.
Bringing Order to Chaos: The Case of Collision-Resistant Chameleon-Hashes 📺
Chameleon-hash functions, introduced by Krawczyk and Rabin at NDSS 2000, are trapdoor collision-resistant hash-functions parametrized by a public key. If the corresponding secret key is known, arbitrary collisions for the hash function can be efficiently found. Chameleon-hash functions have prominent applications in the design of cryptographic primitives, such as lifting non-adaptively secure signatures to adaptively secure ones. Recently, this primitive also received a lot of attention as a building block in more complex cryptographic applications ranging from editable blockchains to advanced signature and encryption schemes. We observe that in latter applications various different notions of collision-resistance are used, and it is not always clear if the respective notion does really cover what seems intuitively required by the application. Therefore, we revisit existing collision-resistance notions in the literature, study their relations, and—using the example of the recent redactable blockchain proposals—discuss which practical impact different notions of collision-resistance might have. Moreover, we provide a stronger, and arguably more desirable, notion of collision-resistance than what is known from the literature. Finally, we present a surprisingly simple and efficient black-box construction of chameleon-hash functions achieving this strong notion.
Revisiting Proxy Re-encryption: Forward Secrecy, Improved Security, and Applications
We revisit the notion of proxy re-encryption ($$\mathsf {PRE}$$PRE), an enhanced public-key encryption primitive envisioned by Blaze et al. (Eurocrypt’98) and formalized by Ateniese et al. (NDSS’05) for delegating decryption rights from a delegator to a delegatee using a semi-trusted proxy. $$\mathsf {PRE}$$PRE notably allows to craft re-encryption keys in order to equip the proxy with the power of transforming ciphertexts under a delegator’s public key to ciphertexts under a delegatee’s public key, while not learning anything about the underlying plaintexts.We study an attractive cryptographic property for $$\mathsf {PRE}$$PRE, namely that of forward secrecy. In our forward-secret $$\mathsf {PRE}$$PRE (fs-$$\mathsf {PRE}$$PRE) definition, the proxy periodically evolves the re-encryption keys and permanently erases old versions while he delegator’s public key is kept constant. As a consequence, ciphertexts for old periods are no longer re-encryptable and, in particular, cannot be decrypted anymore at the delegatee’s end. Moreover, delegators evolve their secret keys too, and, thus, not even they can decrypt old ciphertexts once their key material from past periods has been deleted. This, as we will discuss, directly has application in short-term data/message-sharing scenarios.Technically, we formalize fs-$$\mathsf {PRE}$$PRE. Thereby, we identify a subtle but significant gap in the well-established security model for conventional $$\mathsf {PRE}$$PRE and close it with our formalization (which we dub fs-$$\mathsf {PRE} ^+$$PRE+). We present the first provably secure and efficient constructions of fs-$$\mathsf {PRE}$$PRE as well as $$\mathsf {PRE}$$PRE (implied by the former) satisfying the strong fs-$$\mathsf {PRE} ^+$$PRE+ and $$\mathsf {PRE} ^+$$PRE+ notions, respectively. All our constructions are instantiable in the standard model under standard assumptions and our central building block are hierarchical identity-based encryption ($$\mathsf {HIBE}$$HIBE) schemes that only need to be selectively secure.