Skip to main content
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Improved formatting
Source Link
AleksanderCH
  • 6.5k
  • 10
  • 31
  • 64

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$f$. The function would take one bit string in input, of size p$p$, and would produce a combination (k$k$ elements among n$n$). n$n$ is a power of 2$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 Log2(n)$\log_2(n)$ whose value represents the position of the element in the set of size n$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.

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

Are there 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 Log2(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.

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.

Source Link
Fraktal
  • 229
  • 1
  • 5

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 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 Log2(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.