International Association
for Cryptologic Research

Standard symmetric encryption schemes, such as AES and block ciphers and their modes in general, are highly effective for many standard scenarios. But what if the situation is somewhat different from the standard: e.g., the encrypting process may fail to update the ciphertext at some limited number of times, can the decryption recover the message in full, nevertheless? Or, another situation is when encrypting a bulk of messages that should be packed together within the same ciphertext space (i.e., encryption done holographically)? Can a process compress the messages this way? Another issue may be that we want to hide the ciphertext and camouflage it as some other cryptographic exchange (like exchanging an encrypted set to perform a protocol like “private set intersection”), or when we want to hide the number of messages packed together? Can a paradigm be developed that allows these non-standard properties that, under specific working conditions, may become necessary? Can it be based directly on a simple symmetric key cryptographic tool (and preferably be post-quantum)? This paper introduces Encryption via Hash (EvH), a symmetric randomized cipher built upon keyed cryptographic hash (i.e., MAC) functions and Bloom Filters. EvH’s core novelty lies in its prefix decryption capability. This unique property enables a paradigm in which encryption is tightly integrated with online compression and robust resilience to omission errors. By representing message prefixes in a Bloom filter, EvH allows a receiver to decrypt the initial part of a message even if subsequent data is lost and recover from an omission of a prefix decryption in the middle of the encipherment process, a significant advantage over conventional block cipher modes. Furthermore, this prefix-based approach facilitates simultaneous compression during the decryption phase by dynamically pruning invalid message continuations, using shared k-gram dictionaries or Large Language Models (LLMs). The result is a stateless and parallelizable cipher that, while computationally distinct from traditional ciphers, offers unique functional benefits for such specific use cases, and the price is that its correctness is ensured probabilistically (but the error can be well controlled and made small).