# One-one correspondance complete function

I am reading the paper by John B. Kam and Georges I. Davida (1979) titled Structured Design of Substitution-Permutation Encryption Networks.

On page 749 it reads the following: Definition: Given a one-one corespondence: f:{0,1}n --> f:{0,1}n, f is said to be complete if, for every i,j belongs {1, ..., n}, there exist two n-bit vectors X1 and X2 such that X1 and X2 differ only in the ith bit and f(X1) differs from f(X2) at least in the jth bit.

My questions are:

• What is meant by vectors here? (Can someone explain it using less math if possible?)
• Can someone explain this, proably with a nice and easy example?
• In general, what is the idea behind this?

If this is the wrong place to ask the question, please let me know so that I take this to the write place instead of voting negative or closing the question.

What is meant by vectors here?

Just the inputs and outputs of the function. The function $f$ takes, as input, a sequence of bits (for example, 1010), and returns a sequence of bits (for example, 1100); the text refers to such a sequence of bits as a vector

Can someone explain this?

Well, the idea is that every output bit depends on all input bits. That is, if we were to compute an output bit $j$, we would still need to know every single input bit (because for every output bit $j$, there is a pair of inputs $X_1, X_2$ for which input bit $i$ matters). In other words, for any change in an input bit, there's a possibility that it may affect any output bit.

That sounds like a reasonable goal; however it turns out to be a very weak guarantee.

To see this, consider a function f that is made up of two operations:

• Take the input, treat in as an $n$ bit unsigned integer, and increment it modudo $2^n$

• Take the msbit of the result, if it is 0, the value remains the same, if it is 1, flip all the other bits. This can also be viewed as xor'ing the msbit into all the other bits.

• Return that as your result.

For example, consider the input $1010$; in the first step, we treat that as an unsigned integer (the value ten, as it happens), and we increment it to eleven (or $1011$). Then, in the second step, we take the msbit (which is a 1) and exclusive-or that into the rest of the values, turning the lower three bits $011$ into $100$, giving us a final result of $1100$.

Now, this rather odd function just happens to meet the criteria of a 'complete function' for $n>2$; it's one-to-one (as both steps are invertable), and for every $i, j$ pair, we can find two inputs $X_1, X_2$ that differ only in the $i$-bit bit and $f(X_1)$ and $f(X_2)$ differs in the $j$th bit (and possibly elsewhere).

For example, for $i=4$ and $j=2$, consider $X_1 = 0010$ and $X_2 = 0011$. These two vectors differ only in the 4th location (counting 1 as the first bit); $F(X_1) = 0011$ and $F(X_2) = 0100$, which differs in the 2nd location (as well as the third and the fourth; we're allowed to change other output bits in addition to output bit $j$).

And, for $i=2$ and $j=4$, consider $X_1 = 0111$ and $X_2 = 0011$. These two vectors differ only in the 2nd location; $F(X_1) = 1111$ (remember, we first increment $0111$ into $1000$, and then xor the top bit into the rest of them, flipping all three 0's into 1's), and $F(X_2) = 0100$, which differs in the 4th location (in addition to the first and the third).

I won't go through all the combinations, but such pairs exist for all $i, j$ values.

On the other hand, this example shows that it is a rather weak guarantee; I picked the specific function $f$ because it meets the criteria, but not in a particularly useful way. For large $n$, yes, every $i, j$, you can find a pair $X_1, X_2$; however for most $i, j$ pairs, output $j$ rarely depends on input $i$.

• Poncho, thanks a lot for giving your time to explain this in detail. I have seen your contribution to this site and it is amazing. Many many thanks for your efforts for sharing knowledge and making this site a better place. :) I still did not read the answer. I'll read it at a later time and get back if I have any questions ! – tony9099 Mar 3 '15 at 7:14