I wonder if we can construct a family of (increasingly large) semigroups of second-preimage resistant one-way functions. More precisely, I would like to have an indexed family (let's denote the index by i) of semigroups of functions (where the semigroup operation is composition) such that:
- i-th semigroup has size >= i,
- the members of the i-th semigroup can be described by natural numbers from a range of size poly(i),
- there are algorithms polynomial in input size that:
a) read i, descriptions of two functions from the i-th semigroup and output the description of their composition,
b) read i, description of a function from i-th semigroup, an input, and evaluate the function,
- the functions in i-th semigroup are resistant to second preimage attacks with security parameter log(i) [^].
tl;dr I want families of efficiently composable hash functions.
[^] I could just as well request a family indexed by i and the security parameter separately (and have all the complexities be poly(input size + security parameter)). This is equivalent.
