close

Вход

Забыли?

вход по аккаунту

?

el%3A19970980

код для вставкиСкачать
= 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
Документ
Категория
Без категории
Просмотров
2
Размер файла
299 Кб
Теги
3a19970980
1/--страниц
Пожаловаться на содержимое документа