ElGamal Pair Sequences

[lhmerino]

Kyber currently implements PairShuffle where one can shuffle a list of ElGamal ciphertexts. The goal of this issue is to implement the protocol provided by Andrew Neff in Section 5 of his “Verifiably Mixing (Shuffling) of ElGamal pairs” to shuffle more than one ElGamal pair.

I have implemented a prototype of this protocol but the following needs to be resolved:

1. In terms of the protocol itself, why does the verifier need to generate a random and independent value (EGAR1)?
2. In terms of the implementation, how to reliably fetch those values from the verifier before the prover continues onto the next step of the protocol (EGAR2)?
3. In terms of the implementation, how to integrate the extra proof parameters (XXUp, YYUp, XXDown, YYDown) into the prover context?

[nkcr]

I am not very familiar with the current neff shuffle implementation, but here are my "high-level" comments on 2 and 3:

In terms of the implementation, how to reliably fetch those values from the verifier before the prover continues onto the next step of the protocol (EGAR2)?

This should be the responsibility of the one using this library. Kyber provides the functions to generate messages, the synchronization and message passing part is done by the one using kyber (like this is the case for DKG).

In terms of the implementation, how to integrate the extra proof parameters (XXUp, YYUp, XXDown, YYDown) into the prover context?

I guess that if we want to keep backward compatibility, that would be easier if we implement that new version of neff shuffling in a new package. Like so we are free to include whatever parameters needed.