Encryption scheme with variable and provable key-length

I'm currently studying the possibility of a novel ransomware technique, where an adversary instead of forcing the victim to pay a ransom, forces them to brute force a key of given length and thus spend a lot of computational power.

However before beginning the victim would need some assurance that recovery is actually possible with their given means.

I've considered the case where you give the victim a partial key used by a well known block cipher in combination with a way of verifying that the partial key is correct. However a "partial key oracle" would clearly compromise the scheme, since the victim could query the oracle and guess the key bit by bit in linear time.

So I'm looking for an algorithm that allows for a variable key-length (preferably down to bit-level, so the attack can be tuned to the victims capabilities) and a way to prove from the ciphertext/AD that the key had a certain length.

If anyone knows of such a scheme or can give me some more insight into how it can be accomplished (if at all possible), I'd be very grateful.

I would also like to note that this is only meant for academic purposes and I will not implement or use this for malicious purposes.

• TIme lock puzzle can solve this, though. Also, just release 88-bit AES-128 key and let them compute 40-bit space with some known-plaintext? Sep 14, 2023 at 13:43
• But if they have no way of knowing/verifying that the released partial key was a part the the key used to encrypt the data, then the scheme falls apart. It would be a way to do it, but who's going to trust a ransomware actor? But I'll look into the time-release crypto you referenced. Thanks! Sep 14, 2023 at 13:58
• who's going to trust a ransomware actor Many did and payed for their data. They are for money not for destruction or torture. They can write a small note about the puzzle/computation to be held so that you can try it with an off-line system. This style no longer can be called ransomware, it is like computationware Sep 14, 2023 at 14:09
• This sounds like a scenario where a witness from arguments/proofs of knowledge might be able to attest that a particular computation (encryption) operation was done, without revealing the plaintext or key. I am not well versed enough to give an explanation for how it works, though. Sep 15, 2023 at 0:43
• @aiootp this seems very promising! I'll look into it. Thanks! Sep 15, 2023 at 8:26

First and foremost, I must emphasize the ethical and legal implications surrounding the development and discussion of ransomware, even for academic purposes. That said, if the objective is purely academic and research-based, it's crucial to ensure that any knowledge obtained or shared doesn't fall into the wrong hands.

• Proof of Work (PoW): Your idea somewhat resembles the concept behind Proof of Work used in blockchain technologies, especially in the context of Bitcoin. Here, participants (miners) must solve computationally intensive puzzles to validate and add transactions to the blockchain. The difficulty of these puzzles can be adjusted. You can explore PoW as a theoretical starting point for your research.
• Zero-knowledge Proofs: In cryptographic systems, zero-knowledge proofs allow one party to prove to another party that they know a value x, without conveying any information apart from the fact they know the value x. This might provide a mechanism by which assurance can be given to the victim about the feasibility of finding the key.