What characteristics define a function to be a block cipher

Question

I'm trying to understand what characteristics or properties make the result of a function a block cipher. I understand that for a function to be a block cipher it has to be invertible and can't be a one-way function.

What I don't get is how to compute a cipher. So for example, I have the following cipher: $F_k^r(m) := r(k,m)$. Now $r$ is defined as a random compression function such that $r: \{0,1\}^{3n} \rightarrow \{0,1\}^n$. The length of $k$ and the number of bits for the message $m$ are both $n$, i.e. arbitrary.

What I don't know is how to compute the cipher and why it may potentially not be a block cipher? I think it isn't a block cipher because you are starting with $3n$ and then getting an output $n$ in the random compression function. But I think I am going wrong something.

I know I am getting close in better understanding it, I just kindly need someone to clarify the cipher and why it may not be a block cipher

Answer 1

The Wikipedia definition states;

In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called a block, with an unvarying transformation that is specified by a symmetric key

A block cipher consists of two paired algorithms, one for encryption, E, and the other for decryption, D. Both algorithms accept two inputs: an input block of size n bits and a key of size k bits; and both yield an n-bit output block. The decryption algorithm D is defined to be the inverse function of encryption.

Your $F_k^r(m) := r(k,m)$ with $r: \{0,1\}^{3n} \rightarrow \{0,1\}^n$ is not a block cipher since:

• The input block size and the output block size are not same as in the Wikipedia definition. Therefore you cannot define the inverse (decryption). With the key concerned, the input space must be $2^{2n}$, not $2^{3n}$ and output space must be $2^{n}$.

Answer 2

So for example, I have the following cipher: $F_k^r(m) := r(k,m)$. Now $r$ is defined as a random compression function such that $r: \{0,1\}^{3n} \rightarrow \{0,1\}^n$. The length of $k$ and the number of bits for the message $m$ are both $n$, i.e. arbitrary.

This doesn't quite make sense, there is certainly a mix of mistakes and missing context:

• It can't be the case that both $k$ and $m$ are of length $n$, and that $r$'s domain is strings of size $3n$. (I think it's likely that what was meant is that $m$ is of length $n$ but $k$ of length $2n$.)
• Saying that the length $n$ is arbitrary is imprecise at best; it makes it sound like we're talking about variable length messages. Likely what was meant is that $n$ can be any size chosen at the time the definition is instantiated (not at the time the function is used).
• I don't see that it's strictly wrong, but it's odd to talk about a block cipher with block size $n$ and key size $2n$ as taking a single input of size $3n$.
• The fact that the formulation here mentions compressions functions suggests that we're in a hash function scenario, but the question doesn't mention that anywhere.

The last point I think is a critical clue of what's going on here. The problem is that the term "block cipher" is used with slightly different senses in more than one context:

• When talking about encryption and message authentication codes, a block cipher is a practical instantiation of a pseudorandom permutation family.
• When talking about hash functions, however, people often talk about block ciphers in the stronger sense of the ideal cipher model, where a block cipher is modeled as a family of random permutations. A compression function can be built straightforwardly out of an ideal block cipher.

So it turns out that what's precisely meant by "block cipher" actually depends on context, but the stable property is that it's a keyed family of permutations (i.e., a collection of permutations where each permutation is identified by a key), such that to a computationally-limited adversary it "looks random." The bit in scare quotes then needs to be clarified by a contextually appropriate model, e.g., PRP for encryption vs. ideal cipher for hashing.