Let $BC$ be a block cipher with similar security as AES (in ECB mode). This $BC$ is applied to a message $m$ of same bit size. The result is a cipher $c$.


$$BC(key_A,m) = c_A$$ $$BC(key_B,m) = c_B$$

I'm looking for a $BC$ with: $$BC(key_A,c_B) = c_{BA}$$ $$BC(key_B,c_A) = c_{AB}$$ where $$c_{AB}=c_{BA}$$ but for the majority: $$c_{A}\not=c_{B}$$

Is there any way to construct keys $key_A, key_A$ with this property for a suitable $BC$?

(Or at least for a big subgroup of the elements)

This questions includes an answer (from Thomas) to a similar question: Are there any secure commutative ciphers?

But as far as I understand it this implies the $BC$ is commutative for all keys. I'm fine with just a small amount of keys which are commutative to each other.

Also in target application the $BC$ just serves as a random number generator. The next number will be generated by applying $BC$ to the current. It should be hard to determine the 'index' of a given value or computing $i$-steps ahead.

A commutative RNG which can compute the next and previous value out of the current (+ some constants (like the key or seed) would also do the job.

Edit: The key/seed will been known.

  • $\begingroup$ Huh? The answer of Thomas explains that "In that sense, a commutative block cipher cannot be secure "as a block cipher". " The initial part of the question requests exactly that, although you do introduce a mention of related keys. What really surprises me though is the fact that BC just serves as a random number generator - for that you also don't need to have a decryption function, so in that case are we not limited to a PRP / block cipher anymore? $\endgroup$
    – Maarten Bodewes
    Jul 24 at 21:20
  • $\begingroup$ @MaartenBodewes It don't need to be that strong as in shown link. Instead of all keys some keys would be enough. Also the keys will be known anyways (did some edit). The decryption is needed because out of a random value the next and previous number (=decryption) need to be computable. As written above it need to be hard to compute the index and no short cut for computing i-steps ahead. The cycle size need to be close to the bit-size (or equal). I already checked many PRP or RNG. They always had some problems. AES-like has best properties so far but any alternative idea would be nice as well. $\endgroup$
    – J. Doe
    Jul 24 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.