Difficulty of finding partially matching ciphertexts for a given plaintext when encrypted with two different keys

I'm trying to find a simple, practical proof-of-work scheme based purely on encryption (due to wide availability of optimized, hardware accelerated AES execution on most platforms, including modern mobile devices).

I've considered the following:

• Let $k_1$ and $k_2$ be two different randomly selected keys.

Find a counter value $c$, where $0 \le c < n$ such that: $$\mathit{Prefix}_m(\operatorname{AES}_{k_1}(c)) = \mathit{Prefix}_m(\operatorname{AES}_{k_2}(c))$$

Or in plain words: find a counter value in a given range such that when independently encrypted with two different keys would result in two ciphertexts sharing a minimum prefix of $m$ bits.

By successive trials with $c = 0, c = 1, c = 2, ...$ the probability of finding a match by brute force is $\frac{1}{2^m}$ in each trial and $1 - (\frac{2^m-1}{2^m})^t$ after $t$ trials. The maximum counter value $n$ is adjusted such that it allows for sufficient number of trials such that a solution is found with high probability (say $0.99$ or more). If the client fails to find a solution in the given counter range they must try again with a different pair of keys.

The question is, since both keys (and the underlying algorithm) are known, is there a way for an attacker to use this knowledge to find a solution faster than brute-force?

I'm aware of known-key distinguishing attacks, but not sure if they are relevant here?

(I've intentionally chosen an approach where two keys are used, rather than just one, with the intuition that each permutation path would be defined by a completely different set of subkeys)

Edit 1: it seems reasonable that using two, completely different, encryption algorithms, one for each key (say one key with AES, and the other with Salsa20), might be stronger? (though the original goal was to use the same one - as AES is currently the only one with widely available hardware acceleration)

Edit 2: this is not intended to be a memory-hard PoW. I'm also working on one that is (also using purely encryption), separately, so memory-hardness isn't relevant here.

• I think the answer is no. There is no known way to pick a key to generate a plain/cipher pair. I think this is a birthday paradox however so instead of 2^m trials to get a match it will be 2^(m/2). Just hold the counter fixed and try different keys. – Matthew Fisher Aug 7 '17 at 18:31
• @MatthewFisher Each counter value is encrypted both with $k_1$ and $k_2$. The probability that the second ciphertext would match the first to the desired number of bits is $1/2^m$. A match only happens when the exact same counter is used as plaintext. There is only a single possibility per trial. This is the equivalent of throwing two dice and expecting the result being the same. A birthday scenario would happen if any counter was allowed for a match (I have worked on those variants too). – yellowlive Aug 7 '17 at 18:44
• Who picks the keys? If the miner can pick any two random keys then they can produce the birthday collision by selecting many keys and keeping the counter fixed. In this way a large number of pairs can be created and a collision created – Matthew Fisher Aug 7 '17 at 18:49
• @MatthewFisher The keys are picked either by a server (in a client-server scenario) or in the case of a blockchain in the same way that it is picked commonly (hash-state of the blockchain). My original intention for this particular variant was actually not for mining/cryptocurrencies use but for casual DoS protection. I'm also working on a memory-hard variant with trivial verification (which is based on birthday properties so far), but it's not related to this one. BTW The maximum counter range might not actually be necessary, it is only for extra protection (no space to explain here). – yellowlive Aug 7 '17 at 19:38
• @MatthewFisher In the case of a blockchain, the state of the blockchain should be hashed with the miner's public key (though that might not be strong enough). You are right, I have not given deep thought to the blockchain scenario. I'm mostly thinking of it for another context. But I believe the keys can be generated securely. I need to think about this further to verify it is strong enough. – yellowlive Aug 7 '17 at 19:43