We propose here the first efficient publicly verifiable hybrid mix-net. Previous publicly verifiable mix-net was only efficient for short ciphertexts and was not suitable for mixing long messages. Previous hybrid mix-net can mix long messages but did not have public verifiability. The proposed scheme is efficient enough to treat large scale electronic questionnaires of long messages as well as voting with write-ins, and offers public verifiability of the correctness of the tally. The scheme is provably secure if we assume random oracles, semantic security of a one-time symmetric-key cryptosystem, and intractability of decision Diffie-Hellman problem. This paper is the full version of the extended abstract appeared in FC 2006 [10].

We propose an authentication scheme in which users can be authenticated anonymously so long as times that they are authenticated is within an allowable number. The proposed scheme has two features: 1) no one, not even an authority, can identify users who have been authenticated within the allowable number, 2) anyone can trace, without help from the authority, dishonest users who have been authenticated beyond the allowable number by using the records of these authentications. Our scheme can be applied to e-voting, e-cash, electronic coupons, and trial browsing of content. In these applications, our scheme, unlike the previous one, conceals users' participation from protocols and guarantees that they will remain anonymous to everyone.

In this paper, we present an electronic voting scheme with a single voting center using an anonymous channel. The proposed scheme is a 3-move protocol between each voter and the center, with one extra move if one wants to make objection to the tally. This objection can be broadcasted widely since it will not disclose the vote itself to the other parties besides the center. The main idea in the proposal is that each voter sends anonymously a public key signed by the center and an encrypted vote decryptable using this key. Since even the center cannot modify a received ballot to a different vote using the same public key, the key can be used as an evidence in making open objection to the tally.

In anonymous survey, statistical information by attributes of respondents -such as his gender, age or adress-plays an important role in the interpretation of data. However, giving away all his attributes may cause privacy problem. That is, gathering many attributes may help identifying specifically who responded to the anonymous survey. In this paper, we propose a protocol executed among several `entities in charge' in order to compute statistical information for surveys. The advantage of adopting this protocol is that it does not release extra information of attributes on calculating statistical results. We can show that this protocol is a secure computation in the sense of Micali-Rogaway if played by semi-honest entities. We furthurly give a protocol with zero-knowledge proofs to ensure that the entities are indeed semi-honest.