# One-way function with combination sets as output / image

One-way functions generally operate on bit strings, for the input and the output.

Are there any examples of one-way functions that produce a combination set in output? Let's call this function $$f$$. The function would take one bit string in input, of size $$p$$, and would produce a combination ($$k$$ elements among $$n$$). $$n$$ is a power of $$2$$.

Concrete example of combinations set: 64 elements among 256. The size of this set is 1.9E+61 (204 bits)

I have an algorithm to generate a combination through a hash function: the hash function is used to generate a pseudo random bit string, then the bit string is split into sub-strings of size $$\log_2(n)$$ whose value represents the position of the element in the set of size $$n$$. If the value was already selected, to check the next value. If the hash function has good properties the loop will stop after some iterations.

I would like to know whether there are constructions considered as primitives for this problem.

• A bitstring can encode any object, so just take any OWF and parse its output as whatever you want Commented Jan 18, 2019 at 1:12

## 1 Answer

From what I know, there's a prior art here.

The random oracle / hash function used in BLISS signature scheme hashes a certain bit string into a sparse vector (see section 4.4). And the way they do it, is similar to what you just described.

I've got an old code sample lying around you can reference, I've incorporated a few later improvements.