= e(al)(i = I, 2, ..., 2t). If R(x) has e (I t) symbol errors, then the syndrome values can also be written as: + + + Si = Y ~ Z : ~202: . . . Y,",: ( p = 1,2, ..., 2e) (1) where xJ is the location of thejth error symbol and I :is the corresponding error value. Lzmma 1131: (i) if e < t, then det(M,O) # 0 and det(M,O) = 0 (e < i 5 t); (ii) if e = t, then det(M,O) # 0. rsy S,W . . . s: 1 + + = (1 - ~ 3 ~ ~ 1 ) ( ~j =- i 1 1,i 2 , ...,e ) Using eqns. 6 and 7, II;" (j = 1, 2, ..., e) can be evaluated, (7) Calculate Calculate Evaluate Evaluate Total clock's xJ r, number syndrome o(x) [3]'s method n [4]'s method n - nt t2 n(t+l)+tZ 2t nt 2tz n(t+l)+ 2t(t+l) Our algorithm where det(M,O)indicates the determinant of matrix M,O; w indicates the wth iteration. Prooj (see 141). From Lemma I, we have the following corollary: Corollary: The rank of matrix M,O is equal to e (the number of xJ in eqn. I), and bears no relation to T (# 0). Let x be one of the symbol locations xt (i = 0, 1, ..., n-1) of R(x); we iterate the syndrome values as follows: SI = sz-1 - .-1si-' j+l = y z i y+12;+l . Y,iZi 3 3 ( j = 1,2, ..., 2(e - 1) 1) ( 3 ) + +.. + + = (1 - z 3 z - 1 ) ~ 2 - 1 ( j = i ,i i indicates ith iteration, 3 - l - + I, ..., e) (4) are calculated by using eqn. 3 when x xL+,. Lemma 2: (i) if x # xJ (j= i, i+l, ..., e), then det(M;_,,) + 0; (ii) if x = x,,j is one of (i, i+l, ..., e), then det(M;-,+,) = 0, det(MM;_,)+ 0. Prooj When i = I, comparing eqns. 1 and 3, we see that eqn. 3 is the same as eqn. 1 except for when TI + TO. (i) if x # xJ,then q1# 0 (j = 1, 2, ..., e) and the number of xj in eqn. 3 is e. From Lemma 1 and the corollary, we have det(M,l) # 0. (ii) if x = x,, without loss of generality, let x = xi. Since and # 0 (j = 2,3, ..., e), eqn. 3 can be written as: S: = ~ , ' z j 2 + ~ ~ x ( + . . . + (~j = ~ x1,2, ~ ..., 2e-1) Y,l =0 error symbols: (i) calculate 3 0 ('j = I , 2, ..., 2t); (ii) find out e; (iii) if e = 0, then R(x) = c(x), go to (xiv); (iv) store S,O; (v) let i = 1, k = 0; i indicates ith iteration; k indicates the kth symbol location of R(x); (vi) iteration: S; = 8 - l xk?;/ ('j = 1, 2, ..., 2(e-i)+l); (vii) compute det(M:_,+,); (viii)) if det(M:_,+,)f 0, according to Lemma 2, xk is not the location of any error symbol, are discarded, and go to (xiii); (ix) if det(M;_,+,)= 0, according to Lemma 2, xk is the location of an error symbol; (x) store SIi and k; (xi) if i = e, then go to (xiv); (xii) i = i + 1; (xiii) k = k + 1, go to (vi); (xiv) end. Calculate yo: - sf= Y p q + Y,OQ + + y,o2, s: = Yi22 + Y;Z3 + + Y,12, ' ' ' ' (6) sle-1 = y,"-lz, 14th August 7997 (n-t)t+ t(t+1)/2 nt+t t(t+1)/2 Conclusions: Our algorithm has two main advantages: (i) after every error location has been found out, the algorithm reduces the orders of the syndrome matrix by one, resulting in a decrease in decoding time. (ii) by S,' and x,,the error values yocan be easily calculated. Therefore, (see Table 1) our decoding algorithm performs faster for the same complexity than that in [3]and for lower complexity than the conventional decoding scheme in [4]. Because of the simplicity in structure and circuit realisation, the algorithm may be easily implemented in one chip by using VLSI technology. 0 IEE 1997 26 June 1997 Electronics Letters Online No: 19971005 Suming Ju and Guangguo Bi (Division 41, Department of Radio Engineering, Southeast University, Nanjing, Jiangsu 210096, People's Republic of China) References 1 CHEN,C.L.: 'High-speed decoding of BCH codes', IEEE Trans., 1981, IT-27, (2), pp. 254256 WEI, s.w., and WEI, c.H.: 'High-speed decoder of Reed-Solomn codes', ZEEE Trans., 1993, COM-41, (ll), pp. 1588-1593 3 YAO, M.Y.,and XIN, D.J.: 'A new method for decoding BCH codes', J. China Inst. Commun., 1989, 10, (S), pp. 10-14 4 WANG, X.M., and XIAO, G.z.: 'Error-correcting codes - Principle and method' (XIDIAN University Press, 1991), pp. 296323 2 How to prevent cheating in Pinch's scheme H. Ghodosi, J. Pieprzyk, G.R. Chaudhry and J. Seberry New algorithm: Using Lemma 2, we can determine all locations of ELECTRONICS LETTERS ~ (5) the number of xJ in eqn. 5 is e - 1. From Lemma 1 and the corollary, we have that det(M,') = 0, det(A4-J # 0. When i = m and we have found out (m-1) error locations xj ('j = I, 2, ..., m-I); the proof is the same as when i = 1. ' n Vol. 33 Indexing term: Security of data A modified protocol is proposed which prevents cheating in the Online multiple secret sharing scheme proposed by Pinch. Introduction: The goal of a secret sharing scheme is to distribute a secret among a group of participants in such a way that the secret can be reconstructed by designated subsets of participants. An important issue in a secret sharing scheme is that the reconstruction procedure must provide the valid secret to all participants from an authorised set. That is, a dishonest participant must not be able to fool the others so that they obtain an invalid secret while the deceiver is able to get the valid secret. This problem has been discussed by several authors (see, for example, [l 31). Cachin [4] proposed a computationally secure scheme for online secret sharing with general access structures, where all the shares are as short as the secret. The scheme provides the ability to share multiple secrets and allows us to add participants dynamically, without having to redistribute new shares. These abilities are realised by storing additional authentic information at a publicly accessible location. Pinch [5] points out that Cachin's scheme does not allow shares to be reused after the secret has been reconstructed without a further distributed computation protocol such as that of Goldreich et al. 161. Pinch presents a modified protocol for computationally secure online secret sharing, based on the intractability of the Diffie-Hellman problem, where shares can be reused. - No. 77 1453 In this Letter, we show that Pinch’s scheme is vulnerable to cheating. We then modify it to prevent cheating. cheating but does not detect the cheat(s) and also cannot prevent cheating. That is, the cheater(s) obtain the secret while the others gain nothing. Pinch’s scheme: M is a cyclic group of order q (written multiplica- tively) in which the Diffie-Hellman problem is intractable (that is, given elements g, gx and g y in M , it is computationallyinfeasible to obtain g x y ) and$ M 4 G is a one-way function. The group operations in G and M are addition and multiplication modulo a large prime p . The set P of participants is denoted by PI,..., P,,. Certain subsets X E 2p are authorised to recover the secret K. The family of minimal authorised sets of participants is denoted by r (an authorised set XI is minimal if XI c_ X,, and X, E r implies that XI = X2). Pinch’s protocol works as follows : The dealer D,who knows the secret K, randomly chooses shares s, (integers prime to q) for each participant P, E P and transmits s, over a secure channel to P,.For each minimal authorised set X E I-, 14 = t, the dealer randomly chooses g, to be a generator of M and computes and posts the pair (gx,T,) on the notice board. To recover the secret K, a minimal authorised set X = {PI, ..., Pi}of participants comes together and performs the followhg steps: (i) member PIreads g, from the notice board, forms g,”’ and passes the result to P,; (ii) each subsequent member Pz,for 1 < i < t, receives g;’..’I-’ and raises this value to the power si to form g2...siwhch is passed to P,+l; (iii) the final participant P, receives g2.’Sf1and raises this value to the power s, to form vx = - Q..St nz,x sz gx (iv) on behalf of the access set X , member P,reads T, from the notice board and reconstructs K as K = T, + f ( V,). If there are multiple secrets to share, then it is possible to use the same one-way function J; provided that each entry on the notice board has a fresh value of g, attached. Pinch also has a variant proposal which, according to him, avoids the necessity for the first participant PI to reveal gjl at step (i). PI takes r modulo q at random and forms g;l and passes the result to P,, and so on. At the end of protocol, P, returns the computed value g?””‘ to PI which computes vx . T.51.. S t TF1 = (gx (mod P) where rl is the inverse of Y , that is r x rl = 1 mod q (the other parts of the protocol are the same as the original protocol). How to cheat: Pinch‘s scheme has a major disadvantage in that it is vulnerable to cheating. In this scheme, a dishonest participant P, E Xmay contribute his fake share s’, = as,,where a is a random integer modulo q. Since every participant of an authorised set X (14 = t) has access to the final result g$ L‘ S t , the participant P, can calculate the value How to prevent cheating: Let C = CIS,g? correspond to an authorised set X.We assume that in the initialisation phase of the Pinch scheme the dealer also publishes C, = g:. Note that this extra public information gives no useful information about the secret or about participants’ shares. Otherwise, we could solve the discrete logarithm in M and easily solve the Diffie-Helhnan problem. Let X be an authorised set of participants. At the reconstruction phase, every participant P,E X computes g,”’ and broadcasts it to all participants in the set X. Thus, every participant P, E X receives t - 1 values g,”’ corresponding to all P, E X , PI f P,. Each participant computes C and verifies C, P gxc. If the verification fails, then the protocol stops. Let participants agree to perform computation in the cycle P I , ..., PI. If the check C, P gxc is successful, then each participant P, (i = 1, ...., t) knows the true value G2-I of its predecessor (PI is the predecessor of PI). So participant P,(i = 1, ..., t ) initiates the protocol by computing (g;-l)‘Land passing it to P,+r.The protocol proceeds as in the Pinch scheme and ends at P,2. In this way, the participant Pz-l cannot directly contribute to the computation which started by P,. Let there exist only one cheat, Pi(1 5 i I t) in the system. If P, cheats, the computation initiated by P,+, must be correct (the correctness can be verified as gxVx P g$, where V, is the result obtained by P,J. That is, although cheating has occurred, the honest set of participants can recover the secret. If there exists a group of collaborating cheats, then in the above protocol each participant must play (simultaneously) the role of P, for every other t , participants in the set X.Although the number of computations increases rapidly, before completing the protocol any possible cheating will be detected and the protocol will be stopped. At stagej (1 < j < t), for every set o f j (out of t) participants (without loss of generality, for PI,..., P,) there will bej! difaferent computations of g?’ -9. Hence, inequality of these values indicates cheating in the system. Moreover, assuming the majority of participants are honest (this is a reasonable assumption for any robust secret sharing scheme) the minority of participants who obtain values different from the common value in stage j , are the cheats. Remark: A group of m cheats can cheat the system at the first stage, that is, they can contribute with fake shares such that the resulting C is equal to the original one. However, the above protocol detects their cheating in next stages (there are at least 2m + 1 stages for such a set of collaborating participants). 0 IEE 1997 25 June 1997 Electronics Letters Online no: 19970980 H. Ghodosi, 3. Pieprzyk, G.R. Chaudhry and J. Seberry (Center for Computer Security Research, Department of University of Wollongong, N S W 2522, Australia) Computer Science, References and hence the correct secret as in Pinch’s scheme, while the other participants calculate an invalid secret. 1 2 How to detect cheating: Suppose in the initialisation phase of the Pinch scheme, the dealer publishes g T X (corresponding to every Let the reconstruction protocol be the same as authorised set 8. in the original Pinch scheme and let VG be the fmal result. Every participant x E X , can verify whether If the verification fails, then cheating has occurred in the protocol and thus the computed secret is not valid. This protocol detects 1454 and WOLL, H.: ‘How to share a secret with cheaters’, J. Cryptol., 1988, 1, (2), pp. 133-138 Remark: Cachin’s scheme is secure against this form of cheating, ,,, because in his scheme participants have no access to V, = .sC Thus, if a participant contributes a fake share, he cannot modify the result to obtain the valid secret (the function f is assumed to be one-way). TOMPA, M., 3 4 5 6 and GOLDWASSER, s.: ‘The detection of cheaters in threshold schemes’ in GOLDWASSER, s. (Ed.): Advances in Cryptol. - Proc. CRYPT0 ’88, Vol. 403 of Lecture Notes in Comput. Sci., (Springer-Verlag, 1990), pp. 564577 LIN, H., HARN, L., IMAI, R.R.H., and MATSUMOTO, T.: ‘A generalised secret sharing scheme with cheater detection’ in IMAI, R.R.H , and MATSUMPTO, T. (Eds.): Advances in Cryptol. - Proc. ASIACRYPT ’91, Vol. 739 of Lecture Notes in Comput. Sci., (Springer-Verlag, 1993), pp. 149-158 CACHIN, c., and BOYD, c . : ‘On-line secret sharing’, in BOYD, c. (Ed.): Cryptography and Coding: 5th IMA Conf., 1995, (Institute for Theoretical Computer Science, ETH Zurich), Vol. 1025 of Lecture Notes in Comput. Sci., (Springer-Verlag, 1995), pp. 190-198 PINCH, R.: ‘Online multiple secret sharing’, Electron. Lett., 1996, 32, pp. 1087-1088 GOLDREICH, O., MICALI, S , and WIGDERSON, A.: ‘ H O W to play any mental game’. Proc. Nineteenth ACM Symp. Theory of Comput., STOC, 25-21 May 1987, pp. 218-229 BRICKELL, E., STINSON, D., ELECTRONICS LETTERS 14th August 1997 Vol. 33 No. 17

1/--страниц