Compressed field elements challenge draft 2
Challenge:
Given a prime finite field and a hash function that produces elements of that field. Individuals A and B can independently generate the same list X of elements by using the hash function. X can be any size. The purpose of X is to allow deterministic randomness. Individual A wants to generate a list R of elements of size n (n >= 2) where each element appears random to Individual B (note that this means each element appears unrelated to any element of X, or any other scalar B knows about). One element of that list, at an unknown index \pi, is the product of a one-way function of the other elements; f(R’) -> r_pi, R = {R’, r_pi}. Individual A wants to send R to Individual B with as little space as possible. Ideally, with the space of one or two field elements regardless of the size of R. He is determined not to reveal the index \pi, and also determined that B be able to recover the entirety of R.
Conditions of victory:
1) prove that the task of individual A is impossible
2) describe an algorithm Q to compress R into a size less than R without revealing \pi or allowing B to reduce the possibilities for \pi to some subset of R, and another algorithm P that B may use to recover R; half credit if the compressed size is larger than two elements; Q is allowed to generate its own randomness, and to define R’, while r_pi is equivalent to the output of a hash of R’ and is therefore not determinable by Q