Compact Verifiable Shuffles for ElGamal Ciphertexts

본문 미리보기

A verifiable shuffle proves that output ciphertexts are a rerandomized permutation of the inputs without revealing the permutation or rerandomization factors. It is a core primitive in mix-nets for electronic voting and blockchain-based anonymization, where each mix server publishes an auditable proof. Existing deployed schemes typically have proof size $O(N)$ or $O(\sqrt{N})$ in the number of ciphertexts $N$, making shuffle proofs a major bandwidth cost. We present a logarithmic-size verifia