m M ti il N « a a a O Inform atica An International Journal of Computing and Informatics Special Issue: Cryptology and Network Security Guest Editors: Francesco Bergadano, Chuan-Kun Wu The Slovene Society Informatika, Ljubljana, Slovenia Informatica An International Journal of Computing and Informatics Archive of abstracts may be accessed at USA: http://, Europe: http://ai.ijs.si/informatica, Asia: http://www.comp.nus.edu.sg/ liuh/Informatica/index.html. Subscription Information Informatica (ISSN 0350-5596) is published four times a year in Spring, Summer, Autumn, and Winter (4 issues per year) by the Slovene Society Informatika, Vožarski pot 12,1000 Ljubljana, Slovenia. The subscription rate for 2002 (Volume 26) is - USD 80 for institutions, > : - USD 40 for individuals, and - USD 20 for students Claims for missing issues will be honored free of charge within six months after the publication date of the issue. ETjÄ Tech. Support: Borut Žnidar, Kranj, Slovenia. Lectorship: Fergus F. Smith, AMIDAS d.o.o., Cankarjevo nabrežje 11, Ljubljana, Slovenia. Printed by Biro M, d.o.o., Žibertova 1, 1000 Ljubljana, Slovenia. Orders for subscription may be placed by telephone or fax using any major credit card. Please call Mr. R. Mum, Jožef Stefan Institute: Tel (+386) 1 4773 900, Fax (+386) 1 219 385, or send checks or VISA or Eurocard card number or use the bank account number 900-27620-5159/4 Nova Ljubljanska Banka d.d. Slovenia (LB 50101-678-51841 for domestic subscribers only). Informatica is published in cooperation with the following societies (and contact persons): Robotics Society of Slovenia (Jadran Lenarčič) / - , : Slovene Society for Patteni Recognition (Franjo Pernuš) : : ' . Slovenian Artificial Intelligence Society; Cognitive Science Society (Matjaž Gams) Slovenian Society of Mathematicians, Physicists and Astronomers (Bojan Mohar) Automatic Control Society of Slovenia (Borut Zupančič) Slovenian Association of Technical and Natural Sciences / Engineering Academy of Slovenia (Igor Grabec) ACM Slovenia (Dunja Mladenič) Informatica is surveyed by: AI and Robotic Abstracts, AI References, ACM Computing Surveys, ACM Digital Library, Applied Science & Techn. Index, COMPENDEX*PLUS, Computer ASAP, Computer Literature Index, Cur. Cont. & Comp. & Math. Sear., Current Mathematical Publications, Cybemetica Newsletter, DBLP Computer Science Bibliography, Engineering Index, INSPEC, Linguistics and Language Behaviour Abstracts, Mathematical Reviews, MathSci, Sociological Abstracts, Uncover, Zentralblatt für Mathematik The issuing of the Informaticajoumal is fìnancially supported by the Ministry of Education, Science and Sport, Trg OF 13,1000 Ljubljana, Slovenia. Post tax payed at post 1102 Ljubljana. Slovenia taxe Percue. Special Issue on Cryptology and Network Security We have come to an age of information explosion. Information is useful in all aspects of our life, however, without proper management, to get the right information from the massive data is not an easy task. Fortunately computer networks, particularly the Internet, enables people to share information worldwide. The recent development of electronic commerce has extended the use of the Internet, and companies can do their business over the Internet. It has brought many conveniences to our everyday life. In spite of the conveniences that computer networks have brought to us, they also have brought many security problems: poorly designed algorithms, inappropriate use of security systems, inappropriate choice of passwords, inappropriate personnel management, and physical network destruction are all examples that information transmitted over the public networks are under threat. Some of the threats may cause data confidentiality problems, some may cause entity authentication problems, some may cause information integrity problems, and some may cause privacy problems. To eliminate these security problems, traditional legislation is not good enough, even newly added legislations covering electronic criminals are not sufficient enough to release people from having those concerns, because convincing evidence may be hard to get. It is realized that technical prevention and detection will continuously play an essential role in information security. Techniques for information security have been used for many years. Formal and overwhelming study on this topic started from the mid of the 20th century. It is just in recent years that those techniques are widely used in commercial activities. The fundamental techniques for information security are from cryptography, a science of designing algorithms for data encryption/decryption, digital signatures and hash functions which can be used in various areas. Cryptanal-ysis, on the other hand, focuses on finding security flaws of the designed cryptosystems. These fundamental cryp-tosystems serving as basic building blocks will be used to further design network security protocols, which are real applications to information security. The needs for information security today is almost everywhere if computer networks is a necessary component, and the study of information security is extensive worldwide. Many journals have included information security as one of their themes, and there are some new journals created in recent years that are particularly devoted to publishing papers on information security. Even though, there are still many good research papers that can hardly find an appropriate literature to publish. It is under this circumstances that we have selected 8 papers from the 2002 International Workshop on Cryptology and Network Security to form this special issue. Hope this excercise will somehow promote information security research. The 2002 International Workshop on Cryptology and Network Security (CNS02) was held in San Francisco, California, Sep. 26-28, 2002. It was the second time the workshop was organized with the same theme. The workshop accepted 18 papers out of 27 submissions. Each paper was sent to three referees (normally program committee members) for reviewing. Based on the review reports (rating of the papers and confidence of reviewers considered), 8 papers have been selected for publication as a special issue of Informatica - An International Journal of Computing and Informatics. These 8 papers cover new techniques in cryptography, cryptanalysis, key management schemes, water marking techniques, and secure web transaction protocols: A Complete Group Cryptographic System by Y. Mu and V. Varadharajan Group cryptography is a relatively new topic driven by the wide use of distributed systems. One of the important applications of group cryptography is group signatures. In a group signature system, any group member can create a signature on behalf of the group, where the validity of the group signature can be verified by the public having the group's public key (or keys). The group signature verifier cannot tell which group member created a particular signature, but in case of dispute, the signer can be identified internally within the group, normally by the group manager. Digital signatures (including group signatures) are often used together with data encryption. This paper proposes a new approach of integrating data encryption and group signatures together. This is of significance both in theory and practice. Cryptanalysis of Some Hash Functions Based on Block Ciphers and Codes by Hongjun Wu, Feng Bao, Robert H. Deng Cryptosystems are designed to have certain desired security strength. However, many cryptosystems are shown to be less secure than what was initially targeted. Even worse, some crypto algorithms have been broken not long after their publication, some even broken before their formal publication. This is not surprising as there is no theoretical warranty for any cryp-tosystem designed so far. Therefore, cryptanalysis is an important procedure for any cryptosystem before it is adopted for practical use. This paper gives a cryptanalysis of some particular hash functions designed using existing block ciphers and codes. Some weakness has been found, which means that those hash functions are not as secure as they were targeted. The flaws found can be of help in designing similar hash functions, or in design other cryptosystems using the similar techniques. Analysis of AES S-box with Walsh Spectrum by Baodian Wei, Dongsu Liu, and Xinmel Wang Cryptanalysis can be on a whole system, or part of the system, and this paper is the latter case. It is believed that S-box is a core technique in the security of symmetric key block ciphers, although a weak S-box may not necessarily mean the straight forward broken of the cipher. This paper presents a cryptanalysis on the S-box of advanced encryption standard (AES) that was adopted by the US in 2000. The cryptanalysis uses the technique of Walsh spectrum. Some cryptologic properties of the S-box are given in terms of Walsh spectrum representation. These results further supports that the Rijndael algorithm of AES has a good design. The paper also noted that further research needs to be done on how those Walsh spectrum properties can be converted into specific attacks with less effort than brute force attack. Practical Construction for Multicast Re-keying Schemes by Chun-yan Bai, Roberta Houston, and Gui-liang Feng Sometimes a new technique may result in unexpected research results. However, to explore an effective new method is not easy. Coding theory has been an overwhelming research area dominating Information Theory's research that started from Shannon's age. There have been many research results from the combination of error-correcting codes and cryptography. This paper uses Reed-Solomon codes and Algebraic-Geometric codes to construct re-keying schemes in multicast systems. Although more research needs to be done before implementation of the re-keying schemes in order to make them practical for large groups (e.g. in the application of video on demand), the method used in the paper is encouraging and appropriate. Multisecret Sharing Immune Against Cheating by-Josef Pieprzyk and Xian-Mo Zhang Secret sharing being a means of secret key management has been proposed for many years. In a secret sharing scheme, each participant has a piece of secret information (called share), and when some of them put their shares together, the original secret can be constructed. With smaller than the required group size, it is computationally infeasible to compute the original secret given their shares. However, in the case where a group of the share holders suppose to be able to recover the secret, if one of the participants is not honest and presents a random number instead of the correct share, then in secret recovery process, if all the others present their correct shares, the original secret cannot be recovered. However, the one who cheated can recover the original secret since the other shares have been given. In this case, although everybody noticed that someone cheated, no one knows who it was, except for the cheater itself. In light the possibility of cheating, cheating resistant secret sharing schemes would be more practical. This paper gives specific construction methods for multisecret sharing schemes that are immune against cheating. The construction is very technical but the approach is also practical. Digital Semipublic Watermarking by Valeri Korzhik, Guillermo Morales-Luna, Dmitry Marakov and Irina Marakova With the rapid growing of electronic commerce and web publications in recent years, protection of intellectual property of electronic documents becomes more and more subtle. Although there are legal procedures of accusing those who infringe the laws, technical process is still critical to gather the evidence of the infringement. One of the very effective techniques in protecting copyright of electronic documents is digital watermarking, and there has been large amount of study on this topic, particularly on images and multimedia documents. This paper studies the techniques for digital semipublic watermarking, where a new concept of "semipublic" is introduced. Robustness of the watermarking technique is analyzed. An Improved Anonymous Fingerprinting Scheme by Bo Yang and Yong Li Fingerprinting being another technique in copyright protection of electronic documents is also important. It can be used not only for visual documents as watermarking would, but also for other type of electronic documents including softwares. Using cryptographic approach to achieve fingerprinting normally involves large amount of computation. This paper improves one of the existing fingerprinting schemes by reducing the computational complexity significantly. This improvement has both theoretical and practical significances, though computers are becoming faster and faster. An Efficient Anonymous Fingerprinting Scheme for secure web transaction over Internet by Changjie Wang, Yumin Wang, Fangguo Zhang One of the important applications in electronic commerce is intelligent mobile agents. Since mobile agents are supposed to travel from one host to another over the network, in particular the Internet, and often they are out of control by the originator when they come to a foreign host, security issues associated with mobile agents become a big concern. Letting mobile agents to be communicating with the originator frequently would eliminate the chances of the agents to be tempered by a hostile host, but this would significantly reduce the mobility of the agents, and produces more traffic problems. This paper proposes a new scheme which is claimed to enable secure web transactions over the Internet. All these papers have variety of contributions to Cryp-tology and Network Security, which meets the theme of the workshop. Selection of the papers was not based on the area, it was based on the reviewers' comments only. There are also many other high quality papers which have not been selected for the publication by this special issue of the journal for various reasons. Continuous support from scholars to the workshop and the Journal is highly appreciated. Dr. Francesco Bergadano, Dr. Chuan-Kun Wu Special Issue Editors Appendix: Referees of the selected papers Francesco BERGADANO Kefei CHEN-Lily CHEN Dengguo FENG Guang GONG Ren-Junn HWANG Shin-Jia HWANG Chi-Sung LAIH Wei-Bin LEE Chin-Laung LEI Mitsuru MATSUI Yi MU Toshihisa NISHIJIMA Kouichi SAKURAI Chuan-Kun WU Tzong-Chen WU Xinmei WANG (Università di Torino, Italy) (Shanghai Jiaotong University, China) (Motorola, USA) (Chinese Academy of Science, China) (University of Waterloo, Canada) (TamKang University, Taiwan) (TamKang University, Taiwan) (National Cheng Kung University, Taiwan) (Feng Chia University, Taiwan) (National Taiwan University, Taiwan) (Mitsubishi Electric, Japan) (Macquarie University, Australia) (Hosei University, Japan) (Kyushu University, Japan) (Australian National University, Australia) (National Taiwan Univ of Science & Technology, Taiwan) (Xidian University, China) Group Cryptography: Signature and Encryption Yi Mu and Vijay Varadharajan Department of Computing, Macquarie University, Sydney, Australia Email: {ymu,vijay ) @ics.mq.edu.au Keywords: public key cryptography, group signature, distributed encryption Received: May 12, 2001 Traditional group signature schemes reflect only one side of the spectrum of public cryptography, i.e., signing, where the group public key is used for a sole purpose: verification of group signatures. This paper describes a new group cryptographic system that presents a promise for both signing and encryption. That is, besides verifications, a sole group public key can be also used for encryption and the associated decryption can be implemented by any member in the designated group. The proposed system meets all key features for an ideal group cryptography. 1 Introduction In practice, it may be necessary to construct a cryptographic group that possesses a unique group public key and each of its members possesses a private key associated with the group public key. Any member in the group can sign on behalf of the group and the signatures can be verified using the group public key. The group public key can be also used for encryption where encrypted message can be decrypted by any member in the group. We refer to this kind of systems as public-key group cryptography covering both Group Signature and Distributed Encryption. The concept of group oriented cryptography was actually introduced by Desmedt[7] in 1987, however from the best of our knowledge, there is no a compound scheme that includes both signature and encryption. The concept of group signatures was initially introduced by Ghuam[5] and then several major improvements have been proposed[6, 2, 3, 4], especially for Camenisch's Scheme[4]. All existing group signature schemes cannot be converted to include group oriented encryption. For example, the group signature scheme in [4] is based on the RSA signature scheme[ll], where the group certificate of a member is signed by the group manager using his RSA private key. Any member in the group can prove his/her membership without revealing his/her identification. Since the group public key is the group manager's public key whose associated private key is used to sign the group certificates of group members, the message encrypted using the group public key can be decrypted only by the group manager but not group members. It is found that using the RSA based method is infeasible for us to construct a group cryptographic system that allows encryption. We often refer to a group oriented encryption as distributed encryption. This is because the encrypted message is distributed to the group and all members in the group can decrypt the message. There are two such schemes were in- dependently proposed[l, 9]. Unfortunately, these schemes cannot be converted to include group signatures. In this paper, we present a new group public-key scheme where the group public key can be used for both encryption and signing. The proposed new group system is based on the ElGamal signature scheme[8]. The certificate of a group member is signed by the group manager using the ElGamal signature scheme. We will see later that our method is naturally associated with the ElGamal encryption scheme. The rest of this paper is arranged as follows. In Section 2, we give the model of our group cryptographic system. In Section 3, we construct some building blocks that will be later used in the construction of the group signatures and encryptions. In Section 4, we study the details of group signature scheme. In Section 5, we show how to use the group public key to encrypt a message. In Section 6, we propose some potential applications based our scheme. We then conclude the paper in Section 7. 2 Model Like a normal group signature system, there is a designated group that consists of a manager and a group of members M. - Group Manager: The group manager has a pair of personal private and public key. The group manager's personal public key is also the unique group public key. The group manager's private key is used to sign group certificates of group members. The certificates are associated with group members' private keys. The group public key can be used to encrypt a message and all legitimate group members can decrypt it. The group public key is also used to verify a group signature from any member of the group. - Group Members: A member Mi £ M can prove to any party that its certificate is indeed signed by the group manager. Every member has a private key known to itself only. The exponential function of its private key is signed by the group manager and the resultant signature token is the group certificate of the member. This private key can be used to sign on the group's behalf and decrypt a message encrypted with the group public key. The signer of a group signature is anonymous to all parties involved except the group manager. There is a revocation algorithm that allows the group manager to find out who is the signer of a group signature. There are seven major algorithms in our system: (1) The algorithm of key generation that produces a pair of group manager's private and public key as well as the private keys group members. (2) The algorithm of certificate signing that takes an exponential function of a group member's private key and the private key of the group manager as input and produces an ElGamal signature as output. (3) The group signature algorithm that takes a message and the private key of a group member as input and produces a branch of signature knowledge proofs based on the ElGamal algorithm. (4) The verification algorithm of group signatures that takes the signature knowledge proofs as input and produces a boolean value, true or false. (5) The encryption algorithm that takes a message and the group public key as input and produces a ciphertext based on the ElGamal encryption. (6) The decryption algorithm that takes the ciphertext and a group member's private key as input and returns the original message. (7) The revocation algorithm that takes a signature knowledge as input and returns the identity of the corresponding signer. The proposed group cryptographic system meets the following requirements: - Robust. The size of the group public key is independent of the number of group members. Therefore, the number of members can be increased without changing the group public key. - Group member anonymity. Any verifier of a group signature cannot find who is the signer, but he knows that the signature definitely comes from one of members in the designated group. - Group member untraceability. If a group member has generated two group signatures, the verifier cannot find any connection between them. - Revocation. Group manager can find who is the signer of a group signature when needed. - Non-repudiation. Group manager cannot sign on behalf of any group member, therefore the signer cannot deny his action of signing. 3 Preliminary and Building Blocks In this section, we give the definition of signature knowledge proofs of discrete logarithms. We consider three building blocks. The first two proofs were given by Camenisch[2], but used under our requirements. The third one shows a more efficient version of signature knowledge proof of double discrete logs. We follow the Camenisch-Stadler setting[4] assuming that there is a cyclic group G = {g) of order n. There exists h G Zn such that g'^' for some x exists (x is the smallest value). 3.1 Signature Knowledge Proof of a Discrete Logarithm The first signature knowledge proof involves only a single discrete log. The signer/prover has a pair of secret and public key {x,y), where y = g"^ for g e G and X e Zn- We also assume a collision resistant hash function H : {0,1}* {0,1}^ where é is the length of a hash value. This signature knowledge proof is equivalent to a Schnorr signature[2, 12]. Definition 1 A pair (c, cr) € {0,1}* x Z„ satisfying c = H{m\\y\\g\\g'^y'^) is a signature of knowledge of discrete logarithm of the element y 6 2* to base g on message m 6 {0,1}* and is denotedSKLOG[x : y = This discrete log proof shows that the signer knows the value of the secret key x, i.e. x — log^ y, but reveals no additional information to the verifier. In the signing/proof process, the signer chooses an integer r Gr "Ln and computes c H{m\\y\\g\\g^) and a = r — ex. Obviously, the proof can only be generated when knowing the value of x. The verification is done by computing the hash value c and ? checking the equality g^ = g'^y'^. 3.2 Signature Knowledge Proof of Representation of Discrete Logarithms We will use Camenisch and Stadler's definition of signature knowledge of representation[4]. Definition 2 A signature of the knowledge of representation of y and z to base gi and g2 (in G) on message m is denoted as follows SKREP[(ai,Q2) :y = g^^Az = g^^g^] The signature consists of a triplet (c, si, S2) 6 {0,1}^ x Z^ satisfying c = H{m\\gM\yUgnz'g{'g'2') for Si = r\ — cai (f^ «2 = — ca2. □ This is used for proving the discrete logarithm of y to the base gi and a representation of to the base gi and 52, and that the g2-part of this representation equals the discrete logarithm of y to the base gi. The signing procedures are as follows; - Compute a = = and 02 = yj^ for ri,r2 £R - Compute c = H{7n\\gM\y\\gl'\\gl'g?). - Compute Si and S2, which can be done by the signer/prover only. To verify the signature knowledge, the verifier needs to compute c = fr(m||5i||52||2/||a||aia2) 9 7 and verify: a = y^gl^ and 0102 = z'^gl^g^. In our system, signature knowledge proofs require un-traceability, i.e., a proof should have no any traceable link with the previous proof. This can be done by simply using a different base for every proof, i.e. replacing g with g^, where r -is a secret random number known to the prover only. It can be easily applied to SKLOG. 3.3 Signature Knowledge Proof of a Double Discrete Logarithm We also need to use the knowledge proof of double discrete logarithms[]3, 4]. The proof algorithm is based on a cut-and-choose method. Here, we give a much more efficient method without using the cut-and-choose. Let X be the secret key and z = g^, where y = h^ that is then given to the verifier. Definition 3 A pair (c,a) £ {0,1} x Z„ satisfying c = H(m\\g\\h\\h'^\\{g'^'')^"') is a signature of knowledge of double discrete logarithms of the element y to bases g and h on message m E {0,1}* and is denoted by SKLOGLOG[a; : z = g''']. In the process of a proof, the signer - picks an integer r at random, - computes the hash value c = fl"(m||g||/i||/i''||z), - computes a — x - rc. To verify the signature proof, you compute the hash value ? c = H(m||g'||/i||/i''|l2;) and check the equality = It is clear that the signer cannot cheat in a proof, since the hash value c ensures that the signer cannot change the value of hJ'. 3.4 Security of the ElGamal Signature Scheme Let fc Sfi Z„ be a secret key of a signer and z = g'' he its corresponding public key. To sign a message to, the signer selects an integer 7 Gr Z„, computes his signing commitment a = g'', and then C = (to - ak) modn. The ElGamal signature consists of the triplet (a, C, m). To verify the signature, you check whether or not the following equality holds: = The original ElGamal signature scheme is existentially forgeable[ 10]. It suffers from the so-call one-parameter and two-parameter forgeries. The problem can be fixed by using a cryptographic hash function, but it is not suitable for our case. Fortunately, in our system, the message m is an exponent; therefore those forgeries do not apply to our system. Lemma 1 Given the tuple {z,a,C,m) and m is an exponent, it is computationally infeasible to find a' a), C C), m' m) in probabilistic polynomial time such ' C' ' that the verification equality still holds: z°- a' = . The proof is easy once we understand the forgeries. The reader is referred to Ref. [10] for the detail. 4 Construction of a Complete Group Cryptographic System In our scheme, Alice signs Bob's group certificate using ElGamal signature scheme rather than the RSA. This eliminates the need of using e-th root knowledge proof of discrete logarithms that is quite inefficient and enables a compound scheme of signature and encryption. 4.1 Setup The group public key consists of a doublet, (zx ,22), where zi = and Z2 = . h and /c2 are the corresponding secret keys known to Alice only. The signing key for Alice is fc = fci -f ^2 and her corresponding signature verification key is z = ZiZ2- Each member of the group is issued with a group certificate signed by the unique group manager, Alice. Suppose Bob is a member of the designated group. To obtain his group certificate, Bob selects an integer x and computes y = h'^ mod n as his group key, where x is the secret known to himself only and y is sent to Alice. Alice then signs y — 1 using the ElGamal signature scheme to form Bob's group certificate, C — - 1 - afc) modn, where - 7 is a large random number known to Alice only. Note that 7 is unique to Bob. - a = is Alice's signing commitment. - y and C are known to Alice and Bob but not others. Bob's group key y along with a are used by Alice to construct Bob's decryption key d = g^z^, which also satisfies d = for suitable rji and 772, where y -I- kia ^ Vi + ^2^72 — 7 under modulo n and the difference between them must divide n. Note that it is easy for Ahce to compute d, since she has the values of ki and ^2, but computing d by any one else is equivalent to solving a discrete logarithm problem. Lemma 2 The setup of group member's decryption key is secure and collusion-resistant. Proof: This is because it is impossible for group members to find ki and k2 from available information. For Bob, by using his information, he can establish an equation intending to find ki and y + kia = ?7i -I- /22^2 — 7 + A, where A is the product of an integer and a factor of n. Noting that 7 is unknown to Bob and is unique to Bob, the number of equations to solve ki and k2 by collusion is always less than unknown variables. □ At the end of setup process, Bob obtains his signed group certificate C along with the tuple {x, y, a, d, Tji, 7^2) as his secret keys (including C), where x is Bob's signing key known to Bob only. Therefore, No one else including Alice can sign for Bob. 4.2 Signing Protocol To sign a message m E Z„, Bob does the following: - Selects 9 E fi Z n as the blind factor used for the current signing to make the signature knowledge untraceable. - Blinds the base, g = g^. - Blinds the group public key, ž = 2®. - Blinds the Alice's signing commitment, ä — a^. - Computes ui = U2 = à^, U3 = g'^'. - Prepares the proof of equality: guiu^ = U3, which is equivalent to an ElGamal signature verification, provided that the following proofs are true. - Proves ui(a) o U2{a), which denotes that a of ui divides à of «2- Computes u"^ = ž"'^"'"' . - Prepares the proof: So = SKLOGLOG[^ : f^']for5 = C + 9-\ - Prepares the following signature knowledge proofs: - Si = SKREP[(0, a, C) : A In this proof. Bob proves his knowledge in the following discrete logarithms: 6 = logg g, logg g = logj ž, a = log^ ž", and C = log,àC - 52 = SKLOGLOG[a; : usjim) These proofs can be executed only by a legitimate group member - in our case. Bob, because only he knows x and his certificate, y — I, which has been signed by Alice. In the SKREP verification, g®, aP should be known to the verifier. This differs from the original proof, but maintains the same functionality (in fact this proof is stronger). The signature tuple consists of {m,g,g,a,ž, U1,U2,U3, So, Si, 52). The verification protocol is as follows: — Verification: - Compute: u"^. - Verify: Wi(a) U2(a). - Verify: So,Si,S2. 7 - The verifier verifies the equalities, guiu2 = U3. Completeness: The verification of 5i shows that the same blind parameter and correct bases have been used on the left side of the verification equation. The verification of 52 shows that Bob has the knowledge of some values (a and C) on the left side of the equation, whereas he does not know that Bob has used the correct value of a. So can be verified by the verifier, showing that Bob indeed knows the value of a; = logg(log;j M3). Soundness: Bob cannot cheat in the signing process. Bob can only prove that 1/ - 1 has been signed by Alice, but not anything else. The lemma below supports this point. Lemma 3 There exists no a variant ofy (say, y') such that both y and y' satisfy equation guiu2 — U3. Proof: Two cases should be addressed. First, let e be an integer in such that g'^u\u2 = ^3. Since the base g (in this case, g'^) is pubhc, the base for proof So must be Second, let 9 be the product of two integers, 9i and Ö2. Let us see if it is possible to make a new funcfion y' by combining y with Ö2 and using 61 as the blind parameter. The verification equation now looks like this: = where the tilde represents for the base A. However, due to the discrete log problem, it is impossible to solve the equation Ö2 (y — 1) +1 = 1;' for 1;' = h^ mod n to find a;'. □ The proof of the lemma above actually implies that the blind fact 9 does not impact the correct verification of Alice's signature on y — 1. That is, the verification equality, guiu2 = U3, is equivalent to the normal ElGamal verification, gz'^a^ = gy. This property is the exact one we want. along with So forms a complete ElGamal verification that ensures the correctness of the signature knowledge proof. Lemma 4 Proving ui (a) U2 (a) ensures that ui and U2 are correctly constructedfrom the ElGamal verification the signature knowledge proof is unique. Proof: It is obvious that is an original ElGamal verification if we write it in the form z^a*^' for C = 9C. In fact, since we are ensured by 5i and g in the verification equation — g^ that a common blind factor 9 has been used, is of the exact ElGamal verification. To make the equality gz'^a'^ — g^ and discrete log proofs So,Si,S2, one has to use one of two ways: (1) having correct values of Alice's signature C, a, y and x, and (2) having the value of Alice's secret key k. There is no a third method that constructs a legitimate signature for Bob. Assume that Eve is a cheater who does not have C and a issued by Alice. It is easy to see that it is impossible for her to construct a correct equality. In fact, it is easy to see that Eve cannot find suitable A and B, which lead to correctly constructing Sq, in the forged verification equation, z^A^ = g^, where C is not a function of k. Although Eve can easily find A = {g'^/ž^)'^ , to product the proof knowledge Sq, Eve has to find out X from BA = A^. This is a discrete log problem, since A is a function of B. □ We would like to stress the following properties that have been mentioned in Section 2. Only Bob can sign the message, no one else including Alice can do so on his behalf. This is because only Bob has the value of his private key X. The signature knowledge proofs are not linked to any other proofs, since blind factor 9, which is used only once for a particular signature, is introduced to make the proof data different from other signature knowledge proofs. The group certificates of members are based on the ElGamal signature scheme. Since every member has a different signature commitment, a, using for the associated certificate, according to the proven security of ElGamal signature scheme, it is impossible for any group members to collude in order to find the group manager's administration key, k. 4.3 Revocation of a Signature Having shown that the proposed group signatures are untraceable and unlinkable, we now show that as the group manager Alice can find out who actually signed a group signature. This is because Alice knows group keys of her members. To find the signer (say, Bob), she checks the ? equality,, = U3, by trying a member's group key y picked from her database till finding a match. However, this method is not efficient in a large group. Luckily, our scheme can be easily modified to suit a large group without making any substantial change in the signing procedure. To sign a message. Bob computes A = y{6 — 1) and encrypts g^ using A to obtain the ciphertext g^g^ along with S2 <- z^. Note that g^g^ = g^^ = U3. Bob must prove that g'^ is indeed encrypted correctly by using the discrete log knowledge proof of representations: SKREP[(2/,A) Note that since 6 is used once only, and A as an encryption parameter is used once as well. This makes the signature unlinkable and untraceable. Alice can decrypt to obtain g^ by removing g^, i.e., gy = 5-\_ j82 . This therefore reveals the identity of the signer. 4.4 Distributed Encryption The public key doublet, (2:1,22), can be used for encryption and an encrypted message can be decrypted.by any legitimate member in the group using its decryption key. Bob's decryption key d is constructed using his signing key, d = gyz1 ord = g'^'Zi'^'/a. The encryption steps are as follows: - Select a number, r Er Zn- - Compute the ciphertext, = mzl, along with U2 = 22'" andfx = g''. Bob decrypts the ciphertext by: - Computing ujlfiy = m'^g^'^^'^'+y^ = m'^d'' and LO. - Removing d^ and a from m'^d'^ to obtain m. Any one can encrypt a message using the group public key, but only a legitimate member in the designated group can decrypt and obtain the message. The Completeness of the protocol is obvious. If the message is correctly encrypted, it can be decrypted by any member in the group. The soundness of the protocol lies in the security of decryption keys. In the Setup section, we have proved that the setup of decryption keys is secure and collusion-resistant. 4.5 Conclusion We have proposed a novel group cryptography that includes both signing and distributed encryption. >From the best of our knowledge, our system is the first such system ever proposed. The novel group cryptography has some potential applications to electronic commerce. For example, in a bank a group of bank staff should be able to sign or issue the bank files such as billing electronic letters on the bank's behalf, while at the meanwhile they should be also able to receive and handle electronic payments encrypted using the unique bank or group public key. References [1] D. Boneh and M. Franklin (1999) An efficient public key traitor tracing scheme, Adances in cryptology - CRYPTO '99, Lecture Notes in Computer Secience 1666, Springer Verlag, Berlin, pp. 338-353. [2] J. Camenisch (1997) Efficient and generalized group signatures, Adances in cryptology ■ EUROCRYPT'97, Lecture Notes in Computer Secience 1233, Springer-Verlag, Berlin, pp. 465^79. [3] J. Camenisch and M. Michels (1998) A group signature scheme with improved efficiency, Advances in Cryptology-ASIACRYPr98, LNCS 1514, Springer-Vertag, Beriin, pp. 160-174. [4] J. Camenisch and M. Stadler (1997) Efficient group signature schemes for large groups, Advances in Cryptology, P roc. CRYPTO 97, LNCS 1296, Springer-Verlag, Berlin, pp. 410-424. [5] D. Chaum and E. van Heijst (1991) Group signatures. Advances in Cryptology, Proc. EUR0CRYPT9Ì, LNCS 547, Springer-Verlag, Berlin, pp. 257-265. [6] L. Chen and T. P. Pedersen (1994) New group signature schemes. Adances in cryptology - EUROCRYPT'94, Lecture Notes in Computer Secience 950, Springer-Verlag, Berlin, pp. 171-181. [7] Y. Desmedt (1987) Society and group oriented cryptography: A new concept. Advances in Cryptology, Proc. CRYPTO 87, LNCS 293, Springer-Verlag, Berlin, pp. 120127. [8] T. ElGamal (1985) A public-key cryptosystem and a signature scheme based on discrete logarithms, Advances in Cryptology, Proc. CRYPTO 84, LNCS 196, SpringerVerlag, Beriin, pp. 10-18. [9] Y. Mu, V. Varadharajan, and K. Q. Nguyen (1999) Delegated decryption, Procedings of Cryptography and Coding, Lecture Notes in Computer Science, Springer Verlag, Berlin, pp. 258-269. [10] D. Pointcheval and J. Stem (2000) Security arguments for digital signatures and blind signatures. Cryptology, 13(3) pp. 361-396, [11] R. Rivest, A. Shamir, and L. Adelman (1978) A method for obtaining digital signatures and public-key cryptography, Communications of the ACM, 21(2) pp. 120-126. [12] C. P. Schnorr (1990) Efficient identification and signatures for smart cards, Adances in cryptology - CRYPTO'89, Lecture Notes in Computer Secience 435, Springer-Verlag, Beriin, pages 239-251. [13] M. Stadler (1996) Publicly verifiable secret sharing, Advances in Cryptology, Proc. EUROCRYPT96. LNCS 1070, Springer-Veriag, Beriin, pp. 190-199. Cryptanalysis of Some Hash Functions Based on Block Ciphers and Codes Hongjun Wu, Feng Bao and Robert H. Deng Institute for Infocomm Research 21 Heng Mui Keng Terrace, Singapore 119613 {hongjun, baofeng, deng} @i2r.a-star.edu.sg Keywords: cryptanalysis, hash function, block cipher, codes Received: June 2, 2002 At PKC 2000, Inoue and Sakurai proposed some methods to design hash functions from block ciphers and codes (block codes and convolutional codes). They claimed that their hash functions are secure: encryptions are necessary to find a collision, where d and m are the minimal distance of the code and the block size of block cipher, respectively. However, we show in this paper that a collision could be found with about a ■ 2™ encryptions, where a is a small number. 1 Introduction A hash function is a one-way function that maps an arbitrary-length message into a fixed-length quantity. It plays important roles in integrity protection, authentication and signature generation. There are two basic requirements on a secure hash function, namely, the collision resistance property (that it is hard to find two messages with the same hash result) and the preimage resistance property (that it is hard to find a message corresponding to a given hash result). There are two approaches to design hash functions. One approach is to design customised hash functions, such as the MD4 [10], MD5 [11] and SHA-1 [3]. Another approach is to design hash functions based on some existing secure crypto algorithms (most likely, some block ciphers). A number of hash functions based on block ciphers have been proposed. The construction of single-block-length hash functions (the size of the hash result is the same as the block size of the block cipher) has been studied extensively and a synthetic study on this issue was done by Preneel, Govaerts and Vandewalle [9]. The drawback of this design is that for block cipher with small block size m, the hash function is not secure since a collision could be found with only about operations due to the birthday attack. The multiple-block-length hash functions are thus needed. But it is not easy to design a secure and efficient multiple-block-length hash function. Some proposed multiple-block-length hash functions are proved to be insecure: the MDC-4 [1] were broken by Knudsen and Preneel [8]; the Parallel-DM [4] was broken by Knudsen and Lai [6], Some multiple-block-length hash functions remain secure but with relatively poor performance [7, 8]. Inoue and Sakurai recently proposed some multiple-block-length hash functions and claimed that their hash functions are secure and efficient [5]. However, as will be shown in this paper, their hash functions are not as secure as they claimed. We believe that with the emergence of large block size block ciphers, such as the Rijndael with flexible block size up to 256 bits [2], the design of secure and efficient block cipher based hash functions could eventually be simplified. This paper is organised as follows. Section 2 gives an introduction to Inoue and Sakurai's hash functions. The cryptanalysis of Inoue and Sakurai's block code based hash functions and convolutional code based hash functions are given in Section 3 and Section 4, respectively. Section 5 concludes this paper. 2 Inoue and Sakurai's Hash Functions Most of the hash functions are in iterated form, i.e., they are based on the iterative computations of an easily computable compression function h{-, •). The function h{-, •) compresses two binary sequences of respective lengths m and an I into a binary sequence of length m. The message M is denoted as t /-bit blocks, M = (Mi, M2, • • • , Mt) (In case the length of M is not multiple of I, padding is used). The hash result H = Ht is obtained by computing iteratively Hi = h{Hi_x,Mi) i = l,2,---,t, where Hq is a pre-specified inifial value. The compression function of a block cipher based hash function is constructed from a block cipher. In the rest of this paper, we consider only the block cipher with equal key length and block size since Inoue and Sakurai's constructions are based on this kind of block cipher. To construct a compression function/i(-, ■) with m-bit output from a block cipher with m-bit block size, the following Davies-Mayer function could be used: where both Mi and Hi are m-bit binary sequences. To construct a hash function with n • m-bit (n > 1) hash result from a block cipher with m-bit block size, the following multiple Davies-Meyer function could be used. Definition 1 (Multiple Davies-Meyer Function). Let Ek{-) be a block cipher with m-bit block size and key length. Let /ii, /i2, ■ • • , /i« be different instantiations of the Davies-Meyer function, i.e., hi{Xi,Yi) = Exi{Yi) © Yi, obtained by fixing [log2n] key bits to different values. The Mi and Hi are expanded by an affine mapping to the n pairs {Xi,Yi). The output is the concatenation of the outputs of the function hi,h,2,--- ,h„. To construct a compression function h based on the multiple Davies-Meyer function, the main task is to design the affine mapping. In Knudsen and Preneel's work [7, 8], non-binary codes are used. Recently Inoue and Sakurai introduced the block codes as well as the convolutional codes in designing the affine mapping [5]. In Inoue and Sakurai's affine mapping, the input are k m-bit message blocks (Mi) and n m-bit blocks of the previous iteration output but only the message blocks M» are encoded. Their design are given in the following two subsections. 2.1 Construction with Block Codes The input to the affine mapping are the k m-bit message blocks (Mi) and n m-bit blocks of previous hashed value The fc-block Mi is encoded into n m-bit blocks, denoted as Ci, with the use of an (n, k, d) error correction code. From Hi-i and Ci, form n input pairs to those n different Davies-Meyer functions. A typical example in [5] is given below: Example 1. Consider the (7,4,3) Hamming code with the following generator matrix: 0 = 10 0 0 0 10 0 0 0 10 0 0 0 1 a hash function constructed from an {n,k,d) code in this way, about encryptions are required to find a col- lision. 2.2 Construction with Convolutional Codes Let the convolutional code be with parameters (n, k, d; N), where n, k, d and N denote the output size, input size, minimum distance and constraint length, respectively. The length of a message is padded to multiple of km bits. Then {N — l)km zero bits are padded to the message. The message after padding is denoted as (Mi, M2, • • ■ , Mt), where each Mi is a fcm-bit block. The input to the compression function h{-,-) are (Mj_Ar+i,--- ,Mj) and the n-block Hi-i. The (Mi-AT+i, ■ • • , Mi) is encoded into an n-block code word, Ci — (Ci,i, Cj,2, ■ ■ ■ Ci,n) with the use of an (n, k, d\ N) convolutional code. From ffj-i and Ci, form n input pairs to the n different Davies-Meyer functions. The final hash result is the concatenation of the last N iterations' outputs {Ht-N+i,--- ,Ht~i,Ht). We give a simple example below to illustrate the operation of this kind of hash function. Example 2. Consider a simple (2,1,3;3) binary convolutional code. For each output, the following generator matrix is used: " 1 1 1 1 0 1 1 1 G = Let Mi = (Mi,i,Mi,2,Mi,3,Mi,4), where Mjj is an mbit block. Mi is encoded as Ci — (Cj,i, Ci,2, • • ■ , Cij), where Cij - Mij for j = 1,2,3,4, and Ci,5 = Mi,I ® Mi,2 ® Mi,3 Ci,6 = Mi,2 ® Mi,3 ® Mi,4 Ci,7 = Mi,i © Mi,2 © Mi,4 Let Fi_i = (ili_i,i,ili_i,2, • • • and i^i = {Hi,\, Hi,2,- ■ ■ , Hi,i). Hi is obtained as follows: Hi,j = hj{Hi_i,j,Ci,j) j = 1,2, ■■■J The other block codes with higher error correction capability could also be used. It was claimed in [5] that for (Mi_3,Mi_2,Mi_i,Mi) is encoded into Ci = (Ci,i,Ci,2) where Ci,i = Mi_3 © Mi_2 © Mi Ci,2 = Mi_3 © Mi_2 © Mi_i © Mi Hi is obtained as follows: Hi,j = hjiHi^i,j,Ci,j) j = 1,2 The concatenation of the outputs of the last three iterations are the final hash result. It was claimed in [5] that for a hash function constructed from an (n, k, d; N) convolutional code in this way, about 2(d-i)m/2 encryptions are needed to find a collision. 3 Attack on the Hash Functions Based on Block Codes Inoue and Sakurai claimed that about encryp- tions are needed to find a collision of their hash functions based on block codes [5]. In this section, we give an attack to find a collision with only about d ■ 2™ encryptions. The flaw in Inoue and Sakusai's design is that the differences introduced into the n-block hash output do not affect one another in the following iterations, i.e., there is no difference propagation. It allows us to deal with those differences separately. Our attack is based on the following assumption: Assumption 1. Consider a Davies-Mayer function h{X,Y) = Ex{Y) ® r, where Ek{-) is a block cipher with m-bit block size and m-bit key length. For two randomly chosen Y and Y' with Y ^ Y', an X satisfying h{X, Y) =: h{X, Y') exits with probability 0.368. The following attack is to find two different messages M and M' satisfying Hash{M) = Hash(M'), where the hash function is based on an (n, k, d) block code. 1. Find a A;-block AMi so that (n - d) blocks of its n-block code word are with value zero. The positions of those non-zero blocks are denoted as £ = (ei, 62, • • • , Cd), where 1 < Ci 0, then />(/(;,) = w' . =->-^^ = Pifix) = » ' ~ •^(Z)'^"' ^ - p(f{x) = w . It indicates 2 that w'«a:ìs the best linear approximation of f(x) . If , then P{f{x) = w'»x + l) = - >-= w .^ + 1)>-= P{f(x) = w" »x) . It implies that w»x + \ is the best linear approximation of f(x). Two types of Walsh spectrum both have some relation with the properties of Boolean fianctions as summarized in Theorem 2. Theorem For the n-tuple Boolean function f{x), (1) fix) is balanced if and only if 5'y(0) = -j or (2) Identity two kinds of linear structure set C/}"' and U'-p with {a I fix) + fix + a) = 0) and {a\f{x) + f{x + a) = 1} respectively. We have that a e Uf^ if and only if for any weGF(2") and wa= \ , S^J■^iw) = Q . We also have that a e Uf if and only if for any we GF(2" ) and w • a = 0, S^^^iw) = 0. (3) Nonlinearity of fix) ,Nf = 2"~\\- Max «ec/--"(2) OV Nf=2''-\\-Max{l Max | /-^Cw)U 1-2x5';r(0)|}) . HeG/''"{2)/{0} By the definition, 5^(w)=-(|{x€G/^2")|/(x) = w.x}| (4) /(;,) is a Bent function if and only if for any -1 {x6 GF{2" ) I fix) ^ w.x} I) (21 {x£ GF(2") I /(x) = w*x)\-2") = —il"-\[xzGFi2")\fix)^y^*x)\) .That is to 2" say that type- II Walsh spectrum shows how much fix) is close to the linear function wx . The idea is described in the following theorem. Theorem If w,xeGFir) and fix) is a n-tuple Boolean function, then Pifix) = wx + \) = Pifix) '"•^(Z)^'"^ ^ where P(») is the probability. w€ GF(2"), 5'(y)(w) = +2 2 or Sj iw) = • ~ ^ ^ '""" ±2 2 -l/2,w = 0 ( 5 ) fix) satisfies SAC if and only if for any «€ GFiT) and W„ia) = 1, = « ■ »s/i- (6) fix) safisfies PC for a e GF(2")\{0} if and only if aieGF"(2) aeGF"(2) (7) fix) satisfies PC of degree k if and only if for any ae GF"(2) and \ t. Member-joining is easy to handle by just encrypting the new session key with the old session key which is decrypt-able by all old members and sending the new session key individually to each new member encrypted by their own secret keys. So we just focus on the member-leaving case and assume that there is a group controller(GC) who knows all the system keys in this paper. The initial study on the secure multicast communication can be traced back to the early 90's [1]. And a lot of works had followed [2,3,4,5,6,7,8,9]. All in all, the work can be divided into two major groups, one of which [2,3,4,5] uses the concept of key tree structure to set up the new session key based on the Diffie-Hellman key agreement. In [2], Wallner proposed a scheme which requires only 0(n) = 0(n 4- (n - 1)) keys for GC, = 0(d +1) keys for each user and have at most = 0{kd - 1) trans- missions overhead per single eviction. The requirement is further improved in[3,4,5] which greatly reduces the transmission and storage complexity of re-keying schemes. Another stronger property of the tree structured scheme is that it allows the number of excluded users k to be arbitrary, rather than fixed in advance. But some balanced tree structure based schemes have the disadvantage of not providing collusion prevention. The other group makes use of the broadcast encryption idea proposed by Fiat and Naor[6]. The broadcast encryption scheme enables the GC to communicate data secretly to dynamically changing authorized users while preventing any coalition of users to learn anything about the data. Other studies on broadcast encryption schemes can be found in [7,8] and [9]. In [7], the concept of the Perfect Hash Family(PHF) is reviewed and proved to be useful for the secure new session key distribution. The possibility of using the error corrècting code to construct such a scheme is given there without providing any practical and detailed construction. Hartono et.al. [8] borrows the idea of Key Distribution Pattern (KDP), based on which the broadcast encryption scheme that can remove up to t users from a group of n users and is secure against collusion of t malicious users can be set up. How to use the error correcting codes to construct such a KDP is not discussed. In [9], Poovendran and Baras show that by assigning probabilities to member revocations, the optimality, correctness and the system requirements of some of the schemes in [6,7,8] can be systematically studied using information theoretic concepts and also show that the optimal average number of keys per member in a secure multicast scheme is related to the entropy of the member revocation event, thus provides a way for us to inspect each scheme from the theory point of view. 2 Related Work Review Assume that there is a set of users U, a group controller GC and a set K of Key Encrypting Keys (KEK) that is generated and stored by the GC. Session keys are used for group member communication. A user m will have a subset of Key Encrypting Keys, K{ui) C K. KEKs are used to update the SK in the event of membership change due to any of the following reasons: (a) a new member admission, (b) expiration of the SK, (c) member compromise, (d) voluntary leave, and (e) member revocation. We only consider the last case, member revocation in this paper. The secure group communication requires KEKs to securely distribute the updated SK. If every member has an individual public key, for a group consisting of n members, the SK update will involve 0{n) encryptions by the GC. The linear increase of the required number of encryptions in group size is not suitable for very large scale applications common in Internet, due to the amount of computational burden on the GC. Next, we will review two scalable re-keying schemes which can reduce the number of encryptions. 2.1 Re-keying Scheme Based on PHF A re-keying scheme called OR scheme in [7] specifies an algorithm by which the GC produces a common session key for the group U\W without letting those users in W to know the new session key, where W C U. The scheme is as follows: 1. Key initialization : The GC generates and stores a set K of KEKs and securely gives Uj the set of his KEKs K(ui) C K. 2. Broadcast : To remove a set of users W from U, the GC randomly chooses a session key and encrypts it with those keys not belonging to W, then broadcasts the encrypted messages to all the users. That is, the GC broad- casts keK,k^ K{W),K{W) = UjewK{uj)}. 3. Decryption: Each user Ui £ U \ W uses one of his own KEKs k S K {m) to decrypt E^ik""^^) and obtain the new session key k^'^^. We review the concept of PHP here for the completeness of this paper. Let n and m be integers such that 2 ' w \ „ {N - d), thus can be used for the construction of the above re-keying scheme. Such a scheme can prevent w users from colluding. The performance of the re-keying scheme based on PHP is determined by the parameter N when w and m are fixed, which should be minimized to reduce the storage and transmission complexity. But the author didn't mention any details on which kind of error correcting code should be used and how it is used for the construction. 2.2 Re-keying Scheme Based on KDP In [8], H. Kumio reviewed the concept of Key distribution Patterns(KDP). Let X = {xi,X2,..;Xn} and B = {Bi,B2,-.^B^} be a family of subsets of X. The pair {X, B) is called an (n, N, i)-key distribution pattern if mnB^) \ uU-BsJ|>i for any {t+ 2)-subset {i, j, Si,..., St} of {1,2,..., A''}. With the idea of KDP, the author presented a theorem to show the existence of a multicast re-keying scheme with dynamic controller based on KDP. But how to effectively construct KDP is still an open problem. Inspired by the work from [7] and [8], we look at the problem of multicast re-keying from the error-correcting codes point of view in this paper. In order to achieve constructions with feasible storage that do not require computational assumptions, we make an improvement on the constraints that must be satisfied to construct the broadcast encryption scheme in[7,8] by avoiding the requirement of being PHF and KDP. Based on the OR model mentioned above and assumed a system with GC, we give two practical construction of schemes based on Reed-Solomon codes and avoid any computational assumptions. Conditions underlining the constructions are also given together with examples to show the detail constructions. Kumar et.al. [10] also consider the blacklisting problem through error-correcting codes, but their method is quite different from ours. 3 Multicast Re-keying Scheme Based on R-S Code 3.1 Background on Code Let GF{q) be a finite field. Definition 3.1 (Linear Code) An [m, k, d] linear code is a k-dimensional subspace Vm,k of m-dimensional linear space Vm over GFq, where the minimum Hamming distance between any pair of elements is d. Reed-Solomon code is an important kind of linear block BCH codes which had been widely used in such areas as space communication systems, spread-spectrum communication systems and computer storage systems. Definition 3.2 (Reed — Solomon Code) Let Xi,...,Xm € GF{q) be distinct and k > 0. The {m,k)g Reed-Solomon code is given by the subspace {{f{xi),...,f{x,n))\f e whereGFg,k denote the set of polynomials on GF{q) of degree less than k. R-S code is a Maximum Distance Separable (MDS) code, which means that the error-correcting capability of the R-S code can reach the Singleton bound. The RS code has the property that the (m, fc), R-S code is an [m, k,m — k -\-'\]q linear code and it requires that m < q. 3.2 R-S Code Based Construction In the key initialization phase, The GC generates and stores a set of Nq keys defined as K = | h G H,b e B}. For a user Uj, 1 ■w*{N — d), then Ui has at least one function that is different from all those functions belong to W. That is, there exists a function ha S H such that {ha{j)\j = ii,Ì2, are all distinct. It follows that ismK{ui) C K{U\W),soUi can decrypt the encrypted message and obtain the new session key □ The theorem holds for any set L of members who wants to leave the original group as long as \L\ < w. Example 3.1 Take the {N, k, d) = (4,2,3) RS code over finite field G F {A) = GF{2'^) = {0,l,a,a2}. The primitive element a is the root ofx^ -I- a; -I-1 =0. From theorem 3.] we know that, if 3.2.1 First Construction Theorem 3.1 Let (TV, k, d) be a Reed-Solomon code over GF{q), where N is the length of the codewords, k is the length of the information bits and d is the minimum distance of the code. The number of the codewords n = q''. Let W be a subset of {1,2,..., n} with \W\ = w. Then such an error-correcting code can be used to construct a multicast encryption scheme as long as it satisfies that N >'w*{N-d). Proof: Let T be the set of codewords of a {N, k, d) code, |T| = n. We write each element of T as (ca, Ci2, •••, Cìn) with dj e {l,2,...,q], where I < i < n,l < j < N and n is the number of codewords. For each j we define a function hj from A = {!,...,n} to ß = {!,...,9} by hj{i) = dj and \siH= {hj\j = 1, ...N}. N - w{N -d)>0, then there exists a broadcast encryption scheme based on such a RS code, which means that w < jf^ = = 4. Since k = 2, the information sequence is m = (mi,m2). The codewords, that is KEKs for all users corresponding to all possible information sequence is shown in Table L 3.2.2 Discussion 1. From [7], it is also known that any (N,k,d) error correcting code gives rise to a PHF(N,n,m,w) which is proven to be effective to set up the multicast encryption scheme. C.Y. Bai et al. 1712 n^i h(0) h(l) h{a) h{a') Ui 0 0 0 0 0 0 U2 0 1 1111 U3 0 a a a a a U4 0 a'^ c? a^ a^ a'^ Us 1 0 0 I a oi^ UQ 1 1 1 0 a^ a U7 1 a a a^ 0 1 Us 1 a^ a 1 0 Ug a 0 0 a a^ 1 UlO a 1 1 a^ a 0 Uli a a a 0 1 a^ "12 a 0? a^ 1 0 a Ul3 0 0 a^ 1 a Uli 1 I a 0 a^ "15 OL^ a a 1 Q^ 0 "16 a' a' a^ 0 a 1 Table 1: User KEKs constructed from (4,2,3) R-S code There, it requires that the minimum distance of the error-correcting code d' satisfies that d' > w 2 - 1 iV \ That is,the minimum d' that satisfies the above inequality is ' ' ' w 2 -1 iV + 1. While here, from the above theorem, since N >w*{N-d), the minimum distance d has to satisfy that d > ( 1 - wj N. That is, the minimum d that satisfies the above inequality is U) — 1 d = -N VJ + 1. then from we get w < N ui{N - d) ^ 8 > 3(8 - 6). 3.2.3 Extension of the Scheme In order to improve the communication efficiency, the OR scheme we discussed can be slightly modified with erasure code such that the bandwidth used by the GC for broadcasting information can be reduced. An [n, k, m] erasure code is a special class of error-correcting codes that allow recovery of a message if part of its messages(< {n — m)) are damaged or erased during the transmission. An erasure code can be constructed using Reed-Solomon code over finite field GF{q). The decoding procedure uses k pairs of {ei,pv{ei)) to recover the original k information messages, where ej is one of the field element overGF(g) andp(a;) = + is the polynomial for the R-S encoding. The broadcast encryption scheme described in Theorem 3.1 can be modified as follows. In the broadcast phase, before broadcasting the new session key , an encoding procedure is first applied to the new session key. The new session key k^^"^ was divided into t pieces ku\w ^ then encodes them using [Nm^ t, a] erasure code to obtain the codeword = (ci,c2,...,cjvm). The GC uses all the KEKs that do not belong to the users of W to encrypt the corresponding components of and broadcasts the encrypted messages to all the users. That is, the GC broadcasts {Ek,{ci)\kieK,ki^KiW)}. As long as each non-excluded user has at least a keys that can decrypt a messages of {Eki (cj)}, he can then apply the erasure code to obtain the new session key. While for those users in W, same as before, they can not find the session keys. Theorem 3.2 The above scheme works as long as the following inequality holds: N - w{N -d)>a. For an [n, k, m] erasure code over GF{q), we expect k to be as large as possible in order to minimize the extra bandwidth n/k for the transmission. Actually, the basic scheme we discussed in Theorem 3.1 is a special case of using [n, 1,1] erasure code for the construction. Example 3.3 Consider the same example as in Example 3.1: the RS code iN,k,d) = (4,2,3) over finite field GF(4) = GF{2'^) = {0, l,a,a2}. The primitive element a is the root ofx^ + a; +1 = 0. The KEKs for all users corresponding to all possible information sequence is shown in Table 1. For the above scheme to work, it needs that that is, that is. N -w{N -d) > a, 4-w(4-3) > a, 4 — w > a. For a = 1, w can be 1,2 or 3. For a = 2, w can be 1 or 2. And for a = 3, w can only be 1. We take w = 2 and a = 2 as an example. We divide the new session key k'-'^^ into two parts = then encodes using a [16,2,2] erasure code to obtain a codeword C(fc^V^) = (ci(0),c2(l),c3(a),...,ci6(a")), where and Ci{ei)=p{ei),eieGF{lQ) Then a broadcast encryption scheme can be constructed which can remove up to w users from a group ofn users. In this scheme, The GC generates and stores a set X of KEKs in the key initialization phase, and sends each user Ui a subset [/j C [/ of X as the user's KEKs. When a set of users W want to quit from the group, the GC selects a new session key and encrypts the session key with all KEKs except those belong to users in W, that is, GC broadcasts {EkAk^""^) lkreX\(U,,UU,,...UUsJ}. So, those users in W can not decrypt the encrypted message. While, since for Vui that Ui E X\W, it has at least one key that does not belong to W, so it can decrypt E/,^ {k^^^'^) and obtain the new session key k^^^. >From the theorem we know that for any given w and n, we should make n* as small as possible. Same, for any given w and n*, we hope n to be as large as possible. Next, we will show how to use Reed-Solomon code to construct the KEK set X and U and how the scheme works. 3.3.2 R-S Code Based Construction We take the R-S code {N,k,d) over the finite field GF{q) = {0,1, a,...a''"^}. The number of users n = The RS codeword č of length N is generated from k information symbols taken from the finite field GF{q) through polynomial h{x) = Too + mix + m2X^ + ... p{x) = ko + kix. Suppose any two users W = {uj^,u^^}) 1^1 — 2 want to leave the group, the GC uses all the KEKs that do not belong to this two users to encrypt all these 16 pieces of encoded keys and broadcasts the encrypted messages to all the users. Then each user that is not in W has at least 2 keys to decrypt 2 messages, thus can recover the original new session key. 3.3 Second R-S Code Based Construction In [8], Hartono proposed a broadcast encryption scheme based on the KDP(Key Distribution Pattern) which can be used for dynamic GC. If the GC is fixed in the system and is trustable, then the condition for the scheme can be improved to make it work for general case. 3.3.1 Scheme Description Theorem3.3 Let X = {xi,x2, ...Xn'} be a set of KEKs, U = {Ui,U2,-.,Un} be the set of users' KEKs, which is a family of subset of X, that is, for 'ii, Ui C X. Let W = be a subset of U with = w. lffor\fi, it satisfies that: where TO = (TOo,mi,...mfc_i) and C= {CO,Cl,...,Cg-l) For each user ui, the KEK set that corresponds to the k information symbols Wi = {mii,mi2,...mik) is where \Ui\ = q = N. So, the KEK set for all users is U = UUUi. The total KEK set X for GC is X = {Xi, i = l,2,...,n*}, where n* = N * q = q^, and Xi = {{h,ß) I h € {h{0),h{a),/i(q«-1)}, ß e GF{q).] Next, we will use an example to show the exact procedure on the RS-code construction of the scheme. Example 3.4 Take the same example as in Example 3.1: that is the {N, k, d) = (4,2,3) RS code over finite field GF{A) = GF{2'^) = {0, l,a,Q2}. The primitive element a is the root of x^ + x + 1 =0. The KEKs for all users corresponding to all possible information sequence is shown in Table 1. After extending the users' KEKs by use of the way shown in section 3.3.2, we obtain the KEKs set X = {Xi,i = 1,2,..., 16} as shown in Table 2. >From Table 2 we can see that, = {a;i,a;5,a;9,a;i3} = {(/ll,0),(/l2,0),(h3,0),(/l4,0)} U2 — {x2,X6,Xio,Xu} = {(/11,1), (/12,1), (/13,1), (/14,1)} = {(/ii,a),(/i2,a),(/i3,a),(/i4,a)} Ui = {a;4,a;8,2;i2,a;i6} U5 = {xi,x6,a;ii,xi6} = {(/ii,0),(/i2,l),(/i3,a),(/i4,a')} Ui6 = {i4,a;5,a;ii,a;i4} = {(/ii,a2),(/i2,0),(/i3,a),(/i4,l)}. All the KEKs hold by the GC is given by: Suppose there are w — 2 users who want to quit from the group {ui,u2,..., Wie}, ^'^y users W = {«7,^8}, we can check that for each user Ui 0 W, For example. So such a set of KEKs can be used to implement the broadcast encryption scheme. 4 Construction of the Scheme Using A-G Code Since the R-S code over GF{q) requires the length of the codewords N < q, we can not make the codeword longer than q. Using Algebraic-geometric code(A-G code), the scheme can be extended to the case when codeword length N > q. Next we will show an example on how to use A-G code to construct the OR model for the multicast re-keying scheme. 4.1 A-G Code For those who are interested in more details about A-G code, please refer to the paper [11] and [12]. 4.2 Example of A-G Code Based IVIulticast Re-keying Scheme Let us consider the Hermitian code over GF(4) = GF(2^) with k = 2. The Hermitian curve over GF(2^) is x^ + y'^ + y = Q. The curve has rational points: {(0,0),(0,l),(l,a),(l,a2), (a,a),(a,a2),(a^a),(a^a2)} {((3:i,t/i), (0:2,2/2), (2:3,2/3), (3:4,2/4), (3:5,2/5), (3:6,2/6), (3:7,^7), (3:8,2/8)}- Let code polynomial be c{x) = mo + rriix, it has 16 codewords: Č = (c(a:i,?/i),0(0:2,2/2),0(2:3,2/3),0(0:4,2/4), 0(3:5,2/5), c(a:6,2/6), 0(2:7,2/7), o(x8,2/3)) All the codewords, that is, the KEKs set are shown in Table 3. In this example, c{x) has at most 2 zero points, d = 8-2 = 6. since g = 4, AT = 8, d = 6, the number of users n = q'^ = 16, the number of keys isA^*9 = 8*4 = 32. For the OR multicast re-keying scheme to work, it requires that N > wiN-d), that is, 8 > ?i;(8-6), so w can be 2 or3. Since w can be 3, from A'^ ——d) = a, we know that a can be 2. 5 Conclusions In this paper, two practical constructions for Multicast Re-keying Schemes using Reed-Solomon Codes are given with examples to show the detailed construction procedure. Because it has many properties we expected, RS code provides us a practical way to construct the multicast re-keying hi hi hi hi /12 h2 h2 h2 h3 h3 h3 h3 hi hi hi hi 0 1 a a' 0 1 a 0 1 a 0 1 a Xi X2 Xi a;5 xe x-r Xs Xg XlO xn Xl2 Xl3 Xii Xl5 Xl6 Ui 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 U2 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 U3 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 U4 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 U5 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 U6 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 U7 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 Us 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 Ug 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 UlO 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 Uli 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1 Ul2 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 Ul3 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 UlA 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 «15 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 M16 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 Table 2: Construction of Re-keying scheme with (4,2,3) R-S code. m2 Till h(0) h(l) h(a) h{a') Ul 0 0 0 0 0 0 0 0 0 0 U2 0 1 0 0 1 1 a a Q'^ a'^ Us 0 a 0 0 a a a' a' 1 1 Ui 0 a' 0 0 a' a^ 1 1 a a U5 1 0 1 1 1 1 1 1 1 1 Me 1 1 1 1 0 0 a^ a^ a a U7 1 a 1 1 a a 0 0 Us 1 a' ] 1 a a 0 0 a^ UQ a 0 a a a a a a a a UlO a 1 a a a' a' 0 0 1 1 Uli a a a a 0 0 1 1 Ui2 a a' a a 1 1 a'^ 0 0 Ul3 a' 0 a' a' a'^ a'^ a'' a a Uli a' 1 d' a' a a 1 1 0 0 Uli a' a a' 1 1 0 0 a a Uie a' 0 0 a a 1 1 Table 3: User KEKs constructed from (8,2,6) A-G code. scheme efficiently. The storage complexity and transmission complexity have been reduced at the same time, which is another advantage of the method proposed in this paper. Because this paper is only an initial work for using RS-code in constructing the re-keying scheme, a lot of work is being done and will be done in die future such as how to improve the communication transmission efficiency by encoding the new session key with error correcting code first, how to deal with multiuser and multistage leaving from the group, how to handle when a new user is joining, but the members in the group has reached the maximum, how to apply AG code instead of RS code in the construction to improve the performance, how to make the GC be a group member also, how to extend these two schemes to apply for the distributed environment and so on. References [1] S.Berkovits. How to Broadcast a Secret. Advances in Cryptology - EUR0CRYPT'91, Lecture Notes in Computer Science 547, p535-541,1991; [2] D.M.Wallner, E.J.Harder and R.C.Agee. Key Management for Multicast: Issues and Architectures. In-tenet Draft, September, 1999; [3] C.K.Wong, M.Gouda an dS.S.Lam, Secure Group Communication using Key graphs. Proceedings of SIGCOMM'98, p68-79, 1998; [4] A.Perrig, Efficient Collaborative Key Management Protocols for Secure Autonomous Group Communication. CrypTec'99, Hongkong, December, 1999; [5] I.Chang, R.Engel, et.ai. Key Management for Secure Internet Multicast using Boolean Fnction Minimization Techniques. WFOCOM'99,September, 1999; [6] A.Fiat and M.Naor, Broadcast Encryption. Advances in Cryptology - CRYPT'92, Lecture Notes in Computer Science, vol.773, p481-491,1993; [7] S.Naini R. and H.Wang, New Constructions for Multicast Re-Keying Schemes using Perfect Hash Families. 7th ACM Conference on Computer and Communication Security, ACM Press,p228-234,2000; [9] R.Poovendran and J.S.Baras, An Infomiation Theoretic Analysis of Rooted-Tree Based Secure Multicast Key Distribution Schemes. IEEE Transactions on Information Theory, May, 1999; [10] R.Kumar, S.Rajagophlan and A.Sahai, Coding constructions for blacklisting problems without computational assumptions. Advances in Cryptology -CRYPTO'99, Lecture Notes in Computer Science, p609-623,1999; [11] G.L. Feng and T.R.N. Rao, Decoding Algebraic Geometric Codes up to the Design Minimum Distance. IEEE Transaction on Information Theory, vol.1, No.l,p37-45,Jan. 1993; [12] G.L. Feng, V.K. Wei, TR.N. Rao, and K.K. Tzeng, Simplified Understanding and Efficient Decoding of a Class of Algebraic-Geometric Codes. IEEE Transaction on Information Theory, vol.40, No.4, p981-1002, Jul. 1994; [8] H.Hamio, R.S.Naini, W.Susilo and H. Wang, Key Management for Secure Multicast with Dynamic Controller. Information Security and Privacy, 5th Australasian Conference, ACISP'OO, Lecture Notes in Computer Science 7847, pl78-190,2000; September, 1998; Multisecret Sharing Immune Against Cheating Josef Pieprzyk and Xian-Mo Zhang Centre for Advanced Computing - Algorithms and Cryptography Department of Computing Macquarie University Sydney, NSW 2109, AUSTRALIA E-mail: josef, xianmo@ics.mq.edu.au Keywords: Secret Sharing, Multisecret Secret Sharing, Cheating Immune Secret Sharing Received: May 19, 2002 Cheating in multisecret sharing is considered. Multisecret sharing Is defined by a mapping F: —> that provides a generic model. In this model, we propose nonlinear multisecret sharing that is immune against cheaters. Two cheating strategies are considered. In the first one, all cheaters always submit their invalid shares and they collectively know their own valid shares. In the second one, some cheaters may submit their valid shares while again sharing their knowledge about their valid shares. The combiner (or recovery algorithm) interacts with shareholders by collecting shares from them and distributing the recovered secrets back to active participants. Two different scenarios are considered when the combiner recreates all secrets (this is simultaneous recovery) or gradually (so called sequential recovery). Probabilities of successful cheating are derived and constructions for cheating immune multisecret sharing are given. 1 Introduction Cheating prevention in secret sharing and group oriented cryptography becomes one of the central security issues. Roughly saying, secret sharing is cheater-immune if a cheater is not better off than a participant who follows the protocol honestly. Tompa and Woll [8] demonstrated how Shamir secret sharing can be subject to cheating so after the recovery phase, honest participants are left with an invalid secret while cheaters are able to compute the valid one. The problem of cheating prevention was investigated in [6]. It was shown that secret sharing can be constructed in such a way that cheaters after revealing an invalid secret by the combiner (or recovery algorithm), are getting no information about the valid secret. In a sense, the knowledge about the valid secret of honest and dishonest participants is the same with an obvious exception that cheaters know that the recovered secret is invalid while the honest ones will learn about this fact later when the recovered secret fails to trigger the intended action. Multisecret sharing was probably first discussed in [5]. General formulation of the problem for the case when m different secrets are shared among participants with a single access structure was studied in [1]. Some further works can be found in [3, 4, 2]. Clearly, cheating participants in multisecret sharing schemes have more possibilities to deviate during the reconstruction of secrets depending on how the combiner who collects shares is working and also how the secrets are reconstructed. To make our considerations explicit we assume a simple multisecret sharing model in which ev- ery n participants can recover the secrets. The combiner who reconstructs the secrets can return all secrets (parallel reconstruction) or secret by secret (sequential reconstruction) where secrets are recreated in a some publicly known order. From now on we assume that the combiner is implemented in such a way that it accepts shares and after getting the appropriate number of them, reveals the reconstructed secret to all active participants (shares are never revealed by the combiner). This of course, does not restrict dishonest participants who may reveal their shares to each other. 2 Notations Multisecret sharing is defined by a mapping F: —> F is called the defining mapping (or dis- tribution rule) and is publicly accessible. Each vector a € GF{p^)" determines a collection of n shares held by n participants and the vector F{a) £ GF{p*')™' specifies a collection of m secrets. In particular, when m = 1, the defining mapping becomes the defining function that was studied in [6]. We consider two basic cheating strategies that are possible for dishonest participants to undertake. The strategies characterise the way the combiner works: • simultaneous recovery of all secrets - in this case dishonest participants can modify all their shares or perhaps, they can collectively decide that some portion of their valid shares will be submitted to the combiner (those two scenarios will be considered). Note that the knowledge of cheaters is restricted to the shares they hold, • sequential recovery of secrets - again dishonest participants submit a collection of invalid shares to the combiner who returns a single secret. The recovery process of a single secret is independent as dishonest participants can deliver a different collection of invalid shares for each recovery. Observe that the knowledge of cheaters changes after each recovery as they obtain a secret returned by the combiner. We assume that the combiner is honest and returns the secret corresponding to the submitted shares and after the recovery it "forgets" all shares and secrets. Let GF{p*-) denote a finite field with p*- elements where p is a prime number and t is a positive integer. We write to denote the vector space of n tuples of elements from GF(j/). Then each vector a S GFip^)"^ can be expressed as a = (oi,... ,an) where ai,... € GFip*-). The Hamming weight of a vector a G GF{p^)", denoted by HW{a), is the number of nonzero coordinates of a. We consider a mapping F: GF{p^Y —> GFip^)"" written either F{x) or F{xi,... ,Xn) where x = {xi,...,xn) and each xj e GF{p*). F is said to be regular if F{x) takes each vector in GF{p*-)'^ precisely pKn-m) tijifjgs while X goes through each vector in GF{p^)^ once. A regular mapping GF{j/-)'^ GF{p^)^ exists only when n > m. A mapping /: GF{p^)" —GF{p^) is called & function on GF{p^)". A regular function / is also called a balanced function. A mapping F: GFip^Y —GFip^)"" can be expressed asF = {fi,...,fm) or F{x) = ih{x),..., U{x)), where each coordinate fj is a function on and X € GF{pY- Leta; = (a;i,..., 2;„) and 5 = ((5i,..., be two vectors in GF{p^Y. Define a vector 6 GF{p^)", whose jf-th coordinate is xj if Sj 0, or 0 if S j = 0. In addition, we define a vector xJ € whose j- th coordinate is 0 if Sj 0, or Xj if 6j = 0. Clearly iß + 7)1 = ßt + li, iß + 7)7 = ßj + li and ßj +ßs =ß hold for any /3,7 € GF{p'Y, also 5f = Ó, = 0. Let T = (ti ,..., r„) and ó = (ói,..., be two vectors in GFip'')^. We write r (5 to denote the property that if Tj ^ 0 then Sj / 0. In addition, we write r ^ (5 to denote the property that r (5 and HW{t) < HW{S). Clearly if r :< đ then r -I- ö :< <5. In particular, if <5' 5 and HW(5') = HW{S) we write <5 1x1 S'. It is easy to verify that 5 IX] 5' d' J and <5 ^ <5' both xj = xf, and xJ — xJ, hold for any x € GF{p*-)"-, where denotes "if and only if". 3 Simultaneous Recovery of Secrets with Cheaters Using Invalid Shares only 3.1 Probability of Successful Cheating In this work we use a mapping F\ GF(p^)"- —^ GF(p')'" that defines a multisecret sharing. Let 5 be a nonzero vector in GF{p^)", T ^ (5 and /i e GF{py. F can be equiva-lently represented in the form of table T with rows containing {a,F{a)). SetJ?F(<5,r,M)= K ] F{xJ +T)=^l}. We also simply write Rf{S,t,ix) as R{S,t,ß) if no confusion occurs. The following statement can be formulated. Lemma 1 Let 5 be a nonzero vector in GF{p'')^, t G GF(p^)", T ^ S, and ß £ Then for any given mapping F: GF{p'')"' —> GFip^)"", (i) RÌS,t,h) = R{S',t,ii) ifS X S'. (ii) R{S,at,iJ,) = R{S,^f,p)for any a, 7 € GF{p^)'^ with af = 7^, (Hi) there exists some e GF{p^)'^ such that R{S, r, p) 0, where 0 denotes the empty set. Weintro- Given a mapping i^: GF{p''y^ duce the following notations: • Let a e GF{p^Y be the sequence of n shares held by the group V = {Pi,...,Pn} of n participants and the multi-secret p = F{a). • The collection of cheaters is determined by the sequence S = {Si,S2,. ■ ■ ,Sn) where Pi is a cheater <;=> Si is nonzero. • At the pooling time, the cheaters submit their shares. It is assumed that the cheaters always submit invalid shares. The honest participants always submit their valid shares. We consider the vector a + S. From the properties of aj and a^, we can write that a + S = aj + aj + S. Thus the combiner obtains a -f J that splits into two parts: aj -the part submitted by honest participants, and a^ -f <5 - the part submitted by the cheaters. The combiner (or recovery algorithm) returns an invalid multisecret /x* = F{a + S). Note that the cheaters always change their shares. We assume that there exists at least one cheater, in other words, S is nonzero or HW{5) > 0. • aj determines valid shares held by the cheaters. The set R{S,aj,ß),o<[ = m}> determines a collection of rows of T with the correct multisecret p and valid shares held by the cheaters. • The set a/ -f (5, /i* ), or {a;71 4- a+ + (5) = }, represents the view of the cheaters after getting back ß* from the combiner. In this work the cheating means the action of cheaters by submitting incorrect shares, and successful cheating means the case that the cheaters not only submit incorrect shares but also guess the correct secret. The mapping F is called the defining mapping as it determines the multisecret sharing. The nonzero vector <5 = (^1,..., is called a cheating vector, a is called an original vector. The value of ps^a = if'iP-iS, aj -t- <5, fJ.*) n R{S, aj, n))/#R{S, aj -F S,n*), expresses the probability of successful cheating with respect to S and a, where denotes the number of elements in the set X. As an original vector a is always in R{S, aj+S, fj,*) Pi R{S, aj jH), the probability of successful cheating always satisfies ps^a > 0. Clearly the number of cheaters is equal to HW{S). Theorem 1 Given a multisecret sharing scheme with its defining mapping F: GF(p')" ^ Let S G GF{p'-)" with 0 < HW{6) < n be a cheating vector and (x he an original vector in GF{p*'Y. If ps,a < then there exists a vector'y € GF{p'^)" such that ps^y > Proof Let F (a) = p and F{a + <5) = ß*. By definition, R{S,aj,n) = {xJ\F{xJ + a;[) = p} and + = {xJ\F{xJ + a+ + <5) = p^}. We partition + 5,p*) into p'™ parts: R{S,aj + S,p*) = UasgfCpM-'Sa where (5a = R{S,aj + 5, ß*) n R{6,aj,X + p). Clearly #RiS,a+ +S,p*)= Note that Rid, aj" + <5, A*) n R{5, aj,X)=Qo. Therefore P5,a = #{R{S, aj + 5, p*) n R{S, aj,p)) /éRi6,a++ 6, p*) = + il) Since < from (2), #Qo/#ii((5,a+ + (5,/i*) < p-'™. It follows that (3) From (1) and (3), we know that > (1 - <5, p^). Thus there exists some A' € G'F(p')™ with A' ^ 0 such that > + 5,p*). By definition, Qy = {x^ -f -I- 5) = p*, FixJ + al) = A' + /i}. Then there exists a vector ßg e and then Fiß^ -f -F <5) = /i*, Fißl + c^t) = A' + M- Set 1 = ßs + aj. Thus F(7 -I- = fi* and ^(7) = X' + fi. Clearly = aj and 7^ = ß^. Next we choose 7 as an original vector. Due to 7^ p*) = {xj \FixJ + 7+ + <5) = p*}, RiS,^+,X' + p) = + 7+) = X' + p} and 7+ = a+ we know that R{d,-f+ + ö,p*) n RiS,jj,X' + p) = Qy and = MRiS,j+ + S,p*) n RiS,jt,X' + /i))/#fi(<5,7+ + 6,p*) = H.Qyl#Ri5nt + = 4 Theorem 2 Given a multisecret sharing with its defining mapping F: GF(p')" —Then the multisecret sharing is k-cheating immune for any integer I with I < I < k, any Ò £ with HWÌ6) = I, any t < 5 and any £ GF(p')™, the following conditions hold simultaneously: (i) r, p) = (ii) #iRiS, T, p) n Ri6, r + S, p)) = ptin-i-2m)_ The proof is given in the Appendix. Theorem 3 Given a multisecret sharing with its defining mapping F: GF(p')" —Gf (p^)™. Then the following statements are equivalent: (i) the multisecret sharing is k-cheating immune, (ii) for any integer I with 1 < I < k, any 6 £ GF(p^)" with JlWió) = I, any t < 5 and any GF(p')"', wehaveij^iRi5,T,p)f\Ri5,T + 5,p)) = pt{n-i-2m)^ (Hi) for such I, 6, T, p and v mentioned in (ii), the system of equations: Fixg + r) = precisely ' solutions on Xg . Proof Clearly (ii) (iii). Due to Theorem 2, (i) Corollary 1 Given a multisecret sharing scheme with its defining mapping F: GFip^ —> GFip^)"". Then max{p^,a|a e GF(p^)"} > for any fixed nonzero vectors £ GF(p')". 3.2 fc-Cheating Immune Multisecret Sharing Given a multisecret sharing with its defining mapping F on GF(p*)". For a fixed nonzero 5 G GF(p')", due to Theorem 1, it is desirable that ps,a = p"'™ holds for every a G GFÌp'-)'^. a multisecret sharing is said to be k-cheating immune if p^^a = p"'™ holds for every J G GFijf)'^ with 1 < HWi5)< k and every a G GF(p^)". (ii). To complete the proof, we only need prove that (ii) (i). Assume that (ii) holds. Thus r, 1/) n J?(<5, r -I- 5, p)) = pt(-'i-i-2m) fo^ ^ GFip^)"". Note that Riö,T,v)= Ri6,T,p)r\Ri5,T-^S,p) and then i/) = E^eGflp')-" T,i^)nR(S,T-^6, p)). This proves that T, J/) = ptin-i-m)^ Using Theorem 2, we have proved that (i) holds. Corollary 2 Given a multisecret sharing with its defining mapping F : GF(p^)" —> GF(p*)". If the multisecret sharing is k-cheating immune, then (i) n > 2m k, (ii) F is regular. Proof Let I — k in Theorem 2, we have r, v)!! Riö,T + S, p)) = pti^-f'-^m) > I xhis proves that n > 2m -I- k. Again from Theorem 2 we have t, v) = pt{n-k-m)^ for any r ^ (5 and any u G This means that for each fixed r with t < 5, the mapping Fixg + r) is regular. Thus the mapping F is regular. Due to Corollary 2, a A;-cheating immune multisecret sharing, defined by a mapping F: GF(p^)" —> GF(p^)'", exists only when n > 2m -f k. 4 Simultaneous Recovery of Secrets with Cheaters using Valid and Invalid Shares 4.1 Probability of Successful Cheating Given a mapping F: GFip*)"" GFip^)"". We introduce the following notations. As before we can see F as a table T with rows containing (J, F((5)). We also assume that the combiner returns all secrets (or the multisecret for short). • Let a e G F (p'-)" be the sequence of shares held by the group V = {Pi,... ,Pn} of n participants and the secret M = Fia). • The collection of cheaters is determined by the sequence <5 = (Ji, (^2 J • • ■ ! <5n) where Pi is a cheater if Si 0. • At the pooling time, the cheaters submit their shares. This time it is assumed that cheaters may submit a mixture of valid and invalid shares. The honest participants always submit their valid shares. The collection of cheaters who submit invalid shares is determined by the sequence r = (ti ,..., r„) where t j = O Pj is honest or Pj is a cheater who submits a valid share, in other words, tj ^^ 0 Pj is a cheater who submits an invalid share. Clearly T : 0. We consider the vector a + t. Due to the properties of operations aj and aj, we can write a + t = a^ + af + t. The combiner obtains a + r that splits into two parts: a^ - the part submitted by honest participants and af + t the part submitted by cheaters. The combiner returns an invalid multisecret /I* = F{a + t). • R{6,aj + t,pi*),ot {xJ\F{xJ +aj +t) = ß*}, where a determines valid shares held by the cheaters, represents the view of the cheater after getting back ß* from the combiner. • The set R{S,a'l,fi), or {xj\f{xj -Fa/) = n], determines a collection of rows of T with the correct multisecret /U and valid shares held by the cheaters. As mentioned in Section 3, the cheating means the action of cheaters by submitting incorrect shares, and successful cheating means the case when cheaters are able to guess the correct secret. In generalised model of cheating, r is used to determine how to cheat while <5 is only used to determine which participants are dishonest, therefore we can define <5 as a (0,1)-vector in GF(p*)". However, in basic model of cheating, S is not only used to determine which participants are dishonest but also used to determine how to cheat, thus S has a more general form. The mapping F is called the defining mapping of multi-secret sharing. We assume that the combiner returns mul-tisecrets (all secrets). The nonzero vector S = {6i,..., is called a cheating vector, the nonzero vector r <5 is called an active cheating vector, a is called an original vector. The value of = -I-n R{S,a'g,n))/i^R(6,a'l + t,fj.*) expresses the probability of successful cheating with respect to <5, t and a. As an original vector a is always in R{S,aj + t,fj.*) n R{S, a^jfi), the probability of successful cheating always satisfies ps,T,a > 0. Clearly the number of cheaters is equal to HW{S) and the number of active cheaters is equal to HW{t). In particular, if t = 6, we regain basic model of cheating. 4.2 Strictly /c-cheating Immune Multisecret Sharing By using the same arguments as in the proof of Theorem 1, we can state: Theorem 4 Given a multisecret sharing with its defining mapping F: GF{p^Y —> C?F(p^)™. Let ó e 0 < HW(ó) < n, be a cheating vector, let t ■< 5; t ^ 0, be an active cheating vector, and let a G GF{p^)"' be an original vector (representing valid shares). If ps,T,a < then there exists a vector 7 € GF(p')" such that Corollary 3 Given a multisecret sharing with its defining mapping F: GF(p')" —GF{p^)'^. Then | Q 6 GFip^Y] > for any fixed 5 and r with t < 6 and r ^ 0. For the same reason mentioned in Section 3.2, we introduce the concept of A;-cheating immunity. Given a secret sharing with its defining mapping F on GF{p^)^. Let k be an integer with I < k < n-1. The secret sharing is said to be strictly k-cheating immune if the probability of successful cheating satisfies p&^T,a — for every 5 € GFijp*')'^ and any r J with 1 < HW{t) < HW{5) < k and every a £ GF{p^Y. The following theorem establishes a relationship between the two models of cheating immunity. Theorem 5 Given a multisecret sharing with its defining mapping F: GF{p*'Y —> GF(p')'". Then the multi-secret sharing is strictly k-cheating immune for any integer r with 0 < r < k - 1, any subset {ji, ...,>} of [l,... ,n] and any ai,...,ar £ GF{p^), the mapping -F(a;i,... ,a;„)|xij=oi,.,.,x3v=ar' w'irÄ the variables where {ii,... ,in-r} U {jl,...,jr} = {1,..., n}, is the defining mapping of a {k — r)-cheating immune secret sharing. Proof Assume that the multisecret sharing is strictly fc-cheating immune (model in Section 4.1). Denote F{xx,... by G. Then G is a map- ping: GF{p'-y^-'' —> GF{p^)'^. Comparing the model in Section 3.1 with the model in Section 4.1, we know that G is the defining mapping of [k — r)-cheating immune secret sharing (model in Section 3.1). This proves the necessity. By definition, we can prove the sufficiency by inverting the above reasoning. 5 Secret Sharing versus Multisecret Sharing We regard GF{p*-™-) as a simple extension of GF{p*') and then there exists an element e € GF{p''"^) such that each element in can be uniquely expressed as h + b2e + ■■■ + where each bj £ GF(p'). Let / be a function on GF{p' tm\n I.e., a mappmg: GFip^"")" —GFÌp*""), and iphca nonzero linear mapping: —From / and ijj, we now define a mapping Ff^^: GF{p^Y —^ GF(p')™ such that F/,^(oi,...a„) = (bi,..., 6™), where each e GF{p^), ^ /(ci,...c„) = c, where aj = V(cj), j = 1,..., n, and c = bi + 62^ H-----H m-l Theorem 6 Given a secret sharing with its defining function f on GFIp^"^)"'. Let ip be a nonzero linear mapping from GFijf-"^) to GF(j)*-). If the secret sharing is k-cheating immune then the mapping Ff^^: GF{p^)" is the defining mapping a k-cheating immune multisecret sharing. Proof Let 6 be any vector in GF{py with HW{5) = I, where I < I < k, and r be any vector in GF{p*')'^ with T <5. Consider the system of equations: FfA^'š +T) = (6i,...,6,„) where each aj, bj € GFtj/'), and f fi^s + T6) = ai-Ì-a2e-\-----ha I fi^J -f r) = 61 + fcae + • • • + " """ -m—1 (4) (5) function on GF{p^Y ^ ^ GF(p')". Let s be an integer with 1 < s < m and {ji,... ,js} C {l,...,n}. Define a mapping H: GF{p^Y —GF{p*-y such that H{x) = (x), ..., fj, {x)). If F is the defining mapping of a k-cheating immune multisecret sharing, so is H. Proof Without loss of generality, we only prove the theorem in the special case that ji = l,...,js = s. Consider the system of equations: H{xJ -\-t + 5)=u H{xJ + r) = (7 where 6 GF{p'-y. Since F is the defining mapping of a fc-cheating immune multisecret sharing, due to Theorem 3, for any integer I with 1 < I < k, any S e GF{p^Y with HW{ö) = I, any t :< 5 and any fj.,iy E GF{p'-)™-, the system of equa- F{XJ -f r + ,5) = M p^^^j^^jy ptin-l-2,n) (6) Due to Theorem 3, Equations (5) have precisely ptm{n-i-2) solutions. Note that for each element a E GFijf'), there precisely exist p^t™"^) elements c G GFij/"") such that ^(c) = a. Therefore for each vector (ai,...,a„_;) G GF{p^Y~'-, there precisely exist pt(m-l)(n-l) (ci,...,C„_() G such that ),..., ?/)(c„_i)) = (ai,...,a„_;). Summarising the above, we know that Equations (4) have precisely ptm{n-l-2) lpt{m-l)(n-l) ^ pt{n-l-2m) solutions. Due to Theorem 3, we have proved that the mapping GF(p')" —^ GF{p*-)"' is the defining mapping a k-cheating immune multisecret sharing. Combining Theorems 5 and 6, we can prove the following statement. Corollary 4 Given secret sharing with its defining function f on GFip''^)"'. Let ip be a nonzero linear mapping from GF{j>*'™') to GF{p^). If the secret sharing is strictly k-cheating immune then the mapping Fj^^: GF{p*')^ —> is the defining mapping of a strictly k-cheating immune multisecret sharing. The construction of a A;-cheating immune secret sharing defined by a function has been studied [6], Therefore applying Theorems 6 and 4, we can construct a A;-cheating immune secret sharing defined by a mapping from a k-cheating immune secret sharing defined by a function. Using Corollary 4 and construction given in [6], we can obtain strictly cheating immune secret sharing defined by a mapping. The constructions will be shown in Examples 1 and 2. Theorem 7 Let F be a mapping: GFip'-y —GFip^)"". Write F{x) = {fi{x), ..fm{x)) where each fj is a tions: -, _ > solutions on x'^. On the other hand, there precisely ex-\^lpt(m-s) vectors ß G GF{p'-)"^ satisfying ß = (to.y) where y G and there precisely exist vectors u G satisfying v = (er, 2) where G GFip')'""^. It is easy to see that the system of equations (6) has precisely ^«("-'-2™) . p2t(m-s) ^ pt(n-i-2s) lutions on x'^. Applying Theorem 3 to H, we have proved that H is the defining mapping of a fc-cheating immune multisecret sharing. The above theorem can be rephrased to the following statement. Theorem 8 Let F be a mapping: GF{p^Y —> GFip^)"" such that F{x) = (/i(a;), ..., fm{x)) where each fj is a function on GF(p')" and x G GF{p^Y. If F is the defining mapping of a k-cheating immune multisecret sharing then each fj is the defining function of a k-cheating immune secret sharing. Applying Theorem 5 to Theorem 8, we obtain Corollary 5 Let F be a mapping: GF{p^Y — such that F{x) = {fi{x), ..., fm{x)) where each fj is a function on GF{p^ y and x G GF(p^ Y. If F is the defining mapping of a strictly k-cheating immune multisecret sharing then each fj is the defining function of a strictly k-cheating immune sharing. Theorem 9 Let F be a mapping: Gi^(p')" —^ GFip^)"^ and B is a nonsingular mxm matrix over GF{j/'). Define another mapping G: GF{p''Y —such that G{x) = {F{x))B. If F is the defining mapping of a k-cheating immune multisecret sharing, so is G. Proof For any integer I with 1 < / < fc, any 5 G with HW{S) = any T ^ J and any E GF(p')'", consider the system of equations: | r)"^*^!/ ^ that is equivalent to F{xJ + T-h 6) = ßB-^ (7) Since F is the defining mapping of a /c-cheating immune multisecret sharing, due to Theorem 3, (7) has precisely pt(n-i-2m) solutions OH xj. Therefore G has precisely pt{n-i-2m) solutions On xj. Again using Theorem 3, G is also the defining mapping of a fc-cheating immune multi-secret sharing. .t\n Theorem 10 Let F be a mapping: GF{jp^) GFip')"" such that Fix) = {fi{x), /„(a;)) where each fj is a function on GF(p')" and x € GF\p^Y. If F is the defining mapping of a k-cheating immune multisecret sharing then any nonzero linear combination of fi,...,fm, i-e., bifi + • • ■ + bmfm where each bj e GF{p') and (Òi,..., ^ (0,..., 0), is the defining function of a k-cheating immune secret sharing. Proof Let (òi,..., &„) be a nonzero vector in GF{p*')"^. Let S be a nonsingularm x m matrix over GF{p*'), whose first column is (òi,..., where X^ denote the transpose of the matrix X. Set G{x) = {gi{x),... ,gm{x)) — {fi{x), ..., fm{x))B. Using Theorem 9, we know that G is the defining mapping of a fc-cheating immune multisecret sharing. Applying Theorem 8 to G, we know that gi is the defining function of a A;-cheating immune secret sharing. Since gi = bifi-{-■■■ bmfm, we have proved that bifi H-----h bmfm is the defining function of a fc-cheating immune secret sharing. Applying Theorem 5 to Theorem 10, we obtain Corollary 6 Let F bea mapping: G F {p' i\n -^GFip^) t\m such that F{x) = {fi{x), ..fm{x)) where each fj is a function on GF{p'')" and x £ GF(p^ Y. If F is the defining mapping of a strictly k-cheating immune multisecret sharing then any nonzero linear combination of fi,..., fm is the defining function of a strictly k-cheating immune secret sharing. Due to Theorem 10 (Corollary 6), we have /i, •.., /m that are m coordinate functions of the mapping F. Denote the set of all the nonzero linear combinations of /i,---,/m,by n = Then each is the defining function of a (strictly) fc-cheating immune secret sharing. Clearly gj ± gi £ fl for j ^ i, and thus g j ± gi is the defining function of a (strictly) fc-cheating immune secret sharing. Due to Corollary 2, g j ± gi is balanced. This means that any fj does not give any information on any other fi with i ^ j as balance means unbiased for every element in GF{p*). Note that ü U {0}, where 0 denotes the zero function on GF{p'^)"' form an m-dimensional linear space over GFip*'). 6 Constructions The following two examples indicate how to construct a multisecret sharing mentioned in Theorem 10 and Corollary 6. Example 1 Define a function X2k+i on by X2k+iixi,...,X2k-i-i) = xiX2 -t- X2X3 -}-■■• -\-X2k^2k+i + X2k+iX\ and then define a function XAk+2 on f^y Xik+2{Xu...,X^k+2) = X2k+l{x\.,. . ■ ,a;2fc+i) +X2k+l{x2k+2, ■ ■ .■,Xik+2)- Let k and s be positive integers with s > k 1, Til,...,Hg = 4fc + 1 or + 2, and n = ni -f- • • • -h ris. Define a function on such as f{x) = XnAy) + ••• -I- Xn.{z) where x = {y,...,z), y € ,..., z € GFip'^r-, and ,..., Xn. have disjoint variables mutually. From [6], the secret sharing with the defining function f is k-cheating immune. Let tjj be a nonzero linear mapping: GF{p^^) —^ GF{p^). Due to Theorem 6. the mapping Fj^^: GF{p'')" —> GF{p*')"' is the defining mapping a k-cheating immune multisecret sharing. Example 2 Let A„,p be a function on (n > 2p^ -I- p) defined by \n,p{xi,... = where [z](„) denotes the integer j such that 1 < i < and j = i mod n (we replace i by as i is possibly greater than n). Let s be an integer with s > ni,..., n^ = + p or 2p^ -f p + 1, and n = rii ■ ■ ■ Ug. Define a function on such as f{x) - X„i,p{y) -I- • • • -)- where x = {y,...,z),y E ..., z € , andXni,p, ■ ■ ■ have disjoint variables if i j. From [6], the secret sharing with the defining function f is strictly p-cheating immune. Let be a nonzero linear mapping: GF{p''"^) —> GF{p''). Due to Corollary 4, the mapping Ff^^: G'F(p^)" —s- GFip^)"" is the defining mapping a strictly p-cheating immune multisecret sharing. 7 Sequential Recovery of Secrets Given a multisecret sharing with its defining mapping F; GF(j}'r GFip')"^ such that F = {fi,..., fm) where each fj is a function on GF{p'-)^. In the multisecret sharing schemes mentioned in Sections 3 and 4, we stipulate that the multisecret as a vector (òi,..., bm) that determines m secrets. We assume that those secrets are recovered simultaneously. In this section, we consider a scenario where the combiner will recover single secrets (instead of the multisecret) in a some order (perhaps imposed by the participants) and return the recovered secrets to active participants. We will study two basic cheating strategies • cheaters use the same cheating vector and the same original vector for all recoveries - this case is equivalent to the simultaneous recovery of secrets, • cheaters modify their cheating vectors depending on the returned secrets. Assume that the participants sequentially perform m secret sharing schemes with defining functions /1,.. •, /m by taking cheating vectors 5i,...,5m 6 GF(p^)" and original vectors, ßi,... ,ßm £ GF{p^)^ and original vectors. Since the secret of each secret sharing defined by fj is independent to the secret of secret sharing defined by fi if i i, the probability of successful cheating is identical with /9<5j,/3i • • ■ where Pi^ß^ denotes the probabil- ity of successful cheating of the secret sharing defined by fi with respect to the cheating vector 5i and the original vector ßi. We notice that each ps^^ß^ can be calculated by the definition of probability of successful cheating. Obviously the probability of successful cheating of sequentially recovery is invariable under a permutation on the order of participants. In particular, F = {fi,..., fm) is the mapping of a k-lh immune secret sharing, then using Theorem 10, we conclude that = • • • = ps^ß^ = p""^ Therefore the probability of successful cheating is identical withp"^™. As for the model that cheaters submit a mixture of valid and invalid shares, using the same arguments, we conclude that the probability of successful cheating is identical with Pöußi ■ • • In particular, F = {fi,..., fm) is the mapping of a k-tii immune secret sharing, then using Theorem 10, we conclude that P0i,ßi — ■ ■ ■ — Päm,ß^ — ■ Therefore the probability of successful cheating is identical with p-'™. 8 Conclusions We define a multisecret sharing by its defining mapping F: GF{p'')" —^ GFip'-)"^. For n participants, each vector a e GF{p^)'' is a share and the vector F{a) € GF{p^)"' is the multisecret corresponding to the share a. It has been proven that the probability of recovery of correct multisecret by cheaters is can be made as small as Clearly, cheaters who are interested in getting a single secret may get it with the probability no smaller than In a sense each recovered invalid secret provides no information about the valid secret but also gives no help in gaining information about other secrets. We have investigated two models of fc-cheating immune secret sharing defined by a mapping. A relationship between defining mappings and functions has been examined and constructions of /c-cheating immune multisecret sharing have been given. We have shown how fc-cheating immune multisecret sharing relates to a linear space defined over fc-cheating immune secret sharing schemes. We have also demonstrated that A;-cheating immunity guarantees that multisecret sharing can be used for simultaneous and sequential recovery without any impact on the probability of guessing of valid secrets by cheaters. Acknowledgement The work was partially supported by Australian Research Council grant A00103078. References [1] C. Blundo, A. De Santis, and U. Vaccaro (1993), Efficient sharing of many secrets. In K.W. Wagner P. En-jalbert, A. Finkel, editor. Proceedings of STACS93, 10th Symposium on Theoretical Aspects of Computer Science, Springer, LNCS No. 665, pp. 692-703. [2] Carlo Blundo, Alfredo De Santis, Giovanni Di Crescenzo, Antonio Giorgio Gaggia (1984), and Ugo Vaccaro, Multi-secret sharing schemes, In Advances in Cryptology - CRYPTO'94, LNCS No. 839, Springer-Verlag, pp. 150-163. [3] Wen-Ai Jackson, Keith M. Martin, and Christine M. O'Keefe (1994), Multisecret threshold schemes, In Douglas R. Stinson, editor, CRYPT093, Springer, LNCS No. 773, pp. 126-135. [4] Wen-Ai Jackson, Keith M. Martin, and Christine M. O'Keefe (1994), On sharing many secrets. In J. Pieprzyk and R. Safavi-Naini, editors, ASI-ACRYPT'94, Springer, LNCS No. 917, pp. 42-54. [5] E.D. Karnin, J.W. Greene, and M.E. Hellman (1983), On secret sharing systems, IEEE Transactions on Information Theory, IT-29: pp. 35-41. [6] J. Pieprzyk and X. M. Zhang (2001), Cheating prevention in immune secret sharing over GF{p^), In In-docrypt 200J, LNCS No. 2247, Springer-Verlag, pp. 79-91. [7] A. Shamir (1979), How to share a secret. Communications of the ACM, 22: pp. 612-613. [8] Martin Tompa and Heather Woll (1988), How to share a secret with cheaters. Journal of Cryptology 1 : pp. 133-138. Appendix: Proof of Theorem 2 Proof Assume that the secret sharing is fc-cheating immune. Choose 5 as a cheating vector and any vector a £ as an original vector. Due to Lemma 1, there exist /x', 1/' 6 GF(p')™ such that R{d, aj + <5, p') 0 and R{6, aj,!^') ^ 0. Note that R{S, aj -I- S, p') can be partitioned into parts: R{5,a++ 6, p') = U R{5,a+ + 8,ß')r\R{5,aty) (8) i'SGF(p')'" Assume that i?((5,a| 5, p.') n R{S,af,v) ^ 0 for some V e GF{p'-)'". Then there exists a vector ßg e R{S,a++6,p')nR{6,a+,iy).Set'y = ßj + af. Since the secret sharing is fc-cheating immune, #{R{S, -I- p') n J. Pieprzyk et al. R{S,jÌ,u))/#R{5,j+ +d,fi') = ps,^ = p-''", where 7/ = a+ Thus (9) whenever R{6, a j + S, fi') n RiS, aj,^)^^ 0. From (8), i^RiS,a++ S,/,') = Y^ #{R{S,at + S,,s')nR{S,aj,,^)) (10) Combing (9) and (10), we know that R{5, aj + 5, ß') n i?((5, at, J/) 0 for every j/ e GFip^)"" and thus = (11) for every G GF(j/')™-. Replacing a, J, by a + 5, (p—1)^ respectively, due to the same arguments for (11), we have for any I/ G GF{p'')"^. From (15) and (14), we have proved that aj +S,fi)n R{S, aj, »/)) = p'C"-'-^™) (I6) for every /i, S GF{p^)™'. For any t :< 5, choose a € GF{p'-Y such that aj = r. Due to (15) and (16), both conditions (i) and (ii) hold. Conversely assume the defining mapping F satisfies conditions (i) and (ii). Choose any 5 G GF{p^Y with HW[6) = I, where 1 < / < A;, as a cheating vector and any a as an original vector. Set F{a) = ß and F{a + S) = ß*. By definition, ps^a = Ìé{R{S,aj + S, /i*) n RiS, aj, ß))^R{5, + Ò, ß*). Due to conditions (i) and (ii), p^^a = Thus we have proved that the secret sharing is /c-cheating immune. 4{R{{P-I)5,aj +p5,v') C\R{(p-l)5,aj +5,ß)) for every ß G GFip'-)™. Since the characteristic of the finite field GF{p^) is p, pe = 0 for every e G GF{j>^). It follows that #(Ä((p - 1)(5, aj, v') n i?((p -l)S,aj+S,ß')) = l)<5,a+,i/') for every ß G GF{p'-)"^. Using Lemma 1, we obtain m{S,aj,i.')nR{S,aj + S,ß)) (12) for every ß G Recall that R{d, aj + S, ß') 0 and R{S, aj,v') ^0. Therefore (11) and (12) imply that R{5, aj,v) ^0 and R{5, aj +6, ß)^^ for every p., G Due to the same reasoning for (11) and (12), we have il:{R{0,aj + 5,ß)nRiS,aj,u)) = p-'"'#R{0,aj+S,ß) (13) and #ÌRÌ5, aj,iy)nRi5,aj + 6, ß)) = p-'"'#R{S,aj,u) (14) for every ß,v E GF{p*')'^. Comparing (14) with (13), we conclude that #Ä(<5, a^ -I- <5, p) = aj, v) for every p,!/ G GFip^)"". Therefore both -f S,ß) and #R{S,aj,1/) are constant. Note that = We have proved that ,+ jA _ „t(n-l-m) (15) Digital Semipublic Watermarking Valéry Korzhik Telecommunication Security Department State University of Telecommunications St. Petersburg, Russia E-mail: ibts@ns.lanck.ru Guillermo Morales-Luna' Computer Science Section CINVESTAV-IPN, Mexico E-mail; gmorales@cs.cinvestav.mx Dmitry Marakov and Irina Marakova Institute of Radio Electronics and Telecommunication Systems Odessa National Polytechnic University, Ukraine E-mail: nOmad@all.odessa.ua Keywords: information security, copyright protection, information hiding, watermarking Received: June 13, 2002 The theory still remains uncompleted. There have been some advances in asymptotic theory concerning capacity of WM as well as in some practical proposals, mainly where WM is applied without any theory. Most of times, references are made to public watermarking, in which the watermark detector does not require any secret key at all. In this paper, our contribution is a WM that we name semipublic watermarking. This is a scenario in which any ordinary user is enabled to detect WM without any secret key, if the message is not subject of attack trying to remove its WM. Moreover, at any time, the owner of WM is able to detect WM even after such an attack. We propose two methods of semipublic WM and we calculate the probabilities Pm, of missing WM (when WM is present, indeed), and Pfa of WM false alarm (when WM is absent but its presence is supposed). The first method guarantees that both Pm and Pfa converge to zero as the number N of WM elements increases, only if the distortion constraints are very strong. In second method also Pm, Pfa converge to zero as N increases, for any distortion constraints, but it is required the so called property of quadratic compensation; In order to compensate an m times increase of the distortion constraint "signal-to-noise ratio", the number at WM elements should increase m^ times. Although we consider just additive noise attacks, our results are useful since they provide lower bounds for WM reliability for any optimal attack with given distortion constraints. 1 Introduction tion is the opportunity to estimate theoretical lower bounds for the probabilities of WM-missing and WM-false alarm Information hiding (IH) is a rather new area of informa- functions of the WM system main parameters. An addition security. The goal of an IH designer is to hide even of consideration into this model is the fact that a the fact that messages do exist in some ostensible harmless '^e most optimistic results regardhost data (the so called cover message (CM)). Watermark- ^M application in comparison with other types of ing (WM) is one of IH applications: The CM should be ™ sophisticated attacks. combined with some other information, like owner identi- j^^in types of WM are known [1, 2, 4, 6, 7]. In the fication, for instance. Then identification code is perma- ^ersjo^ both the encoder and the decoder use secret nently embedded in the data and should remain present ^^^ j^e public (blind) version no suplementary infor- within the data after any transformations initiated by the „.^tion ^^ ^11 is available to the decoder. Since the term attacker attempting to remove the WM (or to disable it of semiprivate has been introduced already for another sce- being detected by the owner) keeping an acceptable quality ^^ propose the term semipublic for this version of WM. In this case, it is assumed that each user is able to We consider in the current paper only one type of attack extract WM out of the watermarked message without any - additive noise attack. The reason of such a hard restric- secret key, provided the absence of an attacker trying to re- 280 Informatica 26 (2002) 279-285 V. Korzhik et al. move WM. At the same time, the WM designer, possessing the secret key, is able to detect WM even after an attack if it satisfies some given distortion constraints. 2 Performance Evaluations of Semipublic WM 2.1 Semipublic WM Based on Double Sequence In this case the stegomessage (SM) (or in other words - the watermarked message) is formed as and compare it with some given threshold A. If A > A, then a WM has been detected, otherwise it has not. (It is easy to show that such detector is optimum if C(n) is a Gaussian sequence with independent samples.) Let us derive the formulas for the probability of WM-missing (Pm) (when detector is unable to find WM in the watermarked SM) and the probability of WM-false alarm (Pfa) (when detector claims the presence of WM, while in fact it is absent in that message at all). If WM is present in SM then we have N A = J2 + A(n)e(n)) e(n) =: Ai (4) 5(n) = C7(n)+u;(n), n = l,2,...,iV (1) and if it is not present in SM then where C{n) is the cover message, w(n) = A(n)e(n), A(n) is a nonnegative-real valued sequence, e{n) is a sequence of signs 4-1,-1 and N is the number of WM elements, e.g. pixels of image CM. The key point of our approach is to consider A(n) and e(n) as randomly chosen sequences (although they should be fixed later for a particular system). Different WM designers can select their WM sequences randomly. We are going to estimate the average WM reliability over all possible choices. We consider only the case when CM is not used by the WM-encoder to form A(n) and ein). From the decoding process point of view, we assume that it is impossible for any ordinary user to use the CM (since otherwise the WM can be removed trivially) but it is possible for the WM owner to use the CM in order to detect WM after an attack. We consider just the particular case of WM when each SM either contains or does not contain WM. Hence any decoder of WM has to decide just one of two possibilities: Is there or not a WM in the presented SM? (Zero-bit watermark system [3]). In the semipublic version of WM, the sequence e(n) is assumed to be known for every user, whereas the sequence A(n) is kept secret. The sequence e(n) takes independent and equally distributed samples of signs ±1 and A(n) takes also independent and uniformly distributed nonnegative samples within an interval (0,D), where D > 0 is a fixed positive number. These sequences are statistically mutually independent. The cover message C(n) is described by a random discrete zero-mean process with variance Oq . The distortion constraint after watermarking is given as a signal-to-noise ratio riw = var (C(n)) __ ^ var (A(n)e(n)) ~ D^ (2) We propose for each ordinary user to detect WM as follows. Calculate the value N A ^ 5(n)e(n) (3) N A = ^ C{n)e{n) =: Aq (5) 11=1 Since A(n) and e(n) are independent identically distributed (i.i.d.) random sequences we get for large N as a consequence of the Central Limit Theorem [9] that both Aq and Al are Gaussian random variables independent on the C(n)-probability distribution (this means that the detector based on the correlation sum A is indeed an asymptotically robust detector). Using the fact that Aq and Ai are Gaussian variables we can derive quite easily the formulas for the sought probabilities P,„ and Pfa Pm = l-Q Pfa = Q A-E(Ai) VvärÄT VvarAo ) (6) (7) where It is easy to see that +00 e 2 dt. E{Ao) = 0 £(Ai) = N-E{A{n)) =N varAo = N ■ a^ = varAi D (8) Substituting (8) into (6) and (7), and taking into account the relation (2) we get = l-Q (A'-l). I3N -iriw na = Q X\ \ l3N (9) (10) / n=l where A' = Comparing formulas (9), (10) with the formulas for Pm and Pfa corresponding to the case of private WM in which CM is unknown by both encoder and decoder [5], we can find just medium degradation coefficient by increasing the WM length N. Now, let us consider an additive noise attack against WM detection, performed by ordinary users. The decision about the presence or absence of WM is taken after comparing with a given threshold A, the value N (11) n=l where S'{n) = S{n) + e(n), for an attacking additive noise e(n). Since the attacker knows the sequence e(n), for n = 1,..., A'', (as indeed does any other ordinary user) he is able to detect the presence or absence of WM in the CM with a high reliability. Hence he can create an additive noise sequence e(n), forn = 1,..., A'^, as e{n) = ae{n) 0 if WM is absent otherwise Thus, the following expectations of A' result, for ordinary users trying to detect WM after the attack: f E{A'q) = N -a if WM is absent = I ^(M) = ^ otherwise Using the distortion constraint after attack _ var C(n) _ Gq vare(n) cr^ we get (12) a = ria (13) On the other hand, the distortion constraint after watermarking (2) gives the relation D = M Vw (14) We can replace rja in (13) by r]w since the attack occurs only in the absence of WM. This allows to represent the equations (12) as follows E{A'o) = Na = N E{A[) = and A(n). Then he compares with a given threshold A the value N 7V" = ^S'(n)e(n)A(n) (17) n=l Since the attacker knows with a high probability whether WM is presented or not in SM he can create the following optimal noises: , N J eo{n) := ae{n) if WM is absent \ ^lin) '■= — A'(n)e(n) otherwise (18) where tJ is a nonnegative parameter, A'{n) is a nonnegative i. i. d. random sequence, uniform within an interval (0,D'). In the case of WM absence, we get from (17) and the first case in (18) E(A") = aNE{A{n)) (JND (19) Otherwise, if WM is present we get from from (17) and the second case in (18) E{K") = E{A'l) = N [£;(A(n)2) - £;(A(n))E(A'(n)) ,, fD'^ DD' = N = N Vv —S-D' 16 (20) / A comparison between (19) and (20) shows that < E{iV{) (and as a consequence that WM can be detected by the WM owner after an attack for large N) if and only if D' is very small. It means in turn that such semipublic WM system works fine whenever the distortion constraint after the attack is very strong, that is rja ~ ri^, where rja is the signal-to-noise ratio after the attack, and it can be determined as follows (15) (16) Va = varC(n) var (w{n) + e{n)) (21) Since (15) is always larger than (16), the attacker can cause false alarm of WM with a high probability for any threshold A chosen by ordinary users. This fact compromises completely the WM system as a public one but in our case it is a semipublic WM system where WM detection after attack is just possible for the WM owner since he is the only person knowing the secret sequence A(n). Let us consider the case when the detector (as the WM owner in his role of detection) knows both sequences e(n) Due to the fact that condition r/a « rj^ is not interesting enough in practice we throw away this method and consider instead in the next section another semipublic WM system based on a periodic sequence. 2.2 Semipublic WM based on a Periodic Sequence Let us define the SM as follows S{n) = C{n) +win), n = 1,2,... ,2No (22) V. Korzhik et al. where w{n) — a-iT{n) and A^o = y- The sequence 7r(n) is an i.i.d. random sequence whose entries are signs ±1, periodic with two periods of length No each. (In practice it is not necessary to use all N elements. We can take Nq < y and select elements of both periods within N elements in such a way to distinguish the WM of different owners. Another reason for do not selecting consecutive elements in each period of 7r(n) is to provide an interleaving of the CM elements). If a periodic WM has been used in the SM but the sequence 7r(n) is the secret sequence of the WM owner then each ordinary user can calculate the value No A = Y^S{n)S{n + No) (23) n=l and compare it with a given threshold A. Here, we are assuming that for the semiprivate WM there has not been an attack on the SM in the case of WM detection by ordinary users, hence S'{n) = S{n). Then in the case of WM presence A' = A'l No = ^ (C(n) + u;(n)) (C (n + A^o) + w(n)) n=l No = +-^o) n=l No -I- + C{n + No)) 71=1 + a'^N (24) In the case of WM absence No A = Ao = Y^C{n)C{n + No) n=l Pm = 1-0 Pfa = Q VNct. 1 C J (25) (29) (30) / / / / 0 100 300 MO m 600 700 600 900 Figure 1 : The number N of WM bits required for any ordinary user to provide P^ = Pfa = 10"^ versus the distortion constraint 77u,. The distortion constraint after WM is given as the signal-to-noise-ratio ^ var jCjn)) ^ 4 ^ varw(n) a^ which, together with (29)-(30), gives / (31) Pm = 1-0 (A'-l). N Vl + 2??«; 1-Q (V-.).S Iw / (32) (33) Let us arrange elements of periods with enough interleaving. There are two Gaussian distributions resulting from both Ao and Ai, consequently the formulas (6), (7) can be used to find the probabilities Pm and Pfa. It is easy to see that E{Ao) = 0 , £(Ai) = a'^N (26) var(Ao) = NE{Cin)^)E (c (n + No)^) - Na^c- (27) Assuming that C(n) and C {n + No) are uncorrected random variables, after interleaving, we get var( Al ) = N{a^c+ ^c ) (28) Substituting (26)-(28) in (6)-(7) we obtain A-«2 AT where A' = A comparison of (9), (10) with (32), (33) shows a dramatic degradation in the case when a periodic sequence is used for WM. In fact, in order to "compensate" an increasing of r^u, say by m times, it is necessary to increase N also by m times for the WM method when using double sequences (see eqs. (9), (10)), while it is necessary to increase N by m^ times for the WM method when using a periodic sequence. This situation is illustrated in Fig. 1, where the number of WM bits required to provide = Pfa = 10"'' is presented versus rjw. (It is worth to remark that a similar effect of "quadratic compensation" is known in telecommunications spread spectrum systems in the case when it is necessary to use a noncoherent receiver [8].) This quadratic compensation is a pay off for the use of the semipublic method that works (as we show in the sequel) for any distortion constraints after WM (rj^) and after attack (jJq) in contrast to the previous method that works only when ria » r?«,. In order to show that this method is actually WM semipublic instead of WM public we remark that an attacker may always disable the WM by creating the noise sequences as follows: - For the case of WM absence: e(n) = T]a » I, we get from (40), (41) 1-Q Pfa = Q (42) (43) This case is illustrated in Fig. 2, where the number of WM bits required to provide Pm = Pfa = 10 ^ is presented versus 77^. We can see from (40), (41) that in contrast to the first method based on the use of a double sequence, the strong restriction rja ^ Vw, is no longer necessary here and any high reliability of watermarking can be provided for any r]a, r]^ at the cost of increasing N. And, in contrast to WM detection by ordinary users (see (32), (33)) we get from (40), (41 ) a linear compensation for WM owners who posses the secret key sequence 7r(n). Moreover, those owners can significantly improve WM detection if the CM is known by the WM decoder and it is considered as part of the secret key. In fact, in this case the owner's detector is able to calculate 2No A = Y, (S'in) - Cin)) 7r(n) (44) n=l and compare it with some threshold A. The variable A = Ao in the case of WM absence and the variable A = Ai in the case of WM presence are, as before, Gaussian variables. It is easy to show that £;(Ao) = 0 , £;(Ai) = 2aiVo varAo = ANoa"^ = var Ai (45) Substituting (45) into (6), (7) and taking into account (38), (39) we get Pm = l-Q Pfa = Q A' V (A' - 1). No in-i) No iv-i) (46) (47) where A'= A comparison of (46), (47) with (40), (41) shows that the case in which CM is used by the owner as decoder is more favorable for WM detection. Let us confirm this fact by means of the following: Example. If rju, = 120, rja = 100, then the probabilities Pm and Pfa are the same for both cases (in which CM is known and is unknown by the detector) if and only if the number N of CM elements used for WM in the second case is 300 times greater than this number as required for the first case. ■ 3 Conclusion and Open Problems In this paper we have proposed two constructions of semipublic watermarking. Such schemes enable WM detection for any ordinary user whenever the SM has not been subject of a previous attack attempting to remove the WM or to disable it. However these schemes enable WM detection even after an attack if some distortion constraints are satisfied but it is possible just by the WM owner only. We have derived the formulas for the probabilities of WM-missing and WM-false alarm as functions of distortion constraints and the length of WM. These probabilities approach to zero, as the length of WM approaches to infinity, but only under some strong distortion constraints for the first method and without any restrictions for the second method. We have shown also which significant gain in the length of WM can be achieved if CM is used at the detection performed by the WM owner. We emphasized also a "quadratic compensation behavior" of the second semipublic scheme: in order to compensate an m times increase of the distortion constraint given by the signal-to-noise-ratio, it is necessary an rn? times increase of the WM length. Thus, an interesting open problem is to propose a WM semipublic scheme having linear compensation for any distortion constraints. Perhaps a possible solution to the last problem can be provided by using the knowledge of the CM at the encoder side to form WM as it has been considered in [5]. There is also a more interesting open problem: how to design an effective WM pure public scheme and present its performance evaluations. It is worth to note that there exists a trivial construction of a semipublic WM-scheme in which two independent additive WM sequences are used to watermark CM. Namely, let S{n) = C{n) + Wsin) + Wp{n) (48) where Wg (n) is a secret sequence, known only by the WM-owner, and 'Wp{n) is a public sequence known by all users. But in this case two main defects arise from scheme (48): The first one is that, using the knowledge of the public watermak Wp{n), it can be removed completely from SM without any distortion of CM. The second is that Wp{n) produces an additional corruption of CM. The WM's presented in this paper should transmit only one bit of information: "there is or there is not a WM in the presented message". This problem statement can be extended to the case of multiple bit transmission. It is just the case of fingerprinting when WM can contain either the name of the WM owner, data and/or the name of person who bought this CM legally from the owner. We foresee that there will not be any problem in such extension and we are going to present its solution in the immediate future. The consideration of additive noise attack differs from our model essentially just by the practical situation condions. But as we have already mentioned in the Introduction of this paper, it provides an useful result for practical WM application because it determines lower bounds for WM reliability. Hence, any practical WM system will require more elements for the WM than our bound. In the near future we are going to consider more general types of attacks on WM systems such as combinations of linear filtering and additive noise attack. References [1] R. E. Anderson. Information hiding: First international workshop. Lecture Notes in Computer Science, 1174, 1996. [2] D. E. Aucsmith. Information hiding: Second international workshop. Lecture Notes in Computer Science, 1525, 1998. [3] I. J. Cox, M. L. Miller, and J. A. Bloom. Digital Watermarking. Morgan Kaufman Publishers, 2002. [4] S. Katzenbeiser and F. Petitcolas. Information Hiding. Artech House Inc., 2000. [5] V. Korjik, G. Morales-Luna, D. Marakov, and L Marakova. A performance evaluation of digital private watermark under an additive noise attack condition. In the forthcoming "VII Spanish Meeting on Cryptology and Information Security" 2002, 2002. [6] L S. Moskowitz. Information hiding: Fourth international workshop. Lecture Notes in Computer Science, 2137, 2001. [7] P. Moulin and J. O'Sullivan. analysis of information hiding. on IT1998. IEEE, 1998. Information theoretic In Proc. IEEE Symp. [8] R. Peterson, R. Ziemer, and D. Borth. Introduction to Spread Spectrum Communications. Prentice Hall, 1993. [9] J. Proakis. Digital Communications, Fourth Edition. Mc GrawHill, 2001. An Efficient Anonymous Fingerprinting Scheme Yong Li, Bo Yang and Xiang Hua National Key Lab. of Integrated Service Networks, Xidian Univ., Xi'an 710071, China Phone: +86 29 8202525 yonglee2001@163.com Keywords: Anonymous Fingerprinting, Digital Fingerprinting, Digital Watermarking, TTP, STPC Received: May 13, 2002 An anonymous fingerprinting scheme was presented by Domingo, which can identify the redistributors without the help of registration authority. However, this scheme on average requires N/2 exponential operations when the merchant identifies the redistributors, where N is the number of public keys in the directory. Chanjoo Chung proposed a more efßcient scheme than Domingo's, but there is a fatal weakness in the proposed registration protocol of his scheme. This weakness causes that any impersonator can personate an honest buyer with the probability of 1/2. In this paper*, we give an efficient scheme that requires only one exponential operation, which improves the whole scheme's efficiency. Security analysis is also given at last. 1 Introduction Protection of intellectual property in digital form has been a subject of research for many years and led to the development of various techniques. Fingerprinting schemes are an important class of these techniques. They are cryptographic methods applied to deter people from redistributing a data item by enabling an original merchant to trace a copy back to its original buyer. Dishonest buyers who redistribute the data item illegally are called traitors. The identifying information, called fingerprint, is embedded into copies of the original data item. The underlying watermarking techniques should guarantee that the embedded fingerprints are imperceptible and resistant to data manipulation as long as a traitor only uses one copy. The first enhancement is the addition of collusion tolerance [1,2], i.e., resistance even if traitors compare up to a certain number of different copies. But both the merchant and the buyer know the fingerprinted copy in a symmetrical scheme, which means that the merchant's previous knowledge of the fingerprinted copies would not be used as proof of redistribution to a third party. A second addifion [3,4,5] is asymmetry, whereby only the buyer knows the fingerprinted copy. The drawback of this scheme is that any merchant knows the buyer's identity even if the buyer is honest. The third addition [6] is anonymity where the buyer can stay anonymous in purchasing a fingerprinted data item. Only when some buyers redistribute the data item, the identity is revealed. We adapt the meaning of anonymity as the original definition in [6], i.e., any coalition of merchants, central parties and other buyers should not be able to distinguish purchases of the remaining buyers. A weak form can easily be achieved by using any asymmetric fingerprinting scheme under a certified pseudonym instead of a real identity. But on finding a fingerprinted copy, the merchant needs the help from a registration authority to identify the redistributors. In [7], Domingo introduced a new anonymous fingerprinting scheme, which identifies the redistributors without the help of registration authority. However, this scheme on average requires N/2 exponential operations when the merchant identifies the redistributors, where N is the number of public keys in a directory. In [8], Chanjoo Chung proposed more efficient scheme than Domingo's scheme, but there is a fatal weakness in the proposed registration protocol of his scheme, which leads that any impersonator can personate an honest buyer with the probability of 1/2. We will give detailed explanation about this point in Section 3.1. In this paper, we introduce an efficient scheme that requires only one exponential operation when one identifies the redistributors, which improves the whole scheme's efficiency. In addition, it is shown that nobody can personate an honest buyer. The remainder of the paper is organized as follows: Section 2 shows our anonymous fingerprinting scheme. Section 3 describes the performance and security of our scheme. Conclusion is given in Section 4. 2 Our Scheme System setup Let p be a large prime such that q = {p-\)ll is also a prime. Let Z^ be the multiplicative group modulo p, and let g be a generator of Z^ such that computing The work is supported by the National Natural Science Foundation of China (No. 69972034) and Foundation of National Laboratory For Secure Communication of China, grand no. 99JS06.3.1 .DZOl 12 discrete logarithms to the base g is difficult. Assume that both the buyer B and the registration authority Ji have ElGamal-type public-key/private-key pairs. The buyer's private key is x^ and his public key is yg ~ S"" "lodp . The registration authority R is Trusted third party (TTP) and uses its private key to issue certificates which can be verified by using it's public key. All the public keys are assumed to be known and certified. The whole scheme is constructed as follows: Protocol 1 (Registration) Protocol 2 (Fingerprinting) RC B yr -► Compute: ~ yr '' p y, = g 'l mod p Encrypt i2 Decrypt Check: S/' s mod p >■.'' = r» mod p Create: Cert(yi) w [Vi, CmOl)]. lexi Sign:text Sig=Sign,i(tcxt). Input: ■v'A'. .vn— M Cheek: Cert(y,) Record: [y,, Cert(yi)] Cc«0'ill.Vi) STPC lin= Hrijy,(lcxl.sig.y,) lin:/}',(y,,Cen(y,lli J. jj) -ilem'= Fmg(Hem ,emh) V] ipri Hem veri veri (i) R chooses a random secret nonce a:, e Z^ and sends y^ = g"' mod p to B . (ii)B chooses secret random numbers s, and s^ in Z^ such that ^,52 and computes 5, = mod p and y^=g''moAp , encrypts s^ using the registration authority's public key pk,, into , and then sends , y, and to R . The buyer B convinces R with zero-knowledge the possession of s,. In fingerprinting, y, will act as a pseudonym and an anonymous public key of the buyer B . (iii) The registration authority R decrypts the value ^pkS^i) using his private key sk^ and checks that mod/3 and y^''=y^moàp hold. If verification is successful, R returns to B the certificates Cert{y,) and Cert{y,\\s,). By going through the above registration procedure for several times, a buyer can obtain several different pseudonyms y,. Figure2. Fingerprinting Protocol (i) The buyer B sends and text to the merchant M , where text is a string identifying the purchase. B computes an ElGamal signature sig on text using the private key s,, sig is not sent to M. Signature process is as follows: (a) Selects a secure random number k^Z^ o (b) Computes H(text)iH{ ) is a Hash function) r = mod p s = (H(text) - mod(/7 -1) o (c) Signature is sig = {text, r, s) o (ii) U verifies the certificate on y, and records ly, \\Cert{y,)]. (iii) B and M enter a secure two-party computation [9]. M's inputs are text, v, and item, where ;to«is the original information to be fingerprinted. The inputs of B are sig, s^ and Ce/-(y, || ^j). The computations performed are: (a) ver, = Verijy,(text,sig,y^). The signature sig on text is verified using the public key y,. The output ver, is a Boolean variable that can only be seen by the merchant M which is true if and only if the signature verification succeeds. {b)ver^ = Verify^(y^,Cert{y^ || Firstly, the certificate Cert{y^ || i^) is verified. Secondly, it is verified that the value of y^ in the certificate Cert{y^ || s^) is the same as the value y^ input by M . Thirdly, it is checked that the value of Jj in the certificate Cert{y^ || s^) is the same as the value Sj input by B. The output ver^ is a Boolean variable only seen by the merchant M which is true if and only if the aforementioned checks succeed, (c) item'= Fing{item,emb) . A classical fingerprinting algorithm is used to embed emb into the original information item, where emb = text || sig || y, || II Cert(y, || s,) (2) The fingerprinted information item' is obtained as out and is only seen by the buyer B . In the above two-party computation, M obtains outputs first and, unless ver, and ver^ are both true, B cannot obtain the output item'. Protocol 3 (Identification) On finding a redistributed copy, M extracts emb. The extracted information contains the values specified by equ.2 and is combined by M with the purchase record [y,,Cert{y^)\ to construct a redistribution proof (i) The signature sig on the text is verified using y,. (li) It is checked that the value y, is the same as the value y, in the certificates Cert{y^) and Cert{y^ || i^) . Since it is part of the certificates, y, cannot be altered, (iii) Finally, to identify a buyer, the merchant M computes y/' = y^ mod p . The dishonest buyer B has been identified. Note that, since 's certified, it cannot be forged by the merchant M to unjustly accuse a buyer. Protocol 4 (Disputation protocol) This protocol is perfonned only when the merchant M shows the redistribution proof to an arbiter. The merchant M sends the proof (purchase record [>',,Cert(;i^,)] and the extracted information emb) to the arbiter. The arbiter verifies the proof He first verifies the certificate Cert{y^) using the registration authority's public key, then checks if y,'' = _v„ mod p hold. If above three verifications in the identification protocols are valid, then the owner of the public key y^ is accused. If the registration record is necessary to prove guilty of buyer, the arbiter asks registration record to the registration authority. 3 Security analysis 3.1 The Security weakness of Chanjoo Chung's scheme Chanjoo Chung [8] gave a more efficient scheme than Domingo's, but there is a fatal weakness in his registration protocol. We review this registration protocol. The buyer B chooses two secret random numbers and ij in Z^ such that = x„ e Z^ , computes J', =g''mod/? , encrypts ^^ using the registration authority's public key sends and to the registration authority Ä . decrypts E with his private key sk,^ and checks if yg = y, ''' mod p . If this is hold, R returns to ß the certificate. In the above procedure, Ji verifies if a buyer is the owner of y^ by only checking whether yjj - y, '' mod p . However, a malicious buyer can personate the owner of y^ by selecting t and x from Zp such that y^ ^f^'mod p . We can construct such values t and x. Based on the Fermat theorem and the Quadratic Residue theorem, we have yB = ys ^"''^"ys mod p , where (p-l)/2 _ modulo p. The probability of y^ being a quadratic residue is 1/2. If y^ is a quadratic residue, we can factor (/? + ])/2 into the multiplication of x^ and x^ with high probability, i.e., (p+ l)/2-x^x^. Let t = y/' mod p and x — x^, we gain t and x satisfying =/''mod p , which means we can personate the buyer B . 3.2 The performance and security of our scheme Performance We now discuss the performance and security of our scheme. Firstly, in the registration protocol, we replace in Domingo's scheme with s^- x„b Z^. In view of security, the length of key should be two times longer than the one in Domingo's scheme. But computation complexity isn't increased since x^ does not participate in the computation when the scheme is performed. Secondly, in order to transmit s^, we require the encryption and decryption on s^, which adds 2 exponential operations in our registration protocol than Domingo's, but pass numbers and transmitted parameters are both decreased by one. Finally, when the merchant identifies the redistributor, exponential operations in our scheme are required 1 time, but averagely required NU in Domingo's scheme, where N is the number of public key in directory. Generally, the number of public key N is very large, which means that much computation quantity is needed. In order to accurately illuminate our scheme's efficiency, we contrast our scheme with Domingo's scheme according to the computation quantity of view. This result is as follows (Table 1): ^^^^ Scheme Object^^^ Domingo's Scheme Our Scheme Exponential Operations 14+N/2 (Average) 13 (Any case) Multiply Operations 8 6 Transmitted Parameters 22 18 = 1 mod p if jg is a quadratic residue Table 1. Comparison of performances Security Since our scheme is the same problem based on computing discrete logarithm as Domingo's scheme, security is not decreased than previous scheme. The following two results show the security of our scheme. Proposition 1 (Buyer's registration security) Registration protocol provides any impersonator cannot personate an honest buyer. Proof: In registration, if some impersonator wants to personate an honest buyer B, he must find the values y,', 5,'and ij' which are related in the same way as y, , 5, and , i.e. y„ =y,"^'mod;7 and y/' =5,"''modp . Hence the impersonator can compute the discrete logarithm x^ = log^ y^ mod p . If the impersonator is feasible, so is computing discrete logarithm problem. In general, discrete logarithm problem is hard, so any impersonator doesn't make x^ such that Vr = s'' "lO'i P ■ Proposition 2 (Buyer's anonymity) An honest buyer who follows the fingerprinting protocol will not be identified if computing discrete logarithm is hard and secure two-party computation is feasible. Proof: In the fingerprinting protocol, the merchant M knows [yt,Cert(y^)] and his outputs of the secure two-party computation that ver^ and ver^. Finding the public key y^ would require knowledge of s^ . However, if the secure two-party computation is feasible, the merchant will not attain any knowledge of • 4 Conclusion We presented an efficient anonymous fingerprinting scheme. It not only protects the electronic data copyright and hides the buyer's identity, but also possesses higher efficiency than Domingo's scheme. Since our scheme is based on discrete logarithm, its security is the same as Domingo's scheme. With the development of electronic commerce, more efficient scheme is necessary. The efficient of scheme will play an important role in defending against the piracy of many software and multimedia contents. Electronic Information with Automatic Identificat ion of Redistributors". Electronics Letters 43/13, 1998, pp 1303-1304. [8] Chanjoo Chung. Seungbok Choi, Youngchul Choi, Dongho Won. "Efficient Anonymous Fingerprin ting of Electronic Information with Improved A utomatic Identification of Redistributors". In PK C2000,pp 221-234. [9] Chaum D., Damgaard. I. B., and Van De Graaf. J. "Multiparty Computation Ensuring Privacy o f Each Party's Input and Correctness of the Res ult". Advances in Cryptology, Proceedings of C RYPTO '87, vol. 293 of Lecture Notes in Com puter Science, Springer-Verlag, 1987, pp.87-119. [10] Chaum D. Evertse J. H. and Van De Graaf J. "An Improved Protocol for demonstrating Posses sion of Discrete Logarithm and Some Generaliz ations". Advances in Crypto-Eurocryt'87. LNCS 304, Spinger-Verlag, Berlin 1988, 127-141. 5 Reference [1] G. R. Blakeley, Catherine Meadows, George B. Purdy, "Fingerprinting Long Forgiving Messages". Crypto'85, LNCS 218, Spinger-Verlag, Berlin 1 986, 180-189. [2] Boneh. D and Shaw. J, "Collusion-Secure Finger printing for Digital Data". Advances in Cryptolo gy. Proceedings of CRYPT-0'95, vol. 963 of LN CS, Springer-Verlag,Berlin 1995, pp. 452-465. [3] Pfitzmann. B and M. Schunter, "Asymmetric Fin gerprinting". Advances in Cryptology, Proceeding s of EUROCRYPT'96 v-ol. 1070 of LNCS. Spri nger-Verlag, 1996,pp.84-95. [4] Pfitzmann. B and M. Waidner, "Asymmetric Fin gerprinting for Larger Collusions".4th ACM conf erence on Compuetr and Communication Security, Zurith, April 1977, 151-160. [5] Ingrid Biehl, Bernd Meyer, "Protocols forCollusio n-Secure Asymmetric Fingerprinting". STACS97, LNCS 1200, Spinger-Verlag, Berlin 1997, 399-4 12 [6] Pfitzmann. B and M. Waidner, "Anonym-ous Fin gerprinting". Advances in Crypto-logy, Proceedin gs of EUROCRYPT'97. v-ol. 1233 of LNCS. Sp ringer-Verlag,1997, pp.88-102. [7] J. Domingo-Ferrer, "Anonymous Fingerprinting of An Anonymous Mobile Agents Scheme for Secure Web Transaction over the Internet Changjie Wang and Yumin Wang National Key Lab. On ISN, Xidian University, Xi'an 710071, P.R.China cjwang@ee.cityu.edu.hk, ymwang@xidian.edu.cn AND Fangguo Zhang CAIS Lab. ICU (Information and communications Univ.), Korea. zhfg@icu.ac.kr Keywords: Mobile Agent, Digital Signature, Anonymity and Electronic Commerce Received: May 7, 2002 A major problem of mobile agents is their apparent inability to authenticate transactions in hostile environments. In this paper, we propose a new secure anonymous mobile agent scheme for the prevention of agent tempering without compromising the mobility or autonomy of the agent In our scheme, a mobile agent can produce valid signature on Website's bid (means that transact a contact with the Web site) on behalf of its customer, without leaking the customer's really private key. In addition, the anonymity of the customer is also achieved when its agent transacting with the Websites. Furthermore, the customer who issued a malicious agent or deny the transaction can be identified and revealed by Agent Management Center (AMC). Therefore, our scheme is practical in the future electronic commerce over Internet. 1 Introduction Mobile agents are autonomous software entities that are able to migrate across different execution. In contrast to traditional communication mechanisms like client-server system, the main feature of mobile agent system are mobility and autonomy, which make permanent connections unnecessary; thus mobile agents are suitable for providing low-bandwidth connections and asynchronous communication [1,2,3], Furthermore, they provide better support for heterogeneous environments such as World Wide Web. The characteristics of mobile agents make them ideal for electronic commerce applications in open networks. Besides providing a very flexible approach for information gathering on special products ^ service and assets available from the several company servers they visit, they can effectively take over the different aspects of the electronic commercial transaction, from price settlement to paying and delivery of goods purchased. However, mobile agents are vulnerable to several attacks [4] and in particular to attacks by malicious hosts. Without any protection scheme, a visited site may read an agent's data and thus collect information about the agent's owner, e.g. its services, customers, service strategies, collected data, etc. Furthermore, In order to contact transaction with Websites, and sign on a contract on behalf of its' owner, the agent software may take the private key of its owner when roaming among Websites. In such case, the malicious host may steal and abuse the private key of the customer easily. In this paper, we propose a secure mobile agent scheme for Web transaction over Internet, where both the securities of the Websites and the mobile agent software are considered. In addition, the anonymity of the customer is achieved during the transactions, which is a new security property of our scheme contrast with existing mobile agent systems. Following is the organization of the paper. We firstly present the previous work in Section 2. A secure mobile agent scheme and the implementing protocols for Web transaction are proposed in Section 3, in which allow a mobile agent to conduct a transaction with the Website without being abused, in Section 4, we analyze the security of our scheme and finally the conclusion. 2 Previous Work By far, many mobile agent systems have been proposed [5,6,7], most of which have considered the security problem. The most security concern of current mobile agent systems is how to protect Web server from attacking by the malicious agent software. The familiar security measure is based on the rules that the Web server should verily the identity of the agent (i.e. verily the customer's signature on the agent software or verily the signature signed by agent on behalf of the customer) before authorizing the access of the agent software. However, the security of the agent is seldom considered. Usually, the protection of mobile agent software from malicious host is considered more difficult than that for Websites. Until quite recently there was a general belief that mobile agent vulnerability could be prevented only with hardware solutions. Such solutions, as described in [2], are always based on an extra trusted and tamper-resistant hardware in system. However, the above belief has been shown misleading in [8], in which Sander and Tschudin propose the use of encrypted functions to solve the security problem under the conditions without extra hardware. As described in [8], the user encrypts a function s attached to the agent, which is then executed by the Website, without the host having access to the j. We give an example to show the above solution: Suppose that a customer wishes to send a mobile agent to purchase some goods from an electronic shop over Internet. The ägent can authenticate the transaction only if it is able to use a signature ftinction i (i.e. knowing the secret key of the customer) of the customer. However, the agent is executed by a potentially malicious Web server. To protect the signature function s, the customer encrypts it with a function / to obtain: ^./^„^rf = ('/(■) ) and embeds the pair of llinctions {fOfsignedO) into the agent executable code. On migration, the Web server executes the pair (f(.),fsigmdC)) on input x (which is linked to the server's bid) to obtain the so-called undetachable signature pair: f(x) = m and fsig„e) ' = (h')" = k (.). Thus, on migration the server executes the agent on the input x (which is linked to the server's bid) to obtain the undetachable RSA signature (m, z), where m = f(x) - h" mod n and z == fsigm;d(x)'= mod n = (H')' mod n =( h''f= m'' mod n = s(m). Above scheme is an effective implementing of undetachable signature. However, the scheme is not very practical when applied to electronic commerce due to the less consideration of users' anonymity. It is well known that the anonymity of users is an important consideration in electronic commerce. For example, anonymous electronic payment scheme is suggested for E-commerce, which is designed for the protection of users' privacy. That is, the bank should not know the form details of the e-cash withdrew by the customers, and the electronic shop should not know the identity of the customer in an electronic transaction. More discussion about the anonymity of electronic payment can be referred to elsewhere [10][11]. Such anonymity property of the users will has to be broken if an agent system is applied for electronic transaction, without considering the anonymity of the agent. That is, the shop server may reveal the identity of users in an electronic transaction easily just by verifying the identity of the agent, though an anonymous electronic payment system may be adopted. 3 A Secure and Anonymous Mobile Agent Scheme In this Section, we propose a secure and anonymous mobile agent scheme for electronic transaction, using a digital signature algorithm with pair of one-off keys. In our scheme, not only the customer's private key but also the anonymity of the user can be protected. We first introduce the model of our scheme, and then propose the implementing protocols. An elliptic cure based digital signature with pair of one-off keys is also proposed in order to protect the anonymity and private key of user. Model There are three parts in the model of our scheme, named "User Agent Home {UAH)", "Agent Management Center {AMQ" and "Websites" respectively, as shown in Fig.l. )Agent home registraion (|)Preparing agent ČOMigration and transaction with websites (4)malicious agent tracing User Agent Home Fig. 1 Model of our scheme The working flow is illustrated at the down right corner of the Fig.l, and the explanations of the participators in the rnodel is below; User Agent Home {UAH)\ In our system, an agent control platform (called "User Agent Home") should be installed on each User's computer, who is in charge of the preparing, issuing and receiving of the User's mobile agent. Agent Management Center {AMC)\ We introduce a new role (i.e. AMC) in our model, whose duty is dealing with the registration of customer and the tracing of malicious agent. Websites: We use "Websites" to denote all kinds of Web severs (may be electronic shop) over the Internet. Implementing protocols In the following, we present the detailed implementing protocols of our scheme: Settings. We use ECC-based signature scheme settings. Let /7 be a large prime , a, b G GF(p) satisfy The elliptic curve E(s,,h){GF(p)) is defined to be the set of points {X,Y)G GF(p)XGF(p) satisfying equation Y^ = )Č+aX+b and a special point O (called infinity). These points form; an. Abelian; group. G is an element of £(a,b)(GF(/p)) with order q, which is a prime at least 16Ö bits long. denotes Xhs x-coordinate of point A. For more details of elliptic curves, one can be refer to [12,13]. Let 7/ be a one-way hash function, //:{0,1}^{0,1]^(ä; = 160). Denoted (»I*) by the concatenation of two strings. In our scheme, AMC first selects JQ^c 6 GF{q)* randomly as his secret key, then calculate his public key Pamc=XamcG=(Xp, Yp). Finally, AMC publishes the following public parameters to all Users and Websites: ( £(a,b)(G^(p)), G, q, P MO H)- User registration. In our scheme, each User should first register with AMC before accessing the service of mobile agents system. The protocol for registration (between UAH and AMC) is shown in Fig.2 (in the following, IDx denotes the identifier of X). 294 Informatica 26 (2002) 291-297 C. Wang et al. UAH (1) UAH first selects secret key: Xc G RGF(q)*, and calculates: Yc=XcG (6) Verifies whether (Aq J' c ) is really from AMC on Vc by checking the congruence: + RMc)Pmìc (2)submits(7^,/Dc) Internet (5)return(/(o Jc) AMC J (3) AMC then selects wc S rGF(^)* randomly, and calculates: a) Ac = w^G-Y^', + mod q (4) records ( Ac, Yc. Yo HI. Wc) Fig.2 Protocols for User registration At the end of above protocol, AMC records the information of the user's identity (Yc, IDc) while knowing nothing about the private key of user. In addition, a registered UAH obtains a certificate {Ac,, Vc) from AMC. Here, Yc and Xc are the long-term pair of keys of the User, and {Aq Vc) is the long-term certificate of the user. Preparing agent. Before issuing mobile agent according to the User's request, UAH should generate a pair of one-off keys and a virtual certificate attached to the agent as the part of its executable code. This procedure is described below: Firstly, UAH select secret key xcE RGF(q)* randomly, and the corresponding public key yc=xcG. Then calculate: T= vG, ( vrG i{GF(q)* and ly should be selected such that R,(T)=t^O modq), a=Ac+T, ß=ta, z=tR^(Ac) mod q /1= Yct+( Vt - Xct + xcH(M) )H(Xp\ Yp) mod q, here, M is a message includes all static part of agent code (such as the customer's request, routing table and the time-stamp). Thus, the UAH has produced a pair of one-off keys {xc,yc), with a virtual certificate VCert: {yc ,cc, ß, Ä, z}, for the mobile agent. Then UAH attaches the above data to the mobile agent code as shown in Fig.3, and issues the agent out. User's request Informat ion base Routing table Time stamp Other static data Dynamic data Veert-, {yc.a ß ^ {yc, Xc} <- M -► Fig.3 The structure of an issued mobile agent Executing agent. On migration, the Websites first verify bid according to the User's request), to obtain an one-off the validity of the agent and then execute the agent on signature Sig:{K,r}of m. The detailed protocol is input m = H (IDw, W_bid) (here, W_bid is the Website's described below: Parameters Input Output {yc, xci- pair of one-off keys of User Verct {yc.a, ß À, z}-. one-off certificate of User Website's bid: m=H (IDw, W bid) One-off Signature on m: Sig:{K,r} M: all part of static code of agent (constraints) (2) Migration Fig.4 Protocols for executing agent We give some explanations of above protocols. In step (4), Websites should verify the validity of the agent by checking the congruency: ÀG = H(Xi,\\Yp)( ß+ycH(M)) + zPamc ' before authorizing the mobile'agent corresponding access to the Website's resource. Here, successful verification means that the mobile agent is really issued by a registered UAH and does not been modified while roaming over Internet. In this way, the Websites can resist the attack from a malicious agent. In step (6), the agent generates a one-off signature on the W_bid (the bid from the Website) if the bid satisfies the Users' request. Otherwise, the agent just migrates to the next Website for another negotiation. In this way, the agent can sign on a contrast (i.e. the W_bid from Website) on behalf of its' owner without leaking the real private key of the customer. Note that, M (includes the request of User) is a constraint to prevent any malicious Websites from abusing the one-off keys to sign on a bogus bid. More security considerations will be discussed in next section. In step (9), message Sigiv(IDw, W_bid) means that the Website is required to sign on (ID^, WJ>id) to bind itself ' That is: H(Xp\\Yp)(ß+ycH(M)) + zP^^c = H(Xp\\Yp)(ta+xcGH(M)) + tR/Ac)X,Mc G = (H(Xp\\Yp)(tw,-tXc+t W+xcH(M)) + tR,(Ac)X^SG = (t(H(Xp\\Yp)wc +R.(Ac)X„^c) + H(Xp\\Yp)(t V-tXc+xcH(M)))G = (tyc+ (t V-tXc-yxcH(M)) H(Xp\\Yp))G = À.G. to the bid to avoid the impersonation attacks on the Website. After the transaction, the agent obtains a message of Website's bid, and the Website records the data {Veert, Sig, M), which is helpful in tracing the User when necessary. Note that even if a Website abuses the one-off private key to produce a signature of the User for a bogus bid, the signature will be invalid due to that the content of the signature may disagree with the constraint M, which includes the User's request. In fact, if the Website is not willing to bid for a transaction, then it forwards the agent to another Website. Agent identification. When necessary, the Websites can submit the VCert and Sig of an agent to AMC to reveal the identity of the mobile agent (i.e. its Owner). Here, we use "necessary" to denote the situation when the mobile agent is considered to be malicious or the User want to deny the transaction signed by its' agent. When receiving VCert, Sig and M, AMC first verifies whether the User of the agent has been registered by checking the congruence: /IG = H(Xp\ I Yp)( ß+ycH(M)) + zP^c ■ Then for each record (A,-, r/ ,7 ,/D, ,W/ ) in AMCs database, AMC checks whether the following congruence 9 holds: ß - (z/R/Ai))a^. It can be proved that the above congruence has a unique solution ( Ac, VcJc JDc,wc). In such way, the identity of the mobile agent (i.e. its Owner) can be identified by AMC. It seems that this - That is: (z/R,(Ac))=( tR,(Ac)/ R.(Ac)) a =ta=ß approach is not efficient enough if there are many Users in one AMC database, and we will make more improvements in the fiature work. 4 Security analysis of our scheme Our scheme is mostly based on a digital signature with pair of one-off keys and its security is depended on elliptic curve discrete logarithm problem (ECDLP). As it is well known that to solve the ECDLP over finite field is open problem, we presume that the attacker do not have the ability to solve the ECDLP. In the following, we make a security analysis of our scheme: (1) One important security property of our scheme is that the mobile agent can produce valid signature on Website's bid on behalf of its customer, without leaking the customer's long-term private key. Instead of the long-term private key, in our scheme, a pair of one-off keys and a Veert is attached to each agent to make signature. Clearly, it is easy for a malicious Website to construct a signature on a bogus W_bid for a given {yc, xq). The problem for a malicious Website is to construct a new Verct': {yc .OC, ß, À., z} of the user which will include modified constraint M' of the user. As proposed in our protocols, if above attack is possible, then one can also solve the ECDLP. (2) Ensuring users' anonymity while using the mobile agent system is another new security property of our scheme, which is not achieved in other existing mobile agent system. In some case, the Websites may deal with many agents from the same user for different goals (such as for enquiry of different goods). If these agents are signed with the unaltered private key of Users, the Websites will identify the customer of these mobile agents easily just by comparing that whether both of the signed agents can be verified by the same public key (i.e. the same public key certificate). In our scheme, the VAH produces a pair of one-off keys and a virtual certificate attached to each issuing mobile agent. Even the Web server has transacted with many agents issued by the same user, the Website cannot identify the user because that the agents are attached with different pair of keys and Veert. In order to identify the user by recuperating his really certificate {Aq rd from the virtual certificate VCert: {yc. a, ß, Ä, z}, what a Websites have to do is shown below: First, solve the t from the equation: ß=ta *, therefore get the T; accordingly, solve the^c as: Ac =a- T\ Second, solve the Xamc from the equation: Pamc'^-^amcG solve the X c from the equation: yc=xcG * and solve the V from the equation: T= w G. Then solve the variables: Yc,Xc, Wcfrom the simultaneous equations: Yc=H{X,\Y,,)W,-RMC)^A>.C A = + + XcH{M))H{Xp \\Y, ) To make a successfully attack as shown above, a Website has to solve the ECDLP at three places, marked out with *. As our presumption above, the ECDLP is difficulty to be solved. Therefore, the anonymity of the agent is achieved. In addition, AMC can repeal the anonymity of agent's User when necessary. However, such revocation is under constraints and can be carried out by AMC only when an agent is regard as malicious. In this way, any User also cannot deny what its agent has transacted with the Website. 5 Conclusion Current research on software-based active prevention contradicts the general belief that mobile code vulnerability could be actively prevented only with hardware-based solutions. In this paper, we propose a practical scheme for mobile agents to conduct private and binding transactions in a hostile environment, by using cryptographic technique. As a conclusion, we summarize the main features of our scheme below: • Efficiency. The implementation of our scheme is most based on a signature scheme of ECC, which is more effective due to that the key length and computation amount of ECC-based signature scheme are less than that of other similar scheme, such as RSA. • Secrecy: The mobile agent can contact a transaction with the Websites by making a signature Sig, while nothing of the User's secret key is leaked. In addition, the Websites is able to bind the User to the transaction via Sig and Veert, which link the constraints of the agent A/and the bid of the Website lV_bid. • Anonymity: The mobile agent issued by a registered User can make an anonymous transaction with Websites. The Websites can only verify the validity of the agent to resist the malicious agent, while knowing nothing about the User's identity. • Fairness: A dishonest User who issued a malicious agent or denied the transaction contacted by its agent can be traced and revealed by AMC. Note that the work mode of AMC is off-line. This means that AMC will not involved the transaction only when a disputation is happened. • Unforgeability: A malicious Website can use a pair of one-off keys {xc, yc} and the Veert { yc, a, ß À, z } io generate a forgeable signature Sig{K', r') of a message m ' that includes a bogus bid WJjid'. But such a signature will be invalid due to that the pair of keys {xc, yc} and the Veert {yc,a,ß,Ä,z} are constrained by a unique M, and the W_bid' is non-compatible with the customer's request in constraint M. 6 Acknowledgment This work is supported by the National Nature Science Foundation of China under the reference number 60073052. Reference: [1]. Danny B. Lange and Mitsuru Oshima. "Seven Good Reasons for Mobile Agents", Communications of ACM, P.88-89, 1999 Mar. [2], Chess, D., Grosof, B., Harrison, C., Levine, D., Parris, C. and Tsudik, G. "Itinerant Agents for Mobile Computing", Technical Report, RC 20010 (1995) IBM T.J. Watson Research Center, NY [3]. Kotzanikolaou Panayiotis, Katsirelos George and Chrissikopoulos Vassilios. "Mobile Agents for Secure Electronic Transactions". Recent Advances in Signal Processing and Communications, World Scientific and Engineering Society Press (1999) 363-368. [4]. Wayne Jansen, Tom Karygiannis. "NIST Special Publication 800-19 - Mobile Agent Security". Technical Report MD 20899, National Institute of Standards and echnology Computer Security Division Gaithersburg, 1999. [5]. IBM, Inc. IBM Aglets Documentation web page. Available at URL http:// aglets.trl.ibm.co.jp/documentation.html, 1998. [6] "Concordia-Java Mobile Agent Technology". Available at http://www.meitca.com/HSL/Proiects/Concordia/ [7]. Robert S.Gray. "Agent Tei. A flexible and secure mobile-agent system." In Proceedings of the Fourth Annual Tcl/Tk Workshop (TCL'96), Jul 1996 [8]. Sander Tomas and Tschudin Christian F. "Protecting Mobile Agents Against Malicious Hosts". Mobile Agent Security, LNCS Vol.1419, Springer-Verlag, (1998) 4460. [9], Panayiotis Kotzanikolaou , Mike Burmester and Vassilios Chrissikopoulos. "Secure Transactions with Mobile Agents in Hostile Environments". Information Security and Privacy. Proceedings of the 5th Australasian Conference, ACISP 2000. LNCS Vol. 1841, SpringerVerlag, pp. 289-297, 2000. [10]. J.Claessens, B.Preneel and J.Vandewalle, Anonymity controlled electronic payment systems, Proceedings of the 20"^ symposium on information theory in the benclux. Haasrode, Belgium,May 27-28 1999, pp.109-116. [11], D. Chaum, A. Fiat, and M. Naor, "Untraceable electronic cash", in Proceedings of Crypto'88, LNCS, Springer-Verlag, pp. 319-327, 1990. [12]. V.S.Miller, "Use of Elliptic Curve in Cryptography", In Advances in Cryptology— CRYPTO'85(Santa Barbara,Calif.,1985),LNCS 218(1986), pp.417-426, Spring-Verlag. [13]. N.Koblitz, "Elliptic Curve Cryptosystems", Mathematics of Computation, 48(1987), pp.203-209. Compiling and Using the IJS-ELAN Parallel Corpus Tomaž Erjavec Department of Intelligent Systems Jožef Stefan Institute Jamova 39 SI-1000 Ljubljana Slovenia tomaz.erjavec@ijs.si, http://nl.ijs.si/et/ Keywords: natural language processing, corpus annotation, multilinguality, lexicon extraction Received: July 10, 2002 With increasing amounts of text being available in electronic form, it is becoming relatively easy to obtain digital texts together with their translations. The paper presents the processing steps necessary to compile such texts into parallel corpora, an extremely useful language resource. Parallel corpora can be used as a translation aid for second-language learners, for translators and lexicographers, or as a data-source for various language technology tools. We present our work in this direction, which is characterised by the use of open standards for text annotation, the use of publicly available third-party tools and wide availability of the produced resources. Explained is the corpus annotation chain involving normalisation, tokenisation, segmentation, alignment, word-class syntactic tagging, and lemmatisation. Two exploitation results over our annotated corpora are also presented, namely a Web concordancer and the extraction of bi-lingual lexica. 1 Introduction With more and more text being available in electronic form, it is becoming easy to obtain large quantities of digital texts and to process them computationally. If a collection of such texts is chosen according to specific criteria and is consistently and correctly marked-up [19], it is said to be a text corpus. Such corpora can be used for a variety of different purposes [17], from empirically grounded linguistic studies, lexicography and language teaching, to providing datasets for language technology programs for terminology extraction, word-sense disambiguation, etc. Collected and uniformly encoded collections of texts are already quite useful, but it is the addition of (linguistic) markup that makes corpora a prime resource for language exploration. As will be seen, we view the process of compiling a corpus as one of annotation accrual: starting from a plain text, we successively add mark-up, thereby enriching the information contained in the corpus. This markup is typically automatically produced, but can be hand validated and, in a cyclic process, can serve for inductive programs to learn better models of the language with which to annotate subsequent generations of corpora. The added annotation enables the people and software using the corpus to employ extra levels of abstraction, leading to better exploitation results. If monolingual corpora are already useful for a variety of purposes, it is multilingual corpora that open the way for empirical study of the translation process. Especially valuable are so called parallel corpora, i.e., corpora consist- ing of texts together with their translation into one or many languages. They can be used directly as translation aids for humans or can provide data for the automatic induction translation resources (lexica) and software (machine translation). In this paper we explore the process of compilation and exploitation of such parallel corpora, grounding the discussion in our experience with two annotated parallel corpora: the 7-language MULTEXT-East corpus [6, 9], which contains the novel "1984" by G. Orwell (100,000 words per language) and has had its annotation manually validated; and the larger (500,000 words per language) automatically annotated Slovene-English IJS-ELAN corpus [8, 10]. Our work is characterised by the use of open standards for text annotation and the use of publicly available third-party tools. We claim that it is better to invest labour into producing high-quality annotated corpora than in trying to build from scratch tools for such annotation. Unlike local and idiosyncratic software, linguistic resources encoded in a standard manner will be sooner useful to other research groups. Such largesse aside, there also exist more and more (statistical or symbolic) machine learning programs that are able to induce language models from pre-annotated corpora. They are typically more robust and, with large enough training sets, might even perform better than hand crafted systems. The rest of this paper is structured as follows: Section 2 introduces standards for corpus annotation, which are then used in the examples in the remainder of the paper; Section 3 enumerates the basic (pre-linguistic) processing steps in- volved in the compilation of a corpus; Section 4 details the more complex word-level syntactic annotation, which is performed by a trainable algorithm; Section 5 turns to the exploitation of corpora and gives two examples: an online concordancer, and an experiment in bi-lingual lexicon extraction; Section 6 gives conclusions and directions for further research. 2 Encoding Standards While the question of the encoding format for corpora and other language resources might seem incidental to the main task of producing and exploiting the corpora, it has long been known that the proliferation of data formats and annotation schemes, many of which are proprietary and poorly documented, is a significant bottleneck for resource sharing, re-use and longevity. There have been therefore a number of attempts to standardise the encoding of various language resources, among them corpora. All such standardisation efforts have as their basis the ISO Standard Generalized Markup Language, SGML, or, more recently, the W3C Extensible Markup Language, XML [26], a simplified form of SGML meant primarily for interchange of data on the Web. SGML and XML are metalanguages, that is, a means of formally describing a language, in this case, a markup language. They do thus not directly define a particular set of tags but rather enable the mechanisms for defining such sets for particular purposes, e.g., for the encoding of corpora. The best known and widely used set of conventions for encoding a wide variety of texts, among them corpora, are the SGML-based Text Encoding Initiative Guidelines (TEI), the most recent version of which is also XML compliant [20]. The TBI consist of the formal part, which is a set of SGML/XML Document Type Definition fragments, and the documentation, which explains the rationale behind the elements available in these fragments, as well as giving overall information about the structure of the TEL The DTD fragments are combined to suit an individual project, and, if necessary, also extended or modified. We have used parametrisations of TEI for both the MULTEXT-East corpus as well as for the IJS-ELAN corpus. TEI encoded examples from these corpora will be used in the rest of this paper. 3 Pre-processing the Corpus In this section we deal with the basic processing steps involved in normalising and marking-up the corpus, in order to make it minimally useful for exploitation and to prepare it for further annotation. The steps we outline below usually proceed in sequence, and can be, for the most part, performed automatically although — given the unconstrained nature of texts — are likely to be less than 100% accurate. While further development of tools and associated resources lowers the error rate, manual validation might still be necessary for high-quality corpora. The texts constituting a corpus can be collected from a variety of sources and so usually come in a range of formats. The first step in corpus preparation is therefore invariably the normalisation of the texts into a common format. Usually custom filters — written in pattern matching languages such as Perl — are employed to, on the one hand, normalise the character sets of the documents and, on the other, to remove and convert the formatting of the originals. 3.1 Character sets As far as character sets go the corpus compliers have a few options at their disposal. One possibihty is to use — at least for European languages — an 8-bit encoding in the corpus, preferably a standard one, e.g., ISO 8859 Latin 2 for encoding Slovene texts. While the advantage is that the corpus texts are immediately readable — given that we have installed the appropriate fonts — the disadvantage is that a number of processing applications do not handle well 8 bit characters and, more importantly, that it is impossible to mix languages that use different character sets; this is, of course, a special concern in multilingual corpora. Until a few years ago the standard solution involved translating the non-ASCII characters of the original texts into ISO-mandated SGML entities. SGML (and XML) entities are descriptive names, somewhat like macros, which the application then substitutes for their values. In our case, the names are of the characters in question; so, for example, the Slovene letter č is written as the entity č (small c with acaron), where ampersand starts an entity and semicolon ends it. Such entities for characters are defined in public entity sets, for the case of Sccaron; in ISO 8879 :1986//ENTITIES Added Latin 2//EN, i.e., the added entity set for encoding the Latin alphabets of Eastern European languages. Similar entity sets exist for Western European languages (Latin 1), for Greek, Russian and non-Russian Cyrillic, as well as for mathematical relations, publishing symbols, etc. The advantage of using entities is their robustness: because they are encoded in (7 bit) ASCII characters they are portable, and can be read on any platform. For the application, the SGML processor then translates them into the desired encoding via their definitions. With the advent of XML, this solution has somewhat lost its currency. While entities are supported in XML, the default character set of XML is Unicode, which, because a character can be encoded in two bytes, is sufficient to accommodate most of the characters of the world's scripts; so, this is in fact the only solution for Easter language scripts, such as Kanji. But while using Unicode makes for a theoretically good solution, practice still lags behind, with many applications not yet being Unicode-aware. In our corpora we have therefore chosen to use SGML entities for the representation of non-ASCII characters. 3.2 Markup of gross document structure Various encodings of input texts also encode the structure of the documents in vastly different and often inconsistent manners. This structure includes such things as divisions of the text, headers and titles, paragraphs, tables, footnotes, emphasised text, etc. In general it is a very hard task to correctly and completely transform this structure into descriptive TEI markup. For many natural language processing applicadons this might not even be necessary, as the task here isn't to preserve the layout of the text, but only the information that is relevant to correctly classify the text and to enable linguistic processing. To illustrate a case of relatively detailed structure markup, we give, in Figure 1, a TEI encoded example from the MULTEXT-East corpus.
First part
I

It was a bright cold day in April, and the clocks were striking thirteen. Winston Smith, his chin nuzzled into his breast in an effort to escape the vile wind, slipped quickly through the glass doors of Victory Mansions, though not quickly enough to prevent a swirl of gritty dust from entering along with him.

Figure I : Structure markup in TEI 3.3 Header Information A corpus is typically composed of a large number of individual texts. For.analysing the corpus or for choosing a particular subset out of it, it is vital to include information aboiit^he texts into thexorpus. Of course, the coipus as a unit must also be documented. The TEI provides a header element, expressly meant to capture such meta-data. The TEI header contains detailed information about the file itself, the source of its text, its encoding, and revision history. The information in a text or corpus header can be — depending on the number of texts and the regularity of provenance - either inserted manually or automatically. Given that the corpora discussed in this paper have relatively few components, their headers have been entered manually via an SGML/XML aware text editor. 3.4 Tokenisation and segmentation The next step in corpus preparation already involves basic linguistic analysis, namely isolating the linguistic units of the text, i.e., words and sentences. The identification of words — and punctuation marks — is usually referred to as tokenisation, while determining sentence boundaries goes by the name of segmentation. On the face of it, determining what is a word and what a sentences might seem trivial. But correctly performing these tasks is fraught with complexities [12] and the rules to perform them are, furthermore, language dependent. So, while sentences end with full stops, not every full stop ends a sentence, as with, e.g., Mr. \ and if some abbreviations will never end sentences, e.g., e.g., other almost invariably will, e.g., etc. Correct tokenisation is complex as well; punctuation marks can sometimes be part of a word, as is the case with abbreviations and, say, Web addresses. Some domains, e.g., biomedicine have "words" with an especially complex internal structure, e.g., Ca(2+)-ATPase. In the process of tokenisation various types of words and punctuation symbols must be recognised and this information can be retained in the markup, as it can be potentially useful for further processing. In Figure 2 we give an example of a segmented and tokenised text from the US-ELAN corpus, where the type attribute expresses such information on words. Euromoney's assessment of economic changes in Slovenia has been downgraded (page 6) . Figure 2: Segmentation and tokenisation in TEI While it is possible to write a tokeniser and segmenter using a general purpose computer language there also exist freely available tools for this purpose. We have extensively. used the MULTEXT tools [3], which, however,,no longer, seem to be maintained. Fortunately, other good choices exist, e.g., the text tokeniser tool, LT TTT [13], which is freely distributed for academic purposes as binaries for Sun/Solaris. LT TTT is based on XML and incorporates a general purpose cascaded transducer which processes an input stream deter-ministically and rewrites it according to a set of rules provided in a grammar file, typically to add mark-up information. With LT TTT come grammars to segment English texts into paragraphs, segment paragraphs into words, recognise numerical expressions, mark-up money, date and time expressions in newspaper texts, and mark-up bibliographical information in academic texts. These grammars are accompanied by detailed documentation which allows altering the grammars to suit particular needs or develop new rule sets. While we have already successfully used LT TTT for processing English texts, the localisation of its grammars to Slovene remains still to be done. 3.5 Sentence Alignment An extremely useful processing step involving parallel corpora is the alignment of their sentences. Such alignment would be trivial if one sentence were always translated into exactly one sentence. But while this may hold for certain legal texts, translators — either due to personal preference, or because different languages tend towards different sentence lengths — often merge or split sentences, or even omit portions of the text. This makes sentence alignment a more challenging task. High-quality sentence alignment is still an open research question and many methods have been proposed [23] involving the utilisation of e.g., bilingual lexicons and document structure. Still, surprisingly good results can be achieved with a language-independent and knowledge poor method, first discussed in [11]. The alignment algorithm here makes use of the simple assumption that longer sentences tend to be translated into longer sentences, and shorter into shorter. So, if we come across, e.g., two short sentences in the original, but one long one in the translation, chances are, the two have been merged. Hence the input to this aligner is only the lengths of the respective sentences in characters and the program, with an algorithm known as dynamic time warping, finds the best fit for the alignments, assuming the valid possibilities are 1-2, 0-1, 1-1, 1-0, 2-1, and 2-2. Several public implementations of this algorithm exist; we have used the so called Vanilla aligner [4], implemented in C and freely available in source code. The quality of the automatic alignment is heavily dependent on the manner of translation but, in any case, is seldom perfect. For our corpora we have manually validated the alignments via a cyclic process, with initial errors of alignment corrected and the text then being automatically re-aligned. The end result is the sentence aligned text; Üie alignment information might then be encoded in one of several ways. One possibility is to encode the alignments in separate documents, where only pairs of references to sentence IDs are stored. Figure 3 gives a hypothetical Slovene-English alignment span illustrating the syntax and types (one, many, zero) of the alignment links. The first link encodes an 1-1 alignment, the second a 2-1 and the third an 1-0 alignment. Figure 3: Example of stand-off bilingual alignment 4 Word-class syntactic tagging It is well known that the addition of word-level syntactic tags adds significantly to the value of a corpus [22]. Knowing the part-of-speech and other morphosyntactic features. such as number, gender and case, helps to lexically determine the word and serves as a basis for further syntactic or semantic processing. In a parallel corpus such annotations can also act as guides for automatic bilingual lexicon extraction or example based machine translation. The flip side of morphosyntactic tagging is lemmatisa-tion, i.e., annotating the words in the corpus with their lemmas or base forms. Such a normalisation of the word-forms is useful in concordancing the corpus and in identifying translation equivalents. While lemmatisation for Enghsh is relatively simple (although wolves and oxen complicate matters) it is a more difficult task in Slovene, which is a heavily inflecting language. Manual annotation is extremely expensive, so corpora are typically tagged and lemmatised automatically. Below we explain our work on the US-ELAN corpus, where we used the statistical tagger TnT which had been trained on the MULTEXT-East parallel corpus, and initial results improved in various ways. 4.1 The TnT tagger Trainable word-class syntactic taggers have reached the level of maturity where many models and implementations exist, with several being robust and available free of charge. Prior to committing ourselves to a particular implementation, we conducted an evaluation (on Slovene data) of a number of available taggers [7]. The results show that the trigram-based TnT tagger [1] is the best choice considering accuracy (also on unknown words) as well as efficiency. TnT is freely available under a research license, as an executable for various platforms. The tagger first needs to be trained on an annotated corpus; the training stage produces a table with tag tri- bi- and uni-grams and a lexicon with the word forms followed by their tag ambiguity classes, i.e., the list of possible tags, together with their frequencies. Using these two resources, and possibly a backup lexicon, tagging is then performed on unannotated data. 4.2 The training corpus The greatest bottleneck in the induction of a quality tagging model for Slovene is lack of training data. The only available hand-validated tagged corpus is the Slovene part of the MUUTEXT-East corpus, which is annotated with validated context disambiguated morphosyntactic descriptions and lemmas. These morphosyntactic descriptions (MSDs) for Slovene — and six other languages, English among them — were developed in the MUUTEXT-East project [6, 9]. The MSDs are structured and more detailed than is commonly the case for English part-of-speech tags; they are compact string representations of a simplified kind of feature structures. The first letter of an MSD encodes the part of speech, e.g.. Noun or Adjective. The letters following the PoS give the values of the position determined attributes. So, for example, the MSD Ncfpg expands to PoS:Noun, Type : common, Gender : feminine, Number : plural. Case : genitive. In case a certain attribute is not appropriate for the particular combination of features, or for the word in question, this is marked by a hyphen in the attribute's position. To illustrate the properties of the training corpus, as well as the difference between Slovene and English we give in Table 1 the number of word tokens in the corpus, the number of different word types in the corpus (i.e., of word-forms regardless of capitalisation or their annotation), the number of different context disambiguated lemmas, and the number of different MSDs. The inflectional nature of Slovene is evident from the larger number of distinct word-forms and especially MSDs used in the corpus. English Slovene Words 104,286 90,792 Forms 9,181 16,401 Lemmas 7,059 7,903 MSDs 134 1,023 Table 1: Inflection in the MULTEXT-East corpus 4.3 Tagging Slovene Unsurprisingly, the tagging produced by TnT trained only on the MULTEXT-East corpus had quite a low accuracy; this can be traced both to the inadequate induced lexicon, as more than a quarter of all word tokens in US-ELAN were unknown, as well as to n-grams applied to very different text types than what was used for training. To offset these shortcomings we employed two methods, one primarily meant to augment the n-grams, and the other the lexicon. It is well known that "seeding" the training set with a validated sample from the texts to be annotated can significantly improve results. We selected a sample comprising 1% of the corpus segments (approx. 5,000 words) evenly distributed across the whole of the corpus. The sample was then manually validated and corrected, also with the help of Perl scripts, which pointed out certain typical mistakes, e.g., the failure of case, number and gender agreement between adjectives and nouns. The tagger n-grams were then re-leamed using the concatenation of the validated ELAN sample with the Slovene MULTEXT-East corpus. It has also been shown [14] that a good lexicon is much more important for quality tagging of inflective languages than the higher-level models, e.g., bi- and tri-grams. A word that is included in a TnT lexicon gains the information on its ambiguity class, i.e., the set of context-independent possible tags, as well as the lexical probabilities of these tags. The Slovene part of the ELAN corpus was therefore first lexically annotated, courtesy of the company Amebis, d.o.o., which also produces the spelling checker for Slovene Word. The large lexicon used covers most of the words in the corpus; only 3% of the tokens remain unknown. This lexical annotation includes not only the MSDs but also, paired with the MSDs, the possible lemmas of the word-form. We first tried using a lexicon derived from these annotations directly as a backup lexicon with TnT. While the results were significantly better than with the first attempt, a number of obvious errors remained and additional new errors were at times introduced. The reason turned out to be that the tagger is often forced to fall back on uni-gram probabilities, but the backup lexicon contains only the ambiguity class, with the probabilities of the competing tags being evenly distributed. So, TnT in effect often assigned a random tag from the ones available, leading to poor results. To remedy the situation, a heuristic was used to estimate the lexical frequencies of unseen words, taking as the basis the known frequencies from similar ambiguity classes taken from the training corpus. Using this lexicon and the seeded model we then re-tagged the Slovene part of the IJS-ELAN corpus. Manually validating a small sample of the tagged corpus, consisting of around 5,000 words, showed that the current tagging accuracy is about 93%. As had been mentioned, the lexical annotations included lemmas along with the MSDs. Once the MSD disambiguation had been performed it was therefore trivial to annotate the words with their lemmas. But while all the words, known as well as unknown, have been annotated with an MSD, we have so far not attempted to lemmatise the approximately 3% of the corpus words which are unknown. The results of the tagging were encoded in the corpus as attribute values of the TEI element. To illustrate, we give in Figure 4 an example sentence from the corpus: Razlike med metropolitanskimi centri in njihovim zaledjem so ogromne. / The differences between the metropolitan centres and their hinterlands are enormous. Razlike med inetropolitanskimi centri in njihovim zaledjem so ogromne . Figure 4: Linguistic annotation in the corpus 4.4 Tagging English Tagging the English part of the corpus with the MULTEXT-East MSDs was also performed with TnT, using the English part of the MULTEXT-East corpus as the training set. However, automatic tagging with this model is bound to contain many errors, although less than for Slovene, given the much smaller tagset. Rather than try to improve the accuracy of our own tagging, we opted for additional annotations with other, better, models and also with a better known tagset, namely (variants of) the one used in the Brown corpus [15]. For the additional annotation of the English part we combined the output of two taggers. First, the TnT tagger distribution already includes some English models. We chose the one produced by training on the concatenation of the Brown corpus with the Wall Street Journal corpus; this training set contained approximately 2.5 million tokens and distinguishes 38 different word-tags. Second, we used QTag [16], which is also freely available probabilistic tri-gram tagger, although the underlying algorithm differs from that employed by TnT. The English model of QTag uses a similar, although not identical, tagset to the TnT English one. QTag is also offered via an email service, which in addition to tagging the texts, also lem-matises them; we used this lemmatisation to annotate the corpus. To illustrate the tagging of the English part, we give an example in Figure 5. There are huge dif ferences between the centres and their suburban areas . Figure 5: Linguistic annotation in the English part 5 Utilising the Corpus The US-ELAN corpus was thus encoded in XML/TEI, segmented, tokenised, aligned and tagged with morphosyntac-tic descriptions and lemmas. It was now time to turn to exploiting the corpus. Given that the texts that are included in the corpus do not have copyright restrictions (they are mostly publications of the Slovene government), it was trivial to ensure one type of "exploitation", namely to simply make the complete corpus freely available for downloading: it can be accessed at http://nl.ijs.si/elan/. In this section we discuss two methods of utilising the corpus. The first is geared directly towards human usage, and has to do with making the corpus available for sophisticated on-line searching. The second employs a statistics-based tool that extracts a bi-lingual lexicon from the corpus. 5.1 Web concordancing For our corpora we have developed an on-line concordancing system. This Web concordancer comprises a set of HTML pages, a simple Perl CGI script and a corpus processing back-end. The back-end is the CQP system [2], a fast and robust program, which freely available for research purposes as binaries for a number of platforms. CQP supports parallel corpora and incorporates a powerful query language that offers extended regular expressions over positional (e.g., word, lemma, MSD) and structural (e.g., ,

, ) attributes. The Web page of the concordancer contains various input fields and settings available to the user. The settings and options have associated hyperlinks, and clicking on them gives help on the particular topic. So, for example, the Display setting affects how the search results are presented: the Bilingual Display shows the hits in the target corpus, followed by their aligned segment in the translation; the KWIC Display shows the results in the familiar key-word in context format; and Word List Display gives a list of word types found in the corpus, together with their frequencies. The last option makes the most sense with fuzzy queries. The result of the query can also be refined by specifying an additional query on the aligned corpus. This constraint can be either required or forbidden. The latter option is useful when exploring 'unexpected' translations. The on-line concordancer has been in used at the Department of Translation and Interpreting at the University of Ljubljana for different purposes such as contrastive analysis, translation evaluation, translation-oriented lexical and terminology studies, discourse analysis, etc. The methodological aims of this work were, on the one hand, to help students gain a deeper understanding of living language and remember things they discover themselves, and, on the other, to enable them to become skilled and critical users of corpora for translation purposes. The concordancer is also being used by translators, esp. by the volunteers of LUGOS, the Linux Users' Group of Slovenia, that are localising Linux documentation, e.g., the HOWTOs and the KDE desktop environment. As the US-ELAN corpus contains a whole book on Linux and the PO localisation files, it can be a welcome source of terminology translations. 5.2 Lexicon extraction We have also performed an initial experiment in automatic bi-lingual lexicon extraction from the corpus. Extracting such lexica is one the prime uses of parallel corpora, as manual construction is an extremely time consuming process yet the resource is invaluable for lexicographers, ter-minologists, translators as well as machine translation systems. A number of similar experiments had already been performed on the US-ELAN corpus [24, 5, 25], using a number of different tools. The software we have used here is the PWA system [21], which is a collection of tools for automatically finding translation equivalents in sentence aligned parallel corpora. The output of the system is, inter alia, a list of word token correspondences (i.e., translations in the text), a list of word type correspondences (i.e., a lexicon) and lists of monolingual collocations (i.e., a terminological glossary). The system is freely available under a research license as a binary for various platforms. For the data, we have used one of the elements of the US-ELAN corpus, namely the book "Linux Installation and Getting Started" by Matt Welsh et al., and translated into Slovene by Roman Maurer. The book contains 2 x 5,773 aligned sentence segments, with the English original having 91,526 and the Slovene translation 81,955 word tokens. For lexicon extraction we have not used the word-forms directly but rather the lemmas (where defined) of the words in question. This normalises the input and abstracts away from the rich inflections of Slovene, which would cause PWA to treat different forms of the same word as different words. Secondly, we reduced the input to the system to only adjectives, nouns and punctuation symbols. The reasoning behind this is that most useful (terminological) lexical correspondences will be noun phrases, and eliminating the other word classes reduces the chance of spurious translation correspondences. We have included punctuation signs in order to break up long stretches of nouns, which otherwise tend to get analysed as collocations. For this input data the PWA system took 15 minutes (on a Pentium laptop) to produce the results, i.e., the list of token correspondences totalling 22,880 items, the lexicon containing 2,850 entries, and a list of collocations with 1,329 entries. To illustrate, we show in Figure 6 data for one sentence from the text; first we give the sentence and its translation, then the equivalent input to the system, and finally the computed translation equivalents. Most posited translations are correct, but some are less than perfect. While the system correctly identifies translation equivalents for linux and system, it misses out on the larger collocation linux system, and similarly for user program and development tool. The main shortcomming of the output for the example sentence is the suggested translation equivalent for source code, as it lacks the noun koda. But despite these omissions, the result is already quite useful. English sentence: In addition, all of the source code for the Linux system, including the kernel, device drivers, libraries, user programs, and development tools, is freely distributable. Slovene sentence: Dodatno je dostopna in prosto razširljiva še vsa izvorna koda sistema Linux, vključno z jedrom, gonilniki naprav, knjižnicami, uporabniškimi programi in razvojnimi orodji. English input: addition , source code linux system , kernel , device driver , library , user program , development tool , distributable . Slovene input: dostopen razširljiva izvoren koda sistem Linux , jedro , gonilnik naprava , knjižnica , uporabniški program razvojen orodje . Output English —> Slovene translations: source code izvoren linux linux system -)• sistem kernel jedro device driver gonilnik library —>■ knjižnica user —> uporabniški program -> program development —> razvojen tool orodje Figure 6: Automatically extracted translation equivalents 6 Conclusions and Further Research The paper presented the processing steps involved in building and exploiting parallel corpora and introduced the tools necessary to accomplish this task. We have tried to show how third-party publicly available software is sufficient to operationalise the complete tool chain, and how language resources can be built in a cyclic manner, with initial annotations enabling the production of language models which, in turn, enable refinement and further annotation. The text processing model outlined in this article is especially useful in an academic environment: the software to implement it is free, and can thus be easily acquired by cash-strapped university departments. The building as well as the exploitation of the resources can be profitably used for teaching purposes, be it for computer science courses on natural language processing, or for linguistic courses on the use of language technology. As has been shown, the resources can also be used directly, by helping translators or language students make use of bi-lingual data. As far as corpus compilation goes, our further work can be divided into two areas. The first is, of course, the acquisition of more texts, and hence the production of larger corpora. The second, and scientifically more challenging, is the addition of further markup. In the paper we have discussed only basic linguistic markup. Useful further annotations include terms (either single or multiword), named entities (proper names, acronyms, dates, etc.), chunks (esp. noun phrases), and phrase structure (i.e., full syntactic analysis). Each of these areas has been the subject of much research but, so far, not yet attempted for Slovene. On the exploitation side, in addition to carrying further our research on lexicon extraction, we plan to experiment with statistical machine translation, in particular to use the freely available system EGYPT [18] with the US-ELAN corpus as the training set. Acknowledgements Thanks goes to Amebis, d.o.o., for lexically annotating version 2 the Slovene part of the US-ELAN corpus and to Jin-Dong Kim and two anonymous reviewers for reading the draft of this paper. References [1] Thorsten Brants. TnT - A Statistical Part-of-Speech Tagger. In Proceedings of the Sixth Applied Natural Language Processing Conference ANLP-2000, pages 224-231, Seattle, WA, 2000. http://www.coli.uni-sb.de/~thorsten/tnt/. [2] Oliver Christ. A Modular and Flexible Architecture for an Integrated Corpus Query System. In Proceedings of COMPLEX '94: 3rd conference on Computational Lexicography and Text Research, pages 2332, Budapest, Hungary, 1994. http://www.ims.uni-stuttgart.de/projekte/CorpusWorkbench/. [3] Philippe Di Cristo. MtSeg: The Multext multilingual segmenter tools. MULTEXT Deliverable MSG 1, Version 1.3.1, CNRS, Aix-en-Provence, 1996. http://www.lpl.univ-aix.fr/projects/multext/MtSeg/. [4] Perniila Danielsson and Daniel Ridings. Practical presentation of a "vanilla" aligner. In TELRI Newsletter No. 5. Institute fuer Deutsche Sprache, Mannheim, Mannheim, 1997. http://nl.ijs.si/telri/Vanilla/doc/ljubljana/. [5] Gael Dias, Špela Vintar, Sylvie Guillore, and Jose Gabriel Pereira Lopes. Normalising the US-ELAN Slovene-English Parallel Corpus for the Extraction of Multilingual Terminology. In Computational Linguistics in the Netherlands 1999, Selected Papers from the Tenth CLIN Meeting, pages 29-40, Utrecht, 1999. UILOTS. [6] Ludmila Dimitrova, Tomaž Erjavec, Nancy Ide, Heiki-Jan Kaalep, Vladimir Petkevič, and Dan Tufi§. Multext-East: Parallel and Comparable Corpora and Lexicons for Six Central and Eastern European Languages. In COLING-ACL '98, pages 315-319, Montreal, Québec, Canada, 1998. http://nl.ijs.si/ME/. [7] Sašo Džeroski, Tomaž Erjavec, and Jakub Zavrel. Morphosyntactic Tagging of Slovene: Evaluating PoS Taggers and Tagsets. In Second International Conference on Language Resources and Evaluation, LREC'OO, pages 1099-1104, Paris, 2000. ELRA. [8] Tomaž Erjavec. The ELAN Slovene-English Aligned Corpus. In Proceedings of the Machine Translation Summit VII, pages 349-357, Singapore, 1999. http://nl.ijs.si/elan/. [9] Tomaž Erjavec. Harmonised Morphosyntactic Tagging for Seven Languages and Orwell's 1984. In 6th Natural Language Processing Pacific Rim Symposium, NLPRS'Ol, pages 487-492, Tokyo, 2001. http://nl.ijs.si/ME/V2/. [10] Tomaž Erjavec. The US-ELAN Slovene-English Parallel Corpus. International Journal of Corpus Linguistics, 7(1): 1-20, 2002. http://nl.ijs.si/elan/. [11] William Gale and Ken W. Church. A program for ahgning sentences in bilingual corpora. Computational Linguistics, ]9(l):75-]02,1993. [12] Greg Grefenstette and Pasi Tapanainen. What is a word, what is a sentence? problems of tok-enization. In Proceedings of The 3rd International Conference on Computational Lexicography (COM-PLEX'94), pages 79-87. Research Institute for Linguistics, Hungarian Academy of Sciences, Budapest, 1994. [13] Claire Grover, Colin Matheson, Andrei Mikheev, and Marc Moens. LT TTT - A Flexible Tokenisation Tool. In Second International Conference on Language Resources and Evaluation, LREC'OO, 2000. http://www.ltg.ed.ac.uk/software/ttt/. [14] Jan Hajič. Morphological Tagging: Data vs. Dictionaries. In ANLP/NAACL 2000, pages 94-101, Seatle, 2000. [15] Henry Kučera and William Nelson Francis. Computational Analysis of Present Day American English. Brown University Press, Providence, Rhode Island, 1967. [16] Oliver Mason. Qtag — a portable probabilistic tagger, 1998. http://www-clg.bham.ac.uk/QTAG/. [17] Tony McEnery and Andrew Wilson. Corpus Linguistics. Edinburgh University Press, 1996. [18] Franz Josef Och and Hermann Ney. Statistical Machine Translation. In Proceedings of the European Association for Machine Translation Workshop, EAMT'OO, pages 39-46, Ljubljana, Slovenia, May 2001. http://nl.ijs.si/eamlOO/. [19] John Sinclair. Corpus typology. EAGLES DOCUMENT EAG-CSG/IR-Tl.l, Commission of the European Communities, 1994. [20] C. M. Sperberg-McQueen and Lou Buraard, editors. Guidelines for Electronic Text Encoding and Interchange, The XML Version of the TEI Guidelines. The TEI Consortium, 2002. http://www.tei-c.org/. [21] Jorg Tiedemann. Extraction of translation equivalents from parallel corpora. In Proceedings of the I Ith Nordic Conference on Computational Linguistics, Center for Sprogteknologi, Copenhagen, 1998. http://numerus.ling.uu.se/~corpora/plug/pwa/. [22] Hans van Kälteren, editor. Syntactic Wordclass Tagging. Kluwer Academic Publishers, 1999. [23] Jean Véronis, editor. Parallel Text Processing: Alignment and Use of Translation Corpora. Kluwer Academic Publishers, 2000. [24] Špela Vintar. A Parallel Corpus as a Translation Aid: Exploring EU Terminology in the ELAN Slovene-English Parallel Corpus. In Proceedings of the 34th Colloquium of Linguistics, Germersheim, Frankfurt, 1999. Peter Lang Verlag. [25] Špela Vintar. Using Parallel Corpora for Translation-Oriented Term Extraction. BabelJournal, 47(2): 121132, 2001. [26] W3C. Extensible markup language (XML) version 1.0. URL, 1998. http://www.w3.org/TRyi998/REC-xml-19980210. On Formal Aspects of Zooming in Geographic Maps Daniele Prigioni, Laura Tarantino and Tania Di Mascio Dipartimento di Ingegneria Elettrica Università degli Studi dell'Aquila 1-67040 Monteluco di Roio, L'Aquila - Italy frigioni@ing.univaq.it, laura@ing.univaq.it, tania@ing.univaq.it Keywords: Geographic Map, Poset, Human-Computer Interaction Received: February 10, 2002 Partitions have been identified as a key concept for perception and understanding of space, and have been regarded as a primary tool for spatial analysis tasks in geographic applications. We discuss here some results regarding the exploration of geographic maps structured as nested partitions. In particular, we present a zooming model based on a Level-Of-Detail (LOD) approach, aimed at visualizing sequences of gradually simplified representations of a given area hierarchically structured in a poset. We first describe a set of basic zooming primitives defined as transitions betv/eens maps at differentLOD, and study properties of the corresponding map space. We then introduce the notion of multiple zooming, define two new multiple zooming primitives on top of the basic ones, extend the map space, and prove some theoretical results on the new primitives. 1 Introduction In this paper we report some theoretical results achieved in the framework of a project concerning the design of a visual interaction environment for Geographic Information Systems (GISs). GISs deal with storing, querying, manipulating and displaying geographic information (see, e.g., [2]). The core of a GIS is a spatial database management system. A spatial database consists of a spatial component encoding the geometric aspects of the physical objects under consideration (e.g., location, shape, size), and of a thematic component containing information about the non-geometric properties of the realm of interest (see, e.g., [15] for foundationsiof spatial databases). A GIS normally includes also modules devoted to application specific tasks, such as map production, spatial analysis, and data visualization. We restrict here our attention to primitives aimed at exploring the spatial component of the database. Detail filtering in geographic maps. Technological developments in automated data capturing tools allow the collection of huge volumes of geographic data representing areas of interest with extreme accuracy. As a consequence, manipulation and rendering of complex geographic datasets may require processing resources beyond the power of state-of-the-art computers, hence introducing the necessity of detail filtering during visualization and interaction tasks. The basic idea is to dynamically adapt the resolution to the needs of specific interaction tasks, possibly taking into account user's interest in displayed data (which might imply to vary the resolution over different areas of the map). To achieve this effect, the concept of Level-of-Detail (LOD) has been introduced, sometimes summarized as "always use the best resolution you need - or you can afford -and never use more than that" [6]. Of course the principle has to be characterized to the needs of the specific application, interaction task or visualization strategy. Anyhow, despite application specific differences, there is common ground among LOD models: all aims at defining sequences of gradually simplified representations of the same area that get structured either into a multi-layer model or into a hierarchical model described by a tree [16], In the framework of a LOD approach, the interaction process can be formalized through a map space and rules for traversing it corresponding to transitions between maps at different levels of detail. Several conceptual approaches can be used for the for-, malization of space and of spatial properties. Not only does the adoption of a particular model influence the type of data that can be used, but it also determines the kind of spatial analysis that can later be undertaken. The two extremes in the range of conceptual approaches are the continuous field approach (that views attributes of interest as varying over the space as some continuous mathematical function or field) and the entity-based approach (that perceives space as being occupied by entities described by their properties and mapped using a coordinate system) [2]. In the case of continuous fields, data analysis concerns the spatial properties of the fields; the geographical space is discretized into sets of single spatial units (such as square, triangular, or hexagonal cells), or into irregular triangles or polygons, tessellated to form geographic representations. A LOD representation hence consists of a collection of meshes of different sizes, each representing the object at a different resolution [16]. In the case of entities, data retrieval and analysis may concern: attributes (i.e., the nature of the entities), geographic location (i.e., spatial information about the entities), and topology (i.e., information about the relative positions of the entities). The LOD approaches must then provide different solutions to deal with attributes, geographic locations, and topology. Treatment of topological information encoded in partitions is the main concern of our work. Objectives of our work. We restrict ourselves to databases in which the spatial component is a set of points in the 2-dimensional real space. Roughly speaking, we deal with spatially related collections of regions hierarchically organized as a nested partition. Partitions have been identified as a key concept for perception and understanding of space [9], and have been regarded as the primary tool for spatial analysis tasks in geographic applications and systems (see, e.g., [5, 10]). A number of papers proposed partition-based spatial analysis functions, with operations like overlay, generalization, and reclassification, all producing new partitions as a result (extended discussion on such topic can be found in [5], which also proposes a set of three powerful operations on partitions, sufficient to express all known application-specific operations). Dif-ferendy from these works, we focus on primitives aimed at navigating sequences of gradually simplified representations of a given area. In our conceptual model, the abstraction mechanism for modelling single geometric objects is the region. A region is a closed subset of K^ homeomorphicto: (i) a single point (region of dimension 0); (ii) E (region of dimension 1); (iii) E^ (region of dimension 2). We deal with a finite set Tl = {i?o, . • ■, ßn}. where each Ri is a region. As basic abstraction mechanisms for modelling spatially related collections of objects, in [4] we have considered the nested partition and the aggregation. The former is a recursive subdivision of the plane into pairwise disjoint regions of dimension 2 (denoted blocks), quite common in geographic maps (consider, e.g., countries partitioned into states, partitioned into counties, etc). The latter defines associations among regions, to model real applications where features, i.e., isolated points, lines, and areas, appear within regions (to represent cities, roads, rivers, lakes, etc., depending on the specific portion of the real world at hand). According to LOD principles, we consider an exploration of the database where, starting from a map at a low LOD, more detailed information is successively disclosed on demand. In [4] we proposed a single-focus navigation: at each stage of the interaction session, one region of the map provides the current/ocM^ of interest, while the other (surrounding) regions provide the peripheral context. Roughly speaking, the overall interaction process is a sequence of user's activities composed by viewing the current map, selecting a region visible on the current map, and moving the focus to the selected region. As a result of the focus selection, a new map gets visualized, containing more detailed information on the focus region. According to the selected visualization techniques, the focus region is assigned a greater display area, while peripheral regions shrink yet preserving topology'. It is also possible to get maps at a lower LOD than the current one. The single-focus navigation was supported by a set ^Vbase of basic primitives, defined as transitions between maps at different LOD, allowing to require/hide details regarding either the sub-blocks or the features of a focus region. Correspondingly, the map space is a graph where the set of nodes includes all possible views, and the set of arcs includes transitions between pairs of views defined by the primitives in IVbase • We realized that, at a great extent, the "shape" of the graph depends on the nested partition and on the basic primitives concerning blocks (called zooming primitives). The complete map space, including transitions deriving from primitives concerning features, can actually be viewed as a generalization of a restricted space including only transitions deriving from zooming primitives. Results of the paper. Since the new stage in our project concerns the definition of an extended sets of primitives on top of IVbase, it appears appropriate to proceed in two steps: we now focus on new primitives related to the nested partition (and study properties of the map space in this restricted scenario), while we will extend the set of primitives to include treatment of features in a future step. This paper presents results achieved in the first step concerning the nested partition. The idea is to consider a set of focus regions in place of a single focus region at a time. We hence define two new multiple zooming primitives called mzoom-in and mzoom-out as generalizations of the elementary zooming primitives zoom-in and zoom-out, defined in [4] to allow to require/hide details regarding the sub-blocks of a focus region. Though the definitions of the new primitives might be given independently of zoom-in and zoom-out, it is more interesting to discuss how multiple zooming can be expressed in terms of elementary zooming. These results allows us to conceive a system in which, once a kernel including algorithms corresponding to elementary primitives is designed, extensions can be easily defined by specifying appropriate sequences of zoom-in and zoom-out. In particular, we show that multiple zoom-in (resp., multiple zoom-out) corresponds to a sequence of zoom-in (resp., zoom-out) transitions, considering in any order the regions in the focus set. Clearly, the main advantage of the multiple zooming is that there is no need for rendering the map after each basic zoom-in or zoom-out transition belonging to the sequence. Structure of the paper. In Section 2 we describe our conceptual model refining the results of [4]; in Section 3 we recall the basic zooming primitives of [4] and study the properties of the corresponding map space; in Section 4 we 'Visualization aspects are beyond the scope of this paper We refer to [3] for a general overview on visualization techniques, and to [4] for further discussion on the visual interaction with geographic maps. introduce and formalize the notion of multiple zooming, and extend the map space. Finally, in Section 5 we provide some concluding remarks and outline future research directions. 2 The conceptual model of data In our restricted model without features, the abstraction mechanism for single geometric objects is the block. A block is a closed subset of homeomorphic to M^. In the remainder of the paper a set of blocks B — {Bi ,B2,..., Bp) is called spatial dataset. Given a block B, a partition of i? is a subdivision of this block into a finite set of pairwise disjoint blocks. Definition 2.1 Let B bea spatial dataset, and B be a block in B. A partitio^P = • • •, Bj], j > 1, ofB is a flat partition ofB in B ifBi eB,l I, such that: 1) {ßo} € NVb{Bq); 2) Pi is refinement of {Bo}>J. 1 is easily obtained by iteration. Given Pk = {Pi,. Bn], two cases must be considered: Case 1. Pj is a refinement of Pk with respect to [B^], and Pi is a refinement of Pj with respect io {By}, where By is a block of P j that does not belong to the partition of Bx used to obtain Pj from Pk. It trivially follows that Pj is a refinement of Pfc with respect to {Bx,By). Case 2. Pj is a refinement of Pk with respect to {Bx], and Pi is a refinement of Pj with respect to {Bz}, where B^ is a block of P j that belongs to the partition P of Bx used to obtain P j from Pk. It is easy to see that Pi is a refinement of Pk , with respect to {Bx}, since Pi is obtained from Pk by replacing Bx with a partition whose size is greater than the size of P. >From Definition 2.3 it follows that the partial order {MVbÌBo), <) contains a greatest element (namely the partition {Po}) and a least element (namely the partition L). Furthermore, as in the case of set partitions [18], it can be shown that the pair {MVbÌBq), -<) forms a/am'ce, since any pair of elements in AfpB^Bo) has a least upper bound and a greatest lower bound (for foundations of posets and lattices we refer to [1, 11]). As in any partial order, we can introduce a notion of immediate inferior: in particular, we say that Pi is an immediate refinement of P j if Pi < Pj, Pi Pj, and there not exists P G NVb{Bo), P ^ Pi, P ^ Pj, such that Pi P di Pj- K is easy to see that if Pj is immediate refinement of Pj, then Pj is a simple refinement of Pj (the converse is not true). The notion of nested partition introduced in Definition 2.3 induces a binary relationship sub-block among the blocks of ß: a block B is sub-block of a block B' if B belongs to some flat partition of P'. B is immediate sub-block of B' if there exists a flat partition P such that B' e P and B belongs to the immediate refinement of P with respect to B'. If B is immediate sub-block of B', then B' is the parent-block of B\ if B is sub-block of B' then B' is an ancestor oi B. The relation sub-block over a spatial dataset 23 can be represented by a hierarchical structure, i.e., a tree rooted at Bo, that we denote as Tb{Bo). If B £ B, then the subtree of 7ß(ßo) rooted at B is denoted as Tb{B). The parent-block of a block B in Tb{Bo) will be denoted as parent{B). We say that two blocks Bi and B2 of 7ß(ßo) are siblings when they are immediate sub-blocks of the same block B in Tb{Bo). Definition 2.4 A well-formed spatial dataset is a pair V = {B^MVbÌBq)), where: i) B is a spatial dataset; ii) NVbÌBq) is a nested partition ofB with respect to Bq € B. Concluding, we restrict ourselves to spatial databases in which the spatial component is a set of points in that can be described by a well-formed spatial dataset. Example 2.2 In Figure 1 we show: (a) the tree Tb{Bq) representing the relation sub-block associated to an example well formed spatial dataset V; (b) the partition of maximum size ofD composed by all the leaves o/7ß(-Bo).' (c) a graphical representation of the immediate refinement relationship over V provided by the Hasse diagram (i.e., the transitive reduction of the relation ;<) Notice that in Figure l-(c) (and in the remaining figures as well) partitions are identified by the subscripts of the participating blocks. The example well-formed spatial dataset of Figure 1 will be referred to throughout the paper to illustrate new concepts as they are introduced. 3 Elementary zooming In this section we study and formalize a zooming model for a well formed spatial dataset V = {B^MVbÌBq)). The model includes a "minimal" (yet powerful) set of basic zooming primitives, denoted ZVbase > which can act as a kernel for extended sets of primitives, defined on top of it. The set ZVbase includes basic primitives that, given a focus region, show/hide details related to it: - zoom-in adds details regarding sub-blocks of the focus region; - zoom-out subtracts details related to the focus region. Formally, given a well formed spatial dataset {B.MPbÌBq)), a flat partition P e TVPbC^o), and a block ß of P: ^In a Ha.sse diagram, each po.set element is repre.sented by a dot; furthermore, given two elements A and B of the poset such that A < B, and for no element C of the poset A ^ C ^ B, then the dot representing B is drawn in a position higher than the position of the dot representing A, and the two dots are connected by a line. B4 Bs V jBS ( ) \ ^^ Br \ ß9 Bn Bio \ B4 Bi (h) 2,3,4,5 2,4,5,8,9,1 1,3,6,7 4,5,6,7,8,9, 1,3,7,11,12 12/1,7,8,9,10,11,12 4,5,7,8,9,10,11,12 (C) Figure 1 : (a) The hierarchical structure representing the relation sub-block of an example well formed spatial dataset; (b) the associated partition of maximum size; (c) the Hasse diagram of {MVb{Bo),:<) in the example well formed spatial dataset. - zoom-in{P, B) = P', where P' is the immediate refinement of P with respect to {B}. - zoom-out{P, B) = P' such that P is a simple refinement of P' with respect to the parent block of S. Notice that given P' and B' e P', there exist more than one simple refinement of P' with respect to {B'}, whereas given P and B £ P there is only one P' verifying zoom-o«/(P, B) = P'. Intuitively, the zoom-out primitive generates the partition of maximum size among those superior of P, not containing B, and containing its parent-block. It is worth noting that zoom-in (resp. zoom-out) cannot be applied to £ (resp. {i?o})- Intuitively, the zoom-in primitive generates the partition obtained from the current partition P by replacing the focus region B with its immediate sub-blocks, while the zoom-out primitive generates a partition P' as stated in the following observation. Observation 3.1 If zoom-out{P, B) = P', then P' is obtained from P by subtracting those blocks of P that are in TB{parent{B)) and adding parent{B). Example 3.1 With reference to the example of Figure ]-(c), if the current partition is P = {Bi,B-!, Bs^Bg, Bio, Bii, B12} and the selected block is Bj, then the partition resulting from zoom-out{P, Bj) is P' = {BuB2, Bs, Bg, Bio}. Primitives in ZVbase allow us to conceive a LOD-based exploration of the well-formed spatial dataset in which, starting from the map at the lowest LOD (i.e., the partition {Bo}), maps at higher LOD are visualized by zoom-in operations, while maps at lower LOD are obtained by zoom-out operations. Correspondingly, the map space is a graph where the set of nodes coincides with Af'Pß{Bo), and the set of arcs includes transitions between pairs of partitions defined by the primitives in More formally, the map space is defined as follows: Definition 3.1 The map space associated to a well-formed spatial dataset V - (ß, A/''Pß(Po)). and to the set of primitives ZVbase « a directed graph MS{V, ZVbase) = {Nbase,^base) definedasfollows: - for each flat partition P in NVßiBo) there is a node P inNbase! - for each zoom-in/zoom-out transition there is a zoom-in/zoom-out arc in Abase, as follows: if zoom-in{P, B) = P', then there exists a zoom-in arc from P to P' labelled by B; if zoom-out{P, B) = P', then there exists a zoom-out arc from P to P' labelled byB. We observe that the map space is induced by the lattice: nodes are induced by elements oìNVb{Bq), zoom-in 1,2,3 1,3,7,11,12 Figure 2: A portion of the map space associated to the example well-formed spatial dataset. arcs are induced by the immediate refinement relationship, zoom-out arcs are induced by the simple refinement relationship (but have opposite direction). Example 3.2 With reference to the well-formed spatial dataset of Example 2.2, Figure 2 shows a portion of its map space. In particular, thick arcs represent zoom-in arcs, while thin arcs represent zoom-out arcs. An arc label indicates the focus region of the transition (to avoid picture cluttering transitions differing only in the focus region have been represented by a unique arc having a list of labels). For example, if the current partition is P={Bi,Bs,Br,Bii,Bi2}.then: - zoom-out{P,B7) = {Bi,B2,B3} - zoom-out{P,Bn) = {51,53,-56,^7} - zoom-outiP,Bi2) = {Bi,B3,Be,Br} Other transitions are easily derived from the Hasse diagram in Figure I-(c). An interaction process corresponds to a path in the map space. We denote as zoom-in path (resp., zoom-out path) a path in MS{'D, ZVbase) including only zoom-in arcs (resp., zoom-out arcs). We notice that the set ZVbase Is Complete, in the sense that it allows us to reach all the partition in MVb{Bo) (in other words, there exists a path in MS{V, ZVbase) from {Po} to any partition in MVb{Bo)). In fact, from the definition of zoom-in and the properties of the lattice, it immediately follows that, if P is a partition in MVb{Bo), then there exists a zoom-in path in M.S(V, ZVbase) from P to any other partition P' in J^Vb{Bo), with P' P. All the partitions in MVb{Bo) are hence reachable from {Po}- Similarly, from the definition of zoom-out it follows that if P is a partition in MVb{Bo), then there exists a zoom-out path in MS{T>, ZVbase) from P to any other partition P' in MVb{Bo), with P i. Proof. A zoom-in operation Zi with focus B generates a partition in which B has been replaced by its immediate sub-blocks. A subsequent zoom-in operation Zj, j > i, with focus B, can make B appear again only if B is imme-diat^ub-block of B. This is not possible because, since B and B belong to Xin, and then to the same partition P, B cannot be immediate sub-block of B. □ Notice that neither the sequence Zin nor the corresponding sorting Sin are to be considered parameters of mzoom, since the user specifies the blocks he/she wants to zoomin without providing any indication on the order in which blocks of Xin are to be taken into consideration (the sequence Zin and the sorting Sin are rather related to the system's response to the users' request). We will use the notation @mzoom-in{P, Xin, Sin) when we want to put emphasis on sorting details (i.e., on the execution procedure). Example 4.1 With reference to Figure J-(c), if P = {Pi,52,58,^9,Pio}, Xin = {BuB^}. and Sin = (Pi,P2), then @mzoom{P,Xin,Sin) = {P4, P5, Pe, P7, Ps >-69 !-010 }- In what follows we show that the result of mzoom-in{P, Xin) is independent of the selected sorting of Xin (this independence allow us to relieve the user of the burden of specifying execution details). More formally: Theorem 4.1 Let P be a flat partition ofAfVeiBo), Xin a subset of P, , ZVmzin) = {N,A) obtained from MS{V, ZVbase) = {Nbase, Abase) asfollows: - N = Nbase; - A = Atase U Amzin where Amzin " defined as follows: if mzoom-in{P,Xin) = P', then there exists a multiple zoom-in arc in Amzin from P to P' labelled by Xin. Example 4.2 With reference to the example of Figure 1-(c). Figure 3 shows the portion of MS{V, ZVmzin) containing all arcs outgoing from the node P = {ßj, , -Bs} (one arc for each subset of P). Notice that, a single step is now sufficient to go from partition {Bi,B2, B3} to partition {^4, jBs, JSe, Br, Bs,Bg,Bio}, while three steps were required with elementary zooming only. 4.2 Multiple zoom-out Following the same approach as in the previous section, we want to give the user the possibility of specifying a set of blocks of a given partition he/she wants to zoom-out. Formally, if P = {Bi,B2,..., JS^} is à flat partition, and Xout is a subset of P, then mzoom-out is defined as follows: - mzoom-out{P, Xout) = P', where P' is the flat partition in AfVB{Bo) obtained by a sequence Zgut of zoom-out operations such that: Zout - (P, Z00m-0Mr(Pi_i,Xj) where i — 1.. .k, k i. Proof. By hypothesis B disappears at step i. A subsequent zoom-out operation Zj, j > i, with focus B, can make B appear again only if B is the parent of B. This is not possible because, since B and B belong to Xout, and then to the same partition P, B cannot be the parent of ß. □ The following observation is a straightforward consequence of Lemma 4.2. Observation 4.1 Let B be a block of Xout- If B £ Ph, then B e Pi, 0 < i < h. In fact, if i? ^ Pi for some i < h, then, by Lemma 4.2 B ^ Ph, thus contradicting the hypothesis. As a consequence of Lemma 4.2 we have that the number of steps k (i.e., the number of zoom-out operations in Zout) may result less than \Xout\- In fact, if a zoom-out operation 2j in Zout removes blocks of Xout, then these blocks will not appear again in partitions obtained by subsequent steps and cannot hence be considered as focuses. We denote by Sout a sorting of Xout obtained by taking first the blocks used as focuses (active blocks) in the order in which they are considered in Zout, and then the remaining inactive blocks in any arbitrary order. A number of different sortings may be induced by a sequence Zout, since more than one permutation can be considered for the set of inactive blocks. Notice that, as in the case of multiple zoom-in, neither the sequence Zout nor a corresponding sorting Sout are to be considered parameters of mzoom-out, since the user specifies the blocks he/she wants to zoom-out without providing any indication on the order in which blocks of Xout are to be taken into considerations (the sequence Zout and the sorting Sout are rather related to the system's response to the users' request). We will use the notation @mzoom-out{P, Xout, Sout) when we want to put emphasis on sorting details. Example 4.3 With reference to the example in Figure l-(c). If P = {B3,Bi,B5,Br,Bn,Bi2}, Xout = {Bs,By), and Sout = (Bt^^s), then @mzoom{P,Xout,Sout) = {Bi,B2,B3}. In what follows we show that mzoom-out{P, Xout) is independent of the sorting of Xgut- A preliminary lemma is given, directly deriving from the behavior of zoom-out, which generalizes Lemma 4.2. Lemma 4.3 If a block B of the partition Pj_i disappears as a consequence of mzoom-out{Pi-i, Xi), then B ^ Ph, h> i. Proof. By hypothesis B disappears at step i. By Observation 3.1 a subsequent zoom-out operation mzoom-out{Ph-i,Xh), h > i, can make B appear again only if B is the parent-block of X^,. On the other hand, ^h € Xout and X^ S Ph-i, and then by Observation 4.1, Xh € Pj, with j < h. Hence B and X^ belong to the same partition Pi-i, and B cannot be the parent-block of Xh. □ Theorem 4.2 Let P be a flat partition of MVb{Bo), Xout o. subset of P, Si and S2 two distinct sortings of Xout- Then, @mzoom-out{P, Xout,Si) = @mZ00ni-0Ut{P, Xout, ^2). Proof. The theorem trivially follows if 1000 Another example is to "cluster the part shipment by their city locations and select the cities with average quantity of shipment between 500 and 1000". The query written in SQL is as follows. QUERY 4: Select PARTS.City, AVG(Qty) From PARTS, SHIPMENT Where PARTS.P# = SHIPMENT.P# Group By PARTS.City Having AVG(Qty)>500 AND AVG(Qty)<1000 The main difference between Query 3 and Query 4 above lies in the join attributes and group-by attributes. In Query 3, the join attribute is also one of the group-by attributes. This is not the case with Query 4, where the join attribute is totally different from the group-by attribute. This difference is particularly a critical factor in processing aggregate-join queries, especially in parallel query processing, as there are decisions to be made regarding which attribute to be used for data partitioning. When the join attribute and group-by attribute are the same as shown in Query 3 (e.g. attribute J# of both Project and Shipment), the selection of partitioning attribute becomes obvious. Therefore, instead of performing join first, the aggregate is carried out first followed by the join. Comparatively, join is a more expensive operation than aggregate functions, and it would be beneficial to reduce the join relation sizes by applying the aggregate function first. Generally, aggregate functions should always precede join whenever possible with an exception that the size reduction gained from the aggregate functions is marginal or the join selectivity factor is extremely small. In real life, early processing of the aggregate functions before join reduces the overall execution time as stated in the general query optimization rule where unary operations are always executed before binary operations if possible. However, aggregate functions before join may not always be possible, such as Query 4 above. The semantic issues about aggregate functions and join and the conditions under which the aggregate functions would be performed before join can be found in literatures (Kim, 1982; Dayal, 1987; Bultzingsloewen, 1987; Yan and Larson, 1994). In this paper, we concentrate on more general cases where aggregate functions cannot be executed before join. Therefore, we will use Query 4 as a running example throughout this paper. 3 Parallel Aggregate-Join Query Processing Methods Our parallel database architecture consists of a host and a set of working processors. The host accepts queries from users and distributes each query with the required base relations to all processors for execution. The processors perform the query in parallel with possibly intermediate data transmission among each other via the network, and finally send the result of the query to the host. Our previous work has proved the suitability of this architecture in for parallel database processing (Leung and Ghogomu, 1993; Leung and Taniar, 1995; Liu et al, 1996). Using this parallel architecture, parallel query processing is commonly carried out in three phases: • Data partitioning, the operand relations of the query are partitioned and the fragments are distributed to each processor; • Parallel processing, the query is executed in parallel by all processors and the intermediate results are produced; • Data consolidation, the final result of the query is obtained by consolidating the intermediate results from the processors. There is an important decision need to be made in processing aggregate-join queries, namely the selection of partitioning attribute. Selecting a proper partitioning attribute plays a crucial role in performance. Although in general any attributes of the operand relations may be chosen, two particular attributes (i.e. join attribute and group-by attribute) are usually considered. If the join attribute is chosen, both relations are partitioned into N fragments by employing a partitioning function (e.g. a hash/range function), where N is the number of processors. The cost for parallel join operation can therefore be reduced as compared with a single processor system. However, after join and local aggregation at each processor, a global aggregation is required at the data consolidation phase, since local aggregation is performed on a subset of the group-by attribute. If the group-by attribute is used for data partitioning, the relation with the group-by can be partitioned into N fragments, while the other relation needs to be broadcast to all processors for the join operation. Comparing the two methods above, in the second method (partitioning based on the group-by attribute), the join cost is not reduced as much as in the first method (partitioning based on the join attribute). However, no global aggregation is required after local join and local aggregation, because records with identical values of the group-by attribute have been allocated to the same processor. Based on these two partitioning attribute strategies, we introduce three parallel processing methods for aggregate-join queries, namely Join Partitioning Method (JPM), Aggregate Partitioning Method (APM), and Hybrid Partitioning Method (HPM). They are discussed in more details in the following sections. 3.1 Join Partition Method {JPM) Given the two relations R and S to be joined, and the result is grouped-by according to the group-by attribute and possibly filtered through a having predicate, parallel processing of such query using the JPM method can be stated as follows. Step 1: Data Partitioning The relations R and S are partitioned into N fragments in terms of join attribute, i.e. the records with the same join attribute values in the two relations fall into a pair of fragments. Each pair of the fragments will be sent to one processor for execution. Using QUERY 4 as an example, the partitioning attribute is attribute P# of both tables Parts and Shipment, which is the join attribute. Suppose we use 4 processors, and the partitioning method is a range partitioning, such as part numbers (P#) pl-p99, pl00-pl99, p200-p299, and p3 00-3 99 are distributed to processors 1, 2, 3, and 4, respectively. This partitioning function is applied to both tables Parts and Shipment. Consequently, processor such as processor 1 will have Parts and Shipment records where the values of its P# attribute are between pl-p99, and so on. Step 2: Join operation Upon receipt of the fragments, the processors perform in parallel, the join operation on the allocated fragments. Join in each processor is done independently to each other (DeWitt and Gray, 1992). This is possible because the two tables have been disjointly partitioned based on the join attribute. Using the same example as above, join operation in a processor like processor 1 will produce a join result consisting of Parts-Shipment records having P# between pl-p99. It is worth to mention that any sequential join algorithm (i.e. nested-loop join, sort-merge join, nested index join, hash join) may be used in performing a local join operation in each processor (Mishra and Eich, 1992). Step 3: Local Aggregation After the join is completed, each processor then performs a local aggregation operation. Join results in each processor is grouped-by according to the group-by attribute. Continuing the same example as the above, each city found in the join result will be grouped. If, for example, there are three cities: Beijing, Melbourne, and Sydney, found in processor 1, the records will be grouped according to these three cities. The same aggregate operation is applied to other processors. As a result, although each processor has distinct part numbers, some of the cities, if not ail, among processors may be identical (duplicated). For example, processor 2 may have three cities, such as London, Melbourne, and Sydney, where Melbourne and Sydney are also found in processor 1 as mentioned earlier, but not London. Step 4: Re-distribution A global aggregation operation is to be carried out by re-distributing the local aggregation results across all processors such that the result records with identical values of the group-by attribute are allocated to the same processors. To illustrate this step, a range partitioning method is again used to partition the group-by attribute, such as processors 1, 2, 3, and 4 are allocated cities beginning with letter A-G, H-M, NT, and U-Z, respectively. Using this range partitioning, processor 1 will distribute its Melbourne record to processor 2, Sydney record to processor 3, and leave Beijing record in processor 1. Processor 2 will do the same to its Melbourne and Sydney records, whereas London record will remain in processor 2. Step 5: Global Aggregation Each processor performs an N-way merging of the local aggregation results, followed by performing a restriction operation for the Having clause if required by the query. The result of this global aggregate in each processor is a subset of the final results, meaning that each record in each processor has a different city, and furthermore, the cities in each processor will not appear in any other processors. For example, processor 1 will produce one Beijing record in the query result, and this Beijing record does not appear in any other processors. Additionally, some of the cities may then be eliminated through the Having clause. Step 6: Consolidation The host simply consolidates the partial results from the processors by a union operation, and produces the query result. ® @ © 0 ÄÄtfSn' Redistribution on Ihe group-by attribute Local join and local aggregate fimction Partitioning on the join attribute Records from wiiere they are originally stored Figure 1 : Join Partition Method {JPM). Figure 1 gives a graphical illustration of the Join Partition Method (JPM). The circles represent processing elements, whereas the arrows denoted data flow through data partitioning or data re-distribution. 3.2 Aggregate Partition Method {APM) The APM method relies on partitioning based on the group-by attribute. As the group-by attribute belongs to just one of the two tables, only the table having the group-by attribute will be partitioned. The other table has to be broadcast to all processors. This technique is often known as "Divide and Broadcast" technique, commonly used in naive parallel join operations (Leung and Ghogomu, 1993). The processing steps of the APM method are explained as follows. Step 1: Data Partitioning The table with the group-by attribute, say R, is partitioned into N fragments in terms of the group-by attribute, i.e. the records with identical attribute values will be allocated to the same processor. The other table S needs to be broadcast to all processors in order to perform the join operation. Using QUERY 4 as an example, table Parts is partitioned according to the group-by attribute, namely City. Assume a range partitioning method is used, processors 1, 2, 3, and 3 will have Parts records having cities beginning with letter A-G, HM, N-T, and U-Z, respectively. On the other hand, table Shipment is replicated to all four processors. Step 2: Join operations After data distribution, each processor carries out the joining of one fragment of R with the entire table S. Using the same example, each processor joins its Parts fragment with the entire table Shipment. The results of this join operation in each processor are pairs of Parts-Shipment records having the same P# (join attribute) and the value of its City attribute must fall into the category identified by the group-by partitioning method (e.g. processor 1=A-G, processor 2=H-M, etc). Step 3: Aggregate operations The aggregate operation is performed by grouping the join results based on the group-by attribute, followed by a Having restriction if it exists on the query. Continuing the above example, processor 1 will group the records based on the city and the cities are in the range of A to G. The other processors will of course have a different range. Therefore, each group in each processor is distinct to each other both within and among processors. Step 4: Consolidation Since the table R is partitioned on group-by attribute, the final aggregation result can be simply obtained by a union of the local aggregation results from the processors. Join,Groip-By ^ (Aggregation) and Having operations. Partitioning me table on the gron>by attribute, and broadcast the other table. Reotyds from where they are originally stoned proper value of m can be chosen to minimize the query execution time. Hybrid Logical Architecture Cluster ..J... n 1 2 ...j... 1 2 ...j... n Figure 2: Aggregation Partition Method PA/). Figure 2 shows a graphical illustration of the APM method. Notice the difference between the JPM and the APM method. The former imposes a "two-phase" partitioning scheme, whereas the latter is a "one-phase" partitioning scheme. 3.3 Hybrid Partition Method {HPM) The HPM method is a combination of the JPM and APM methods. In the HPM, the total number of processors N is divided into m clusters, each of which has N/m processors as shown in Figure 3. Based on the proposed logical architecture, the data partitioning phase is carried out in two steps. First, the table with group-by attributes is partitioned into processor clusters in the same way of the APM (i.e. partitioning on the group-by attribute and the other table is broadcast to the cluster). Second, within each cluster, the fragments of the first table and the entire broadcast table are further partitioned by the join attributes as in the JPM. Depending on parameters such as the cardinality of the tables and the skew factors, a Figure 3: Logical Architecture for HPM. The detailed ///'M method is explained as follows: Step l:a) Partitioning into Clusters Partition the table R on group-by attribute to m clusters, denoted by r, where \ < i < m. Table S is broadcast to all clusters. Using Query 4 as an example, first partition table Parts into m clusters based on attribute City. If there are three clusters, table Parts is divided into three fragments. Table Shipment is, on the other hand, replicated to all the three clusters. As a result, each cluster will have a fragment of table Parts and a full table Shipment. b) Partitioning within Clusters Within each cluster i, further partition fragment r, and the full table S on the join attribute to n processors where n=N/m. Each fragment is now denoted by rij and Sj. Suppose that there are twelve processors in total. Since we use three clusters, each cluster will contain four processors. In each cluster, a Parts fraginent and the whole Shipment table are partitioned based on the join attribute P# into the four processors. In practice, steps 1(a) and (b) described above are carried out at once, in order .-tp -reduce communication/distribution time. When doing the two partitioning stepsias a single ffartitioning.step, each record of the tables is applied a partitioning function that determines into which processor and cluster the record should be sent. The partitioning function takes into account whether or not the table is the group-by table. Figure 4 gives the algorithm of the partitioning step in the HPM. The algorithm clearly shows that the table containing the group-by attribute is purely partitioned into all processors, whereas the other table is to some degrees replicated. Let processors be P Let group-by partitioning function be G Letjoin partitioning function be J For each record r of the group-by table Determine cluster / for record r based on partitioning function G Determine processor j for record r based on partitioning function J Distribute record r to processor P.. End " For each record s of the other table Determine processor j for record r based on partitioning function J For each processor k in each cluster Distribute record r to processor End End distribution phase where re-distribution in HPM is a cluster-based, not global in the sense like in JPM. Global aggregate and (he Having operation Redistribution on the group-by attribuie Figure 4: Partitioning Algorithm in HPM. Step 2: Join operation Carry out the join operation in each processor. Join operation is executed like in the other two methods, that is, it is carried out locally and independently in each processor without involving other processors. Step 3: Local Aggregation Perform local aggregation at each processor. This local aggregation operation is carried out as like in the JPM method. As a result, each processor will produce a number of groups and some groups among other processors may be the same, and these groups will be later grouped in the global aggregation stage. Step 4: Re-distribution Redistribute the local aggregation results to the processors within each cluster by partitioning the results on the group-by attribute. This step is similar to that of in the JPM method. The main difference is that in HPM the re-distribution is done within each cluster, not globally involving all processors like in JPM. Step 5: Global Aggregation Merge the local aggregation results within each cluster. Then perform the Having predicate, if exists, in each cluster. Unlike the JPM, again, this process is done locally in each cluster. As a result of this process, each cluster contains a subset of the final query result. Step 6: Consolidation Transfer the results from the clusters to the host. Figure 5 shows a graphical illustration of the HPM method. By the look at it, the flow of process is similar to that of JPM, in which both are a "two-phase" processing scheme. We, however, need to highlight two main differences. One is that the initial partitioning in HPM is different, and in fact, it is a combination between partitioning in JPM and in APM, where both group-by and join attributes are being utilized in the partitioning phase. This unified two-step partitioning scheme is not clearly shown in the diagram, but as shown in the algorithm the partitioning uses both group-by and join attributes. The second difference is related to the re- Local join and local aggregate function Partitioning and broadcasting Records from where ihey are originally stored Figure 5: Hybrid Partition Method {HPM). 4 Cost Models In this section, we present in this section three parallel processing methods for aggregate-join queries. The notations used in the description of the methods and in the subsequent sensitivity analysis are given in Table 1. Parameter IVfeaning N Total tuimber of pticessors m Munto of processor clusters n Nutrtoofprocessor in each duster ( N-m^^ri) r, s Numberofreoor ds in base tables y? and 5 H' 'i Nuntoofrecords of fragments of tables and S atpntxsssor i Sel(i) Join selectivity factor for fragment i Aggregation factor for fragment i e Redtiction factor after perfomiing Having clause a Datapartitio ning skew factor ß Data processing skew factor Incontri Average data transmission tine for each message Tjoin Average join time for each record Tagg Average aggregation time for each record z Nfesage size in terms of the numba- of records Table 1: Notations 4.1 The/PM Cost Model Given the notation introduced earlier, the components of the JPM execution time expressed as follows: Data partitioning cost for JPM is determined by the sum of fragments r, and 5, which are the fragments of the two tables R and S in processor i. x(max(^+5,)) (1) Local join cost is influenced by the sequential join algorithm used in each processor. Using a nested-loop join, the join cost can be determined by r, X s, wiiich follows the 0(N2) complexity, whereas a hash join follows a linear complexity and hence the cost is calculated by r^ + Sj (Knuth, 1973). If one of the join attributes is indexed, one can use a nested index block join algorithm, which is resolved by rj X log Si. Hence, the cost options for the local join operation are as follows. nested loop=x (max(^ x 5. )) hash = r^„,„x(max(^.+5,)) nested block index= J^.^;^x(max(^ xlog5, )) (2) Local aggregation cost takes the result of the join as its input, which is influenced by the join selectivity factor Sel(i). This selectivity factor is a proportion of the cardinality of the Cartesian product between the two tables, and hence the local aggregation cost is: Ta.s'xi^^Är.^^i^Selii))) (3) Re-distribution cost is determined by number of groups formed by local aggregation. This is influenced by the aggregation factor Agg(i). X (max(/;. x x Sel{i)x Agg{i))) (4) Global aggregation cost is composed of the merging of the local aggregation results and the Having operation. The cardinality of these operations is assumed obtained from the re-distribution cardinality. Assuming that the aggregation unit cost and the Having operation unit cost are the same which are determined by Tagg, the global aggregation cost is calculated as follows. T^^^ x (max(/;. x 5, x 5e/(/)x Agg{i))y (l +1) (5) Finally, consolidation cost is a data transfer cost to the host. The cardinality of the consolidation cost is reduced by further from that in the global aggregation cost by a factor of q which is the reduction factor after performing the Having clause. Tco.. X (max(r, x s, x 5e/(/)x Aggii)x 6 )) (6) The total cost for JPM is the sum of equations (1) to (6). Assuming that a nested block index join is used, the total JPM cost is as follows. + T;^^ x (max(/;. x x Selij))) + X (max(A; x 5, x Selii)x Aggiß) + x (max(r, x x Sel{j)x ^gg(/)))x (l +1) + X (max (r, x s, x Sel(/)x Agg(i)x 6 )) (V) The maximum execution time for each of the components in the above equation varies with the degree of skewness, and could be far from average execution time. Therefore, we need to apply the skew factors to the above cost equation. Data skew, in this context, can be categorized into data partitioning skew and data processing skew. Data partitioning skew refers to the uneven distribution of records of the operand tables over the processors and thus results in different processing loads. This is mainly caused by skewed value distribution in the partitioning attribute as well as improper use of the partitioning method. Data processing skew, on the other hand, refers to uneven sizes of the intermediate results generated by the processors. This is caused by the different selectivity factors of the join/aggregate of the local fragments. Since the intermediate results of the join operation are processed for aggregation, data processing skew may lead to different loads of the processors even when there is no data partitioning skew. We introduce two skew "factors a and ß. Data partitioning skew is denoted as (X, whereas data processing skew is represented as ß. Assume that a follows the Zipf distribution where the common word in natural language text occurs with a frequency proportional to / (Knuth, 1973; Wolf et al, 1993a,b), i.e., I Pi where Hf^, is the Harmonic number and could be approximated by (y + (Leung and Liu, 1994). Notice that all elements in pi are in order, and the first element p^ always gives the highest probability and the last element p^ gives the lowest. Considering both operand tables R and S use the same number of processors and follow the Zipf distribution, the data partitioning skew factor a thus can be represented as 1 a =- y + \nN where y = 0.57721 known as the Euler Constant and N is the number of processors. The other skew factor ß for data processing skew is affected by the data partitioning skew factors in both operand tables since the join/aggregation results rely on the operand fragments. Therefore, the range of ß falls in [ar x a„ 1], However, the actual value of ß \s difficult to estimate because the largest fragments from the two tables are usually not allocated to the same processor, resulting that ß is much less than the product of or, and a,. We assume in this paper that or, = or^. = or, and ß = ( or, x or, + 1) / 2 = (a^ + 1) / 2, and a detail discussion on skewness can be found in Liu et al (1995) and Leung and Liu (1994). We also need to make the following assumptions and simplifications: • J, -r^X s j x Sel{i) = J, (i.e. the join result cardinality without skew). 328 Informatica 26 (2002) 321-332 D. Taniar et al. • ^/oin = Tagg = Tp^oc ' an'l • Data transmission is carried out by message passing with a size of z. The cost equation (7) can then be re-written below JPM = / N JxAggy.i\ + G) , or(r + 5)+--1 j 2 as)+ — + ^- ß-^ proc T . conili + T. proc / J \ y + \nN log Y + \nN + APM= Tconin, X(max(r. + 5))+ 7^,,, x (max(r. log^)) + T^^^ X (max(r. x 5 x Sel{j))x (l + Agg{j))) (12) The skew factors a and ß can be added to the above equation in the same way for the JPM method. For the purpose of comparison of the two methods, we assume that Jj=rjXsxSel{j) = J and Agij)=^Agg. Notice that Jj takes s, whereas in the JPM, J, takes Therefore, it is acceptable, that Agg(J) in the APM is equal to Agg (as in the JPM) divided by N. The time of /i/'M method can then be expressed as APM = or + s + JxAggxe ßxN \ Iz + proc 1 + Agg N 4.2 The APM Cost Model The cost components for the APM cost models are explained as follows: Data partitioning cost for APM is the sum of the fragment of r and the full table of s. To differentiate between the JPM and the APM cost models, in the APM cost models, we use j as an index, not an /. Hence, the data partitioning cost is as follows. (8) Local join cost for the APM is similar to that in the JPM, with an exception that the cardinality of the second table is a fiill table, not a fragment. The different local join costs for the APM are then as follows. nested loop = x (max(r^ xs)} hash = x(max(r.+4 nested block index = x (max(r^. x log^)) (9) Aggregation costs consist of the local aggregation and the Having operation, which are calculated as follows. T^^^ X (max(r^ x5 x Sel{j))x (l + Agg{j))) (10) Finally, the consolidation cost is a result transfer cost which is influenced by the reduction factor imposed by the Having operation, as like in the JPM. x(max(r^ xsxSel(j)xAgg(j)x6)) (11) The sum of equations (8) to (11) gives the total cost for the APM, which is as follows. • + 5 + j' + lnA^ 2(y + \nNy JxAggxO \ + (^ + \nNy N h + T. proc log 5 + X + lnA'' 2(/ + lnyvy l + ir + lnNj -xjx 1 + Agg N J ) 4.3 The HPM Cost Model The cost components for HPM ars as follows. Data partitioning cost is determined by the fact that the group-by table is partitioned to all processors and all clusters, whereas the other table is partitioned to all clusters but replicated among all processors within each cluster. Assuming that R is the group-by table, total data transmission time is given by: (13) where / is in the range of [\,m\ and j is in the range of [ 1 ,n], and there are m clusters and n processors in each cluster. Local join cost is determined by cardinalities of the two fragments, which are indicated by and Sy Depending on the join algorithm, the local join costs are as follows. nested loop = x (max(A^ x^^ )) nested block index = r^.„;„x(max(r^.xlog5^ )) (14) Local aggregation cost at each processor is determined by the cardinality of the join result, which is given as follows. (15) Re-distribution cost is determined by the cardinality of the local aggregation results. We use an aggregation reduction factor Agg(J) in the cost equation. The transmission time of the local aggregation results to the processors within each cluster is given as follows. Toorn. X Xs^ xSel{j)x Agg{j))) (16) Global aggregation cost is composed of the merging cost and the Having operation cost. Like in the JPM we assume that the merging unit cost has the same value as the Having operation cost, which is identified by where J = r.jX Sj X Sel{j), 1 1 Y + lnn a =_,and« + r + ]nm 2iy + \nny It can be seen from the above execution time equation that the number of clusters m has strong influence on the performance of HPM. Figures 6 show the experimentation of query execution time when the number of clusters is increased in the HPM. It appears that a value of «7 = approximately gives the optimal cost of the query although the precise value of m may be worked out by finding the minimum value via the differentiation of the equation (19). 2 3 4 5 e No, of Clusters (m) (a) 8 processors 3 5 7 9 11 13 15 No. of Clusters (m) (b) 16 processors T,^ X (max(r, xs^ xSelij)^ Agg{j)))x (l +1) ^^ ^^ ^^^ (17) The last term of equation (17) indicates that one is for merging and the other for the Having cost. Finally, the consolidation cost is the cost to transfer the results from the clusters to the host. The time for data consolidation in the host is small and thus only data transmission cost is counted, i.e. x(max(A^ xSjXSel{j)xAgg{j)x6)) (18) The total execution time of the HPM is the sum of the time of the above equations (13) to (18) and is given as HPM= Tco„,. X (max(r^ + Sj ))+ x (max(r. log^,. )) + r„„„ X (max(/r; X s J x Sel(j))) agg ■ + X (max(/^. X X Sel{j)x Agg{j))) + X(max(/^ X5, XSel{jy Agg{j)))x 2 + T;»»™ X (max(^ X s J x Sel{jy Agg{j)x 6 )) (19) By applying the same simplification assumptions in the previous methods and Agg(j^- — Agg , equation m (19) is re-written as HPM = 5 Performance Evaluation Performance evaluation of the three methods described in the previous sections is carried out in terms of simulation. A simulation program called Transim, a transputer-based simulator (Hart, 1993), was used in the experiments. The programs were written in an Occamlike language supported by Transim. Using Transim, the number of processors and the architecture topology can be configured. Communication is done through channels, which are able to connect any pair of processors. Through this feature, the simulation model adopts a star network Master-Slave topology, where processing is done by distributing the work from the master to all slave processors. The hybrid topology can be built logically. We conducted a sensitivity analysis by varying a number of important factors such as the degree of skewness {a and ß), the aggregation factor, the table cardinality, the join selectivity factor, and the ratio of Tcomm / Tproc- The default parameter values are given in Table 2. i\+e) , Agg ßn m Iz proč J a„xa„xrxl0ia„xs)+jx \+2x ^gg m Parameter Value N 16 or 32 m Vl6=4 ir^N) r 1000 records s 1000 records Sel(i) 5(^/a-)=0.08 Aggr(i) 0.5 e 0.5 a 0.2985 a„ 0.5093 0.5093 ß 0.5446 ß. 0.6297 T^conun 0.1 standard time unit per message Tproc 0.01 standard time unit per record Z 100 records per message This is due to the replication cost imposed by /fPM- the more processors, the higher the data transmission cost for data replication. Overall, //PMprovides the best performance. 0,2 0.4 0.6 O.B Ags(i) (a) 16 processors A09(i) (b) 32 processors Table 2: Data Parameter Values. 5.1 Varying the Aggregation Factor The aggregation factor Agg(i) is defined by the ratio of result size after aggregation to the size of the base table. Figures 7 (a) and (b) show the impact of this aggregation factor on the three methods. In Figure 7(a), the three methods are compared using 16 processors. The aggregation factor is varied from 0 to 1. Notice that APAfs performance is quite constant. The majority of the cost goes to the replication of table S. Once table S is replicated, the operations become simple. Data transmission after joining, and processing the Having predicate do not contribute too much to the overall cost. As a result, the performance looks quite constant. The data to select after the group-by condition {Having is small, since the aggregation factor is already reduced by a factor of the number of processors. On the other hand, JPAfs performance goes up as the aggregation factor increases. This is because JPM works in two levels, and the data to be transmitted during the processes is determined by the aggregation factor. Generally, the larger the aggregation factor the more the running time is needed. The HP Ms performance provides the best performance, as it balances between the other two methods, whereby the join and aggregation are performed locally in each cluster, before the final aggregation is carried out. Using this method, the impact of the aggregation factor (as in JPM) and the replication (as in APM) is minimized. Figure 7(b) shows a comparative performance among the three methods using 32 processors. Increasing the number of processors will reduce the running time despite data partitioning and processing skew. The trend of the three methods is similar. The main difference to note is that when the aggregation factor is small using more processors, JPM performance is than that of APM. Figure 7: Varying Aggregation Factor. 5.2 Varying the Table Cardinality The cardinality of the operand tables is assumed the same elsewhere in the sensitivity analysis and their influences on performance are investigated here. Figure 8 shows the query execution time when we fix the cardinality of one table and other parameters and increase the cardinality of another table. When the table size is small, JPM provides better performance than APM, while HPM outperforms other methods despite varying the table sizes. Comparing Figure 8(a) to Figure 8(b), increasing processors also raises the performance cross-over point of JPM and APM. With a small table, the complexity of join operation is reduced enormously, and consequently JPM takes advantage of the lower local processing cost and produces a comparatively good performance. 100 500 1000 2000 sex» No,ofTn)les(s) (a) 16 processors 100 500 1(X0 2000 5000 (b) 32 processors Figure 8: Varying the Cardinality of Table S 5.3 Varying the Ratio of Tcomm / Tproc The ratio of T^omm I Tp^c reflects the characteristic of network used in the parallel architecture. The data communication time in parallel databases is not as critical as that in distributed systems (Almasi and Gottlieb, 1994). As we increase the ratio, system performance decreases as shown in Figure 9 since we treat Tproc as a standard time unit and increase the communication cost. In the figure, higher ratio means the communication is expensive, and being a parallel database system, this ratio tends to stay small. APM is the most sensitive to the communication cost because in our experiments both Sel(i) and Agg(i) are reasonably large resulting that the cost of the global aggregation in JPM is reasonably low. Nevertheless, HP M always performs better than JPM and APM and the improvement comes from fragmenting tables within each cluster. 0.1 1 10 100 RdtoofToormYTira; (a) 16 processors 1 ,10 100 2C Rctio of TocrmfTpnx (b) 32 processors Figure 9: Varying the Ratio of T„,„„„ / T^, pwc 5.4 Varying the Join Selectivity Factor The join selectivity factor has significant influence on parallel aggregation processing as it determines the number of records resulting from join intermediately. After that, those records are processed for aggregation and evaluated with the predicates. Eventually, the qualified records are union-ed to form the query result. Lower selectivity factor involves less aggregation processing time and transferring time, and thus it is in favour of JPM as shown in Figure 10. Fewer processors will also reduce the impact of the entire second table (both communication and processing) on the overall execution time so it favours APM. 0 2/r 4/r » 8/r 1(Vr Sel(i) (a) 16 processors 2/r 4A- 6»- 8/r 1(Vr Sel(i) (b) 32 processors Figure 10: Varying the Selectivity Factor. . unik« 1 1.5 2 3 3.5 Data Partition Skew (i) (a) Data partition skew 0.75 1 1.25 1.S IData Processing (i) (b) Data processing skew Figure 1 l:Varying the Skewness with 16 Processors. 5.6 Varying the Number of Processors One of the desired goals of parallel processing is to have linear scale up which can be achieved when twice as much processors perform twice as large a task in the same time. When the number of processors is increased, as we expected, the performance is upgraded in spite of the skewness shown in Figure 12. As shown in the figure, when the number of processors is small, APM performs extremely well (even better than HPM) because the number of clusters in HPM may not be optimised and less processors make the communication cost insignificant which is in favour of APM. However, when the database system scales up, both HPM and JPM provide better performance than APM. 5.5 Varying the Degree of Skewness Figure 11(a) indicates the tendency of the performance when the data processing skew changes accordingly with the data partitioning skew whereas Figure 11 (b) provides the comparison when we ignore the data partitioning skew, i.e. a = l/N and alter the data processing skew. The values on the horizontal axis of both figures represent the expanding skewness factor which then is multiplied by the basic unit given by Zip/ distribution. Unlike the factor a, the factor ß is inversely proportional to data processing skew, and the larger the factor j3 the less the data processing skew is. We conclude from Figure 11 that either partitioning skew or processing skew degrades the performance of parallel processing, HPM outperforms APM and JPM even in the presence of skewness, and APM is less affected by the skewness compared with JPM. Nd. of Processcrs(N) (a) (a)/(gg(;) = 0.5,Se/(0 = 5(Mr) (b) Agg{i) = 0.6, Sel{i) = 1 0(/V/a-) Figure 12: Varying the Number of Processors. 6 Conclusions and Future Work Traditionally, join operation is processed before aggregation operation and tables are partitioned on join attribute. In this paper, we demonstrate that group-by attribute may also be chosen as the partition attribute and present three parallel methods for aggregation queries, JPM, APM, and HPM. These methods differ in the way of distributing query tables, i.e. partitioning on the join attribute, on the group-by attribute, or on a combination of both; consequently, they give rise to different query execution costs. In addition, the problem of data skew has been taken into account in the proposed methods as it may adversely affect the performance advantage of parallel processing. The cost analysis shows that when the join selectivity factor is small and the degree of skewness is low, JPM leads to less cost; otherwise APM is desirable. Nevertheless, the hybrid method {HPM) is always superior to the other two methods since the data partitioning is adaptively made on both join attribute and group-by attribute. In addition, it can be observed that the partitioning on group-by attribute method is insensitive to the aggregation factor and thus the method will simplify algorithm design and implementation. Our future work is planned to investigate the behaviour of the HPM method in a real hybrid architecture whereby the number of clusters and the number of processors within each cluster are predetermined. We will also take into consideration the fact that it is common that processors within each cluster normally share the memory (i.e. shared-memory SMP machines), but different clusters communicate through network (i.e. shared-nothing among clusters) (Valduriez, 1993). It will be interesting to see the impact of two levels of partitioning methods like in the HPM model in real hybrid architectures. Acknowledgement I would like to thank M.Z. Ashrafi and L. Tan for formatting the camera-ready version of this paper. References [1] Almasi G., and Gottlieb, A., Highly Parallel Computing, Second edition, The Benjamin/ Cummings Publishing Company Inc., 1994. [2] Bedell J.A. "Outstanding Challenges in OLAP", Proceedings of 14"" International Conference on Data Engineering, 1998. [3] Bultzingsloewen G., "Translating and optimizing SQL queries having aggregate", Proceedings of the is"" International Conference on Very Large Data Bases, 1987. [4] Datta A. and Moon B., "A case for parallelism in data warehousing and OLAP", Proceedings, of 9"' International Workshop on Database and Expert Systems Applications, 1998. [5] Dayal U., "Of nests and trees: a unified approach to processing queries that contain nested subqueries, aggregates, and quantifiers". Proceedings of the 13"' International Conference on Very Large Data Bases, Brighton, UK, 1987. [6] DeWitt, D.J. and Gray, J., "Parallel Database Systems: The Future of High Performance Database Systems", Communication of the ACM, vol. 35, no. 6, pp. 85-98, 1992. [7] Graefe G., "Query evaluation techniques for large databases", ACM Computing Surveys, Vol.25, No.2, June 1993. [8] Hart, E., Transim: Prototyping Parallel Algorithms, User Guide and Reference Manual, Transim version 3.5, University of Westminster, August 1993. [9] Kim, W., "On optimizing an SQL-like nested query", ACM Transactions on Database Systems, Vol 7, No 3, September 1982. [10] Knuth D. E., "The art of computer programming", Volume 3, Addison-Wesley Publishing Company, INC., 1973. [11] Leung C. H. C. and K. H. Liu, "Skewness analysis of parallel join execution". Technical Report, Department of Computer and Mathematical Sciences, Victoria University of Technology, Melbourne, Victoria, Australia, 1994. [12] Leung, C.H.C, and Ghogomu, H.T., "A HighPerformance Parallel Database Architecture", Proceedings of the Seventh ACM International Conference on Sup er computing, Tokyo, pp. 377386, 1993. [13] Leung, C.H.C, and Taniar. D., "Parallel Query Processing in Object-Oriented Database Systems", Australian Computer Science Communications, vol 17, no 2, pp. 119-131, 1995. [14] Liu K. H., Leung C. H. C., and Y. Jiang, "Analysis and taxonomy of skew in parallel database systems". Proceedings of the International Symposium on High Performance Computing Systems (HPCS'95), Montreal, Canada, pp. 304315, July 1995. [15] Liu K. H., Y. Jiang, and C.H.C. Leung, "Query execution in the presence of data skew in parallel databases", Australian Computer Science Communications, vol 18, no 2, pp. 157-166, 1996. [16] Mishra, P. and Eich, M.H., "Join Processing in Relational Databases", ACM Computing Surveys, vol. 24, no, 1, pp. 63-113, March 1992. [17] Valduriez, P., "Parallel Database Systems: The Case for Shared-Something", Proceedings of the International Conference on Data Engineering, pp. 460-465, 1993. [18] Wolf J. L., Dias D. M., and P. S. Yu, "A parallel sort-merge join algorithm for managing data skew", IEEE Transactions On Parallel And Distributed Systems, Vol. 4, No. 1, January 1993(a). [19] Wolf J. L., Yu P. S., Turek J. and D. M. Dias, "A parallel hash join algorithm for managing data skew", IEEE Transactions On Parallel and Distributed Systems, vol.4, no. 12, December 1993(b). [20] Yan W. P. and P. Larson, "Performing group-by before join". Proceedings of the International Conference on Data Engineering, 1994. Developing Software Across Time Zones: An Exploratory Empirical Study Adel Taweel and Pearl Brereton Department of Computer Science Keele University, Keele Staffordshire ST5 5BG, UK Email: a.taweel or o.p.brereton@cs.keele.ac.uk www.keele.ac.uk/depts/cs Keywords: global software development, collaborative working, distributed software engineering, virtual teams. Received: May 11, 2002 Market forces and an increasingly reliable world-wide communications network have made geographically distributed software engineering a reality. Global software development enables businesses to respond more easily and more quickly to global market opportunities and to improve product and service quality. One of the many potential benefits of global development is a reduction in development time through the adoption of an 'around the clock' working practice. This paper introduces a sequential collaborative software engineering process involving shift working across time zones and describes an exploratory empirical study of this working pattern involving the implementation of a small-scale software system. The paper reports on the organisation of the study and on the results obtained through questionnaires, observations and measurements. 1 Introduction The empirical study described in this paper was carried out as part of a research project investigating the potential for reducing the time needed to carry out software engineering tasks (and hence to deliver software products) through the use of around the clock working. The working style being addressed is one where-a task is passed in a sequential manner from one software engineer to another 'across time zones'. We call this sequential collaborative software engineering (SCSE). A general three-site scenario is illustrated in Figure-1, and shows: • the time differences between sites (which may involve some overlap); • the reporting time when, at the end of a working period or shift, a developer records progress made; • the catching up time, when a developer catches up with the work carried out during the previous shift. As well as undertaking an empirical study of SCSE, our research has involved the development of a set of equations which models the relationships between estimated development time using SCSE, estimated development time for single-site working, a number of contextual factors and the overheads associated with SCSE [Taweel02]. The contextual factors that are included in the model are: • the number of sites participating in a collaboration - this is likely to be either two or three sites; • the time differences between the collaborating sites; • the number of participating developers; • the level of concurrency (i.e. the task-specific potential for concurrent working). The overheads of distribution that are accommodated are: • extra management, since the added complexity of SCSE over single-site development is likely to require more planning and progress monitoring; • general task-level communications, which may be needed from time to time for a range of purposes such as reviewing decisions or negotiating the overall approach to be taken; • reporting time - i.e. the time taken by a developer to report progress at the end of a shift; • catching up time - i.e. the time taken by a developer to catch up with work completed since completing his/her previous shift; • distribution effort loss, which is the time lost when a developer at one site fails to complete a task on which a subsequent developer is depending. The aims of our empirical study were to illustrate the feasibility of employing this type of work pattern and to identify the critical success factors for SCSE. We also expected to obtain some values for the associated overheads (such as reporting time and catching up time) for the particular experimental context. The remainder of the paper is organised as follows. Section 2 and 3 describe the preparatory activities (such as the selection of subjects, the design of the study and document preparation) and the execution of the selected task. Section 4 and 5 summarise analysis and observations, critical success factors, and final remarks. 2 Preparatory activities Any empirical study, whether it is a formal experiment, a case studv involving a real project, a survey or, as in our case, an informal exploratory study, is a substantial undertaking needing a considerable amount of careful planning [Bausell86, Kitchenham97]. The task is even more challenging when the subjects need to work collaboratively and are to be located different countries and different time zones. Preparatory activities include the selection of subjects, the overall design of the study and the production of a range of documents needed to support the study and transfer of knowledge between sites. 2.1 Selection of subjects As for many empirical studies, obtaining subjects is a major problem and this was particularly difficult in our case because of the need to recruit subjects at sites located in different time zones. The sites chosen were Keele (our 'home' site in the UK) and Hebron (in Israel), which have a time difference of 2 hours. We were able to use four subjects (2 in each Figure 1 : Three Sites m location) and therefore the SCSE task was executed twice (using 1 subject per site on each occasion). The two sites have similar computing facilities and the subjects have good computing and English language skills. 2.2 Design of the study The design of the study covers a range of activities including the selection of tasks to be carried out, planning the execution in terms of the procedures to be followed, scheduling and monitoring, deciding what data should be collected and arranging the collection of the data. 2.2.1 The software task In choosing a software task, a compromise had to be found between the available resources (especially in terms of people and their time) on the one side and the complexity of the task on the other side. Although it may be feasible to distribute other software engineering tasks (such as design and requirements analysis) we felt that the less creative nature of coding (compared especially to designing) would provide greater opportunity for successful collaboration over the necessarily limited time scale of the study. The software engineering task chosen for implementation was a calculator program based on a design that was produced at Keele. The task was selected on the basis that it should be possible to complete the available but that the be non-trivial. The implementation in the time programming effort would requirements specification and the high level design of the chosen software task are shown in Appendix 3 2.2.2 Methods and tools One essential step was to decide what development methods and tools to use during the study. The approach taken was to choose the method and tools that were familiar to the subjects, in order to avoid the need for training, especially because carrying out training for remote subjects would be very difficult. These constraints led us to select Java as the programming language and a hybrid of the Yourdon method [Yourdon79, Coad91] and UML [OMG98, Rumbaugh99] as the modelling language. 2.2.3 The work pattern Constraints on the availability of subjects led us to schedule the implementation over five shifts each of between two and three hours duration. The time difference between sites meant that the shifts spanned either two or three days. This allowed the subjects in Hebron to fit in their shifts either immediately before or immediately after their normal working hours. The plan was to give the design document to the subjects a few days in advance and to allow them to ask for clarification from the designer if required. An initial expected ordering and scheduling of the implementation activities was determined although the subjects were not required to adhere rigidly to either. 2.3 Data collection, knowledge transfer and preparation of documents Because it was not possible to meet all of the subjects face-to-face, all of the necessary instructions and data collection templates needed to be in electronic form. Several documents were prepared for the different phases of the study: • Instructions to subjects which included an overview of the study and the procedures that should be followed by subjects at each site for each phase; • Task description and design which provided the requirements specification, design and coding convention for the system to be developed; • Implementation schedule proposing an initial allocation of tasks (units of implementation) to subjects over the five shifts; • Development dependency chart describing the dependencies between components of the software system being developed. This document was essential to help subjects understand the various possible orders in which the components could be implemented. This would enable subjects to devise an alternative schedule if they were unable to adhere to the proposed initial schedule; • Set-up completion form to collect information about the documents received by each site and/or problems encountered during the set-up phase; • Knowledge transfer template to be used by subjects during the execution phase to report the status of the task being carried out, enabling them to report problems encountered with received and sent tasks, actions taken by them and progress made. In addition to the code, this template represents the main means of knowledge transfer between sites (see Appendix 5); • Timing collection template to record the catching-up time, reporting time, time spent coding and communication times for each shift; • Subject information form used during the termination phase to collect information about the subjects' experience and personal information; • Questionnaire to collect qualitative data about the subjects experiences and opinions of SCSE. 3 Task execution The task execution involved three phases: the set-up phase, the execution phase and the termination phase. During the set-up phase, documents were distributed to the subjects and any problems addressed. The execution phase included the implementation of the software application, collection of quantitative data and progress monitoring. During this phase only source code files and status report of shifts (or implementation units) were transferred between subjects. In the termination phase, qualitative data was collected and the software application tested. During the three phases, email was used to transfer documents between subjects and between subjects and the evaluator. Details of a particular shift, which illustrates the activities performed and the information exchanged between sites, are included in Appendix 2. 4 Analysis and Observations The quantitative data collected throughout the study enabled us to gain some insight into the overheads associated with SCSE in the particular context of the study. Data relating to time spent on the task for each shift, the catching up time, the reporting time and time spent communicating is shown in Table 1. The variations in values for catching up time and reporting time were small however the communications times for Hebron shifts were considerably longer than for the Keele shifts. This was because the Hebron subjects had to use a dial-up connection whereas Keele subjects had a permanent Internet connection. It can be seen that on average the total knowledge transfer time (catching up time, reporting time and communications) is 31 minutes. Since the total shift time (on average) was 129 minutes, knowledge transfer made up approximately 24% of the time. Although this proportion is high, it is mainly made up of communication time. When communications facilities are good, as for the Keele site, then the proportion is less than 13%. This overhead works out at less than 9% for a working day of 8 hours under the assumptions that the communication time remains constant and the catching up time and reporting time increase linearly. Overall Hebron Keele SD average average average across across across lOshifts 6 shifts 4 shifts (min) (min) (min) Development time 98 101 95 - Catching up time 5 5 3 1 Reporting time 8 11 5 3 Communications time 18 20 6 8 Table 1: Data showing some overheads distribution of It can be seen that on average the total knowledge transfer time (catching up time, reporting time and communications) is 31 minutes. Since the total shift time (on average) was 129 minutes, knowledge transfer made up approximately 24% of the time. Although this proportion is high, it is mainly made up of communication time. When communications facilities are good, as for the Keele site, then the proportion is less than 13%. This overhead works out at less than 9% for a working day of 8 hours under the assumptions that the communication time remains constant and the catching up time and reporting time increase linearly. These quite low values for catching up time and reporting time are encouraging especially given the low level of automation provided during the study to support these activities. A greater level of automation is possible and likely if SCSE is used in a commercial setting. The qualitative data collected was concerned with the subjects' opinions on a number of issues (see Table 2). Although, from their general comments, the subjects felt SCSE to be very efficient it was not a particularly popular way of working. This seems to be because, to some extent, subjects felt that their working style was constrained. Nevertheless some were keen to try the approach for larger scale projects. Of the general comments from subjects, the most notable was an expression of the need for high quality documentation especially relating to requirements, design, design rationale and coding conventions. In terms of product quality, the overall approach and process followed seems to have had no ill effects. In fact the final systems were fully tested and appeared to have no implementation errors (although one design fault was found). An additional observation was that if subjects finished their allocated activities early they did not continue to work until the end of the shift (even though they had been told to do so). However, subjects also felt that they were 'under pressure' to complete the activities scheduled. Clearly a balance needs to be struck between the view that 7 have done my bit so 1 can stop' and 7 can't keep up with the work rate expected of me '. Yes No Was synchronous communications needed? 0 4 Were design documents adequate? 4 0 Were problems encountered with the communications? 1 3 Do you think that SCSE would be more suitable for bigger projects? 2 1 (+1 unsure) Did you feel that SCSE restricted your work? 3 1 Would you prefer to use SCSE as opposed to single-site development? 0 2 (+2 unsure) Table 2: Summary of questionnaire responses 5 Critical success factors The aims of this work were to illustrate the feasibility of employing SCSE, to identify the critical success factors and to obtain values for the associated overheads (in the context of the study). The values for knowledge transfer time, catching-up time and reporting time are not unduly high and suggest that the overheads associated with SCSE will not prevent it from being a feasible working pattern. In addition, although SCSE was not a popular working pattern, subjects felt that it was efficient and had potential for use in larger projects. In the remainder of this section, we outline the critical success factors. 5.1 Planning Good planning is crucial for the success of SCSE. Plans need to include both a detailed task schedule and contingencies. Further, it is apparent that timing restrictions imposed by SCSE put software engineers under pressure. This suggests that the distribution pattern with the maximum timing flexibility should be chosen. In addition, although the values of the overheads obtained cannot be generalised it is clear that such overheads are strongly dependent on organisational and management factors. It is important, therefore, to accommodate controlled deviation from planned schedules. 5.2 Documentation Precise and complete documentation is a critical requirement throughout SCSE as well as being a consequence of the process. A documentation standard must be strictly defined to reduce ambiguities and ensure consistency. Documentation needed includes details of development schedule, requirement specifications, design method and symbols and coding conventions. SCSE also results in the actual process followed being well documented. Any difficulties arising, decisions made, rationales etc. are documented as part of the process and such information could be made available for later analysis if desired. 5.3 Software engineering tasks Although we expect SCSE to be applicable to different types of software engineering tasks, this study only illustrates its applicability to coding and unit testing. It may be that the more creative tasks that would require a higher degree of collaboration (e.g. design) could be done using SCSE, however, it is likely that such tasks would require substantially better tool support and a great level of synchronous collaboration. The success of SCSE for a software task does not only depend on the characteristics of the software task itself but also on how these characteristics are addressed and considered during the planning and documentation. 5.4 Communications Not surprisingly, it is essential that the communications mechanisms and tools are easy to use and reliable for SCSE to work successfully. 5.5 Development methods and tools One of the factors that emerged during this study was the importance of having a compatible set of development methods and tools at participating sites. It was also important that subjects were familiar with their use. 6 Final remarks In addition to the inherent advantages of SCSE in terms of reduce time scales, we can expect the code produced to be both reliable and maintainable. Three observations lead us to this conclusion: • the process requires strict adherence to documented coding conventions; • the code is developed by more than one software engineer so has some of the benefits, such as continuous review, of pair programming [WilliamsOO]); • every step and phase of development is thoroughly documented (driven by the need for extra planning and supplemented by the information accumulated through the knowledge transfer templates). Acknowledgements The authors acknowledge the support of the British Telecommunications pic. who funded this work and the help of the subjects who took part in the empirical study. References Bausell86 Coad91 Bausell, R. B., A Practical Guide to Conducting Empirical Research, Harper & Row Publishers, 1986. Coad, P. & Yourdon, E., Object Oriented Analysis, 2nd Ed., Yourdon Press, Englewood Cliffs, N.J, 1991. Kitchenham97 Kitchenham, B., Linkman, S. & Law, D., DESMET: a methodlogy for evaluating software engineering methods and tools, Computing & Control Engineering Journal, Vol. 8, No. 3, pp. 120-126, June 1997. OMG98 OMG, Unfiled Modeling Language Specification, Object Management Group, Framingham, Mass, URL: www.omg.org, 1998. Rumbaugh99 Rumbaugh, J., Jacobson, 1. & Booch, G., The Unified Modeling Language Reference Manual, Addison Wesley Longman, Inc., 1999. Taweel02 Taweel, A., & Brereton, O.P., Software Development Across Time Zones, In preparation. WilliamsOO Williams, L. and Kessler R. R., Cunningham,W. and Jeffries, R., Strengthening the Case for Pair-Programming, IEEE Software, 2000. Yourdon79 Yourdon, E. & Constantine L., Structured Design: Fundamentals of a Discipline of Computer Program and Sytems Design, Yourdon Press, Englewood Cliffs, N.J, 1979. Appendix 1: Equations for estimating distributed development time The gain factors (G/^ and GF,^ ) in development time (with respect to single site development) are represented by equations 1.0 and 2.0 where: N^ is the number of utilised sites N^ is the number of developers O, is the overlap between consecutive sites GFjv is the gain factor based on the number of utilised sites GF^ is the gain factor based on the number of developers WD is the working day at each site (it is assumed that the working day at all sites has the same value). = E N xWD n.-x f = S WD-O^. NX WD Where Oji is the overlap between i* site where the i* developer is located and the i+1 site where i+1 developer (member of the team) is located. Osi = 0 for developers who are not part of a team. The reduction in development time (Reduction Factors) is expressed in the following equations: RF^^ = , 0 The estimated development time for SCSE is expressed by the following equation: NDT = STx RF^ +PTx RF^^ + Overheads Where ST is the development time estimate for sequential tasks PT is the development time estimate for parallel tasks EDT is the development time estimate for single site development and PW is the level of potential concurrent working in the given software task. NDT is the multi-site development time estimate ST = EDT-EDTxPW where PT=EDTxPW and The equations derived are based on the assumption that all utilised sites work within a 24-hour period. This is expressed by the following equation: Total working period = ^ ÌVD. - TD. \ Appendix 2: Details of a shift The particular shift described is shift two for subject pair B. At the beginning of the shift the subject received eight files as email attachments. These were: • the knowledge transfer form (an MSWord document) which was completed by the collaborating subject at the end of shift one; the seven source files that had been created during the set up phase and which held all of the coding produced so far. These were made up of four Java source files - Calculator .java, MathFunction.java, Accumulator.java and Operation.java and three VisualCafe project files - Calculator.vep, Calculator.ve2 and Calculator, vpj. The activities undertaken and the outcomes or results are shown in Table 1 below. After approximated 70 minutes of the two-hour shift the subject had completed the scheduled activities (see row three in table 1). He had been told that if he finished early he should move on to the activities scheduled for the following shift. However, he did not do this, but instead moved to the 'end of shift' activities. Figure 2: Shift Plan - Subject Pair A Figure 3: Shift Plan - Subject Pair B Activity Outcome/result 1. checked if all necessary documents were received and readable Yes .... No problems 2. reviewed the knowledge transfer form (see Appendix 5) One problem noted; actionPerformed method could not be fully tested because it calls methods that had not yet been written. To enable testing of all the class, the code written for calling these methods is kept as comments. Subjects at subsequent shifts retest respective code portions of this method when the methods being called are completed (this is part of the unit testing plan outlined in the task description and design document). 3. coded according to the implementation schedule from the point at which the collaborating subject finished Since the scheduled activities had been completed during shift one this subject worked on methods for the Accumulator class, Operation class and MathFunctions class, until all scheduled activities were completed and tested. This shift also involved testing the respective part (that used the methods written in this shift) from the actionPerformed method according to the problem highlighted above. 4. performed 'end of shift' activities Completed a knowledge transfer form, reporting that all files had been received successfully from shift one, all scheduled activities had been performed and no problems had been encountered. All completed tasks were marked with a Y (yes) in the implementation schedule (see Appendix 5). The knowledge transfer form and seven source files were emailed to the collaborating subject (who would work during shift three). Table 1: Typical Shift Activities 340 Informatica 26 (2002) 333-344 A. Taweel et al. Appendix 3: Requirements specification and class diagram ;iSy.vtó«i7Vdwe; Calculator Requiremem Specifìcutìons: This application is a normal common calculator. It should have the following specifications: 1. An applet based application ihat runs in a Java-based browser 2. Can be activated using the mouse. 3. Performs the following mathematical functions 3.1. Addition (+) 3.5. Power (x'^y) 3.2. Subtraction (-) 3.6. Square (x*x) 3.3. Multiplication (*) 3:7. Percent (%) 3.4. Divisione/), 3.8. Square Root 4. It has a standard interface ìi lExdusions: 1. It does not provide a help systems 2. It does not include any menu/options for upgrade. 3. It runs on a browser that supports the current version of Java (version 1.2) 4. It.can only be activated using the mouse and not the keyboard , Behavioural Restrictions: 1. Display: Numbers should be left aligned with respect to the display. Calcularor when started/restarted/reinitialised should display 0.0. Numbers when displayed should be in the double format (e.g. li.0,11.2, 0.112 etc.) 2. One Operand Functions: For these functions enter a number and then requesting a function should do the calculation on the entered number and display the result. 3. Two operand Functions: for these functions enter a number, request a function, enter another number and then requesting another function or get a result function (Equal) displays the result of the first requested function. 4. Get a result function (Equal): execute the last requested operation (for two operand function only) and displays the result of the calculation. Subsequent request of this function should not invoke any function or change displayed result Class Diagram Appendix 4: Implememtatioe Schediiile arad Dependency Chart Impìementatìon Scheduiile M 3» GO Ö* » K> C« 5? U) 00 J C« Ö" B C« cr os Hebron Keele Class iComponents Calculator SysAction Display initO — the interface only All AU Class Accumulator Operation Math Functions Components All All Add(), Sub(), Div() Power() Class Components Math Functions Control Variables Multo, SquareO, Percent() SqRootO All Class EventHandler Components ClearButtonO NumbersButtonO DecimalPointButtonO Class Components EventHandler SysAction ExecuteOperationO OneOperandOperationButtonO TwoOperandOperationButton Equal ButtonO actionPcrlbrmedO - Update Task Integration and Testing Components All Start Level 1 Level 2 Taskl : Code Setup Task2: Interface Level 3 Tasks : Accumulator Task4; Operation Tasks : Display Level 4 Task6: MathFunctions Level 5 Task?: ControIVariables i Tasks : EventHandler Task9: SysAction End Development Dependency Chart 344 Informatica 26 (2002) 3 3 3-344 A. Taweel et al. Appendix 5: Knowledge Transfer template Date: | xx/xx/xxxx Shift No Personal/Site Information Name: j xxxxxx Site: I Hebron Team Name Hebron Received Task Are all received files readable (Yes/No) If no, write down names of unreadable tiles yes Any missing components/methods in the received files (Yes/No) j no If yes, write down names of missing/expected componenls/methods Sent Task Are ALL scheduled subtasks completed (Yes/No) .:If;no, write the uncompleted subtasl«/com ...................................... Subtask/Method | .......... 'wh'y''(re'a'so if any)..... yes Problems encountered (if any) (Yes/No) If yes, write down encountered problems yes Problem IE Description/Suggestion ActionPerfortned method all methods are kept as comments (because not written yet) but can not test if there is spelling mistakes or any other mistakes. Display class methods not called by any other method to test, but 1 used extra button to call them , they work tine. 1 deleted the extra code. Inipk'iiiciitnlini Schidiile » 5 cr 3 s Calculalor V linilo -> InlcrljJc. SysAclioii \S:|actionPerfbnne' Display " Y L'lidiiicDispl.n ; ill. Y Ro.iJDispl.n ("IcatOi^pLi) ^ n Accuiiiiiliilor Sei-Accuniuldldi GclAccumuLiior,' CLmi \ccuiiiiil O pc ration SoiOpcuiiion UclDpciuiinn n C IcLiiUpci.ilioi, MathFuiiclion.N Add Sub Div Power ff| Malhl'iinctions Mull SqULiic Poi L-cni «n 0- 1-1 O B m Sl.ll<(HH GonlrolN'analili s Scll,nici\'cv\Nuinl"ici SciDccnnalPo GelEnterNevviSumhot GelDccjnidlPi ml; n n r\entlliuidlcr CIcLirlUiiion Numbciv.l3uiU M rp Dccini.ilPoinilUillon Evenillandlc-r X rt cr -i o 3 l-AOLULcOpeu Onc( )pci cindOperàtion 1 w o( )pcMixl{)pcj .iiion S>sAcllon (updiiti. ' [iictiimpL-rformcd,^,' Integration & letlinu All t —-—*-^ JOŽEF STEFAN INSTITUTE Jožef Stefan (1835-1893) was one of the most prominent physicists of the 19th century. Born to Slovene parents, he obtained his Ph.D. at Vienna University, where he was later Director of the Physics Institute, Vice-President of the Vienna Academy of Sciences and a member of several scientific institutions in Europe. Stefan explored many areas in hydrodynamics, optics, acoustics, electricity, magnetism and the kinetic theory of gases. Among other things, he originated the law that the total radiation from a black body is proportional to the 4th power of its absolute temperature, known as the Stefan-Boltzmann law. The Jožef Stefan Institute (JSI) is the leading independent scientific research institution in Slovenia, covering a broad spectrum of fundamental and applied research in the fields of physics, chemistry and biochemistry, electronics and information science, nuclear science technology, energy research and environmental science. The Jožef Stefan Institute (JSI) is a research organisation for pure and applied research in the natural sciences and technology. Both are closely interconnected in research departments composed of different task teams. Emphasis in basic research is given to the development and education of young scientists, while applied research and development serve for the transfer of advanced knowledge, contributing to the development of the national economy and society in general. At present the Institute, with a total of about 700 staff, has 500 researchers, about 250 of whom are postgraduates, over 200 of whom have doctorates (Ph.D.), and around 150 of whom have permanent professorships or temporary teaching assignments at the Universities. In view of its activities and status, the JSI plays the role of a national institute, complementing the role of the universities and bridging the gap between basic science and applications. Research at the JSI includes the following major fields: physics; chemistry; electronics, informatics and computer sciences; biochemistry; ecology; reactor technology; applied mathematics. Most of the activities are more or less closely connected to information sciences, in particular computer sciences, artificial intelligence, language and speech technologies, computer-aided design, computer architectures, biocybemetics and robotics, computer automation and control, professional electronics, digital communications and networks, and applied mathematics. ranean Europe, offering excellent productive capabilities and solid business opportunities, with strong international connections. Ljubljana is connected to important centers such as Prague, Budapest, Vienna, Zagreb, Milan, Rome, Monaco, Nice, Bern and Munich, all within a radius of 600 km. In the last year on the site of the Jožef Stefan Institute, the Technology park "Ljubljana" has been proposed as part of the national strategy for technological development to foster synergies between research and industry, to promote joint ventures between university bodies, research institutes and innovative industry, to act as an incubator for high-tech initiatives and to accelerate the development cycle of innovative products. At the present time, part of the Institute is being reorganized into several high-tech units supported by and connected within the Technology park at the Jožef Stefan Institute, established as the beginning of a regional Technology park "Ljubljana". The project is being developed at a particularly historical moment, characterized by the process of state reorganisation, privatisation and private initiative. The national Technology Park will take the form of a shareholding company and will host an independent venture-capital institution. The promoters and operational entities of the project are the Republic of Slovenia, Ministry of Science and Technology and the Jožef Stefan Institute. The framework of the operation also includes the University of Ljubljana, the National Institute of Chemistry, the Institute for Electronics and Vacuum Technology and the Institute for Materials and Construction Research among others. In addition, the project is supported by the Ministry of Economic Relations and Development, the National Chamber of Economy and the City of Ljubljana. Jožef Stefan Institute Jamova 39, 1000 Ljubljana, Slovenia Tel.:-H386 1 4773 900, Fax.:-h386 1 219 385 Tlx.:31 296 JOSTIN SI WWW: http://www.ijs.si E-mail: matjaz.gams@ijs.si Contact person for the Park: Iztok Lesjak, M.Sc. Public relations: Natalija Polenec The Institute is located in Ljubljana, the capital of the independent state of Slovenia (or S^nia). The capital today is considered a crossroad between East, West and Mediter- EDITORIAL BOARDS, PUBLISHING COUNCIL Informatica is a journal primarily covering the European computer science and informatics community; scientific and educational as well as technical, commercial and industrial. Its basic aim is to enhance communications between different European structures on the basis of equal rights and international referee-ing. It publishes scientific papers accepted by at least two referees outside the author's country. In addition, it contains information about conferences, opinions, critical examinations of existing publications and news. Finally, major practical achievements and innovations in the computer and information industry are presented through commercial publications as well as through independent evaluations. Editing and refereeing are distributed. Each editor from the Editorial Board can conduct the refereeing process by appointing two new referees or referees from the Board of Referees or Editorial Board. Referees should not be from the author's country. If new referees are appointed, their names will appear in the list of referees. Each paper bears the name of the editor who appointed the referees. Each editor can propose new members for the Editorial Board or referees. Editors and referees inactive for a longer period can be automatically replaced. Changes in the Editorial Board are confirmed by the Executive Editors. The coordination necessary is made through the Executive Editors who examine the reviews, sort the accepted articles and maintain appropriate international distribution. The Executive Board is appointed by the Society Informatika. Informatica is partially supported by the Slovenian Ministry of Science and Technology. Each author is guaranteed to receive the reviews of his article. When accepted, publication in Informatica is guaranteed in less than one year after the Executive Editors receive the corrected version of the article. Executive Editor - Editor in Chief Anton P. Železnikar Volaričeva 8, Ljubljana, Slovenia s51em@lea.hamradio.si http ://lea.hamradio.si/"s51em/ Executive Associate Editor (Contact Person) Matjaž Gams, Jožef Stefan Institute Jamova 39, 1000 Ljubljana, Slovenia Phone: +386 1 4773 900, Fax: +386 1 219 385 matjaz.gams@ijs.si http://ai.ijs.si/mezi/matjaz.html Executive Associate Editor (Technical Editor) Rudi Mum, Jožef Stefan Institute Publishing Council: Tomaž Banovec, Ciril Baškovič, Andrej Jerman-Blažič, Jožko Čuk, Vladislav Rajkovič Board of Advisors: Ivan Bratko, Marko Jagodic, Tomaž Pisanski, Stanko Strmčnik Editorial Board Suad Alagić (Bosnia and Herzegovina) Vladimir Bajić (Republic of South Africa) Vladimir Batagelj (Slovenia) Francesco Bergadano (Italy) Leon Birnbaum (Romania) Marco Botta (Italy) Pavel Brazdil (Portugal) Andrej Brodnik (Slovenia) Ivan Bruha (Canada) Se Woo Cheon (Korea) Hubert L. Dreyfus (USA) Jozo Dujmović (USA) Johann Eder (Austria) Vladimir Fomichov (Russia) Georg Gottlob (Austria) Janez Grad (Slovenia) Francis Heylighen (Belgium) Hiroaki Kitano (Japan) Igor Kononenko (Slovenia) Miroslav Kubat (USA) Ante Laue (Croatia) Jadran Lenarčič (Slovenia) Huan Liu (Singapore) Ramon L. de Mantaras (Spain) Magoroh Maruyama (Japan) Nikos Mastorakis (Greece) Angelo Montanari (Italy) Igor Mozetič (Austria) Stephen Muggleton (UK) Pavol Navrat (Slovakia) Jerzy R. Nawrocki (Poland) Roumen Nikolov (Bulgaria) Franc Novak (Slovenia) Marcin Paprzycki (USA) Oliver Popov (Macedonia) Karl H. Pribram (USA) Luc De Raedt (Belgium) Dejan Raković (Yugoslavia) Jean Ramaekers (Belgium) Wilhelm Rossak (USA) Ivan Rozman (Slovenia) Claude Sammut (Australia) Sugata Sanyal (India) Walter Schempp (Germany) Johannes Schwinn (Germany) Zhongzhi Shi (China) Branko Souček (Italy) Oliviero Stock (Italy) Petra Stoerig (Germany) JinŠlechta(UK) Gheorghc Tecuci (USA) Robert Trappl (Austria) Terry Winograd (USA) Stefan Wrobel (Germany) Xindong Wu (Australia) An International Journal of Computing and Informatics Introduction Group Cryptography: Signature and Encryption Cryptanalysis of Some Hash Functions Based on Block Ciphers and Codes Analysis of AES S-box with Walsh Spectrum Practical Construction for Multicast Re-keying Schemes Using R-S Code and A-G Code Multisecret Sharing Immune Against Cheating Digital Semipublic Watermarking An Efficient Anonymous Fingerprinting Scheme An Anonymous Mobile Agents Scheme for Secure Web Transaction Over Internet Compiling and Using the US-ELAN Parallel Corpus On Formal Aspects of Zooming in Geographic Maps Parallel Aggregate-Join Query Processing Developing Software Across Time Zones: An Exploratory Empirical Study 245 Y. Mu, 249 V. Varadharajan H. Wu, F Bao, 255 R. H. Deng B. Wei, D. Liu, 259 X. Wang C.-Y. Bai, 263 R. Houston, G.-L.Feng J. Pieprzyk, 271 X.-M. Zhang V. Korzhik, 279 G. Morales-Luna, D. Marakov, I. Marakova Y. Li, B; Yang, 287 X.Hua C. Wang, Y Wang, 291 F. Zhang T.Erjavec 299 D. Frigioni, 309 L. Tarantino, T. DÌ Mascio D. Taniar, Y. Jiang, 321 K.H. Liu, C.H.C. Leung A. Taweel, 333 P. Brereton