Compressed field elements challenge draft 3
Challenge:
Given a prime finite field and a hash function that produces elements of that field. Individuals A and B have access to a list X, of any size, of random elements. Individual A wants to generate a list R of elements of size n (n >= 3) 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 r_pi of that list, at an unknown index \pi, is the product of a one-way function of the other elements R’, or in other words can be considered the output of a hash of the other elements combined with A’s secret data s; f(R’, s) -> r_pi, R contains {R’, r_pi}. The index \pi is determined even before the elements of R’ can be selected. 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) [Bounty: 5 XMR] 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 using the output of Q; both algorithms may take X as an input; half credit if the compressed size is larger than two elements; Q is allowed to generate its own randomness, and to define R’ so long as each element of R’ appears random to B, while r_pi is equivalent to the output of a hash of R’ and is therefore not determinable by Q
2) [Bounty: 0.5 XMR] prove that A cannot communicate R with less than the space of R, or that proving this is not possible within current math knowledge

Bonus Challenge: instead of just one special element, let there be a subset of R with any size, composed of special elements.

Motivation: the family of elliptic curve cryptographic signature schemes inspired by LSAG include a list of scalars, most of which are random. At least one of the scalars is derived from all the other scalars, and it is imperative that its index not be revealed in order to preserve the signer-ambiguity feature of these schemes. It is my hypothesis that most of this randomness can be outsourced to the output of a hash function that provers and verifiers can compute (e.g. hashes of the signed message), thereby reducing the size of these signatures. From the signer’s point of view the list of scalars has three essential pieces of information (which is why I believe it will require at least 2 outputs from Q rather than just 1): a bit of randomness, and a special value with hidden index \pi. There seems to be no absolute reason to communicate all the random scalars. In particular, the cryptocurrency Monero uses MLSAG to sign (prove ownership of) the inputs to its transactions, and the random scalars comprise a substantial proportion of transaction data.

Here is a trivial example of a 1-to-1 `compression’ of the 2 element case, where Q outputs two scalars x and q, c is a random scalar selected by Q, r is the special scalar and depends on c, and a is an apparently random element in the list that cannot be a function of r.

list of scalars [a, b], index pi = 1
def x = 2c - r
def q = r - c
P does:
1. a = x + q = c
2. b = a + q = r

list of scalars [a, b], index pi = 2
def x = 2r - c
def q = c - r
P does:
1. a = x + q = r
2. b = a + q = c

Clearly the index pi will not be revealed.