I'm looking for an encryption scheme that has the following properties:
Naively, I could accomplish #2 and #3 by re-encrypting the data n times and increasing and decreasing n to raise or lower the decryption time.
Is there any such encryption method?
You could throw away bits of the encryption key so that there is a brute-force portion to decrypting e.g. encrypt with a 128-bit key but only share 96 bits.
Or protect the key using something like an RSA time-lock puzzle. The benefit of this is recovering the key cannot be sped up with parallelism.
One idea not already mentioned might be to hash the message data with a key and initialization vector, and have the decryptor crack the hashes.
The encryptor would output blocks of $hash(K || m_{next} || IV || m_{cumulative})$ as "ciphertexts", for some a shared secret key $K$, random initialization vector $IV$, and message $m$. $m_{next}$ indicates the next $n$ bits of the message, while $m_{cumulative}$ indicates all of the message up to the current block:
Decryption speed is tunable by making $n$ smaller/larger. The effect of $n$ on encryption speed is negligible.
This method is also re-usable without having to re-establish a key for every new message.
This is somewhat of an abuse of a hash function - hashing is not encryption!
I think that the easiest thing to do is to use an authenticated encryption scheme that relies on a random IV, and then not provide all of the IV in the ciphertext. For example, assume that you use AES-GCM with a random IV of length 96 bits. Then, in order to require time to decrypt of $2^t$, you provide the first $96-t$ bits of the IV and not the rest. The decryption process works as follows. Try all possible $2^t$ strings to complete the IV until decryption succeeds (you know when decryption succeeds or fails since you are using an authenticated encryption mode). The average time taken to succeed is $2^{t-1}$. (Note, if all fail, then you know that the ciphertext is invalid.)
I've been made aware of this question as a possible dup of one i have asked. I'm surprised that there is not much already established in this area. So here's my idea so far, but i think it needs more work;
instead of finding by brute force progressive segments of the plaintext as suggested by @Ella Rose, my idea instead was to do the same but to the key;
Make a, say, 2048 bit key at random and encrypt the plaintext. Split the key into n parts of m bits each (ie m*n = 2048), then emit n hashes, each of separately the m bit segments, using your favourite hash algorithm. Throw original key away.
To decode, brute force guess each of the n segments until its hash agrees with the given. Finally decode the ciphertext using the recovered key.
Making m bigger and n smaller increases decode time. Keep n a reasonable size to allow "guess" averaging of time.
I didn't previously think of overlapping the hashes as suggested by @Ella Rose's answer. this is a good idea as well to resist a parallel attack.
One idea might be to use byte stuffing; that is, use a normal, fast encryption scheme but add random bytes to the encrypted text in a pseudo-random way. The decryption method could either know where the stuffed bytes are (based on the key), or have to utilize a MAC scheme to one-by-one find, hash, and test for the stuffed bytes.
Because the stuffed bytes would radically alter the decryption process, stuffed bytes would have to be found and removed before normal decryption. This process would rely on multiple re-hashing, which is a long and tedious process. Because encryption is merely adding the random bytes, there would be little to no overhead on the encryption.
