Bayer-Groth verifiable shuffle

tl;dr: Notes on the [BG12] verifiable shuffle.

Notation

• The original ciphertexts $\vec{C} = (C_i)_{i\in[n]} = (B_i, D_i)_{i\in[n]}$
• The shuffled ciphertexts $\vec{C’} = (C’_i)_{i\in[n]} = (B’_i, D’_i)_{i\in[n]}$
• $\rho_i$ is the blinder used to rerandomize for the $i$th ciphertext $C_i$ and permute it into $C’_{\pi(i)}$ for some permutation $\pi$
• $\pi$ is the permutation such that $C’_i = C_{\pi(i)} + \enc(0, \rho_i)$
  • or, in vector notation: $\vec{C’} = \pi(\vec{C}) + \enc(\vec{0}, \vec{\rho})$
• $x$ is a random Fiat-Shamir challenges.

\begin{align} \vec{C}^\vec{x} &= \begin{bmatrix} \sum_i {x_i} \cdot B_i = \sum_i {x^i} \cdot C_i,\\
\sum_i {x_i} \cdot D_i = \sum_i {x^i} \cdot D_i \end{bmatrix}\\
\vec{C’}^\vec{b} &= \begin{bmatrix} \sum_i {b_i} \cdot B’_i = \sum_i {x^{\pi(i)}} \cdot C’_i,\\
\sum_i {b_i} \cdot D’_i = \sum_i {x^{\pi(i)}} \cdot D’_i \end{bmatrix}\\
\rho &= -\sum_i \rho_i x^{\pi(i)}\\
\enc_{\pk}(0, \rho) &=(\rho\cdot G, 0 + \rho\cdot \pk) = \begin{bmatrix} \left(-\sum_i \rho_i x^{\pi(i)}\right) \cdot G,\\
\left(- \sum_i \rho_i x^{\pi(i)}\right)\cdot \pk \end{bmatrix}\\
\end{align}

Key technique

The key check in [BG12]¹ is that: \begin{align} \sum_i {x^i}\cdot B_i = \left(- \sum_i \rho_i x^{\pi(i)}\right) \cdot G + \sum_i {x^{\pi(i)}}\cdot B’_i\\
\sum_i {x^i}\cdot D_i = \left(- \sum_i \rho_i x^{\pi(i)}\right) \cdot\pk + \sum_i {x^{\pi(i)}}\cdot D’_i \end{align}

Does it make sense to decompose the random linear combination entry by entry? No, but let’s write it down anyway… \begin{align} x^i\cdot B_i &= \left(-\rho_i x^{\pi(i)}\right) \cdot G + {x^{\pi(i)}}\cdot B’_i\\
&= x^{\pi(i)} \cdot \left(B’_i - \rho_i \cdot G\right)\\
x^i\cdot D_i &= \left(-\rho_i x^{\pi(i)}\right) \cdot\pk + {x^{\pi(i)}}\cdot D’_i\\
&= x^{\pi(i)} \cdot \left(D’_i - \rho_i \cdot \pk\right) \\
\end{align} It’s more that the random linear combinations by $x^i$’s and $x^{\pi(i)}$’s help “match up” permuted ciphertexts with one another. So, the effective checks is that, for all $i\in[n]$: \begin{align} B_{\pi(i)} &= B’_{i} - \rho_{i} \cdot G\\
D_{\pi(i)} &= D’_{i} - \rho_{i} \cdot \pk\\
\end{align}

Intuition is that they rerandomize the $i$th original ciphertext by $x^i$ and the $i$th new ciphertext by $x^{\pi(i)}$ and check equality of product of rerandomizations.

It’s a bit hard to see but because $B_i$ gets multiplied by $x^i$ and and $B’_i$ by $x^{\pi(i)}$. This means that $B’_i$ will only be cancelled out by a corresponding $B_j$ with $j = \pi(i)$. So that’s why get the non-intuitive equality above.

Open question

Can we improve upon the BG12 approach by leveraging univariate sumchecks for the product argument and/or multi-exponentiation argument (or even multivariate ones)? Or Bulletproof-like (G)IPAs?

References

For cited works, see below 👇👇