Fault Tolerant Anonymous Channel
Wakaha OGATA1, Kaoru KUROSAWA2,Kazue SAKO3, Kazunori TAKATANI1 1 Himeji Institute of Technology,
wakaha@comp.eng.himeji-tech.ac.jp
http://wwwj2.comp.eng.himeji-tech.ac.jp/home/wakaha/
2 Tokyo Institute of Technology,
kurosawa@ss.titech.ac.jp, http://tsk-www.ss.titech.ac.jp/kurosawa/ 3 NEC Corporation, sako@sbl.cl.nec.co.jp
Abstract. Previous anonymous channels, called MIX nets, do not work
if one center stops. This paper shows new anonymous channels which al-low less than a half of faulty centers. Afault tolerantmultivalued election scheme is obtained automatically. A very ecient ZKIP for the centers is also presented.
1 Introduction
Chaum considered an anonymous channel which hides the correspondences be-tween the senders and the messages [Ch81]. Suppose that there are l senders P1;:::;Pl such that each Pi has a message mi. Assume a center called MIX which publicizes his RSA public keyE. Each senderPisendsci=E(mi) to the
MIX. The MIX decrypts them and publicizesm1;:::;mlin the lexicographical order. The MIX, however, knows who sent what message. Finally, Chaum pro-posed a MIX net in whichnMIXes are sequentially connected [Ch81]. Anonymity is protected if at least one MIX is honest.
The MIX net, however, does not work if one MIX (center) stops. This paper shows new anonymous channels which allow less than a half of faulty centers, where faulty centers can stop or deviate from the protocol arbitrarily. Fault tolerant multivalued election schemes are obtained automatically. (Cohen and Fischer type election scheme realizes only yes/no votes [CF85, Be86].) A very ecient zero knowledge interactive proof system (ZKIP) for MIX is also pre-sented.
2 Fault tolerant anonymous channels
This section presents two robust anonymous channels which allow less than a half of faulty centers. One is based on the hardness of factorization and the other is based on the diculty of the discrete log problem. In both schemes, even if less than a half of centers are faulty, (1) randomly shued messages are output and (2) anonymity is protected.
2.1 Proposed scheme based on factoring
Ther-th residue public key cryptosystem is dened as follows [CF85]. Let rbe a prime.
Secret key:
Two large prime numbersp;qsuch thatrjp?1 andr6jq?1.Public key:
N(4=pq) andy such thaty6=xrmodN for8x.
Plaintext:
msuch that 0m < r.Encryption:
E(m;x)4=ymxrmodn, wherex is a random number.
Decryption:
Letc=E(m;x). Thenm=j0 ifc(p?1)=r= (y(p?1)=p)j
0 modp
This cryptosystem satises a homomorphic property such that
E(m1;x1)E(m1;x2) =E(m1+m2modr;x0); for some x0: (1) Then our scheme is described as follows. Suppose that there are l senders P1;:::;Plsuch that eachPihas a messagemi. AssumencentersMIX1;:::;MIXn such that eachMIXj has a public keyEj of ther-th residue cryptosystem. Let
k4
=b(n?1)=2c+ 1:
Denition1.
For a plaintext m, choose a random polynomialR(x) of degree k?1 such thatR(0) =m. LetB(m;R)4
= [E1(R(1);x1);
;En(R(n);xn)]; where x1;
;xn are random numbers. We say that B(m;R) is an encrypted shares ofm.
Denition2.
ForB(m;R), choose a random polynomialU(x) of degreek?1 such thatU(0) = 0. Let^ B(m)4
= [E1(R(1);x1)E1(U(1);w1);
;En(R(n);xn)En(U(n);wn)]; wherew1;
;wn are random numbers. We say that ^B(m) is a reencryption of
B(m). ( ^B(m) is again an encrypted shares ofmbecause ^B(m) =B(m;R+U).)
(Sender's protocol)
Each Pi computes B(mi;Ri), an encrypted shares of his message mi, and
publicizesB(mi;Ri). He proves that he knowsRi(x) by using a ZKIP of
knowl-edge. He is then proving two things:
1. He knows Ri(0) which is his message itself. This proof prevents the
Ptz-mann's attack against Chaum's MIX net [PP89].
(Center's protocol)
Now[B(m1;R1);
;B(ml;Rl)] (2) are publicized.MIX1randomly computes a reencryption of eachB(mi;Ri) such thatB(mi;Ri+Ui).MIX1chooses a random permutationon
f1;2;:::;lgand publicizes
[B(m(1);R(1)+U(1));
;B(m
(l);R(l)+U(l))):] (3)
MIX1 further proves that eq.(3) is computed from eq.(2) correctly by using a ZKIP. For 2jn,MIXj executes the same process sequentially.
(Decryption)
At the end,MIXn publicizes
[B(m'(1);R~'(1));
;B(m'
(l);R~'(l))]
for some permutation', whereB(m'(i);R~'(i)) is an encrypted shares ofm'(i). Let
B(m'(i);R~'(i)) = [ci;
1;:::;ci;n]
EachMIXj decrypts ci;j and publicizes its plaintext vi;j for i= 1;:::;l. Then
everybody can recoverm'(i) from k or more vi;j. EachMIXj proves that he behaved correctly by using a ZKIP.
If somePiorMIXj is detected to be faulty, he is ignored from that time on.
Pl P1 -B(m1;R1) ... B(ml;Rl) MIX1 reencryption and shue -B(1) (1) ... B(1) (l) MIX2
Fig.1.Reencryption and shue, whereB (1) (i)
4
=B(m(i);R(i)+U(i)).
2.2 Proposed scheme based on DLOG
This anonymous channel makes use of the scheme shown in Sec. 5.1 of [PIK93], which uses ElGamal public key cryptosystem. (It is called type 2 channel in [Pf94].)
Each MIXj distributes his secret key xj to all MIXes by using Shamir's
(k;n)-threshold secret sharing scheme. Each sender proves that he knows his message by using a ZKIP to avoid the attack of [PP89]. EachMIXj proves that
not work. Further, the attack of Sec.5.2 in [Pf94] does not work becausexj of a
faultyMIXj is revealed by using the (k;n)-threshold secret sharing scheme.
Let p and q be primes such that q j p?1. Let g 2 Zp be aq th root of unity. EachMIXj chooses a secret keyxj 2Z
q and publicizesyj =gxj modp as his public key. Further, he distributes xj to all MIXes by using Shamir's
(k;n)-threshold secret sharing scheme. He executes Feldman's non-interactive Veriable Secret Sharing [Fe87].
(Sender's protocol)
Each senderPi encrypts his messagemi as(Gi;Mi) = (grmodp;(y1y2
yn)rmimodp) He publicies (Gi;Mi) and proves that he knowsmi by using a ZKIP.
(Center's protocol)
For 1jn,MIXjreencrypts and shues (G 1;M1);;(Gl;Ml) sequentially. He proves that he behaved correctly by using a ZKIP.
(Decryption)
At the end, suppose thatMIXnpublicized ( ^G1;M^1);;( ^Gl;M^l). For each ( ^G;M^), eachMIXj computes
Gj= ^Gxj modp
and publicizes Gj. He proves the validity of Gj by using a ZKIP. Then the
plaintextmis obtained by
m= ^M=(G1 Gn)
If there are some faulty MIXes and someGjis not opend, the remained honest
MIXes reveal the corresponding secret keyxjby using Shamir's (k;n)-threshold
serect sharing scheme.
3 Ecient ZKIP for shue
In this section, we show a very ecient ZKIP for the center's protocol of Sec. 2.1. The communication complexity is 1=lof the standard ZKIP. A similar ZKIP can be obtained for that of Sec.2.2.
MIX1 wants to prove that eq.(3) is computed from eq.(2) correctly in zero knowledge. In eq.(2) and eq.(3), let
B(mi;Ri) = [ai;1;
;ai;n]
B(m(i);R(i)+U(i)) = [bi; 1;
;bi;n]
LetP denote a prover andV denote a verier. Repeat the steps 1 4 below log2N times.
(Step 1)
P randomly computes a reencryption of each B(mi;Ri) such thatB(mi;Ri+ ^Ui). Then P chooses a random permutation on f1;2;:::;lgand sends toV
[B(m(1);R(1)+ ^U(1));
;B(m
Let
B(m(i);R(i)+ ^U(i)) = [di; 1;
;di;n]:
P also bit commits and4
=?1. He sends the commitals toV.
(Step 2)
V sends toP a random biteand random numbersti (1il) such that 0ti< r.(Step 3)
P computes U0 4 = ( Pl i=1ti ^ U(i) ife= 0; Pl i=1ti(^U (i) ?U (i)) ife= 1 Letwj (1jn) be the random number which satisesEj(U0(j);w j) = ( Ql i=1(di;j=a (i);j) ti ife= 0 Ql i=1(di;j=b (i);j) ti ife= 1 (5)
{
Ife= 0,P sendsU0;w 1;;wn and the decommmital of to V.
{
Ife= 1,P sendsU0;w 1;;wn and the decommmital oftoV.
(Step 4)
V accepts if1. U0 is a polynomial of degree at most (k
?1) such thatU
0(0) = 0. 2. Eq.(5) is satised for 1jn.
Theorem3.
If eq.(3) is not computed from eq.(2) correctly, then Pr(V accepts in each round)1=2 + 1=2r for any (possibly cheating) prover.References
[Be86] J. Benaloh, Secret sharing homomorphisms: Keeping a secret secret , in:Proc. of Eurocrypt'86, 251{260 (1986).
[CF85] J.D. Cohen and M.J. Fischer, A Robust and Veriable Cryptographically Se-cure Election Scheme, in:Proc. of 26th IEEE Symp. on Foundations of Computer Science, 372{382 (1985).
[Ch81] D.L. Chaum, Untraceable Electronic Mail, Return Address, and Digital Pseudonyms, in:Communications of the ACM,Vol.24, No.2, 84-88 (1981).
[Fe87] P. Feldman, A Practical Scheme for Non-Interactive Veriable Secret Sharing, in: Proc. of 28th IEEE symposium on Foundations of Computer Science, 427{437 (1987).
[MH96] M. Michels and P. Horster, Some Remarks on a Receipt-Free and Universally Veriable Mix-Type Voting Scheme, in:Proc. of Asiacrypt '96, 125{132 (1996). [Pf94] B. Ptzmann, Breaking an Ecient Anonymous Channel, in:Proc. of Eurocrypt
'94, 339{348 (1994).
[PIK93] C. Park, K. Itoh and K. Kurosawa, All/Nothing Election Scheme and Anony-mous Channel, in:Proc. of Eurocrypt '93, (1993).
[PP89] B. Ptzmann and A. Ptzmann, How to Break the Direct RSA-implementation of Mixes, in:Proc. of Eurocrypt '89, 373-381 (1989).