Any block cipher transforms a block of $N$ bits into another block of $N$ bits based on a $\mathcal{K}$ bit key. This can be considered to be a substitution cipher on an alphabet consisting of $2^N$ symbols. Given a key, the encryption process can be considered a permutation on this alphabet, while given the same key, the decryption process is the inverse permutation.

The number of possible permutations is: $$ 2^N ! $$ Out of this, $1$ permutation is the identity permutation (i.e. plaintext = ciphertext), and the following number of permutations are involutions (i.e. encryption = decryption) $$ \sum_{k=1}^{2^{N-1}} \frac {2^N !} {2^k\;k!\;\left(2^N - 2k\right)!} $$ This leaves the following number of permutation pairs where the two permutations are not the same, but are inverses of each other. $$ \frac {2^N !} {2} \left( 1 - \sum_{k=0}^{2^{N-1}} \frac {1} {2^k\;k!\;\left(2^N - 2k\right)!} \right) $$ This number, being $\mathcal{O}\left(2^N !\right)$, grows very fast with $N$, and would need around $N\cdot2^N$ bits to hold. If we consider that the key is effectively something that selects which permutation to apply, it would appear that we have here a possibility of an asymmetric cipher which preserves block sizes -- if only we could find a way to generate key pairs such that:

  1. The two keys in each pair select distinct permutations that are inverses of one another, and
  2. Given any one of the keys in the pair it is computationally hard to determine the other, especially in the face of a chosen plaintext attack [which becomes an obvious line of attack in a public-key setting.]

Now my questions are:

  1. Is there any known reason why this is impossible?
  2. Is there any known reason why this, even if devised, will not be useful? [see update below]
  3. Is there any ongoing research work [out in the open, of course] on such ciphers -- which can probably be called asymmetric block ciphers or asymmetric format-preserving ciphers?

Update: Thanks @RickyDemer for the pointer. This gives me an answer to my 'will it be useful' question. If I have a key pair of which I advertise one as my public key, I expected two things:

  1. Anyone can encrypt a message with my public key, but no one but me will be able to read it -- it appears that I can't reasonably expect this, because an attacker can simply encrypt all plausible plaintext blocks (of which there will be far fewer than $2^N$) and compare it with the ciphertext block to figure out what the actual plaintext was.
  2. If there is a message that has been decrypted using my public key, it must have been encrypted by me. Does this still hold, and does this mean that we can still use such ciphers against forgery of a message by a receipent [he can't produce the ciphertext for the message he would like to forge] and for non-repudiation [only I could have produced a ciphertext that maps to a claimed plaintext]?

Thanks ...


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.