Two El Gamal ciphertexts, which are input to a two-input two-output unit switching
gates SW forming a permutation network, are randomized with a random number and
randomly permuted, and a zero-knowledge proof, which proves the correspondence
between the inputs and outputs of the switching gates SW, is output to a verifier
without revealing the random number and the random permutation. A decryption unit
decrypts ciphertexts from a unit switching gate SW in he last column through the
use of a secret key, and proves in zero-knowledge the validity of the decryption
without revealing the secret key. A verification unit verifies the proof of each
unit switching gate and the proof of the decryption unit.