# Proof of knowledge of exponentiations

I am reading a paper of Furukawa and Sako, "An efficient scheme for proving a shuffle" from 2001. This paper writes a protocol for verifiable shuffling in mixnets. Their protocol make use of permutation matrixes, and they consider the use of ElGamal cryptosystems. A ciphertext $(g,m)$ is shuffled to $(g',m')$ as follows:

$$(g_i',m_i')=\left(g^{r_i}\prod_{j=1}^{n}g_j^{A_{ji}},y^{r_i}\prod_{j=1}^nm_j^{A_{ji}}\right)\bmod p$$

where $r_i$ is a random number, and $A_{ji}$ is a permutation matrix.

I want to prove that for each pair $(g'_i, m'_i)$ the same $r_i$ and permutation matrix has been used. I have been told that this is a standard proof of knowledge of exponents, but I can't quite find out how this is done. I really appreciate if anyone is able to help me.

• To get an idea for what's going on, write out the equations for $n = 3$ and the permutation $(2, 3, 1)$ and you'll see it's just a system of equations out of which you can make a generalised Schnorr proof. The bit that differs from one mixnet to another is how you prove that $A$ really is a permutation matrix. – Bristol Apr 26 '18 at 20:41