Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Is it possible that there is a cryptographic hash function that outputs a c-membered subset of the n-membered set? In other words, can the set of the binary representation of c-membered subsets of the n-membered set, be the range of a hash function?
The hash function will look like below (for 2-membered subset of the 4-membered set):
H: G --- {0011, 0010}
Yes, take any cryptographic hash function $f$ whose output space is greater than $m:=\binom{n}{c}$ which is the number of possible subsets. To map the value $x$, we reduce the output of $f(x)$ modulo $m$ (if we want uniformity, we rehash if $f(x)<f(x)\mod m$), to get a reduced value $y$ such that $0\le y<m$. We then represent $y$ is the combinatorial number system and use this representation to specify the $c$ elements of the subset.
A more detailed description of the combinatorial conversion can be found in my answer to this question.
