1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ A bitstring can encode any object, so just take any OWF and parse its output as whatever you want $\endgroup$
    – fkraiem
    Commented Jan 18, 2019 at 1:12

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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