False-Bottom Encryption: Deniable Encryption from Secret Sharing

We show how to implement a deniable encryption method from secret sharing. Unlike the related concept of honey encryption, which employs a preprocessing step in symmetric encryption to re-shape the distribution of a plaintext towards making the real plaintext indistinguishable from a ciphertext for a fake message, we can avoid both, computational intractability assumptions and preprocessing of the data. This accomplishes deniability against an attacker that can force decryptions, and it can brute-force break a ciphertext with sufficient computational power. Following the concept of plausible deniability, we herein have different decryption keys to open up distinct plaintexts from within the same ciphertext. For instance, a plaintext revealed from a ciphertext with a key which was shared by a victim under duress, will convince the attacker that it is real, while the actual secret remains unnoticed. False Bottom Encryption constructs a symmetric scheme (in the sense of using the same key to encrypt and decrypt) that shares the properties of both honey encryption and deniable encryption. We specifically formalize and differentiate ‘‘deniable’’ from ‘‘plausibly deniable’’ as a security feature, showing how plausible deniability falls back to (only) deniability, depending on the plaintext distribution. Our scheme is simple, lightweight to implement and efficient in terms of encryption and decryption, and is based on secret sharing. As such, we do not rely on computational intractability. We corroborate the construction by giving numeric examples and providing implementations of the method as a Jupyter notebook supplementary to this work.