Re: deniable encryption

The simple use-case for deniable encryption is an attacker who points a gun at you and demands that you decrypt your Bitcoin wallet so that he can take your coins, hence you decrypt by using a decoy secret key that only gives the attacker a smaller portion of your coins, and while you're in a safe environment you decrypt your wallet with another secret key to access the larger portion of your coins. The attacker might see your screen with your wallet before he approaches you, therefore for everyday use you should prefer to operate with the version of your wallet that only controls the smaller portion of your coins (i.e. the pubkeys that correspond to the larger amount of coins will also be encrypted). This can be done by separate wallet.dat files, but built-in support for BIP32 wallet can be nicer, by selecting some branch in the deterministic tree as your decoy wallet, so you can easily transfer coins to/from that branch (see also post #192 in this thread).

It is easy to see that symmetric deniable encryption implies that the ciphertext must be bigger than the plaintext, simply because ordinary symmetric encryption is highly efficient. Suppose that you have two incompressible files f1 and f2 (i.e. files with high entropy) of same size, and note that the size of AES(f1) is the same as the size of f1. If you could create a ciphertext c1 of same size as f1 that can be decrypted into f1 by using the secret key k1 and can be decrypted into f2 by using another secret key k2, then you effectively compressed (f1,f2) into (c1,k1,k2), which is impossible.

This implies that if the attacker controlled which symmetric encryption algorithm we must use then there's no hope to have deniable encryption, but fortunately we can choose to use by default a symmetric encryption algorithm that expands the size of the ciphertext. Since wallet.dat files are quite small, that isn't really a big deal for end-users.

The straightforward construction for symmetric deniable encryption is simply concatenation, meaning that if we have the real plaintext f1 and the decoy plaintext f2 then the ciphertext is c=(c_1,c_2)=(enc_AES_k_i1(f1),enc_AES_k_i2(f2)) and the decryption algorithm dec(c,k,idx) will invoke dec_AES_k(c_idx), meaning that for {i1,i2}={1,2} the real secret key is (k1,i1) and the decoy secret key is (k2,i2).

The reference Bitcoin client can have by default a checkbox that reads "Support for deniable encryption", and when a user (who doesn't care about deniable encryption) encrypts his wallet the client will simply create a ciphertext that's twice the size of the plaintext where one random half is random data. This checkbox should be on by default, and each user can turn it off if he wishes to have a smaller ciphertext. If the user does care about deniable encryption, he encrypts his wallet with real half and decoy half by using the simple concatenation construction. If an attacker points a gun at this user, he will decrypt with his decoy key, and the attacker cannot tell whether the other half is random data (which would be the case with an ordinary user who didn't specifically choose to use deniable encryption) or not.

To protect against scenarios where the attacker has a reason to suspect that the user did use deniable encryption, and therefore try to force the user to reveal his 2nd secret key, it might be preferable to concatenate some n
Edit: actually it isn't completely clear whether AES can be obliviously generated, meaning that (for random k) enc_AES_k(random) could be distinguishable from random (thanks to Hong-Sheng Zhou for this info), but in the worst case we'd just need to invoke AES once to encrypt random plaintext with random key and throw away the key...