• Non ci sono risultati.

Fault Tolerant Anonymous Channel

N/A
N/A
Protected

Academic year: 2021

Condividi "Fault Tolerant Anonymous Channel"

Copied!
5
0
0

Testo completo

(1)

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)

2.1 Proposed scheme based on factoring

Ther-th residue public key cryptosystem is de ned 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 if

c(p?1)=r= (y(p?1)=p)j

0 modp

This cryptosystem satis es 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:

De nition1.

For a plaintext m, choose a random polynomialR(x) of degree k?1 such thatR(0) =m. Let

B(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.

De nition2.

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

P tz-mann's attack against Chaum's MIX net [PP89].

(3)

(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

(4)

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 Veri able 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 veri er. Repeat the steps 1  4 below log2N times.

(Step 1)

P randomly computes a reencryption of each B(mi;Ri) such that

B(mi;Ri+ ^Ui). Then P chooses a random permutation  on f1;2;:::;lgand sends toV

[B(m(1);R(1)+ ^U(1));

;B(m

(5)

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 satis es

Ej(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 if

1. U0 is a polynomial of degree at most (k

?1) such thatU

0(0) = 0. 2. Eq.(5) is satis ed 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 Veri able 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 Veri able 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 Veri able Mix-Type Voting Scheme, in:Proc. of Asiacrypt '96, 125{132 (1996). [Pf94] B. P tzmann, 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. P tzmann and A. P tzmann, How to Break the Direct RSA-implementation of Mixes, in:Proc. of Eurocrypt '89, 373-381 (1989).

Riferimenti

Documenti correlati

A note on the similarity coefficient method and the problem of improper machine assignment in group technology applications.. Similarity coefficient algorithms for

The relationships of the unitary costs and labour input with slope, field area and altitude were described using the Curve Estimation procedure of PASW 17.0.2..

Department of Earth Sciences, University La Sapienza, Rome, Italy.. 15 Dept of Biological, Geological and Environmental Science (BiGeA), University of

However at the same process conditions, temperature, residence time and hence severity of reaction, HTC biochars show higher energy densification ratio than the LTP chars with a

EDITORIAL Traditionally, strategic management has been analyzed from an economic perspective, with approaches aiming at understanding the mechanisms underlying

Small enterprises should take advantage using these technological channels to increase the lyse the state of the art about the use of interactive and collaborative tools

Studi per Gian Paolo Marchi a cura di..

This pattern is evidence for the correlations between output and consumption, investment, hours worked, employment, unemployment, vacancies and the vu-ratio in response to the two