4
$\begingroup$

I'm reading this article and I have a doubt in the page 7. First I going to describe the required definitions and next I formulate my question.

Let be $$F(n)=\{f_k: \{0,1\}^n\rightarrow \{0,1\}^n| k\in \{0,1\}^n\}$$ a family function.

Definition: The upper bound $\kappa$ is defined as follows: For each pair $(x,k)$, there is at most $\kappa-1$ different keys $k_1,\cdots,k_{\kappa-1}$, which are also different from $k$, such that $f_k(x)=f_{k_i}(x)$ for $i=0\cdots,\kappa-1$. Equivalent we define the lower bound $\kappa '$: For each pair $(x,k)$, there is at most $\kappa '-1$ different keys $k_1,\cdots,k_{\kappa '-1}$, which are also different from $k$, such that $f_k(x)=f_{k_i}(x)$ for $i=0\cdots,\kappa '-1$

My question is with this claim:

The values $\kappa$ and $\kappa ′$ restrict the number of different images $y$ some preimage $x$ can be mapped to by functions in $F(n)$, i.e.

$$\dfrac{2^n}{\kappa}\leq |\{f_k(x): k \in \{0,1\}^n\}|\leq \dfrac{2^n}{\kappa '}$$

for all $x \in \{0,1\}^n$

Why $|\{f_k(x): k \in \{0,1\}^n\}|\geq\dfrac{2^n}{\kappa}$, resp. $(\leq \dfrac{2^n}{\kappa '})$? I make this question because the number maximum of equals images are $\kappa$ and the total number of keys is $2^n$ then for me there are at least $2^n-\kappa$ diffentent preimages.

$\endgroup$
3
$\begingroup$

Remember that the bounds are defined for every key. This means, there will be a first set of keys that contains at least $\kappa'$ and at most $\kappa$ keys that all map $x$ to the same $y$. Now, every key not in this set has to be in another set with the same size bounds that maps within which every key maps $x$ to the same $y$ which is different from all the $y_i$ the other sets map to. And so on.

Hence, there are at least $\frac{2^n}{\kappa}$ such sets of keys. All keys in such a set map $x$ to the same $y$ which is different form the $y_i$'s the other sets map to. Consequently, there are at least $\frac{2^n}{\kappa}$ different $y_i$.

Similarly, there are at most $\frac{2^n}{\kappa'}$ such sets of keys and accordingly no more than $\frac{2^n}{\kappa'}$ different values $y_i$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.