Paper 2005/199

Verifiable Shuffles: A Formal Model and a Paillier-based 3-Round Construction with Provable Security

Lan Nguyen, Rei Safavi-Naini, and Kaoru Kurosawa

Abstract

We propose a formal model for security of verifiable shuffles and a new verifiable shuffle system based on the Paillier encryption scheme, and prove its security in the proposed model. The model is general, so it can be extended to verifiable shuffle decryption and provides a direction for provable security of mix-nets.