Bloom Filter Encryption and Applications to Efficient Forward-Secret 0-RTT Key Exchange

David Derler; Kai Gellert; Tibor Jager; Daniel Slamanig; Christoph Striecks

Paper 2018/199

Bloom Filter Encryption and Applications to Efficient Forward-Secret 0-RTT Key Exchange

David Derler, Kai Gellert, Tibor Jager, Daniel Slamanig, and Christoph Striecks

Abstract

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 seconds 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.

Note: Preliminary version published at Eurocrypt 2018. Full version with major differences published in the Journal of Cryptology.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in JOC 2021
DOI: 10.1007/s00145-021-09374-3
Keywords: Bloom filter encryption Bloom filter 0-RTT forward secrecy key exchange puncturable encryption
Contact author(s): david derler @ iaik tugraz at
History: 2021-03-09: last of 3 revisions; 2018-02-22: received; See all versions
Short URL: https://ia.cr/2018/199
License: CC BY

BibTeX

@misc{cryptoeprint:2018/199,
      author = {David Derler and Kai Gellert and Tibor Jager and Daniel Slamanig and Christoph Striecks},
      title = {Bloom Filter Encryption and Applications to Efficient Forward-Secret 0-{RTT} Key Exchange},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/199},
      year = {2018},
      doi = {10.1007/s00145-021-09374-3},
      url = {https://eprint.iacr.org/2018/199}
}