Bloom filter encryption and applications to efficient forward-secret 0-RTT key exchange (Q5918309)

The paper introduces Bloom filter encryption as an efficient probabilistic puncturable encryption mechanism which tolerates a non-negligible correctness error. Bloom filter encryption is derived from the Bloom filter data structure which is a probabilistic data structure for the approximate membership problem with a non-negligible false-positive probability in answering membership queries. The authors describe different constructions of schemes and show that they yield puncturable encryption mechanism. Therefore, the constructions have applications to forward-secret zero round-trip time (0-RTT) key-exchange (i.e., clients are able to send encrypted payload along with the first key-establishment message). The paper is an extension of a conference paper which appeared in [the authors, Lect. Notes Comput. Sci. 10822, 425--455 (2018; Zbl 1415.94423)]. In contrast to the conference paper, in this paper the authors choose to present all constructions explicitly as KEMs. They are abbreviated by BFKEM. The paper is quite technical and contains various constructions. All constructions are simple and clear. The first construction is build upon ideas from (hashed-based) Boneh-Franklin identity-based encryption. Two simple generalizations follow. The first generalization is a construction from ciphertext-policy attribute-based encryption (CP-ABE) and the second generalization is a construction from identity-based broadcast encryption (IBBE). CP-ABE and IBBE are briefly recalled in the paper. The generic construction of BFKEM from IBBE is one of the extensions for the journal paper. Another difference is a more elaborate discussion on choice of parameters. Moreover, the authors extend the notion of BFKEM to the forward-secrecy setting and also introduce so called time-based BFKEM where the lifetime of a public key is split into time slots. The time time-based BFKEM can directly be used to instantiate forward-secret 0-RTT key exchange. These results are interesting. The proofs are not too difficult. Their arguments are convincing. However, due to the fact that the paper is quite lengthy additional explanations would have been helpful. Furthermore, throughout the paper there are several layout errors which are a bit irritating.