Is there an encryption/decryption algorithm that can give two different outputs?

Question

The recent revelations that airport staff can detain travellers in an interrogation room and force them to give over passwords to encrypted-HDD laptops under threat of jail time has made me think about some sort of dual password encryption/decryption mechanism.

For example:

• Password 1 decrypts all the data as usual.
• Password 2 decrypts most of the data, leaving a portion looking like random 0's and 1's.

I think it has to work at the algorithm level, and not rely on software, because the HDD could be removed from the laptop and then any software protection is useless.

My question is, are there any algorithms that can give two different (but similar) results depending on which key is used?

Answer 1

It looks like you might be interested in applying Deniable Encryption.

The general idea of this kind of encryption is that you can decrypt the data to produce a different (but still plausible) plaintext. In this way, the airport staff or whoever is asking you to decrypt the data, would by no means differentiate between the real plaintext and the alternative one. I suggest to have a look a this paper.

Answer 2

Note that the fact that a deniable encryption scheme has been used or at least is available for use is hard or even impossible to hide.

Competent attackers observing the mathematical possibility of secondary plaintext will assume it has been used and will thus attempt to beat or persuade the second password out of you. So the situation regarding the presence of a deniable encryption scheme (either algorithmically or artifactually) is similar to when the presence of any encryption scheme by ordinary civilians would have raised suspicion in the early 1990s.

Hence to blend into the crowd of people not actually using the scheme (or used for trivial reasons), the use of a deniable encryption scheme (and its space inefficiency) would have to become the default mode for all or most computer users.

Hiding a second plaintext is not dissimilar to deliberately inducing a hash collision. If your key space is as large as the largest of the two plaintexts (i.e. one-time-pad), you could have as many secondary plaintext instances as you like, because the key becomes secondary plaintext.

Alternately, schemes with small keys can encrypt/decrypt different independent ciphertexts for each plaintext variant; no collision inference required. Of course, since most non-deniable schemes don't waste drive space this way - these schemes with more ciphertext than innocent plaintext are a red flag. As suspicious as claiming that, of two large random data files on your computers, "only one of them has been encrypted, Officer, honest!"

Authorities, jackboot and non-jackboot varieties, are in no hurry to encourage people to use deniable encryption as their default file storage mode. Assuming people would otherwise want to buy a 2TB hard drive and only have 1TB available for use.

Typically the solution is to use steganographic tools to hide secrets in mundane files so that the question of encryption never arises. But then you need to hide the steganography algorithm! Because - as before - steganography is not in the default software toolkit of normal computer users... Sigh :-/

EDIT: There are schemes of unknown (well, untested) robustness that use small keys and same size plaintext/ciphertext. Providing you change the keys each time the secondary plaintext changes.