Method for constructing a group- oriented cipher system Chu-Hsing Lin* and Chin-Chen Chang t
In this research note, we propose a solution to the problem of generalized group-oriented cryptography. By apply- ing the scheme presented one can send a confidential message to a group of users such that the message can be revealed only when the specified members coop- eratively work together. The organiza- tion and policy of the target group does not need to be known by the sender; only the public keys of users in the group are needed. The scheme pre- sented is quite practical, and can be used in a large group-oriented network.
Keywords: Diffie-Hellman's scheme, group-oriented cryptography, access structure, access instance
Group-oriented activities play an important role in society. Interac- tions among people within a speci- fic group or between different groups have to be controlled and managed carefully for reasons of privacy and security. In particular, secure messages communicated be- tween two groups should be handled with much more care so that only legal group members can access and reveal authorized mes- sages. The group-oriented crypto- graphy problem (GOCP) ~ refers to the study of ciphering methods for secure communication between
* Department of Computer and Information Science, Tung Hai University, Taichung, Taiwan 407, ROC t Institute of Computer Science and Informa- tion Engineering, National Chung Cheng University, Chiayi, Taiwan 621, ROC Paper received: 18 June 1993
groups. Applications include docu- ment distribution between compa- nies, governments, the military, information sharing and electronic mailing over different groups of users. It is not hard to see that applications of GOCP systems will become increasingly important in the near future.
Group Oriented Cryptography Problem
An encrypted message is sent to a group of users and can be decrypted only by a subset of users, according to the importance of property:
• urgent message: known by any- one in the group
• important message: known only when the number of members whom it is agreed can decipher it exceeds some given constant
• particular message: known only by particular members of the group,
In 1987 the concept of group- oriented cryptography was pro- posed by Desmedt 1. Another G O C P scheme based upon the RSA public-key system was presented by Frankel in 19892. It requires two trusted clerks in each group for the processing messages to be sent or received. Based upon Elgamal's public-key and Shamir's threshold scheme, Frankel 3 proposed another mechanism for GOCP in 1989.
However, their mechanisms still need a trusted clerk to distribute messages to the associated group members. Recently, Hwang 4 pre- sented an elegant method, combin- ing Diff ie-Hellman's key distribution and Shamir's threshold scheme, which can fulfil the require- ments of GOCP. Nevertheless, there are frequently cases when the sender needs to transmit an encryp ted message to a group in such a way that the message can be revealed only when some specific combina- tion of members in the group works together. To explain this idea more clearly, we demonstrate it with a simple example. Suppose there are five users, U1, U2, U3, U4, Us, in a group G. Let U0 be the sender who is sending an encrypted message to group G. U0 encrypts the message in such a way that only two possible combinations of users can reveal it. The first possibility is cooperation between UI and U2; the second is cooperation between U2, U3 and U4. Symbolically, the above situation can be denoted (Ui & U2) @ ((22 & U3 & U4). Unfortunately, none of the schemes described above can fulfil these requirements.
Generalized Group-Oriented Cryptography Problem 5
The conditions are as stated in the definition of the GOCP above. In addition the third class of message is extended as follows:
0140-3664/94/1110805-04 © 1994 Butterworth-Heinemann Ltd computer communications volume 17 number 11 november 1994 805
Constructing a group-oriented cipher system: C-H Lin and C-C Chang
particular message: known only by some specified combination of members.
In this research note we present a scheme for the generalized group- oriented cryptography problem (GGOP). The character of the scheme is that the sender can speci- fy the receivers to be any combina- tion of members in the target group. Further, a message is encrypted and transmitted so that only the speci- fied members are capable of deci- phering it.
and only if ~ii= I/i < /j+l for l < j < ~ n .
By the definition of a super- increasing sequence, we have the following proposition:
Proposition 15 Let I = {Ii, I2 , . . . , /~} be a sequence of superincreasing numbers. Let A = {ail, % . . . . . air}, where ai,'s are distinct elements from L and B = {bt~,bt2 . . . . ,bl,}, where bti are again distinct elements from I. If A ¢ B, then:
B A C K G R O U N D
In this section, we review the math- ematical background used. First, the definition of cross product opera- tion is extended so as to be suitable for the scheme presented.
s
j = l j = l
proof Obvious.
Diff ie -Hel lman's scheme
Cross product 6
Let Vi = (vit, V/z,. •., vi,) be n-dimen- sional vectors over GF(p). The cross product of n - 1 vectors Vt, V2 . . . . . and V,_ i over GF(p) is defined as:
V1 × I/2 × . . . × V,_t (modp)
I VI2 VI3
I V22 V23
\ l V n - 1,2 V n - 1 , 3
• . . V l n [ i
• • • V 2 .
• • • V n - l,nl
VII ~13
V21. V23.
I V n 1,1 V n - 1 , 2
• • • Vln I
• " " V2n I • ~•• , ,
• • • V n _ 1, nl
\ VII V12 . . . V l , n - t [~
i | V21 V22 • • • 122, n - In l
! • . . . .
II)n_ 1,1 I~n 1,2 - - " I ~ n - l , n - l l ]
(mod p)
where I x I indicates the operation of determinant•
Superincreasing sequence
A set o f n integers I = {It, 12 . . . . , I,} form a superincreasing sequence if
Further, let us review Diffie-Hell- man's key exchange scheme• Let p be a large prime number and p - 1 has at least one large prime factor. Let Z be a primitive element or generating element of GF(p). Let Xi and X2 be two distinct elements from GF(p), and let Y1 = (Z) x' (mod p) and Y2 = (Z) x2 (mod p).
Y1, II2, Z and p are made public and Xt and X2 are kept secret• The common key (CK) can be computed as follows:
CK = (Yi) x: (modp) = (Y2) x'
(modp) = (Z) x' x2 (modp)
The difficulty of breaking Diffie- Hellman's scheme has not yet been proved to be equivalent to that of computing the discrete logarithm• However, it is believed that to compute CK knowing only the pub- lic Yi, II2, Z and p is very difficult.
Since we use interpolating poly- nomials in the next section, we also briefly state how an interpolating polynomial (e.g. a Lagrange inter- polating polynomial) can be con- structed. (For general methods of constructing interpolating polyno- mials, see elsewhere8.)
Let there be n two-dimensional points with coordinates (Xi, Yi) where )(is are distinct, i = 1 ,2 , . . . , n.
A Lagrange interpolating polyno- mial with degree n - 1 passing through these n points can be con- structed as follows:
k = 1 j C k
(Xi~ - X#)) m o d p
where p is a prime number and all of the arithmetics are in GF(p).
Proposition 2 6
Let A be an m × 2 matrix, m/> 2, and any two row vectors of A be a full rank square matrix• Let p be a prime number and let VI and V2 be two m-vectors from GF(p). If
KI
K2. = A [ V l l (modp)
then Ki x VI = Cil(V1 × 1/2) (rood p) and Ki × V2 = ci2(Vi × Va) (mod p) for i = l , 2 , . . . , m , where K i = (kit, ki2, ki3) and cil and ci2 are some elements from GF(p).
Proposition 3 6 Let V1 × I/'2 (mod p) = ( d l , d2, d3), d i e 0 . Let Ki× Vk (mod p) = (el,e2, e3) and Kj× Vk (rood p) =(A, f2 , f3) , i C j and k = 1,2. If d ~ l , e l 1 and f~-i exist over GF(p), then (d2d~ 1 , d3d~ l) (mod p) = (e2ei -1 ,
-1 1 e3el I) (mod p) = ( f2f l , f3 f l ) (rood p).
It is not difficult to prove the above propositions now, let us illustrate these propositions with an example.
Example 1 Let:
A = 4 3
Let Vt = (1,2, 3), V2 = (2, 3, 4) and p = 17. We have:
I "' ],,'2: [123421 I', 2 3 3341 ( r o o d 1 7 ) = l l 1 8
8 13 1
806 computer communications volume 17 number 11 november 1994
Constructing a group-oriented cipher system: C-H Lin and C-C Chang
Then, we can obtain that V~ × V2 (mod 17) =(16 , 15, 16). Further Kl x V1 (mod 17) = ( 2 , 4 , 2 ) = 15(16, 15, 16) (mod 17) = 15(VlX /,I2) (mod 17). Similarly, we have Step 1 K2 x V1 (rood 1 7) = (4, 8, 4) = 13(16, 15, 16) (mod 17) = 13(VI x V2) (mod 17) and K3 x Vi (mod 17) = Step 2 (3,6,3) = 14(16, 15, 16) (mod 17) = 14(VI x I/2) (mod 17). Therefore, we can see that (15.16 -l , 16.16 -~) (mod 17) = (8.4-1,4-4 -I) (mod 17) = Step 3 (6-3 I, 3.3-~) (mod 17).
GENERALIZED GROUP ORIENTED SCHEME
Algorithm 1 ]Master key construction and message encryption for the sender]
Step 4
We present a mechanism to solve the problem of GGOCP. Let U0, U j , . . . , U, be n + 1 users in a net- work system. Assume that each user U~ has an identity number L such that the set {Ii,/2 . . . . . I,} is super- increasing. Further, Ui selects a private key X~ from the Galois field GF(p) and makes public the corre- sponding public key Yi = (Z) x' mod p, where Z is a primitive element of GF(p). Let U0 be the sender who sends messages to a Step 5 group of users. Let the group of users G--{Ul , / - /2 . . . . , U,} be the receivers. U0 encrypts a message and sends it to G, depending on the Step 6 importance or property of the mes- sage. Only the specified users in G can decipher the message. In gener- al, all possible combinations of users Step 7 who are specified for the message are represented by an access struc- ture, denoted F =J] @f2@--- @fro, Step 8 where . ~ = Ui,&Ui2&...&Ui, is an access instance. (An access instance f~ =- Ui,&Ui,&...&U~,. means that only when all users Ui~, Ui~ . . . . . Ui,. work together can they decrypt the received message.) An access struc- ture F = f l @ f 2 @ . . . @ f m means that the message can be decrypted by any one or more access instances f . , i = 1, 2 . . . . . m. In the following, we present a protocol for the sender and recipients under the constraint of the access structure specified by the sender. Note that throughout this research note, all arithmetics are in GF(p) and p is a large prime number with p > ~ = i li. Step 9
Randomly choose two row vectors Vi = (VI I , V¿2, 1:13)
and I/2 = (v21, v22, v23) such that Vl2.V23 ¢ v13.v22. Compute (dl, d2, d3) = Vi z V2 mod p, where '× ' de- notes the operation of cross product. Let the master key be M K = (ded~l ,d3dl I) rood p, where d~ -1 indicates the in- verse of di over GF(p). Choose an m x 2 matrix A, such that no two row vec- tors of A are proportional
sage M by the master key MK, C = EMK (M), where EMK is an one-key encryp- tion algorithm with the en- cryption key MK.
Step 10 Publish the access structure F, the polynomials (F0, FI, F2, F3) the vector Vl and the ciphertext C.
In the following we describe how the message can be revealed. On seeing the information published by the sender, the users Ui~, U o . . . , Ui~ in the access instance f can decrypt the message cooperatively using their secret keys without exposing them.
and compute: Algorithm 2 ]Message recovery for the access instance [i ] K2 = A V2 Step 1 Compute Si = ~ = l Ii~.
, S t e p 2 U~ evaluates Fo(I/), for j : il,i2 . . . . . i,..
where Ki = (kil, ki2, ki3) U~ computes a/ = Fo(Ii) • ((yo)XO -1 for j = il i,,
Assign Ki to the access i v .
instance f. for i = 1,2, Step 3 Evaluate Fl(Si). . . . . m. Compute Bil = (Yo) ( ~ / ~ / For each access instance
f i : U i , & U i 2 & . . . & U i , , i = a/) mod p. C o m p u t e kil : F1 (Si) •
1,2 . . . . ,m, compute S: = (Bn) -I modp. V
~ k : I li~. Step 4 Evaluate F2(Si). Randomly choose al, a2, Compute Bi2 = (Z) °" . . . . a, from GF(p). mod p. Compute b / = ( z ) a' mod p, Compute ki2 = F2 (S/) • f o r j = 1 ,2 , . . . , n. (Bi2) -1 mod p. Compute Bil = ((H/cl i bfl Step 5 Evaluate F3(Si). mod p, for each J~, i = 1,2, ComputeB~3 = (Z) sj2 modp.
. . . . m. Compute ki3 = F3 (Si) Construct the following in- (Bi3) -I mod p. terpolating polynomials F0, Step 6 Compute (dl,dz, d3) = (kii, F1, F2 and F3 ki2, ki3) × Vl mod p. F0(X) on the points (li, (ai Step 7 Compute M K = (d2d~ I, (Yi) xo) mod p)'s for i = 1, 2, d3d~ 1) mod p.
. . . , n . Step 8 Decipher the ciphertext C FI(X) on the points (Si, by M = D M x ( C ) , where (kil.Bil rood p))'s for i = 1, DMK is the associated de-
2 . . . . . m. cryption algorithm of EM/~ Fz(X) on the points (S~, with the decryption key (ki2.Bi2 mod p))'s, where MK. Bi2 = (Z) 8" (rood p), for i = 1 ,2 , . . . , m. It is not difficult to see, from the F3(X) on the points (Si, propositions stated earlier and Dif- (k~3.Bi3 rood p))'s, where fie-Hellman's scheme, that the Bi3 = (Z) s'' (mod p), for above algorithm works correctly, i = 1,2 . . . . ,m. i.e. users specified in an access Encipher the sending mes- instance can cooperatively decipher
computer communications volume 17 number 11 november 1994 807
Constructing a group-oriented cipher system: C-H Lin and C-C Chang
the message M. Now, let us inspect the message recovery procedure in Algorithm 2. In Step 2, a user Uj in the access instance J~ can obtain the value of aj by using his private key ~.. Moreover, the value of kil, ki2 and ki3 can be computed by sum- ming up these aj's together from Step 3 to Step 5. Finally, the master key M K is easily obtained, and thus the message can be deciphered. Note that the value of B/l computed in Step 2 of Algorithm 2 will be equal to that computed in Step 7 of Algorithm 1. This can be seen from Diffie-Hellman's scheme, and is stated as follows:
ego,) Bil = (Y0) J~ri modp
= H (Y°)a 'm°dp j¢.~
= I-I (bJ)x°m°dp jEfi
(n = b j m o d p m o d p ',je~
S E C U R I T Y A N D
C O M P L E X I T Y A N A L Y S I S
In this section, we analyse the security of the scheme presented. From Algorithm 2, we know that if someone can deduce the ith row vector, Ki = (ka,ki2,ki3), then he can compute the master key M K by Steps 6 and 7 in the algorithm. From Steps 2-5, to deduce the components of Ki one has to know all of the secret keys Xj. of users Uj in ft. First, let us consider the possibility of direct attack. I f an intruder wants to reveal the secret key ~ of Uj directly from the associated public key yj, he has to compute the discrete logarithm over GF(P). However, computing the dis- crete logarithm has been considered as a difficult problem when all of the factors o f p - 1 are large 9.
As indicated in the algorithm, there are v users specified in the ith access instance J~. Now, suppose there are v - 1 users who conspire to compute the value of Bil as in Step 3 of Algorithm 2. Without loss of general- ity, let these v - 1 users be
gi = { Ui2, Ui3, • , •, Uiv }. They have to guess an a'i, in GF((p) such that a'i~ + ~j~gi ay = ~-~jcf~ ay. The prob- ability of success in this case is equal to I/p, since the a~s are chosen randomly by the sender. Similarly, when v - k users conspire to compute Bil for 1 < k < v; it is required to select k numbers in GF(p) such that the summation of the total v numbers is equal to ~ jc j ; aj. However, it is no better doing it this way than simply guessing a number directly from GF(p) for Ba. Therefore, we may conclude that the probability of success by user conspiracy as stated above is no greater than lip.
Moreover, the sender can ran- domly choose two row vectors V1 and I/2. Then the construction of a master key M K is not interfered with by the secret key of any intended members in group G. Thus, there is no useful information that an in- tended member can reveal to deter- mine the secret key of any other member in the group. Further, for the construction of interpolating polynomials in Step 8 of Algorithm 1, the unintended members are ex- cluded. Therefore, an illegal member fortuitously recomputing the master key M K can thus be prevented.
Further, we consider the compu- tational and storage complexity of the presented scheme. First, we analyse the computational complex- ity, which relies on constructing and evaluating interpolating polyno- mials and computing the inverses of numbers over GF(p). For the con- struction of an interpolating poly- nomial of degree m requires m additions, 2m 2 + 2 subtractions, 2m 2 + m - 1 multiplications, m + 1 divisions; and one modular opera- tion to evaluate an interpolating polynomial of degree m requires m multiplications, 2m additions and one modular operation, if Honer 's rule is applied. Further, for the computat ion of the inverse of a number over GF(p), it needs (0.843.In(p)+ 1.47) division opera- tions, on average I°. Besides, the computat ion of matrix A in Step 4 of Algorithm 1 can be performed by O(m) multiplications.
Finally, the number of bits re- quired to represent the public para-
meters V1 and the three interpolating polynomials are 3 [ l og (p+ 1)] and m [ log (p+ 1)], respectively. Therefore, in total, the storage needed is proport ional to m [log (p + 1)], where m is the number of access instances.
C O N C L U S I O N
We have proposed a scheme for solving the problem of generalized group-oriented cryptography. The scheme does not require a clerk for processing messages received or sent. In general, the scheme can be applied to groups with any type of user structure and access policy. Further, the security analysis and computat ion and space complexity have also been presented. Finally, readers are encouraged to at tempt other attacks!
R E F E R E N C E S
1 Desmedt, Y 'Society and group oriented cryptography: a new concept', Advances in Cryptography: Proc. Crypto "87, Springer-Verlag, New York (1987) pp 120-127
2 Desmedt, Y and Frankel, Y 'Threshold cryptosystems', Advances in Cryptogra- phy: Proc. Crypto '89, Springer-Verlag, New York (1989) pp 120-127
3 Frankel, Y 'A practical protocol for large group oriented networks', Ad- vances in Cryptography: Proc. Crypto '89, Springer-Verlag, New York (1989) pp 56--61
4 Hwang, T "Cryptosystem for group oriented cryptography', Proc. Eurocrypt "90, Houthalen, Belgium (April 10-13 1990) pp 317-324
5 Chang, C C and Lee, H C 'A solution to generalized group oriented cryptogra- phy', in IT Security: The Need for International Security, North-Holland, Amsterdam (1992) pp 265-275
6 Wu, T C and Yeh, Y S 'A conference key distribution system based on cross- product', Int. J. Comput. & Math. with Applic., Vol 25 No 4 (1993) pp 39-46
7 Diffie, W and Hellman, M 'New direc- tions in cryptography', IEEE Trans. Infor. Theory, Vol 22 No 6 (November 1976) pp 644-654
8 Jain, M K, Lyengar, S R K and Jain, R K Numerical Methods for Scientific and Engineering Computation, Wiley East- ern, New Delhi (1985)
9 Pohlig, S and Hellman, M 'An improved algorithm for computing logarithms over GF(P) and its cryptographic signif- icance,' IEEE Trans. In for. Theory, Vol 24 (1978) pp 106--110
10 Denning, D E Cryptography and Data Security, Addison-Wesley, Reading, MA (1982)
808 computer communications volume 17 number 11 november 1994
