The Hash-Based Stateless Signature (HBSS) scheme, presented at CSCML 2023, is a post-quantum signature scheme based on Bloom filters. Its main strengths are statelessness, ease of implementation, and a relatively low computational cost. We extend HBSS construction in two ways: first, the scheme is generalized by applying Lamport’s chain of hashes to generate multi-level preimages. In this way, a new vertical dimension is introduced in the preimage array, to reduce its horizontal dimension, i.e., the size of the keys. Second, we augment the paper with a more general analysis of the choice of values of the parameters. The analysis with the above-mentioned modification allows us to reduce the size of the keys 16 times compared with the HBSS scheme, in which the values of the parameters are set according to the CSCML 2023 paper.