Xavier Bultel

Jannik Dreier
email: jannik.dreier@loria.fr

Pascal Lafourcade

Malika More

How to Explain Modern Security Concepts to your Children *

At the main cryptography conference CRYPTO in 1989, Quisquater et al. published a paper showing how to explain the complex notion of zeroknowledge proof in a simpler way that children can understand. In the same line of work, we present simple and intuitive explanations of various modern security concepts and technologies, including symmetric encryption, public key encryption, homomorphic encryption, intruder models (CPA, CCA1, CCA2) and security properties (OW, IND, NM). The explanations given in this paper may also serve in demystifying such complex security notions for non-expert adults.

Motivation and Contributions

All the technical concepts and notions explained in this paper are well-known to cryptographers, and occur in most introductory courses for modern cryptography. The goal of this paper is to propose explanations and illustrations that can be used to explain these main modern security notions in a simple and understandable manner to non-experts of all sorts: children, students, adults without background in mathematics or computer science, and so on.

The paper is the result of more than ten years of teaching security courses at different levels from primary school to master courses at university. Over time, a set of helpful illustrations and examples for the various concepts have emerged, as well as a certain structure in the presentation. The paper follows this structure: We start with our illustrations for symmetric encryption and asymmetric or public key encryption (PKE). Then we give our illustrations of the different security levels that cryptographic systems can achieve, starting with the different intruders (CPA, CCA1 and CCA2), and followed by the different security properties One-Wayness (OW), Indistinguishability (IND), Non-Malleability (NM) and Key Anonymity (KA). We finish by giving intuitions for Homomorphic Encryption (HE), cryptographic hash functions, signatures and the Diffie-Hellman key exchange.

Related Work:

There is an international effort on the dissemination of computer science1 , in particular towards children. For instance, the authors of the Computer Science Unplugged group have elaborated several activities presenting various concepts of computer science. Among them, they provide several cryptographic activities like for instance the Peruvian Coin Flip, originally proposed in [START_REF] Fellows | Kid krypto[END_REF], where people who do not trust each other and cannot see each other are able to agree on the outcome of a random coin flip. They also propose a Kid Krypto public key encryption scheme that allows children to encrypt and decrypt messages without having to share a secret key, using a graph. Another activity, called Sharing Secrets and also introduced in [START_REF] Fellows | Kid krypto[END_REF], shows how to share personal information accurately without having to give up any privacy at all. In addition, the "Scout Patrol" activity presents a symmetric key encryption originally presented in [START_REF] Fellows | Kid krypto[END_REF]]. In the "CryptoClub" 2 after-school program, middlegrade students explore cryptography while applying mathematics to make and break secret codes. This program is supported by the University of Illinois at Chicago. Since 2010, the National Security Agency (NSA) also has its own pro-gram for kids3 . There are several other websites4 that offer secret messages to challenge kids. Purdue University5 proposes a web page that collects several resources for explaining cryptology to kids. Currently, the cryptographer Jacques Stern oversees a French nation-wide cryptanalysis competition for kids called Alkindi6 , which is the name of a famous Arabic mathematician that did the oldest known cryptanalysis.

Our work follows lines of Quisquater et al. [START_REF] Quisquater | How to explain zero-knowledge protocols to your children[END_REF] where the authors explain the concept of zero knowledge proofs. They use "the strange cave of Ali Baba" as an illustration. This circular cave has a door protected by a secret code. They show how, without revealing her code, Peggy the prover, can convince Victor, the verifier, that she knows the code. In [Beaver, 2009], the author proposes to introduce zero knowledge proofs in a classroom of undergraduate students setting using the cave example and also to study the Fiat-Shamir protocol [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF]. However the activity he proposes requires some advanced mathematical notions. In [START_REF] Gradwohl | Cryptographic and physical zero-knowledge proof systems for solutions of sudoku puzzles[END_REF] a simple sudoku zero knowledge proof using card games is presented. In [START_REF] Bultel | Physical zero-knowledge proofs for akari, kakuro, kenken and takuzu[END_REF], using cards and envelopes, four physical interactive zero knowledge proofs are proposed for four Japanese logic games: Akari, Kakuro, KenKen and Takuzu.

In [START_REF] Bell | Explaining cryptographic systems[END_REF] the authors propose to explain digital signatures, digital cash, on-line poker and secure voting to school children. In [Borovik, 2002], the author gives an implementation of activities proposed in Kid Krypto. More recently in his blog [Green, 2014], M. Green proposes an understandable explaination of the zero-knowledge concept. In [START_REF] Moran | Basing cryptographic protocols on tamper-evident seals[END_REF], the authors use sealed envelopes, locked boxes and scratch cards to construct secure oblivious transfer, bit-commitment and coin flipping. In [START_REF] Fellows | Combinatorially based cryptography for children (and adults). In Congressus Numerantium[END_REF] and [Koblitz, 1997], the authors use several combinatorial objects to explain cryptographic notions to children (and non-expert adults). Using high school mathematics and more complex mathematical notions, they present one-way functions, hash functions, signatures, public key cryptography (thanks to the "Peruvian coin flip" activity and to a cryptosystem based on a graph similar to Kid Krypto). In [START_REF] Naor | Applied kid cryptography or how to convince your children you are not cheating[END_REF], Naor et al. explain to kids how to convince people that you know "where is Waldo" without revealing any information about his position. These activities use simple material that kids can manipulate and help them to understand the challenges behind the construction of a secure primitive. In [START_REF] Caballero-Gil | A cryptological way of teaching mathematics[END_REF], the authors propose for secondary school activities to teach mathematics through cryptography. They present the Vigenère cipher to introduce the notion of functions, a knapsack cipher to introduce vectors, and to present randomness, proofs and equations. They use oblivious transfer, zero knowledge protocols, and the Shamir secret sharing threshold scheme. In [Phan, 2005], an attempt to explain block cipher cryptanalysis to kids is presented. In [START_REF] Forišek | Metaphors and analogies for teaching algorithms[END_REF], some metaphors and analogies for teaching some computer science algorithms are proposed. As it has been shown by A. Finkel in [START_REF] Arnoux | Using mental imagery processes for teaching and research in mathematics and computer science[END_REF], proposing mental representations helps students to learn abstract notions. One of our aims is to propose mental representations to help people understand modern security notions. Another goal is to enable children to understand how security works and to show them that mathematics is used to realize "fancy" modern technology. This paper also shows that security is not easy to obtain.

Outline:

In Section 2, we present our illustrations for the two main notions of encryption: symmetric and asymmetric encryption. Then, in Section 3, we explain our analogies for the security notions used for encryption schemes. We give our illustrations for homomorphic encryption in Section 4, followed by cryptographic hash functions in Section 5, signatures in Section 6 and the Diffie-Hellman key exchange in Section 7. In Section 8, we conclude our paper and present some perspectives.

Illustrating symmetric and asymmetric encryption

All encryption schemes invented before the Second World War are symmetric encryptions, which means that a secret key is shared between two persons, and this key is required to both encrypt and decrypt a message. Using advanced mathematics, R. Rivest, A. Shamir and L. Adelman were able to propose the first asymmetric or public key encryption scheme [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF]. In this case, the encryption and decryption stages are not symmetric, and do not use the same key. The encryption key is public, and can be used by anybody, whereas the decryption key is secret, known only to the recipient of the encrypted messages. This conceptual revolution allows anybody to use the public key of Alice to send encrypted data to her, that only she is able to decrypt using her private key.

Symmetric Key Encryption Schemes

To illustrate symmetric key encryption, we use the following analogy based on a lockable chest and keys as shown in Figure 1.

Illustration 1 (Symmetric Encryption). If Alice and Bob have the same key that opens the chest, then they can exchange secret letters. Alice puts her secret letter, called a plaintext, in the chest and closes it with her key. This is called a cipher. Then she sends it to Bob. Since Bob has the same key as Alice, he can open the chest and get the letter. This is the principle of symmetric encryption: a symmetric encryption uses the same key to encrypt and to decrypt a message. This key is called a symmetric key.

encryption decryption

Figure 1: Symmetric encryption.

To illustrate how padlocks and keys can be constructed in the digital world of computers, a simple example we often use is the Caesar Cipher, where each letter is shifted three letters to the right in the alphabet. In this case the symmetric key used is 3, and the set of possible keys is {1, . . . , 25}.

The Caesar cipher can also be used to illustrate weaknesses and attacks, as a build-up towards the security definitions explained below: often students see directly that such encryption scheme can be broken by testing all possible shifts, which consists in trying only 25 possibilities. This introduces the notion of bruteforce attacks, and illustrates the necessity for a large key space. Since here there are only 25 possibilities, the exhaustive search always succeeds.

Sometimes they also notice that, in English or any other language, some letters are more frequently used than others. Then, by counting the most frequent letters in the ciphertext, provided that it is long enough, it is possible to reduce the number of possibilities to try (the so-called frequency analysis).

To show that not all encryption schemes are vulnerable to attacks such as frequency analysis, a useful example is the One Time Pad Encryption (OTP) (also known as Vernam encryption because it is generally credited to Gilbert S. Vernam and Joseph O. Mauborgne in 1917, but it has been shown in [Bellovin, 2011] that it was actually invented 35 years earlier by Frank Miller). This encryption scheme is perfectly secure, i.e., according to Shanon's information theory, without knowing the key no information about the message is leaked [Vaudenay, 2005, Baigneres et al., 2010]. In this scheme, the encryption of the binary message m with the binary key k is m ⊕ k, where ⊕ is the exclusive-or operator (in other words a bit-wise addition modulo 2), which means that the size of the key k is the same as the size of the message m, which requires to have a large shared secret. For instance, if the message m = 010111 is encrypted with the key k = 10010, then the ciphertext is c = 100101 = m ⊕ k. The decryption consists in computing c ⊕ k = m using the same key k. To allow kids to encrypt messages using this scheme, it is possible to use the OTP principle with normal letters from the alphabet and an addition modulo 26 instead of a binary representation.

Moreover, key re-usage can have dramatic consequences on the security of the communication, as the following 3-pass Shamir protocol illustrates. It aims at exchanging a secret message m without sharing a key beforehand. Formally the protocol is composed of three messages, where {m} k A denotes the encryption of m with the secret key k A of Alice:

1. A → B : {m} k A 2. B → A : {{m} k A } k B 3. A → B : {m} k B
Note that this protocol works only if the encryption has the following algebraic property, called key commutativity: Illustration 2. With kids, this protocol can be realized using a real box (with two places for padlocks), two padlocks, and regular mail, as described in Figure 2 and first proposed in [START_REF] Shamir | Mental poker[END_REF]. The kids have to find a secure way for Alice to exchange a secret message with Bob, without sharing a key. The solution consists in the following protocol: Alice puts her padlock on a box containing the secret message and sends it to Bob. Then Bob adds his own padlock on the box and sends it back to Alice. Now Alice removes her padlock and sends to Bob the box that only has the Bob padlock. Finally Bob removes his padlock and opens the box to discover the secret message.

{{m} k A } k B = {{m} k B } k A .
This simple protocol can be used to illustrate protocol attacks, as there is for example a reflection attack. Suppose an intruder intercepts the first message and simply sends it back to Alice. Then Alice removes her key and sends the plaintext message m to the intruder. This is due to the lack of authentication in this protocol. It is also possible to mount a man-in-the middle attack, where that intruder first plays a full session with Alice and learns the message m. Then he does a second full session with Bob to let him know the message m. In that case Bob could believe that only he and Alice know m, but the intruder also knows it.

Using OTP with this protocol can be used to create an interesting exercise. For this, we need to consider the four algebraic properties of the exclusive-or operator: (x⊕y)⊕z = x⊕(y⊕z) (Associativity), x⊕y = y⊕z (Commutativity), x⊕0 = x (Unit element), and x ⊕ x = 0 (Nilpotency). The goal of the exercise is to ask the students to discover the message m just by listening to the three messages of the protocol. Note that the One Time Pad (OTP) encryption is commutative since:

{{m} k A } k B = (m ⊕ k A ) ⊕ k B = (m ⊕ k B ) ⊕ k A = {{m} k B } k A
and could thus be used here. To help them, it is possible to recall that the intruder collects the following three messages during the execution of the protocol:

m⊕k A ; (m ⊕ k A ) ⊕ k B ; m ⊕ k B .
Then they might discover that the intruder can learn m just by performing the exclusive-or of these three messages, since

m = m ⊕ k A ⊕ (m ⊕ k A ) ⊕ k B ⊕ m ⊕ k B .
The box analogy reflects the fact that the encryption is secure and key commutative, however this analogy does not take into account some algebraic properties of the encryption scheme that might lead to some even simpler attacks.

Public Key Encryption Schemes

We first explain the notion of Public Key Encryption (PKE), then we discuss how to present the RSA and ElGamal encryption schemes as examples.

Illustration 3 (Public-Key Encryption). The principle of a public key encryption scheme is that everyone can get the encryption key of somebody. These keys are often published on web page of their owner and/or stored in some public key storage like for instance the MIT PGP Public Key Server7 . These encryption keys can be seen as open padlocks that are distributed without the associated keys, as shown in Figure 3, and proposed in [Beutelspacher, 1994]. Using these padlocks, called public keys, everyone can encrypt a message but only the owner of the corresponding decryption key (so-called secret key) can open the padlock and recover the plaintext. The public key encryption schemes are also called asymmetric encryption schemes by opposition to the symmetric encryption schemes since they use a public key for encryption and a secret key for decryption.

The notion of trapdoor one-way function is the main concept of public key cryptosytems. A one-way function is a function that is easy to compute but which In this situation, it is easy to find the phone number knowing the name of a person, but it is quite difficult to recover the name of the owner of a phone number knowing only this information8 . A trapdoor one-way function is a one-way function such that knowing some additional information, the trapdoor, the inverse becomes easy to compute. The trapdoor for the phone book example could be a reverse phone directory, which is easy to compile for the person who created the original directory. In public key cryptography the trapdoor corresponds to the secret key which is difficult to find, given only the public information. This secret key allows his owner to decrypt encrypted messages computed using the public encryption function.

The concept of public-key encryption schemes can be illustrated both using the RSA and ElGamal schemes.

Kid Krypto Encryption Scheme. Most real life public key encryption systems use somehow sophisiticated mathematics that are not suitable for kids before high school. The Kid Krypto activity uses only elementary school mathematics and was proposed in [START_REF] Fellows | Kid krypto[END_REF] and used by the Computer Science Unplugged group9 . Despite its security flaw, it can be used in the classroom.

It relies on the difficult (i.e. NP-complete) graph problem called Minimum Dominating Set. A dominating set of a simple graph is a subset of vertices such that any vertex of the graph is either in the subset or adjacent to a vertex in the subset, as it shown in Figure 4. Since the set of all vertices is obviously a dominating set, the question is to find a dominating set containing as few vertices as possible.

As a first step, students have to be convinced that it is actually difficult to find a minimum dominating set on a graph by working out several examples. The Let us now explain how to encrypt and decrypt a number using this graph as a public key, as it shown in Figure 6. Note that this does not work for every graph with a minimum dominating set, but only for "Perfect Code" graph as defined by Fellows and Koblitz in [START_REF] Fellows | Kid krypto[END_REF]. The private key is the minimum dominating set. Encrypting a number is done in two steps. First, the number is randomly decomposed into a sum of numbers and spread over the vertices of the graph, so that the values of all vertices add up to the initial value. Then, the If encrypting and decrypting might be somehow tedious, however this activity requires only few mathematical skills. Finally, note that this scheme is not actually secure, because the encrypting step can be described using linear equations, that are easily (i.e. polynomially) solved, using for instance Gaussian elimination.

RSA Encryption Scheme. In 1978, Ron Rivest, Adi Shamir and Leonard Adleman [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF] designed the first public key encryption scheme called RSA for Rivest, Shamir, Adelman. Their encryption scheme relies on the computationally hard problem of factorization: given n, the product of two primes numbers p and q, we do not know up to now any efficient algorithm to recover p and q, whereas it is easy to compute n from p and q. The public key is composed of e and n, where e is an integer that is coprime to (p -1) • (q -1) and n is the product of the two primes p and q. The secret key is d, the inverse of e modulo (p -1) • (q -1). The encryption of the message m is m e mod n and the decryption of the ciphertext c is c d mod n. The correctness of this encryption scheme relies on the little Fermat's theorem. Although the underlying theory is complex, children can easily execute the encryption and decryption using small numbers and pocket calculators or even online resources like Sage10 or Wolfram Alpha11 , as there are only simple operations such as multiplication, exponentiation and modulo. Moreover one can convince them that factorization is difficult for large numbers by giving an example of a large number and asking them to find the factors.

Moreover, RSA can be used to illustrate the difference between deterministic and randomized encryptions. It is easy to see that RSA is deterministic, which means that the encryption of a message m with a given public key always produces the same ciphertext. To illustrate that this can be a problem, one can sketch a very simple voting protocol where voters encrypt either "yes" or "no" using the public key of a voting authority: if the encryption is deterministic, it is easy to find out how each voter voted by simply encrypting "yes" and "no" and comparing the result to the voter's submissions.

ElGamal Encryption Scheme. This encryption scheme was invented by T. El-Gamal in 1985[ElGamal, 1985]. It is a randomized encryption, which means that each encryption of a given message m, using a given public key, produces a different ciphertext. This encryption scheme relies on the hard problem called discrete logarithm: knowing g, g a mod p and p it is difficult to find a but it is easy from g, a and p to compute g a mod p. The public key is composed of g, p and h such that p is prime, and h = g a mod p. The secret key is a. The encryption of a message m is the couple (g r mod p, h r • m mod p), where r is a random number. The decryption of a ciphertext c = (c 1 , c 2 ) consists in computing c 2 /c a 1 mod p. ElGamal has the advantage of relying on relatively simple math, so that for example high school students can verify the correctness of the decryption.

Moreover, it is easy to see for non-experts that in RSA and Elgamal encryption schemes, the security level depends on the length of the key: one can for example ask them to factorize a small number, and use this to break RSA by decrypting a message without using the secret key. Note that there are several other public key encryption schemes that have been proposed, based on different techniques and different computationally hard problems [Schneier, 1996].

Introducing Encryption Secheme Security Levels

At this point, the children have some intuition on how different schemes work and know some classical attacks. Moreover they have seen that some schemes might be secure in some contexts but insecure in others, and that the choice of parameters is important. This allows us to motivate the necessity for precise security definitions to evaluate the security level of encryption schemes. For this, one has to define the intruders abilities and the security properties. We start by presenting the various intruders and then the different properties. Many relationships between these notions have been established in [START_REF] Bellare | Relations among notions of security for public-key encryption schemes[END_REF]]. Moreover similar results exist for symmetric encryption schemes [START_REF] Bellare | A concrete security treatment of symmetric encryption[END_REF].

Illustrating Intruders

We now present the main intruders against which encryption schemes should try to resist. We start with a basic intruder and then increase its capabilities up to a powerfull intruder.

Basic Attacker (BA)

Illustration 4 (Basic Attacker (BA)). Such attacker that tries to recover the plaintext given only a ciphertext (produced either by a symmetric or assymmetric encryption scheme), called challenge. This is illustrated in Figure 7: on the right we have the intruder, and the challenge is pictured as the locked box on the left. Having an encryption scheme that resists to such an intruder is the minimum security expected from an encryption scheme. In 1984, M. Miccali and S. Goldwasser proposed a more realistic intruder and considered a more powerful security model. In 2014, they received the Turing Prize for their work about the notion of Chosen Plaintext Attacks defined in [START_REF] Goldwasser | Probabilistic encryption[END_REF]. Later on, even more powerful intruders were introduced [Naor andYung, 1990, Rackoff and[START_REF] Rackoff | [END_REF]. Our aim is to present these intruders in an intuitive way. To illustrate the intruders the examples given in Section 3.2 can be used.

Chosen Plaintext Attack (CPA)

The idea is very simple: when studying the security of an encryption, knowing several pairs of plaintexts and ciphertexts can help to break the encryption. A famous example is how A. Turing and his team broke the ENIGMA machine during the second World War.

Illustration 5 (Chosen Plaintext Attack (CPA)). This notion is illustrated in Figure 8 as follows. On the left, we have the intruder before receiving the challenge, and on the right the intruder after receiving the challenge (as above, the challenged is pictured as the locked box). In the case of chosen plaintext attacks, before and after receiving the challenge, he can encrypt some messages, pictured as an open padlock inside a crystal ball. In cryptography, these "crystal balls" that allow the adversary to access certain values or to perform certain operations are called oracles.

Note that such an intruder is more powerful than an intruder that only knows the challenge, i.e., only one ciphertext: in the example of the voting system using RSA encryption given above the attacker could "break" the secrecy of the votes by simply encrypting all possible votes. Thus having a cryptosystem that resists to a CPA intruder is more secure than only resisting to the basic attacker that only knows the challenge, and cannot encrypt values of his choice.

Non-Adaptive Chosen Ciphertext Attack (CCA1)

Illustration 6 (Non-Adaptive Chosen Ciphertext Attack (CCA1)). In 1990, M. Naor and M. Yung [START_REF] Naor | Public-key cryptosystems provably secure against chosen ciphertext attacks[END_REF]] introduced an even more powerful attack model, also known as the "Lunchtime Attack". They consider a scenario where an employee has secret keys on his computer, which he uses to receive encrypted messages. Anyone having access to his computer is able to decrypt all previously received messages, assuming that the computer stores the secret key. Now suppose that the employee goes for lunch but forgets to lock his computer: an attacker can access it during a limited period of time. In particular, he can open all previously received encrypted messages, and decrypt other messages of his choice. After lunchtime, the adversary locks the employee's computer in order not to raise any suspicion.

Then the adversary tries to decrypt the next message received by the employee. In other words, the new adversary model consists in an adversary who can encrypt messages and additionally has access to a decryption oracle, i.e., a functionality that allows him to decrypt a ciphertext of his choice, multiple times before he gets the challenge. This intruder is known as CCA1 for Non-Adaptive Chosen Ciphertext Attack, and illustrated in Figure 9: the key inside the leftmost crystal ball represents the possibility to decrypt, to which he only has access before receiving the challenge.

Adaptive Chosen Ciphertext Attack (CCA2)

Illustration 7 (Adaptive Chosen Ciphertext Attack (CCA2)). In 1993, C. Rackoff and D. Simon [START_REF] Rackoff | Cryptographic defense against traffic analysis[END_REF] imagined an even more powerful adversary. This adversary can encrypt messages, and has access to a decryption oracle multiple times before and AFTER he gets the challenge, but of course he cannot decrypt the challenge. This adversary is known as the Adaptive Chosen Ciphertext Attack, or "CCA2" for short, and illustrated in Figure 10. Formally modeling all these notions requires the use of Probabilistic Polynomial Time Turing machines (PPTs) and security games that exceed the abilities of our young target audience. However, as we showed it is possible to present the different types of intruders and to describe the differences between them.

Security Notions

We now present some security notions that have been introduced simultaneously with the adversary models presented before, where each security notion corresponds to one of the adversaries explained above. For this purpose, we developed a metaphor using different types of containers to model the security properties of cryptographic primitives. In [START_REF] Bellare | Relations among notions of security for public-key encryption schemes[END_REF]], Bellare et al. formally established the relationships between these security notions and the above intruder types.

One-Wayness

Illustration 8 (One-Wayness (OW)). The first security notion is called One-Wayness (OW). For an adversary, given a ciphertext, it should be difficult to recover the plaintext in a reasonable amount of time without knowing the associated decryption key. We represent this kind of encryption as a translucent plastic bag (it is not possible to read the message) that is closed with a padlock (representing the one-way encryption) and contains the secret message.

A one-way encryption scheme is secure against the basic attacker as his only possibility is to directly try to decrypt the message, but it is not secure against stronger adversaries as explained below.

Indistinguishability

An encryption scheme is said to have the Indistinguishability (IND) property if an intruder that knows two different plaintext messages having the same size and a challenge, which is the encryption of one of the two messages, cannot determine which one is encrypted in the challenge. In [START_REF] Goldwasser | Probabilistic encryption[END_REF], the authors introduced this notion. We start by showing that a one-way encryption primitive can leak some information in some situations (see Figure 12). We have two messages: one is written on a gray paper and the second one is written on a white paper. These two messages plus one challenge (the translucent plastic bag) that contains one of the two previous messages, are given to the adversary. Is it possible for the adversary to determine which message has been encrypted in the challenge?12 Usually kids have the intuition that since the bag is translucent it might be possible to determine the color of the message inside, if not to read the plaintext itself. Asking the kids how to prevent such an attack, they naturally propose to put the message in a black bag (see Figure 13). Continuing our metaphor, this image represents the notion of indistinguishability. Some students are able to describe the following indistinguishability attack with a CPA intruder on a one-way public-key encryption scheme: encrypt with the public key one of the two messages and compare the result with the challenge, if they are equal you know which one has been encrypted, otherwise it is the other message that is inside the challenge. This attack is general and works for all deterministic encryption schemes, like for instance RSA as noted above.

In Figure 14, we show the encryption of a padlock image using the symmetric encryption AES, first using Electonic Code Book encryption mode, and in the second image using Cipher Block Chaining encryption mode. The ECB mode is only one-way while the CBC mode is IND-CPA. This example is often convincing that the translucent bag is a good representation of the notion of OW.

Non-Malleability

An encryption scheme is said to have the Non-Malleability (NM) property if an intruder that knows a ciphertext (the challenge) cannot construct other valid ciphertexts for which he knows a relation between the corresponding plaintexts and the plaintext encrypted in the challenge.

Illustration 10 (Non-Malleability (NM)). We illustrate his property by describing an attack on a scheme that does not have the NM property. If we consider a CCA2 intruder, then the black plastic bag is not safe. In order to help students to discover the corresponding attack, we propose a situation where the message is written on a Rubik's Cube and placed in a black plastic bag.

If the students remember correctly the capabilities of a CCA2 intruder, they are able to propose the following attack: turn the Rubik's Cube to modify the challenge and give the new ciphertext to the decryption oracle. The oracle decrypts the modified message and gives it back to the intruder i.e., the oracle opens the bag. He just has to turn back the cube to recover the plaintext corresponding to the challenge. In order to prevent such attack, a more secure encryption can be represented as a rigid back box.

Such a rigid black box illustrates the notion of non-malleability. In other words it is not possible for the intruder to modify the challenge to obtain a valid ciphertext that has a pre-established relationship with the plaintext encrypted in the challenge. This notion has been formally introduced by [START_REF] Dolev | Nonmalleable cryptography[END_REF][START_REF] Dolev | Nonmalleable cryptography[END_REF].

Key Privacy

The previous security properties focus on the security of the messages, but in 2001, cryptographers also introduced a property concerning the security of the key used in a cryptosystem [START_REF] Bellare | Key-Privacy in Public-Key Encryption[END_REF]. The idea is similar to the indistinguishability of the message, only that this time it concerns the key. The adversary selects a message m, and a pair of public keys. The challenge is composed of the message m encrypted with one of the two keys. The goal for the intruder is to determine which key has been used.

Illustration 11 (Key Privacy). Using an ordinary padlock and looking at the shape of the key hole, one can probably determine which key has been used. Note that the original message is part of the challenge. Such an encryption scheme does not preserve the key privacy. Figure 18 presents a digital padlock for which it is not possible to distinguish which digital key has been used to encrypt the challenge: such an encryption has the key privacy property.

Explaining Homomorphic Encryption

In 2009, G. Gentry [Gentry, 2009] solved a long standing open problem introduced by Rivest et al. [Rivest et al., 1978a] that asks for the capability to perform any operation on encrypted data without decrypting the data. Encryption schemes with this property are extremely useful in the cloud applications. Before 2009, several partial solutions called partial homomorphic encryption schemes have been proposed, like for instance [ElGamal, 1985, Naccache and Stern, 1998, Paillier, 1999, Fousse et al., 2011, Goldwasser and Micali, 1984].

Illustration 12 (Homomorphic Encryption). G. Gentry presented the problem of the homomorphic encryption in [Gentry, 2010] as follows: Alice has a raw diamond and some gold. She wants a jeweler to make for her a nice ring, but she is afraid that her precious stone is stolen by the jeweler. For this reason, she needs to put the stone in a safe place. Since she also wants the jeweler to work on the stone, she should ask him to use a secure glove box as presented in Figure 19. In other words, the jeweler should be able to apply any function f on the ciphertext (i.e., from outside the safe) and the effect of f appears on the plaintext (inside the safe). More formally, the fully homomorphic property is the following, where m 1 , . . . m p are messages, k the key and f the function applied outside the encrypted messages and g the function applied inside the encrypted messages:

f ({m 1 } k , . . . , {m p } k ) = {g(m 1 , . . . , m p )} k
Partial homomorphic encryption schemes only allow to perform one operation, like for instance Elgamal [ElGamal, 1985] or RSA [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF], and are a good first example. For instance for RSA, the product of two encrypted messages c 1 = m e 1 mod n and c 2 = m e 2 mod n is equal to (m 1 • m 2 ) e mod n which is the encryption of the product of the two plaintexts m 1 and m 2 .

Moreover, there is a fully homomorphic encryption scheme which does not use sophisticated mathematics: the DGHV encryption scheme [van Dijk et al., 2010]. It only uses modular multiplication and addition and works as follows. The secret key is p, an odd number in [2 η-1 , 2 η [, where η is the so-called security parameter, which evaluates the security of the scheme. The plaintext is a bit m ∈ {0, 1} and the encryption of m is given by:

c = q • p + 2 • r + m
where q is a large random number (q ≈ η 3 ) and r a small random number (r ≈ 2 √ η ), such that 2 • r ≥ p/2.

For decrypting the ciphertext c, knowing the secret key p, it suffices to perform the two following modulo operations on c: m = (c mod p) mod 2 This encryption scheme is somewhat13 fully homomorphic for addition and multiplication (verifying this is a feasible exercise for high school students), hence for all boolean function f . The advantage of this symmetric encryption scheme is that it is simple enough to allow us to explain how to store encrypted data in the cloud. Note that it is possible to modify this scheme to encrypt messages longer than one bit.

Explaining Cryptographic Hash Functions

Cryptographic hash functions are mathematical functions that take as input any bitstring and output a digest of a fixed size, H : {0, 1} * → {0, 1} n . Their desired properties are pre-image resistance, second-pre-image resistance and collision resistance [START_REF] Rogaway | Cryptographic hash-function basics: Definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance[END_REF], which are explained below. These cryptographic primitives tend to be complex to design. Famous examples include MD5, SHA-1, SHA-256 or SHA-3.

Illustration 13 (Cryptographic Hash Function). A cryptographic hash function can been explain using the analogy of fingerprints for humans as shown in Figure 20. Kids can play with ink and fingers, and discover that any object (human) can be reduced to a constant size representation, since each human can be characterized by his fingerprints. Following this representation of hash functions, the desired properties for cryptography can be illustrated as in Figure 21.

Pre-image Resistance: For the fingerprint, given a human, it is easy to obtain his fingerprint, but from a fingerprint it is difficult to recover the corresponding human. This property is close to the one-wayness property for encryption function. More formally given a hash value h it should be difficult to compute a message m such that h = hash(m).

In real life the police have a collection of identities and corresponding fingerprints of most of the criminals. By comparing one fingerprint with this collection it is then possible to identify a suspect. To the same goal, cryptographers have invented the so called "rainbow table" that corresponds to an efficient data stucture that contains the list of precomputed hash values of some messages.

Second Pre-image Resistance: The idea of this property is that given a human it should be difficult to find another one that has the same fingerprint. More formally, given a input message m it should be difficult to find a different input m such that hash(m) = hash(m ).

For instance, the hash function that gives the color of the eyes of a person is pre-image resistant, but not second pre-image resistant, because it is not difficult to find another person with the same color of the eye in the population, because there is a small number of eye colors.

Collision Resistance: A collision pair is two different humans having the same fingerprint. If it is difficult to find two different messages that have the same hash value, then the hash function is called collision resistant. Fingerprints have this property: even true twins do not have the same fingerprint, although they share the same DNA.

Today hash functions are for example used to check the integrity of a received message. For instance when a software S is downloaded from a server, and d is the digest of this file, i.e., d = H(S), the user can check the integrity of the received file S by checking that d is equal to H(S ). If somebody wanted to modify the file by for example including a virus, he would need to find a second pre-image for the given hash value. Moreover, in cryptography, hash functions are also used to reduce the size of some data or to generate random values such as in the Fiat-Shamir heuristic [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF].

Illustrating (Blind) Signatures

Another important primitive in security is the ability to sign documents.

Illustration 14 (Signature). A signature attests that you are the author of the document, i.e., the person who has generated it. In real life, this has been used for ages: for instance kings, emperors and presidents all have unfalsifiable seals, as shown in Figure 22. Beutelspacher [Beutelspacher, 1994] proposed a similar illustration using an asymmetric bolt. These objects are assumed to be difficult to copy, in other words it is difficult to forge a signature of somebody else.

Following the invention of public key encryption, researchers proposed various ways of signing electronic documents. The key principle is illustrated in Figure 23: a secret signature key plays the role of a seal. Then, given a signed Using potatoes and ink, kids can make their own seal and "sign" messages they exchange using envelopes. For high school students, one can present RSA signatures [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF] or Elgamal signatures [ElGamal, 1985].

RSA signatures [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF] can also be used as blind signatures. The idea of a blind signature is to be able to sign an encrypted message, and then remove the encryption to obtain a signature on the plaintext message. This is for example used in electronic elections: before voting, each voter asks the authority to verify that they are registered, and to sign their encrypted (in order to preserve the secret of the vote) ballot. Then the voter decrypts the message, and obtains a ballot of his choice, signed by the authority. The voter uses this signed ballot to vote during the election, where the signature proves that he is registered and has the right to vote.

Illustration 15 (Blind Signature). As proposed in [Chaum, 1985], blind signatures can be illustrated as in Figure 24: a voter sends an envelope (representing the encryption) that contains his ballot and a sheet of carbon paper. Then the authority signs the envelope on the outside, either using a pen or using his seal, and the voter can open the envelope to obtain the signature on his initial ballot. This protocol can easily be realized with kids, one only needs some standard office material.

7 Illustrating the Diffie-Hellman (DH) Key Exchange with Colors

In 1976, W. Diffie and M. Hellman [START_REF] Diffie | New directions in cryptography[END_REF] proposed the first protocol of key exchange. This protocol allows Alice and Bob to establish a shared secret key using a so-called one-way function.

Like the ElGamal encryption, the Diffie-Hellman (DH) key exchange protocol relies on the discrete logarithm problem and works as follows. Alice and Bob know a public number g, where g is a public generator of a multiplicative cyclic group. Alice picks a secret random number a and Bob picks a secret random number b. Alice sends to Bob g a then Bob replies g b . Finally, Alice computes the shared key (g b ) a and Bob can also compute it as (g a ) b .

Illustration 16 (Diffie-Hellman Key Exchange). The Diffie-Hellman protocol can be illustrated using colors as follows14 . The illustration, first proposed by Simon Singh [Singh, 1999], relies on two properties of colors:

• It is easy to mix two colors, for instance mixing yellow and blue gives green.

• Given a color that was obtained by mixing two colors, it is difficult to "separate" the color and obtain the initial colors.

For the colored version of the Diffie-Hellman protocol we assume that the color yellow • is a public color, known by everybody. We also assume that the secret color of Alice is the color blue • and that the secret color of Bob is the color red •. Alice and Bob want to agree on a new shared secret color. For this they follow the protocol described in Figure 25, where the name of the white rabbit is Bob. In the first step, Alice sends the color green • to Bob, which is the result of the public color • mixed with her secret color •. Then Bob sends the color orange • to Alice, which is the result of the public color • mixed with his secret color •. Now they both know a common shared secret color brown • that is computed as follows by Alice and Bob:

• • • + • = • • + • = • • + • + • = •
• Alice mixes the received orange color • with her secret blue color •.

• Bob mixes the received green color • with his secret red color •.

This protocol can be executed with kids using some transparent paper and colored pens, or even with paint as it is shown in the video. Everyone selects his own color and draws a circle on a transparent paper with their public color and the secret color. Then they can exchange the transparent papers, then they just have to use another secret transparent paper that only contains their secret color to obtain the secret shared color. In practice this protocol might sometimes be difficult to set up, in that case using a drawing software such as GIMP15 can be a good alternative to convince the students.

Conclusion

In this paper we proposed child-friendly illustrations of basic modern security concepts that are used in many of the secure electronic devices used by kids today. In the spirit of previous work, we proposed illustrations and analogies that can be used to explain complex security notions to children and non-experts.

As future work, we would like to find similar illustrations for more complex notions like identity based encryption, broadcast encryption, proxy re-encryption or even post-quantum cryptography like lattice based encryption.

Figure 2

 2 Figure 2: 3-pass Shamir protocol.

Figure 3 :

 3 Figure 3: Asymmetric encryption scheme

Figure 4 :

 4 Figure 4: Dominating Set

Figure 6 :

 6 Figure 6: Encryption and Decryption

Figure 7 :

 7 Figure 7: Basic adversary.

Figure 8 :

 8 Figure 8: CPA adversary.

Figure 9 :

 9 Figure 9: CCA1 adversary.

Figure 10 :

 10 Figure 10: CCA2 adversary.

Figure 11 :

 11 Figure 11: Representation of the One-Way property.

  Illustration 9 (Indistinguishability (IND)).

Figure 12 :

 12 Figure 12: IND-CPA attack on OW encryption.

Figure 13 :

 13 Figure 13: Representation of indistinguishability property.

Figure 14 :

 14 Figure 14: Encryption with a OW-CPA encryption and an IND-CPA secure encryption.

Figure 15 :

 15 Figure 15: Attack against IND-CCA2.

Figure 16 :

 16 Figure 16: Representation of Non-Malleability property.

Figure 17 :

 17 Figure 17: Attack on Key Privacy property.

Figure 18 :

 18 Figure 18: Key Privacy property.

Figure 19 :

 19 Figure 19: Glove box.

Figure 20 :

 20 Figure 20: Representation of an hash function, as a deterministic procedure that takes a human as input and produces his fingerprint as a digest.

•

  Figure 21: Properties of hash functions.

Figure 22 :

 22 Figure 22: Seal

Figure 24 :

 24 Figure 24: Blind Signature.

Figure 25 :

 25 Figure 25: Diffie-Hellman protocol with colors.

http://csunplugged.org

http://www.cryptoclub.org/

https://www.nsa.gov/kids

http://www.thunk.com

http://www.cerias.purdue.edu/education/k-12/teaching_ resources/lessons_presentations/cryptology.html

http://www.concours-alkindi.fr/

https://pgp.mit.edu/

The phone book example is generally attributed to Silvio Micali[Khovanova, 2010] and Arto Salomaa[Bauer, 1997].

http://csunplugged.org

http://www.sagemath.org

https://www.wolframalpha.com/

As we have seen for the vote example with CPA adversary, an encryption that is used in a vote system should have the indistinguishability property in order to avoid that an adversary determines the vote of each voter.

Technically it is not fully homomorphic as errors build up over time unless we introduce a bootstrapping.

The following videos show how this protocol works https://www.youtube.com/ watch?v=U1kybvKaUeQ or https://www.youtube.com/watch?v=3QnD2c4Xovk

https://www.gimp.org/

* This work was partially supported by Digital trust Chair from the University of Auvergne Foundation.


Gérald Oster
email: oster@loria.fr

Hala Skaf-Molli

Pascal Molli
email: molli@loria.fr

Hala Naja-Jazzar

SUPPORTING COLLABORATIVE WRITING OF XML DOCUMENTS

Keywords: CSCW, Collaborative Writing, XML, Change Control

Synchronisation of replicated shared data is a key issue in collaborative writing systems. Most existing synchronization tools are specific to a particular type of shared data, i.e. text files, calendars, XML files. Therefore, users must use different tools to maintain their different copies up-to-date. In this paper we propose a generic synchronization framework based on the operational transformation approach that supports synchronisation of text files, calendars, XML files by using the same tool. We present how our framework is used to support cooperative writing of XML documents. An implementation is illustrated through the revision control system called So6, which is part of a distributed collaborative technology called LibreSource.

INTRODUCTION

Cooperative writing is becoming increasingly common, often compulsory in academic and corporate work. Even the World Wide Web or simply the Web becomes a global read-write information space where multiple authors are interacting in contrast to the traditional model of one author publishing to many readers. People involved in cooperative writing can work across space, time and different organisations. In spite of this need for collaboration, it is surprising to see how poorly computer systems support group activities. Very often, people just send the shared document by mail and use a turn taking strategy to avoid conflicting updates. This is a serious bottleneck for productive work since people cannot work in parallel. Therefore, our initial requirements is that a good cooperative editor should allow anyone to write any shared data at any time. Cooperative environments such as Wikis or version control systems such as CVS and Subversion are popular alternatives to the mail approach.

Wiki system is a cooperative writing environment that allows anyone to write at any time the shared documents. However, it restricts editing to a certain type of shared documents, i.e. Wiki pages. A special markup language that offers a simplified alternative to HTML is used for editing Wiki pages. In case of concurrent modifications, Wikis generally apply the last writer wins rule. Consequently, modifications done by some users may not appear in the last visible page. This is a kind of lost updates.

Our requirements to improve the functionality of cooperative editors can be refined as: a good cooperative editor should allow anyone to write any shared data at any time without lost updates.

The existing version control systems such as CVS [START_REF] Berliner | CVS II: Parallelizing Software Development[END_REF]) avoid lost updates. However, CVS was originally designed to support cooperative software development. Only text files containing code sources such as C file and Java files are considered for merging. In this context, when conflicting changes are performed, conflicts appear inside merged files. A special syntax is used to clearly help programmers to locate the problem. Other shared data types are considered as binary files and concurrent changes on this type of data are not merged. Consequently, CVS allows anyone to write any text files at any time without lost updates.

We want to build a cooperative editor that allows anyone to write any kind of data, not only text files, but also XML files, CAD files, calendar files at any time without lost updates. A generic synchronizer that enables to merge any data type without lost up-date is required. We propose to build a generic and safe synchronisation framework. This framework allows to synchronise text files, calendars, XML files by using the same tool while ensuring that conflict resolution will not introduce lost updates.

In previous work, we described how the operational Transformation approach (OT) was used as a theoretical foundation to build such a generic and safe synchronizer [START_REF] Molli | Using the Transformational Approach to Build a Safe and Generic Data Synchronizer[END_REF]. We defined also the specific transformation functions to synchronise linear structure such as text files.

This paper will focus on the transformation functions for XML data and their implementation in an open source collaborative technology called Libre-Source. Our final objective is to build a library for merging blocks of text, strings, trees, graphs. Anyone can use these functions, add new functions or modify existing ones according to their needs.

The paper is structured as follows. Section 2 introduces the operational transformation approach which serves as a theoretical foundation for our generic synchronisation framework called So6. Section 3 presents the architecture and the algorithms used in So6. Section 4 defines the XML transformation functions and demonstrates the use of these functions through an example. Section 5 discusses related work. Section 6 concludes and points out some future work.

BACKGROUND

This section describes the Operational Transformation approach (OT) that is the theoretical foundation of the generic and safe synchroniser So6. OT [START_REF] Ellis | Concurrency Control in Groupware Systems[END_REF] is an optimistic replication model used in real-time group editors domain. OT considers n sites, each site owns a copy of shared data. When a site performs an update, it generates a corresponding operation, which is first executed locally and then broadcasted to other sites. Every operation is processed in four steps: (a) generated on one site, (b) broadcasted to other sites, (c) received by other sites, (d) executed on other sites.

The execution context of a received operation op i may be different from its generation context. In this case, the integration of op i by other sites may lead to inconsistencies between replicas. For instance, we consider two sites site 1 and site 2 working on a shared data of type string of characters initially equal to the string "efect". A string of characters can be modified with the operation ins(p,c) for inserting a character c at position p in the string. We assume the position of the first character in a string is 0. user 1 and user 2 generate and execute two concurrent operations op 1 =ins(2,f) and op 2 =ins(5,s), respectively. When op 1 is received and executed on site 2 , it produces the expected string "effects". But, when op 2 is received on site 1 , since it does not take into account that op 1 has been executed before it, its execution leads to the state "effecst". Finally, the copies of site 1 and site 2 do not converge.

In the operational transformation (OT) approach, before being executed, received operations are transformed regarding concurrent operations that were already executed on the local copy. This transformation is performed by calling transformation functions.

Definition A transformation function T takes two concurrent operations, op 1 and op 2 , must be defined on a same state S. The function computes a new operation op ′ 1 equivalent to op 1 -i.e. has the same effects -but defined on the state S ′ = S ⊙ op 2 . S ′ is the state resulting from the execution of op 2 on state S.

Using OT approach, our previous example is now executed as follows. When op 2 is received on site 1 , op 2 needs to be transformed regarding op 1 . The integration algorithm calls the transformation function T(op 2 =ins(5,s),op 1 =ins(2,f)) = ins(6,s) = op ′ 2 . The insertion position of op 2 is incremented since op 1 has inserted an f before s in state "efect". After the execution of op ′ 2 , the state of site 1 becomes "effects". On the contrary, when op 1 is received on site 2 , the transformation does not modify op 1 's parameters since f is inserted before s. Thus, op 1 is executed as-is and the state of site 2 is "effects". On this scenario, OT approach has ensured that both copies converge to the same value.

The OT approach distinguishes two main components: an integration algorithm and a set of transformation functions. The integration algorithm is in charge of reception, diffusion and execution of operations. When necessary, it calls transformation functions. This algorithm does not depend on type of replicated data. The transformation functions merge concurrent modifications by serializing two concurrent operations. These functions are specific to a particular type of replicated data such as string of characters, XML documents, calendars or file system.

OT approach aims to achieve convergence of copies.

Convergence As every optimistic replication algorithm, OT approach aims to ensure eventual consistency. This means that if no updates are perfomed for a long period of time, all updates will eventually propagate through the system and all the copies will converge towards a same value. In other words, when the system is idle (no operation in pipes), all copies are identical.

To ensure convergence, it has been proved [START_REF] Suleiman | Concurrent Operations in a Distributed and Mobile Collaborative Environment[END_REF] that the underlying transformation functions must satisfy two properties:

Definition The TP 1 property defines a state equivalence. The state generated by the execution of op 1 followed by T (op 2 , op 1 ) must be the same as the state generated by the execution of op 2 followed by

T (op 1 , op 2 ): op 1 •T (op 2 , op 1 ) ≡ op 2 •T (op 1 , op 2 )
Definition The TP 2 property ensures that the transformation of an operation regarding a sequence of concurrent operations does not depend on the order in which operations of this sequence were transformed:

T (op 3 , op 1 •T (op 2 , op 1 ))=T (op 3 , op 2 •T (op 1 , op 2 ))
The operational transformation approach could be used to design a reconciliation framework able to reconciliate divergent copies of any type of data. In order to build such a framework, the following task have to be completed. First, an integration algorithm must be chosen ; regarding this algorithm, TP 2 property may be required on underlying transformation functions. Second, operations which could be performed on shared data types must be defined. Finally, the required transformation functions for all combination of operations have to be provided. In the next sections, we are going to describe our framework.

THE SO6 FRAMEWORK

So6 framework is based on SOCT4 integration algorithm [START_REF] Vidot | Copies Convergence in a Distributed Real-Time Collaborative Environment[END_REF]. Originally, SOCT4 has been designed for real-time group editors andwe adapted it for asynchronous interaction [START_REF] Molli | Using the Transformational Approach to Build a Safe and Generic Data Synchronizer[END_REF]. SOCT4 integration algorithm requires only TP 1 property on transformation functions. It is based on a continuous global order of operations. Shared data are replicated on different sites (workspaces). Each operation generated on a local site is sent with a unique global timestamp to other sites. An operation from a site with a given timestamp can be sent to other sites only if all its preceding operations based on the timestamp order have been received and executed. In this way, SOCT4 ensures that concurrent operations will not be transformed following different transformation paths. This leverages the need for transformation functions to satisfy TP 2 property. Moreover, this mechanism works similarly to the Copy-Modify-Merge paradigm widely used in version control systems such as CVS. Regarding this paradigm, a user can publish her modifications only if she integrated all previously published modifications.

The So6 framework has the following components: one central timestamper also called So6 queue, and several So6 workspaces connected to a timestamper.

So6 Queue

A So6 queue Q is a timestamper that stores a sequence of operations. An operation is timed when a user sends it to the queue. A queue maintains a timestamp lastTicket equal to the last delivered timestamp. When a user creates a queue, the timestamp lastTicket is initialized to zero and the sequence of operations is empty. The publish procedure assigns a new timestamp to the operation op and stores it in Q.

int publish(Operation op) { lastTicket++ Q[lastTicket] = op return lastTicket }

So6 Workspace

Users can work insulated in their workspaces which we are going to refer to as So6 workspaces. A So6 workspace stores all documents shared by the user. This workspace is generally connected to a So6 queue. When users modify a document, they generate corresponding operations. Workspace has the following data structure:

A timestamp siteTicket. It memorises the timestamp of the last operation published to or retrieved from the So6 queue.

Two states currentState and referenceState. They are used to compute the sequence of operations that have been performed locally. currentState is the state on which the user works. referenceState is the state resulting from the execution of all operations integrated by the site.

A sequence of operations Hg. It stores all the operations integrated by the site. This sequence contains all operations published by the site and those retrieved from the timestamper. The operations are ordered according to their timestamps. If the operations contained in the sequence Hg are executed on an empty state, then it obviously computes the state referenceState.

Inside a workspace, the following procedures are defined:

A Commit procedure. During this procedure, the system detects local operations generated since last commit. Then, it sends each operation to the So6 queue in order to be time stamped and stored. The update procedure calls two other subprocedures computeDifference and merge. The computeDifference uses a differentiation algorithm to compute the sequence of operations that were executed on the state state 1 to obtain the state state 2 . For instance, in the case of an XML document, any XML differentiation algorithm can be used. For our prototype, we used XyDiff [START_REF] Cobena | Detecting Changes in XML Documents[END_REF]. The merge procedure integrates two sequences of concurrent operations using the set of transformation functions T . This procedure relies on the SOCT4 integration mechanism. Each operation remote[i] must be transformed to an operation opr regarding the whole sequence of local operations. Then, this operation can be executed on the current state currentState of the site. Additionally, the original operation remote[i] is executed on the state referenceState.

XML DOCUMENTS SUPPORT

In the previous section, we presented our generic framework for reconciliating divergent copies of data. In this section, we describe how this framework could be instantiated to support collaboration over XML documents. In [START_REF] Molli | Using the Transformational Approach to Build a Safe and Generic Data Synchronizer[END_REF], we instantiated our framework to reconciliate a file system and also text documents.

As usual, the XML document is modeled as a node-labelled ordered tree, and each XML element, be it leaf or non-leaf, corresponds to a node of that tree. Since we suppose that the tree is ordered, the children of every node are ordered. Therefore, each node is uniquely identified by its path. This path is defined as the sequence of child number starting from the root. The path of the root node is denoted []. For instance, the XML document presented in Figure 1 is mapped to the tree depicted by Figure 2. And, the path [0, 1, 0] leads to the leaf labelled with the value The abstract is.... <?xml version="1.0" encoding="UTF-8"?> <article> <sect1> <title>Abstract</title> <para>The abstract is...</para> </sect1> <sect1> <title>Introduction</title> <para>Optimistic replication...</para> </sect1> </article> We assume that the tree representation of an XML document can be changed by the following two operations: -, () *+ sect1

[0,0]

x x q q q q q q q q q q q [0,1] /.

-, () *+ sect1

[1,0] [1,1] @ @ /.
-, () *+ title [0,0,0] /.

-, () *+ para [0,1,0] /.

-, () *+ title [1,0,0] /.

-, () *+ para • addNode(parent, n, val) adds a new node as a child of the node identified by the path parent. This node is added as nth child and its value -or label -is val. • delNode(parent, n) deletes the nth child of the node identified by the path parent.

For the sake of simplicity, a move operation on a node of the tree is consider equivalent to the deletion this node from its old location followed by the insertion of this node to its new location.

In order to work with node paths, the following functions are defined. The function length(p) returns the length of the path p, i.e. the number of nodes in this path. The predicate childOf(p 1 , p 2 ) is true if the node identified by the path p 1 is a descendant of the node identified by the path p 2 . The function getPos(p, n) returns the (n + 1)th value of the path p, i.e. get-Pos ([3,2,1,4],2)=1. The function incPos(p, n) computes a new path by incrementing the (n + 1)th value of the path p, i.e. incPos ([3,2,1,4],2)=[3,2,2,4]. In the same manner, the function decPos(p, n) computes a new path by decrementing the (n + 1)th value of the path p, i.e. decPos ([3,2,1,4],2)=[3,2,0,4]. Finally, the function codeInf(val 1 ,val 2 ) allows to compare two values val 1 and val 2 . Such a function can always be defined. For example, for text nodes, codeInf() is defined on the lexicographical order between the values, i.e. codeInf("Abstract","Introduction")=true.

As we explained in section 2, a transformation function computes the result of the integration of two concurrent operations. So, for one XML tree, all possible combinations of operations defined on that XML tree have to be considered. Thus, the following transformation functions for each couple of operations have to be defined: (addNode(),addNode()), (delNode(),delNode()), (addNode(),delNode()) and (delNode(),addNode()). Due to space limitations, we are going to describe in details only the transformation function T(addNode(), addNode()).

Figure 3 indicates the complete definition of the transformation function T for two concurrent addNode operations.

This function transforms op 1 =addNode(p 1 ,n 1 ,v 1 ) regarding

T (addNode(p 1 ,n 1 ,v 1 ), addNode(p 2 ,n 2 ,v 2 )) = if ( p 1 = p 2 ) then if (n 1 < n 2 ) then addNode(p 1 ,n 1 ,v 1 ) elsif (n 2 < n 1 ) then addNode(p 1 ,n 1 +1,v 1 ) elsif (codeIn f (v 1 , v 2 )) then addNode(p 1 ,n 1 ,v 1 ) elsif (codeIn f (v 2 , v 1 )) then addNode(p 1 ,n 1 +1,v 1 ) else Id() endif elsif (childO f (p 1 ,p 2 )) then if (n 2 ≤ getPos(p 1 , length(p 2 ))) then addNode(incPos(p 1 ,length(p 2 )),n 1 ,v 1 ) else addNode(p 1 ,n 1 ,v 1 ) endif else addNode(p 1 ,n 1 ,v 1 ) endif Figure 3: Transformation function for addNode-addNode op 2 =addNode(p 2 ,n 2 ,v 2 ).
The main idea of this function is to compare the insertion position of two concurrent addition of nodes in the XML tree. The following cases have to be considered:

• If the two additions operate on the same parent node, then T compares their insertion positions.

-If op 1 inserts a child at a position after the insertion position of op 2 then the insertion position of op 1 has to be shifted one position to right. Therefore, its insertion position is incremented. -If op 1 inserts a child before the insertion position of op 2 , then the insertion position of op 1 remains the same. -If op 1 and op 2 try to insert at the same position, T must decide the serialisation order. In the above definition, the decision of T is based on the codeInf() function, which compares the lexicographic value of nodes. If lexicographic values are equal, then op 1 and op 2 try to insert the same node at the same position, consequently, the function disables the effect of op 1 by transforming it into an identity operation. Of course, this is an arbitrary choice and other solutions are possible such as the insertion of both nodes.

• If the two additions operate on different parent nodes, then the previous execution of op 2 might move the parent node of op 1 . This situation occurs when the parent node of op 1 is a child of the parent node of op 2 .

To illustrate, consider the initial XML tree given in the figure 4 and two concurrent operations op 2 =addNode([],1,X) and op 1 =addNode([2],1,Y). The execution of the operation op 2 moves the parent node on which | | y y y y y y Transformation functions for couples of operations delNode-delNode, addNode-delNode are defined in the same way. Among the pairs of transformation functions, there is a critical case to consider: what to do when an operation removes a subtree while another concurrent one appends a node to this subtree? This is clearly a case of conflict. The solution we chose is to remove the subtree even if in this case the concurrent changes performed on this subtree are lost. This solution allows to ensure data convergence.

[1] 4 4 i i i i i i [2] @ @ | | y y y y y y 4 4 i i i i i i [3,0] Figure 4: Initial tree [0] | | z z z z z z z [1] [2] h h h 4 4 h h h [3] @ @ Ð Ð Ñ Ñ Ñ Ñ Ñ Ñ Ñ 2
To avoid this lost update, we assume that the system should provide an undo feature in order to restore lost changes if the convergent state is not suitable for users. This undo feature is subject to many research efforts [START_REF] Sun | Undo as Concurrent Inverse in Group Editors[END_REF].

Writing correct transformation functions regarding the TP 1 property is not an easy task. The safety of the operational transformation approach relies on the correctness of transformation functions. If transformation functions do not satisfy TP 1 then the integration algorithm cannot ensure convergence of copies. Proving TP 1 property is error prone, time consuming and part of an iterative process. It is nearly impossible to do this by hand. In order to achieve this task, we used our VOTE environment [START_REF] Imine | Formal Design and Verification of Operational Transformation Algorithms for Copies Convergence[END_REF] which is based on an automatic theorem prover. The input of this environment is exactly the definition of the transformation functions given in this paper. Describing our environment for verifying correctness of transformation functions is out of the scope of this paper, a more detailed description is available in [START_REF] Imine | Formal Design and Verification of Operational Transformation Algorithms for Copies Convergence[END_REF][START_REF] Imine | Proving Correctness of Transformation Functions in Real-Time Groupware[END_REF].

In the following, a scenario illustrating how the So6 framework works is presented. It considers two users who are cooperating for writing an XML document. They are working in their own workspaces called site 1 and site 2 , respectively. Each workspace contains a copy of the shared XML document. At the beginning both copies are identical.

The different steps of this scenario are summarized as follows:

site 1 site 2 op 1 op 3 op 2 commit (send op 3 ) update (compute op ′ 3 , op ′ 1 , op ′ 2 ) commit (send op ′ 1 , op ′ 2 ) update (exec. op ′ 1 , op ′ 2 )
Users work concurrently to edit the document. The first user performs operations op 1 and op 2 while the second performs the operation op 3 . The states of the copies of the document taking into account these modifications are depicted by the Figure 6. After that, the second user commits their modifications i.e. the operation op 3 is sent to the timestamper. Later, the first user updates their workspace in order to integrate modifications published by the second user. During the update, the transformed operations op ′ 3 , op ′ 1 , op ′ 2 are calculated. At this step, only the operation op ′ 3 is locally executed. Then, the first user commits their modifications. During this step, op ′ 1 and op ′ 2 are sent to the timestamper. When the second user calls the update procedure, op ′ 1 and op ′ 2 are executed as-is on the local copy of the workspace site 2 (remember that this user does not perform new operation). At the end of the execution, both copies of the document converge towards a unique value.

RELATED WORK

Configuration Management (CM) tools [START_REF] Berliner | CVS II: Parallelizing Software Development[END_REF] are widely used for asynchronous collaborative editing. Users work in parallel, produce data divergence and reconciliate later using the Copy-Modify-Merge paradigm. Reconciliation is performed by tight cooperation between version manager and merge tools. When a reconciliation is required, i.e. usually when a user updates their workspace, the version manager provides those versions required by merge tools [START_REF] Munson | A Flexible Object Merging Framework[END_REF]. Merge is performed locally in the user workspace. Merge tools extract from different versions concurrent logs of operations using differentiation algorithms [START_REF] Chawathe | Meaningful Change Detection in Structured Data[END_REF]. These differentiation algorithms are specific to data types. Finally, concurrent operations are merged using ad-hoc algorithms specific to data types. An XML merge tool such as DeltaXML [START_REF] Fontaine | Merging XML Files: A New Approach Providing Intelligent Merge of XML Data Sets[END_REF] or XyDiff [START_REF] Cobena | Detecting Changes in XML Documents[END_REF] can be used in conjunction with CM tools for supporting collaboration on XML data. However, in this approach, several merge tools are used: one for file systems, another one for text files and another one for XML files. Each merge tool has its own merge algorithm. They might not be consistent together if they do not apply the same strategy. For example, in CVS, the merge tool used for text files relies on compensation contrary to the merge tool used at the file system level. Thus, whatever are the changes performed on a text file, they will always be merged into the new file version ; even conflicting changes are put in the text file -they are delimited with special mark-ups -. After the merging, a user can compensate what has been performed by the merge tool by editing the content of the text file. On the other side, the merge tool used at the file system level does not apply this principle. In the case it detects a conflict, the reconciliation process is stopped and the user is asked to solve the conflict. The operational transformation (OT) model is more general, more uniform and safer than the model used in CM tools. In the OT approach, the merge algorithm is shared by all transformation functions. It ensures convergence if underlying transformation functions ensure the TP 1 property. In this way, we can extend the reconciliation engine by adding new transformation functions without violating consistency.

Some propositions have been done in the OT model to work with XML data. [START_REF] Davis | Generalizing Operational Transformation to the Standard General Markup Language[END_REF] defined some transformation functions for SGML. These functions present some similarities with our transformations for XML. However, Davis and al.'s functions do not verify the TP 1 property. Thus, using these transformation functions in our framework will not ensure convergence of copies of shared data.

In [START_REF] Shen | Flexible Merging for Asynchronous Collaborative Systems[END_REF], Shen et al. proposed a framework similar to our So6 framework. The main difference is when a conflict occurs between two concurrent operations, the operation coming from the repository is cancelled, and the local operation is preserved. Firstly, this choice is not acceptable since cancelling an operation means losing some previously published work. Secondly, the authors do not provide any information concerning the editing of a tree structure such as an XML document. In parallel to our work, Ignat et al. [START_REF] Ignat | Supporting Customised Collaboration over Shared Document Repositories[END_REF] extended the Shen et al.'s approach to a tree structured document. The main idea is to distribute the log of operations through the tree. Thus, each node is associated with a log containing the operations performed on its content, insertion and deletion of child nodes. Using this model, they are able to use transformation functions defined for a linear structure such as the one proposed for a string of characters by Ressel et al. [START_REF] Ressel | An Integrating, Transformation-Oriented Approach to Concurrency Control and Undo in Group Editors[END_REF]. Their proposition constitues an alternative to our approach.

IceCube [START_REF] Kermarrec | The IceCube Approach to the Reconciliation of Divergent Replicas[END_REF]) is a generic approach for reconciliating divergent copies of documents. It handles reconciliation as a constraints optimisation problem: the one of executing an optimal combination of concurrent changes. IceCube uses semantic constraints between operations that the reconciliation algorithm has to preserve. Basically, Ice-Cube explores all possible combinations of concurrent operations and rejects all combinations violating defined constraints. This approach is interesting because, IceCube is looking for the combinations of concurrent operations that minimize conflicts of reconciliation. Maybe, on this point, the operational transformation approach will not find the optimal reconciliation. On the other hand, IceCube has some intrinsic drawbacks: Combinatorial explosion can occur during the first stage of reconciliation.

The Harmony project [START_REF] Foster | Exploiting Schemas in Data Synchronization[END_REF]) is a generic framework for reconciliating divergent copies. In this framework, the reconciliation process exploits schema of the structures being synchronized to achieve a better accuracy. This framework relies on a state-based approach which means three copies of the document -the two divergent copies and the common ancestor document -are required for reconciliation. As most state-based synchronisers, the goal of the reconciliation engine is to reduce divergence between copies. However, convergence of copies is not achieved in all cases. If conflicting changes are detected between two copies, the conflicts are marked but the copies remain divergent. On the contrary, our framework will always ensure convergence of copies. Simply, in a case of conflicting changes, these changes will be transformed to be integrated as conflicting changes in the copies. This allows every participant to later resolve the conflict. We think sharing conflicts is useful, because sometimes the user informed about he conflict has no knowledge to resolve it.

CONCLUSION

We have presented the SO6 framework for supporting cooperative writing over documents. This framework relies on a theoretical model called operational transformation approach. Our framework is generic in the sense that it could be instantiated to manage multiple types of document. In order to illustrate these features, we explained how to enable cooperative writing of XML documents. This framework and the presented transformation functions are integrated in the SO6 revision management tool included in the Libre-Source (http://www.libresource.org/) collaborative platform. This tool is able to reconciliate copies of a file system containing text documents and XML documents.

If our framework ensures convergence, the convergence state may violate the DTD. For example suppose two users add concurrently a "title" element in an XML document. From the point of view of an ordered tree, two title nodes can appear under the root. However, from the point of view of the DTD, only one title is allowed. Finally, the SO6 framework is able to compute a convergence state, but this state may violate the DTD. This is clearly an open issue for the So6 framework and for XML merge tools.

  merge(Operation[] remotes, Operation[] locals) { for (int i=0; i<remotes.length; i++) { Operation opr = remotes[i] int ticket = remotes[i].ticket for (int j=0; j<locals.length; j++) { Operation opl = locals[j] locals[j] = T(opl, opr) opr = T(opr, opl) } execute(remotes[i], referenceState) Hg[ticket] = remotes[i] execute(opr, currentState) siteTicket = ticket } }

Figure 1 :

 1 Figure 1: An example of XML document.

Figure 2 :

 2 Figure 2: Mapping document of Fig. 1 to an ordered tree

Figure 6 :

 6 Figure 6: Collaborative Editing Scenario

ACKNOWLEDGEMENTS

We wish to thank Claudia-Lavinia Ignat for her very valuable comments and suggestions which helped us to improve the presentation of this article.

the operation op 1 has to be executed. Therefore, the transformation of the operation op 1 regarding of the operation op 2 must give the operation

Comparing and updating the position in the path of op 1 is achieved by using getPos() and incPos() functions. The resulting tree is depicted in figure 5.