In cryptography, we often assimilate bitstrings to integers. Unless otherwise specified, that is per big-endian binary, where a bitstring $S$ of $n$ bits $b_0,b_1,\ldots b_{n-2},b_{n-1}$ is assimilated to integer $s$ with
$$s=\sum_{i=0}^{n-1}b_i\,2^{n-1-i}$$
E.g. bitstring 00010001
(which is 8-bit) is assimilated to integer $16+1=17$. Bitstring 0000000000010001
(which is 16-bit) and bitstring 10001
(which is 5-bit) also are assimilated to integer $17$. Note that for some purposes like hashing, we can't assimilate these bitstrings, even though they are assimilated to the same integer.
$H(x)<2^{n-k}$ compares $H(x)$, which is a bitstring (or perhaps a bytestring for a programmer), to $2^{n-k}$, which is an integer (an element of $\mathbb Z\,$). Some kind of transformation is needed. This is a sure sign that in the question, $H(x)<2^{n-k}$ must be read as:
the integer assimilated to the bitsring $H(x)$ is less than the integer $2^{n-k}$.
Note: In the circumstance it's also OK to assume little-endian binary, which uses the simpler $s=\displaystyle\sum_{i=0}^{n-1}b_i\,2^i$, but one should first get convinced this won't change the result.
There are several things wrong with stating
the size of the hashed $x$ is always going to be $n$ bytes, and $(n\text{ bytes }< 2^{n-k})$ is always true for any positive integer $k$.
- If the question considered the size of "the size of the hashed $x$", it would be written $|H(x)|<2^{n-k}$, rather than $H(x)<2^{n-k}$.
- Even with the statement understood as $|H(x)|<2^{n-k}$, the argument given would be wrong, with a counterexample the choice of $k=n$.
- Cryptographers measure size of bitstrings and integers in bits (not bytes) unless otherwise stated. BTW, the bit size of non-negative integer $s$ is $\bigl\lceil\log_2(s+1)\bigr\rceil$, or equivalently the size of the smallest bitstring assimilated to $s$ (equivalently per big-endian or little-endian binary).
1111
are the integer 15 while the 4 bits0001
are the integer 1. Basically thek
in the question is the minimal number of leading0
in the bit representation. $\endgroup$ – Steffen Ullrich Nov 16 '20 at 19:5411.......111
$\endgroup$ – kelalaka Nov 16 '20 at 19:54