Compressing Apparently Random Finite Field Elements
Challenge:
Given a prime finite field (order greater than 3), and a hash function that produces uniformly distributed 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 element 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 a pair of algorithms Q and P, where Q takes as input the secret index \pi, order of the finite field, and size of R, and outputs both R and the compressed version Rc which occupies less space than R, and P takes as input finite field order, the size of R, and Rc, and outputs R. The construction of Q and P, and the output Rc of Q, may not reveal \pi or allow B to reduce the possibilities for \pi to some subset of R. Both algorithms may take X as an input. Algorithm Q is allowed to generate its own randomness, and to define R’ so long as each element of R’ appears random to B, while element r_pi is equivalent to the output of a hash of R’ and secret data s, where s is provided to Q only after R’ has been defined, and is unknown to B and P. Only reasonably fast algorithms are acceptable.
or 2) [Bounty: 1 XMR] Prove that condition 1 cannot be achieved.

Motivation: The family of elliptic curve cryptographic signature schemes inspired by LSAG include in their signatures a list of elements of a prime finite field, most of which are randomly generated by the signer. Typically one of the scalars is the output of a one-way function of 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 the randomness can be offloaded 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 two essential pieces of information (which is why I believe Rc requires at least the space of two scalars): a bit of randomness that conceals the secret index \pi, and a special value with secret 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.