1
$\begingroup$

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}

$\endgroup$
1
  • $\begingroup$ One possible solution is mapping the output of a cryptographic hash function to the c-members. if the output is even, then to 0010 if odd then 0011. It might be problematic if the c-membered set is not a regular... So, what is the actual use case? $\endgroup$
    – kelalaka
    Sep 3 at 11:50

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Absolutely, a professional answer. Thanks a lot Dr. @daniel-s . $\endgroup$ Nov 18 at 16:24

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.