This paper presents batch processing protocols for efficiently proving a great deal of partial knowledge. These protocols reduce the computation and communication costs for a MIX-net and secure circuit evaluation. The efficiency levels of the proposed protocols are estimated based on the implementation results of a secure circuit evaluation with batch processing.

This paper introduces the concept of "revocable unlinkability" for unlinkable anonymous signatures and proposes a generalized scheme that modifies the signatures to include revocable unlinkability. Revocable unlinkability provides a condition in which multiple messages signed using an unlinkable anonymous signature are unlinkable for anyone except the unlinkability revocation manager. Noteworthy is that the identifier of the signer is kept secret from the manager. In addition, examples are presented in which the proposed scheme is applied to existing group/ring signatures. The proposed scheme employs a verifiable MIX-net to shuffle the identifiers of all potential signers, thus giving it the potential for wide application to unlinkable anonymous signatures.

Contribution of this paper is twofold: First we introduce weaknesses of two Mix-nets claimed to be robust in the literature. Since such flaws are due to their weak security definitions, we then present a stronger security definition by regarding a Mix-net as a batch decryption algorithm of a CCA secure public-key encryption scheme. We show two concrete attacks on the schemes proposed in [1] and [2]. The scheme in [1] loses anonymity in the presence of a malicious user even though all servers are honest. The scheme in [2] also loses anonymity through the collaboration of a malicious user and the first server. In the later case the user can identify the plaintext sent from the targeted user by invoking two mix sessions at the risk of the colluding server receiving an accusation. We also point out that in a certain case, anonymity is violated solely by the user without colluding to any server. Heuristic repairs are provided for both schemes.

We present an efficient Hybrid Mix scheme that provides both routing flexibility and the optimal length of ciphertext. Although it is rather easy to embed routing information in the ciphertext, and a scheme that provides the optimal length of ciphertext is already known, it is not a trivial task to achieve both properties all at the same time. A critical obstacle for providing the optimal length of ciphertext is the session-key encapsulation header in a ciphertext that carries the encrypted session-key to each router, which linearly increases according to the number of intermediate routers. We solve this problem by improving the previously reported Hybrid Mix scheme such that the resulting scheme benefits from routing flexibility with a constant length of such headers. Our basic scheme is only secure against honest, but curious intermediate routers. Therefore, we further address the robustness issue to prevent malicious behavior by incorporating and improving an existing efficient approach based on the Message Authentication Code.

An efficient construction of a permutation network has been proposed by Waksman. However, his construction is only for permutation networks with 2k inputs. This paper provides a construction of permutation networks with arbitrary number of inputs that is an extension of Waksman's construction. By applying our construction to Abe's Mix-net, we can improve the efficiency of the Mix-net.

This paper presents a Mix-net that has the following properties; (1) it efficiently handles long plaintexts that exceed the modulus size of the underlying public-key encryption scheme as well as very short ones (length-flexibility), (2) input ciphertext length is not impacted by the number of mix-servers (length-invariance), and (3) its security in terms of anonymity can be proven in a formal way (probable security). If desired, one can add robustness so that it outputs correct results in the presence of corrupt users and servers. The security is proven in such a sense that breaking the anonymity of our Mix-net is equivalent to breaking the indistinguishability assumption of the underlying symmetric encryption scheme or the Decision Diffie-Hellman assumption.

This paper presents a universally verifiable Mix-net where the amount of work done by a verifier is independent of the number of mix-servers. Furthermore, the computational task of each mix-server is constant with regard to the number of mix-servers except for some negligible tasks like computing hash function when no disruption occurs. The scheme also provides robustness.