Alban Gabillon
email: alban.gabillon@univ-pau.fr

A Logical Formalization of a Secure XML Database 1

In this paper, we first define a logical theory representing an XML database supporting XPath as query language and XUpdate as modification language. We then extend our theory with predicates allowing us to specify the security policy protecting the database. The security policy includes rules addressing the read and write privileges. We propose axioms to derive the database view each user is permitted to see. We also propose axioms to derive the new database content after an update.

 and we obtained a new version of our model which did not have these drawbacks: -We investigated in details interactions between the read privilege and the write privilege.

 was not complete: -We could not give the logical interpretation of the query language.

. In fact, this paper is an extended version of papers [10] and [28]. We have implemented a Prolog-based prototype simulating a secure XML database.

Introduction

Several discretionary access control models for eXtensible Markup Language (XML) documents [START_REF] Bray | Extensible Markup Language (XML) 1.0[END_REF] have been proposed [START_REF] Bertino | Specifying and Enforcing Access Control Policies for XML Document Sources[END_REF][7] [START_REF] Kudo | XML Document Security based on Provisional Authorisation[END_REF] [START_REF] Gabillon | Regulating Access to XML documents[END_REF] [START_REF] Lim | Access Control of XML Documents considering Update Operations[END_REF]. In [START_REF] Gabillon | An Authorization model for XML databases[END_REF], we first reviewed most of the existing access control models for XML and discussed their weaknesses. Based on our study, we then defined a new model suggesting a solution to cope with the problems that our study revealed. The model in [START_REF] Gabillon | An Authorization model for XML databases[END_REF] has the following characteristics: -The model is an interpretation for XML of the SQL security model (with some additional features). -Each user is provided with a view of the source database he or she is permitted to see.

-The model includes a new position privilege that allows knowing about the existence of an XML node but not about its label. Nodes on which users hold a position privilege are shown with a RESTRICTED label in users' views. Thus, sensitive labels are hidden while the structure of the XML document is preserved. -The model includes various write privileges and defines the access controls for the write operations. However, the model in [START_REF] Gabillon | An Authorization model for XML databases[END_REF] has two drawbacks: -It is defined in an informal way.

-Like the security model of SQL, it ignores interactions between the read privilege and the write privilege. In other words, write operations are evaluated on the source database and not on the user's view. As a consequence, users can build some covert channels to learn about the data they are not permitted to see.

In section 2, we make an informal overview of our model and we underline the main limitations of existing security models for XML. In section 3, we define the logical theory representing an XML database. Since we use XPath [START_REF] Clark | XML Path Language (XPath) Version 1.0[END_REF] as a query language and XUpdate [START_REF] Laux | XML Update (XUpdate) language. XML:DB working draft[END_REF] as a modification language, we give their logical interpretation. In section 4, we extend our theory with predicates allowing us to define the security policy protecting the database. The security policy includes rules addressing read and write privileges. We define the logical formulae allowing us to derive the database view each user is permitted to see. We also give the logical formulae allowing us to derive the new database after an update. Finally, section 5 concludes this paper.

Informal Overview of our Model

In this section, we survey existing works and we present our approach in an informal way. The interested reader can also refer to [START_REF] Fundulaki | Specifying Acces Control Policies for XML Documents with XPath[END_REF] for a formal presentation of existing works.

Subjects

The development of an access control system requires the definition of the subjects and objects. There is not much to say about the subjects in existing access control models for XML data. In [START_REF] Bertino | Specifying and Enforcing Access Control Policies for XML Document Sources[END_REF], subjects are simply users. In [START_REF] Kudo | XML Document Security based on Provisional Authorisation[END_REF], they can be users or roles (see [START_REF] Sandhu | Role-Based Access Control[END_REF] for a description of roles). In [START_REF] Gabillon | Regulating Access to XML documents[END_REF], they are users who are structured into a group hierarchy. In [START_REF] Damiani | Securing XML Documents[END_REF], the authors take into consideration the fact that their access control model is to be implemented as an extension to an existing web server. In their model, subjects are users or IP addresses (or a combination of the two), and they are structured into a group hierarchy. In the model presented in this paper, subjects can be users or roles like in the SQL security model.

Objects

An object is a granule of information which can be protected. Regarding the objects, there are basically different approaches among existing access control models for XML data:

-In [START_REF] Damiani | Securing XML Documents[END_REF] [START_REF] Kudo | XML Document Security based on Provisional Authorisation[END_REF], the smallest object is an element. Authorizations specified for an element are intended to be applicable to the element itself, its content (PCDATA) and its attributes.

-In [START_REF] Bertino | Specifying and Enforcing Access Control Policies for XML Document Sources[END_REF], the smallest object is an element or an attribute. Authorizations specified for an element are intended to be applicable to the element itself and its content.

-In [START_REF] Gabillon | Regulating Access to XML documents[END_REF], an object is a node of an XPath tree (see [START_REF] Clark | XML Path Language (XPath) Version 1.0[END_REF] for a description of XPath and figure 1 for an example of an XPath tree). A node of an XPath tree can be an element, the content of an element or an attribute. We want our security model to have a high expressive power. Therefore, in our model, an object is a node of an XPath tree like in the model in [START_REF] Gabillon | Regulating Access to XML documents[END_REF].

Security Policy

In all the existing models, the approach is the same: the security administrator writes the security policy in a separate authorization sheet. The security policy consists of a set of authorization rules which can be either positive (grant) or negative (deny). The reason for having both positive and negative authorizations is to have a way to specify exceptions to authorizations which are applicable to sets of subjects or objects. Authorization rules address granules by means of Xpath expressions. Conflicts between the rules are solved by a conflict resolution policy.

-The model in [START_REF] Damiani | Securing XML Documents[END_REF] supports the read privilege only. In another paper [START_REF] Damiani | A Fine-Grained Access Control System for XML Documents[END_REF], the authors partially address the write privilege but underline the fact that current XML applications are mostly read-only and that no consensus has emerged up to now on a model for XML updates. An authorization specified on an element can be defined as local. In that case, it is applicable to the element itself, its content and its attributes. It can also be defined as recursive. In that case, the permission/prohibition is propagated to the sub-elements. Authorizations can be specified at the document-level or at the Document Type Definitions (DTDs) level. Authorizations specified at the DTD-level propagate to all XML documents that are instances of that DTD. The conflict resolution policy applies "the most specific object takes precedence" principle. According to this principle instance-level authorizations override DTD-level authorizations and a recursive authorization propagates until overridden by a conflicting authorization on a more specific object. For conflicts which cannot be solved by this principle, the authors suggest to apply other principles like "the most specific subject takes precedence" or "denial takes precedence" …etc. -The model in [START_REF] Bertino | Specifying and Enforcing Access Control Policies for XML Document Sources[END_REF] supports two kinds of privileges: browsing (read) and authoring (write). Authorizations are specified along with propagation options. Depending on its propagation option, an authorization referring to an element may propagate to all the direct and indirect sub-elements, propagate to all the direct sub-elements only, or not propagate at all. Like in the previous model, authorizations can be specified at the DTD-level or at the instance-level. The conflict resolution policy is similar to the previous one. -The model in [START_REF] Kudo | XML Document Security based on Provisional Authorisation[END_REF] supports read and write privileges. The authors define three types of propagation policies: no propagation, propagation up (an authorization referring to an element is propagated to all its parent elements) or propagation down (an authorization referring to an element is propagated to all its subelements). The conflict resolution policy is either "denials take precedence" or "permissions take precedence". The main contribution of this paper is to propose a provisional authorization model. A provisional authorization is more than a simple permission/denial. Typically, a provisional authorization specifies that a user has to perform a given action (obligation) before he/she is granted a given privilege -The model in [START_REF] Gabillon | Regulating Access to XML documents[END_REF] supports the read privilege only. The authors do not define any propagation policy. The conflict resolution policy is based on the priority of the different rules. -The model in [START_REF] Lim | Access Control of XML Documents considering Update Operations[END_REF] is based on the model defined in [START_REF] Damiani | Securing XML Documents[END_REF]. The authors add write privileges and suggest a technique for efficiently managing access controls in a web environment which emphasizes the integrity of the documents (i.e. validity with respect to DTDs). They consider XQuery update operators but these operators are not standardized yet [20][3]. The model presented in this paper supports read and write privileges. We assume that security rules are issued in the chronological order. In case of a conflict between two rules, the last issued rule has the highest priority. The default policy is always "denial".

View Access Control

Most of the existing security models for XML define a view-based access control strategy for handling the read privilege. However, these models suffer from problems that were pointed out in [START_REF] Stoica | Secure XML Views[END_REF]: -Regarding the model in [START_REF] Gabillon | Regulating Access to XML documents[END_REF], if access to a node is denied then the user is not allowed to access the entire sub-tree under that node even if access to part of the sub-tree is permitted, therefore limiting the availability of data. -Regarding the model in [START_REF] Damiani | Securing XML Documents[END_REF], in order to preserve the structure of the document, the authors allow elements with negative authorizations (i.e. access denied) to be released if the element has a descendant with a positive authorization (access permitted), thus making the semantics of the negative authorization unclear. These two problems are illustrated in figures 1 and 2. Let us assume tag + represents permission and tag -represents denial for a given user s.

Figure 1 is related to the model in [START_REF] Gabillon | Regulating Access to XML documents[END_REF]. Recall that this model allows node-level security granularity. The left tree represents a sample medical files database which has been tagged according to the authorizations applying to a given user s. The right tree corresponds to the view user s is permitted to see. This view has been computed according to the access control strategy defined in [START_REF] Gabillon | Regulating Access to XML documents[END_REF]. One can see that the sub-tree of which element node /robert is the root is not visible at all although user s has the permission to see some of the descendant nodes. As it is said in [START_REF] Stoica | Secure XML Views[END_REF], this access control strategy reduces the availability of data. One could argue that such a situation comes from a bad security design. Nevertheless, it should be possible to deny access to an internal node while granting access to its descendant nodes.

Figure 2 is related to the model in [START_REF] Damiani | Securing XML Documents[END_REF]. Recall that this model allows element-level security granularity. The left tree represents the source tree which has been tagged according to the authorizations applying to user s. The right tree corresponds to the view user s is permitted to see. This view has been computed according to the access control strategy defined in [START_REF] Damiani | Securing XML Documents[END_REF]. One can see that element /robert is visible in the view. This makes the semantics of the negative authorization unclear. In order to solve the problems mentioned in [START_REF] Stoica | Secure XML Views[END_REF], we introduced in [10] a special privilege protecting the existence of nodes. Therefore, our model includes two kinds of read privileges: one privilege which allows knowing about the existence of a node (we call it the position privilege) and another privilege which allows knowing both the existence and the label (we call it simply the read privilege). The security designer has now two options: if user s is forbidden to know about the existence of node n then the security designer denies both position and read privileges on node n to user s. In that case node n and possible descendant nodes (even those for which the user has permission to read) are not shown in the view user s is permitted to see. if only the label of node n is sensitive then the security designer grants to user s the position privilege on node n (without granting the read privilege). Node n is shown in the view with RESTRICTED label and descendant nodes for which the user has permission to see are also shown in the view. Label RESTRICTED was first used by Sandhu and Jajodia in the context of multilevel databases [START_REF] Sandhu | Polyinstantiation for cover stories[END_REF]. Its semantics is "the label exists but you are not allowed to see it".

In figure 3, tag r (respectively p) attached to a node represents the fact that user s holds the read (respectively position) privilege on that node. Right tree represents the view user s is permitted to see. User s is permitted to read illnesses (most probably for statistical purpose) but she is forbidden to see patients' names.

Write Access Controls

Some of the existing security models for XML consider the write privilege but, they do not clearly indicate in which framework the different update operations for XML are supported, the access control strategy that they use for handling the write privilege is not clearly described, interactions between read access controls and write access controls are not investigated. In fact, these security models were designed to be implemented as extensions to existing web servers. SQL ignores interactions between the read privilege and the write privilege. Indeed, if a user submits a write operation (via one of the standard SQL commands: INSERT, UPDATE or DELETE) then this operation is evaluated on the source database and not on the data the user is permitted to read. As a consequence, users can easily learn about the data they are not permitted to see. For example, consider user_A who is the owner of the employee table and who has granted to user_B the sole update privilege on employee. user_B is not permitted to see user_A's employee table, SQL> SELECT * FROM user_A.employee; ERROR ORA-01031: insufficient privilege but user_B is permitted to update user_A's employee table :   SQL> UPDATE user_A.employee SET salary=salary+100 WHERE salary > 3000; 2 rows updated Although user_B is not permitted to see user_A's employee table, she has been able to learn, through an update command, that there are two employees with a salary greater than 3000. The UPDATE command was evaluated on data user_B was not permitted to see. Note, in particular, that the WHERE clause performed a read operation on the employee table. We could show various examples exploiting this vulnerability.

The model in [START_REF] Gabillon | An Authorization model for XML databases[END_REF] has the same vulnerability since it is an interpretation for XML of the SQL security model. In [START_REF] Gabillon | An Authorization model for XML databases[END_REF], an operation updating XML data is evaluated on the source database regardless of the read privileges held by the user submitting the operation.

In [START_REF] Gabillon | A Formal Access Control Model for XML Databases[END_REF], we investigated interactions between the read privilege and the write privilege and we modified our model as follows: since a write operation is a process running on behalf of a user, it should have the privileges and the limitations of the user. In particular the write operation should not be able to read the data the user is not permitted to see. Conceptually, this means that write operations have to be evaluated on users' views and not on the source database. In order to retrieve the corresponding database node from a given view node, we assign one identifier to each database node. Identifiers are obtained by applying a numbering scheme [START_REF] Cohen | Labelling dynamic XML trees[END_REF][24][8] [START_REF] Gabillon | A Persistent Labelling Scheme for XML and tree Database[END_REF][21][25] [START_REF] O'neil | ORDPATHs: Insert-Friendly XML Node Labels[END_REF]. If a user submits a write operation then the nodes to update are first selected from the view she is permitted to see. Thanks to the identifiers, corresponding database nodes are then retrieved and updated.

Our model supports three kinds of write privileges (insert, delete and update). We give the exact semantics of each of these privileges. We state the privileges that each XUpdate operation requires for completion and we formally define the access controls for each of the XUpdate operations.

XML Database

Mathematical logic has been used to formalize databases in two main directions. These directions are usually called the proof theoretic approach and the model theoretic approach. The former represents a database as a logical theory; the latter represents a database as an interpretation of a logical theory [START_REF] Reiter | Toward a logical reconstruction of relational database theory[END_REF]. In this paper, we adopt the proof theoretic approach, that is, each database is associated with its logical theory db. We also make the closed world assumption. The closed world assumption holds that anything that we cannot show to be true is false.

XML documents modeled as trees

For the sake of simplicity, we shall not consider the type of XML nodes. An XML document is a tree of nodes. Each node is the parent of zero or more child nodes. Each node has one and only one parent except one fundamental node which has no parent and which is called the document node. We state that each node is associated with a unique identifier and a label: -Node identifiers are obtained by applying a numbering scheme (see section 3.2).

-Labels are the data. Labels are small for nodes of type element (in the XML terminology they are referred to as names) and they can be very large for nodes of type text (in the XML terminology they are referred to as values or PCDATA). Figure 4 shows an XML document which we shall use throughout the remainder of this paper. Strings patients, franck, service, otolarynology … are labels. n , n , n 1 2

3 , … denote numbers identifying nodes. The document node has identifier / and label /. The document node has only one child node which is called the root element node. Identifier of the root element is n 1 and label is patients. [START_REF] O'neil | ORDPATHs: Insert-Friendly XML Node Labels[END_REF]. They all support the representation of ancestor and sibling relationships between nodes i.e. one can derive the relationship between any two given nodes by looking at their unique numbers. [START_REF] O'neil | ORDPATHs: Insert-Friendly XML Node Labels[END_REF]. A persistent numbering scheme does not require renumbering after an update i.e. numbers assigned to existing nodes remain the same even after an update modifying the tree structure. The scheme presented in this section is the scheme we defined in [START_REF] Gabillon | A Persistent Labelling Scheme for XML and tree Database[END_REF]. It is a very simple persistent numbering scheme which supports an infinite number of insertions without renumbering. It does not require a space of reserved identifiers like in [START_REF] Weigel | The BIRD Numbering Scheme for XML and Tree Databases -Deciding and Reconstructing Tree Relations using Efficient Arithmetic Operations[END_REF]. It is based on the fact that there exist an infinite number of rational numbers within an interval [a,b], a, b being rational numbers.

Numbering Scheme

Several numbering schemes have been proposed [6][24][8][12][21][25]

Static Numbering Step

We identify nodes by using rational numbers. We represent a rational number by a pair which consists of a signed integer and a strictly positive integer, e.g. we represent rational number 5/2 by the pair [START_REF] Clark | XSL Transformations (XSLT) Version 1.0[END_REF][START_REF] Bray | Extensible Markup Language (XML) 1.0[END_REF] and the rational number -5/2 by the pair

(-5,2).
Our numbering scheme needs modest storage capacities. We assign a quintuple of integers (l,(n ,d ),(n,d We assign the special identifier (0,/,(1,1)) to the root node. 0 is the level. / is the code of the parent node (i.e. the document node).(1,1) is the local code.

Given a level l, if we assume that nodes are visited from left to right then the local code of a node is (i,1), with i being the position of the node at level l.

After the static numbering step, node identifiers of the tree in figure 4 are the followings:

() ( ) () () ( ) () () ( ) () () ( ) () () ( ) () () ( ) () () ( ) 12 7 3 5 46 n 0, /, 1, 1 , n 1, 1, 1 , 1, 1 , n 1, 1, 1 , 2, 1 , n 2, 1, 1 , 1, 1 , n 2, 1, 1 , 2, 1 , n 3, 1, 1 , 1, 1 , n 3, 2, 1 , 2, 1 ⎧ ⎫ ⎪ ⎪ == = = = ⎪ ⎪ ⎪ ⎪ ⎨ ⎬ ⎪ ⎪ == ⎪ ⎪ ⎪ ⎪ ⎩ ⎭

Dynamic Numbering Step

In this section, we show how a newly inserted node is dynamically numbered without changing the number of existing nodes.

Rules for creating identifiers for new nodes -If v is the first node to be inserted at level l then its local code is (1,1) -If v is inserted immediately before the node of local code (i,j) and if there is no other node before (i,j) then the local code of v is (i-j,j). -If v is inserted immediately after the node of local code (i,j) and if there is no other node after (i,j) then the local code of v is (i+j,j). -If v is inserted immediately before the node of local code (i,j) and immediately after the node of local code (k,h) then the local code of v is (a,b) with a=(i.h+k.j)\d and b=2.h.j\d. \ denotes the integer division. d is the highest common factor of (i.h+k.j) and 2.h.j. If, for example, node /albert is inserted between node /franck and node /robert, then its identifier will be (1,(1,1),(3,2)).

Language

Language L of theory db is based on first-order logic with equality. For the sake of simplifying our logical formulae, we shall consider that the database may contain only one document. We shall use the following two-place predicate to represent the database content: reads "there is a node with label

() node n, v
v identified by number n" We shall also use the following predicate to learn about the database tree geometry: -, reads "node

( child x, y) 2
x is a child of node y" There are also other tree geometry predicates like parent, descendant, descendant_or_self, ancestor, following_sibling …

Axioms

Set of axioms A of theory db includes the classical axiom schemata of first order logic with equality plus some proper axioms. We divide these proper axioms into the following two sets: the set F of atomic facts recorded in the database.

the set of formulae allowing us to derive facts belonging to the tree geometry predicates. The sample database we shall use throughout this paper includes the document in figure 4:

( ) ( ) ( ) ( ) ( ) ( ) ( ) 12
⎧ ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ = ⎨ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎭ … (1)
Axioms allowing us to derive tree geometry facts depend on the numbering scheme. In appendix A, we give the axioms for deriving relations child, descendant, descendant_or_self, preceding_sibling, and immediate_preceding_sibling. These axioms are based on the scheme defined in section 3.2.

The following child relation can be derived from these axioms:

( ) ( ) ( ) ( ) ( ) ( ) { } 12

Updating node operations

⎧ ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ = ⎨ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎭ department … xupdate:update:
The following two formulae allow us to derive facts belonging to the new set F after an xupdate:update operation.

() ( ) ( ) ( ) () db db db db new n v,node n,v n v, xpath ,n,v child n,n node n,v ′′ ′′ ′ ∀∀ ∧ ¬∃∃ ∧ → PATH (4)
Children of nodes which are not addressed by PATH are not updated.

( ) ( ) ( ) db db db new n n v , xpath , n , v child n, n node n, ′′ ′′ ′ ∀∀ ∀ ∧ → NEW PATH V (5)
Children of nodes which are addressed by PATH are updated to V NEW . Example: Let us consider the operation xupdate:update which updates diagnosis of franck in pharyngitis:

-PATH = /patients/franck/diagnosis -V NEW = pharyngitis
From formulae 2 and 3, we can derive the new set F:

( ) ( ) ( ) ( ) ( ) ( ) ( ) 12
⎧ ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ = ⎨ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎭ pharyngitis …

Creating node operations

If a node belongs to the original document then it belongs to the final document. Recall that, thanks to our persistent numbering scheme, identifiers of existing nodes remain the same after an insertion or a deletion.

( )

( ) ( ) db db new n v n v n o, xpath , n, v create _ number(n, n , o, n '') node n , v ′′′ ′ ′′ ′ ∀∀∀ ∀ ∀ ∀ ∧ ∧ ′′ ′ → TREE node n , v PATH (7)
The tree to insert shall be inserted as the last subtree of each node selected by PATH (append), or as a new preceding-sibling tree of each node selected by PATH (insertbefore), or as a new following-sibling tree of each node selected by PATH (insertafter). Therefore, each node n' belonging to the tree to insert is inserted at as many places as nodes addressed by PATH. Created numbers n'' assigned to inserted nodes are given by the create_number predicate.

= ′′ ′′ ′′ ′′ ( ) ert , ⎧ ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎭ … )
From the tree geometry axioms we can derive: preceding _ sibling(n , n ), preceding _ sibling(n , n ), preceding _ sibling(n , n ), child n , n , child n , n , child n , n , child n , n

( ) ( ) ( ) ( ) 17
⎧ ⎫ ′′ ′′ ′′ ′′ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎬ ⎪ ⎪ ′′ ′′ ′′ ′′ ′′ ′′ ′′ ⎪ ⎪ ⎪ ⎪ ⎩ ⎭
From the dynamic numbering procedure defined in section 3.2.2, we obtain3 :

() () ( ) () () ( ) () () ( ) () () ( ) { } 12 4 3 n 1,
If a node belongs to the original document and if it does not belong to a deleted subtree then it belongs to the final document.

-, reads "node n does not belong to a deleted subtree"

( ) undeleted n
We can derive facts belonging to the undeleted predicate from the following formulae: [START_REF] Fundulaki | Specifying Acces Control Policies for XML Documents with XPath[END_REF] This formula says that nodes which are not deleted are the nodes which do not belong to a subtree whose root node is addressed by path

() ( ) ( ) ( ) db db db descendant_ or _ self n, n n v, node n, v n v , undeleted n xpath , n , v ⎛⎞ ′ ⎟ ⎜ ⎟ ⎜ ⎟ ′′ ⎜ ∀∀ ∧ ¬∃∃ → ⎟ ⎜ ⎟ ⎜ ⎟ ′′ ∧ ⎟ ⎜ ⎝⎠ PATH
⎧ ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ = ⎨ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎭ …

Secure XML database

We extend the logical theory db to represent a secure XML database.

Extended theory

We extend the language with predicates subject and isa for representing the subject hierarchy, -, reads "s is a subject"

( ) subject s - , reads "subject s is a subject s'" ( ) isa s,s′
We also introduce the predicate rule for writing the security policy: -, reads "subject s is granted privilege r on nodes addressed by path p". t is the priority of the rule.

( rule accept,r,p,s,t) - ( )
rule deny,r,p,s,t , reads "subject s is denied privilege r on nodes addressed by path p". t is the priority of the rule. Since accept and deny rules may conflict with each other, we define predicate perm to represent the actual privileges held by the subjects: -

( )
perm s,r,n , reads "subject s is (definitely) granted privilege r on node n" We extend our theory with the following sets:

the set S of formulae representing the subjects recorded in the database, the set R S of formulae allowing us to derive the subject hierarchy, the set P of atomic formulae representing the security policy, the set R P of formulae allowing us to solve conflicts between security rules,

Subjects

Let us consider the subjects hierarchy at figure 5. In each tree, internal nodes are roles [START_REF] Sandhu | Role-Based Access Control[END_REF] and external nodes are users.

The following set S represents this hierarchy:

() ( ) ( ) ( ) () ( ) ()
subject staff , subject secretary , subject doctor , subject epidemiologist , subject patient , subject beaufort , subject laporte , subject(richard), S subject(robert), subject(franck), isa(secretary, staff), isa(doctor, staff = ( ) ( )

),
isa epidemiologist, staff , isa(laporte, doctor), isa(beaufort, secretary), isa richard,epidemiologist , isa(robert, patient), isa(franck, patient)

⎧ ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎭ (10)
Set R S includes the two following axioms allowing us to derive the reflexive and transitive closure of the isa relation:

s s s , isa s,s isa s ,s isa s,s ′′ ′ ′ ′′ ′ ′ ′ ∀∀ ∀ ∧ → (12)

Security Policy

The security policy may refer to the following privileges: Let us now consider the example of security policy defined by axiom 13. First rule states that staff members have the privilege to read the whole document. Second rule partially denies that right from secretaries. Indeed, secretaries are denied the right to see diagnosis. However, rule 3 states that secretaries may know whether the patient was diagnosed or not. Rule 4 and rule 5 state that patients may access their own medical file ($USER is a variable containing the session user login name). Rule 6 and rule 7 state that epidemiologists are forbidden to see patient names. Rule 8 states that secretaries may insert new medical files. Rule 9 states that secretaries may update patient names. Rules

⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎬ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎩⎭ (13)
From practical point of view, we assume that the security administrator inserts these rules one by one. In case of conflict, the last issued rule has the priority over the previous ones. The timestamp indicating when the command was issued plays the priority role. For example, rule 1 which says that staff members have the permission to see the whole document is partially cancelled by rule 2 which partially denies that right to some staff members (secretaries).

Set R P includes the following axiom allowing us to solve the conflicts between the rules and to derive the actual privileges held by each subject:

( ) ( ) ( ) ( ) ( ) ( ) ( ) () s
′′ ′ ∀∀ ∀∀ ∀∀ ∀ ∧ ∧ ⎛⎞ ′′ ′ ′′ ′ ∧ ⎟ ⎜ ⎟ ⎜ ⎟ ′′ ′ ′ ⎜ ∧¬∃∃∃ → ⎟ ⎜ ⎟ ⎜ ⎟ ′′ ∧∧ > ⎟ ⎜ ⎝⎠ (14)
This axiom says that if there is an accept rule applying to privilege r, subject s and node n and if there is no subsequent deny rule applying to privilege r, subject s and node n then subject s holds privilege r on node n.

Access Controls

The purpose of this section is only to illustrate the semantics of the security policy. In section 4.4.1, we state axioms allowing us to derive the view of the source document that users are permitted to see. In section 4.4.2, we state axioms allowing us to derive the new database content after an update.

In this section we do not address the problem of how queries should actually be enforced. Regarding this issue, let us, however mention there are basically two approaches: -The first approach consists of computing and materializing the view of the source document the user is permitted to see [START_REF] Bertino | Specifying and Enforcing Access Control Policies for XML Document Sources[END_REF][7] [START_REF] Gabillon | Regulating Access to XML documents[END_REF]. Queries are then evaluated on the view. -The second approach [START_REF] Fan | Secure XML Querying with Security Views[END_REF] [START_REF] Mohan | Access Control for XML -A Dynamic Query Rewriting Approach[END_REF][31] consists of computing the view of the data the user is permitted to see. The user expresses queries by looking at her view. Queries are then rewritten according to the privileges held by the user and evaluated on the source document. The main drawback of the first approach is that it is expensive to materialize and maintain a large collection of views. The main drawback of the second approach is query rewriting itself which has proved to be a challenging problem since no solution addressing the full XPath language has been proposed yet. In terms of security both approaches should, of course, be equivalent i.e. the same query should return the same answer with both solutions.

Regarding updates, we could easily figure out the two similar approaches: -The first approach consists of selecting the nodes to update from the view the user is permitted to see. Corresponding source nodes are then retrieved and updated. -The second approach consists of rewriting queries selecting the nodes to update according to the privileges held by the user. Nodes to update are then selected from the source document and updated.

Read Access Controls

The purpose of this section is to define link axioms allowing us to derive the view of the source document that subjects are permitted to see. Each view is represented by a logical theory. Let us denote by s the current session user. Let us denote by view the theory representing the view that user s is permitted to see. The view access control strategy of our model can be informally described as follows:

-If user s holds either a read or a position privilege on node n and the parent of node n is itself a selected node then node n is selected by the view access control mechanism. Axioms 15, 16 and 17 implement that principle. The fact that a node requires its parent to be selected, in order for it to be selected, shows that the view is a pruned version of the source document. -A selected node for which user s holds only the position privilege is shown with the RESTRICTED label. Axiom 17 implements that principle. Note that selected nodes are not renumbered in the view. This cannot lead to inference channels since numbers are for internal processing only and are not visible to users.

The following formula allows us to derive facts belonging to the view user s is permitted to see:

()

view node /, / (15)
This formula says that always belong to the view regardless of user privileges.

()

view node /, / ( ) ( ) ( ) ( ) ()
db db view view n v n v s, node n, v logged(s) perm s, n, read child n, n ' node n , v node n, v ′′ ′′ ∀∀∀ ∀ ∀ ∧ ∧ ∧ ∧ → (16)
This formula says that if the current session user has the permission to read node n with label v and if the parent of node n is itself a selected node then the access control mechanism selects node n with label v.

This formula says that if current session user has the permission to know the existence of node n and if the parent of node n is itself a selected node then the access control mechanism selects node n with label RESTRICTED. If the session user also holds the read privilege then this axiom does not apply. -, reads "s is the current session user"

( ) logged s
Axioms 15, 16 and 17 can, of course, be implemented by a tree traversal algorithm. In [START_REF] Gabillon | An Authorization model for XML databases[END_REF], we give such an algorithm.

We can now derive the view of the sample source database (see axiom 1) each subject is permitted to see.

View for secretaries is the following:

( ) ( ) ( ) ( ) ( ) ( ) ( ) 12
⎧ ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎭ …
Secretaries can see everything except the content of diagnosis elements. If the diagnosis is posed, then they are provided with the RESTRICTED label.

View for patient Robert is the following:

( ) ( ) ( ) ( ) ( ) ( ) ( ) 17
⎧ ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎭
Robert is the current session user. As a patient he has access to its medical file only.

View for epidemiologists is the following:

( ) ( ) ( ) ( ) ( ) ( ) ( ) 12
⎧ ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎭ …
Epidemiologists can see everything except patient names. Doctors can see everything without restriction. Therefore, view for doctors includes the whole database represented by axiom 1.

Write Access Controls

The purpose of this section is to define the link axioms allowing us to derive the database content after an update. The link axioms must take into account the privileges of the user performing the update.

Each XUpdate operation requires the path PATH parameter to select nodes to update. In order to avoid the vulnerability we described in section 2.5, nodes to update are selected from the view the user is permitted to see. This has the following implications:

-Users cannot perform write operations on nodes they cannot see.

-Since users express XUpdate operations by looking at their view, PATH parameter might include some node tests equal to RESTRICTED. Note that only the "selecting nodes" step is performed on the view. Thanks to their identifiers, corresponding database nodes are then retrieved and updated.

Let s be the current session user submitting the XUpdate operation. Let n be one of the nodes selected by PATH.

xupdate:rename: user s needs the update privilege on node n.

xupdate:update: user s needs the update privilege on the child node of node n.

xupdate:append: user s needs the insert privilege on node n.

xupdate:insert-before: user s needs the insert privilege on the parent of node n. xupdate:insert-after: user s needs the insert privilege on the parent of node n.

xupdate:remove: user s needs the delete privilege on node n. Before defining the link axioms allowing us to derive the new database after an update, we need to consider the following issues:

-Each XUpdate operation may address several nodes via the PATH parameter.

Depending on the privileges held by the user submitting the operation, the XUpdate operation may succeed for some nodes and fail for others. -Let us consider an xupdate:rename operation addressing a node n. Let us assume node n is shown in the user's view with a RESTRICTED label. Since renaming node n would update the original label that the user is not permitted to see, we enforce that nodes which are shown with RESTRICTED label cannot be updated. -Let us consider the xupdate:update operation. This operation requires that the user holds the update privilege on the child of each selected node n. In fact, the xupdate:update operation on node n is equivalent to the xupdate:rename operation on the child of node n. Therefore, the child of node n has to belong to the user's view with its original label, that is, the user needs to hold the read privilege on node n. -Let us consider an xupdate:remove operation addressing a node n. If the user removes node n then he actually deletes the subtree of which node n is the root. Some of the nodes which belong to that subtree may not be visible (i.e. may belong to the user's view). Shall we reject the operation if some nodes of the deleted subtree do not belong to the user's view? On one hand, it would preserve the integrity of data the user is not permitted to see. On the other hand, it would reveal to the user the existence of data she is not permitted to see. In fact there is no definite answer to this question. This is typically a case of conflict between confidentiality and integrity. In this paper, we prefer to emphasize the confidentiality that is, the remove operation is accepted (see axiom 25). Link axioms allowing us to derive the new database after an update are given below. Note that for each axiom we use the xpath view predicate for selecting nodes to update from the view: xupdate:rename: We need to adapt axioms 2 and 3 as follows:

() ( ) ( ) () view db db new xpath , n, v logged(s) n v s, node n, v node n, v perm s, n, update ⎛⎞ ∧ ⎟ ⎜ ⎟ ⎜ ⎟ ∀∀∀ ∧ ¬ → ⎜ ⎟ ⎜ ⎟ ∧ ⎜ ⎟ ⎜ ⎝⎠ PATH (18)
Label of nodes which are not addressed by PATH or for which the current session user does not hold the update privilege are not updated.

) ( ) ( view db new n v s, xpath , n, v logged(s) perm s, n, update node n, ∀∀∀ ∧ ∧ → NEW PATH V ) (19)
Label of nodes which are addressed by PATH and for which the current session user holds the update privilege are updated to V NEW . xupdate:update: We need to adapt axioms 4 and 5 as follows:

The tree to insert shall appear as the last subtree of each node selected by PATH for which the current session user holds the insert privilege.

The tree to insert shall appear as the preceding sibling subtree of each node n by PATH provided the current session user holds the insert privilege on the parent of node n. xupdate:insert-after: We need to adapt axiom 7 as follows:

( )

The tree to insert shall appear as the following sibling subtree of each node n selected by PATH provided the current session user holds the insert privilege on the parent of node n. xupdate:remove: We only need to adapt axiom 9: [START_REF] Weigel | The BIRD Numbering Scheme for XML and Tree Databases -Deciding and Reconstructing Tree Relations using Efficient Arithmetic Operations[END_REF] This formula says that nodes which are not deleted are the nodes which do not belong to a subtree that the current session user has the permission to delete and whose root is addressed by PATH.

⎛⎞ ′ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ′′ ′′ ∀∀∀ ∧ ¬∃∃ ∧ → ⎜ ⎟ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ′ ∧∧ ⎜ ⎟ ⎜ ⎝⎠ PATH

Conclusion

In this paper, we gave the formal definition of a secure XML database. We represented the database content, the query language, the modification language, the subject hierarchy, the security policy and the access controls.

All the logical formulae given in this paper are Horn clauses. Based on these clauses, we wrote a prototype in Prolog simulating a secure XML database. The prototype includes a small database, an XPath and XUpdate interpreter, a sample subject hierarchy, a sample security policy and the access control formulae. It can be downloaded from http://www.univ-pau.fr/~gabillon/xmlsecu. The purpose of this prototype was simply to validate the correctness of the axioms given in this paper. Currently, the prototype uses a simplified version of our numbering scheme [START_REF] Gabillon | A Persistent Labelling Scheme for XML and tree Database[END_REF].

The model in [START_REF] Damiani | Securing XML Documents[END_REF] addresses the problem of preserving the validity of the views with respect to the DTD of the original document. Indeed, if a required node in the DTD is not shown in the view the user is permitted to see, then that user can infer about the existence of such a hidden node. Their model does not include the possibility of protecting portions of DTDs. Therefore, they suggest applying a loosening transformation to the DTD so that the view becomes valid with respect to the loosened version of the DTD. Our model does not address this issue which actually belongs to the general problem of inference analysis. A DTD is nothing more than a set of integrity constraints. The security administrator might decide to make a (complex) analysis of possible inference channels which may arise because of inconsistencies between the policy applying to the integrity constraints and the policy addressing the data. Such an analysis is sometimes made for databases which require a high confidentiality level such as multilevel databases [START_REF] Cuppens | Logical Foundations of Multilevel Databases[END_REF]. In our model, if we use XML schema instead of DTDs then nothing prevents the owner of the schema from granting to other users the permission to see or partially see the integrity constraints. Indeed an XML schema is an XML document. However, the problem of closing inference channels which may arise because of inconsistencies between the policy addressing the schema and the policy addressing the instances is beyond the scope of this paper and remains word to be done.

Finally, let us mention that a number of works [START_REF] Mohan | Access Control for XML -A Dynamic Query Rewriting Approach[END_REF][32] [START_REF] Finance | The case for access control on XML relationships[END_REF] address the problem of protecting relationships between nodes. The model presented in this paper does not offer this possibility. We are, however, planning to include this feature in a future version of this model.

Fig. 1 .

 1 Fig. 1. View Access Control in[START_REF] Gabillon | Regulating Access to XML documents[END_REF]

Fig. 3 .

 3 Fig. 3. View Access Control in[START_REF] Gabillon | An Authorization model for XML databases[END_REF]

Fig.

  Fig. 4. XML document

  )) p p to each node: l is the level of the node in the tree. -(n,d) is the local code of the node. Pair (n,d) represents the n/d rational number. -(n ,d ) p p is the local label of the parent node. For a given level, local codes are unique.

  Fig. 5. Subject Hierarchy

  v s, node n, v logged(s) perm s, n, position perm s, n, read child n, n ' node n

(

  xupdate:insert-before: We need to adapt axiom 7 as follows: perm s, f, insert create _ number(n, n , insert-before, n '

  4. XML document

	Some numbering schemes are persistent [12][8][25]
			/
			/
	<patients>
	<franck>		n 1
	<service>		/patients
	otolarynology
	</service >	n 2	n 7
	<diagnosis> tonsillitis	/franck	/robert
	</diagnosis>	n 3	n 5
	</franck> <robert>	/service	/diagnosis
	…
	</robert>	n 4	n 6
	</patients>	text()otolarynology	text()tonsillitis

  We use the following three place xpath predicate to logically interpret XPath expressions: -, reads "node with label v identified by number n is addressed by path p"Since semantics of XPath is well known, axioms interpreting the xpath predicate are given in appendix only (appendix B).Updating XML data is still a research issue (e.g. see[START_REF] Tatarinov | Updating XML[END_REF][20][START_REF] Bruno | Extending XQuery with Transformation Operators[END_REF]). Today, XUpdate is a solution to update XML data. The reader may refer to[START_REF] Laux | XML Update (XUpdate) language. XML:DB working draft[END_REF] for a complete description of XUpdate.Throughout this section, we shall use the following notations: -From the logical point of view, whenever we update the database we obtain a new logical theory representing the updated database. Let db new be the new logical theory representing the updated database. -Let predicate db representing the predicate predicate in the theory db. Let representing the same predicate in the theory db XUpdate operation, we shall give the logical formulae that allow us to derive the theory db new from the theory db.

	( predicate xpath p,n,v db new ) For each	1	3	2	5	2	4	3	6 new .	5	7	1

child(n , /), child n , n , child n , n , child n , n , child n , n ,child n , n , child n , n ,…

3.5

XPath and XUpdate

  There are two XUpdate instructions for updating XML nodes: xupdate:update and xupdate:rename. xupdate:update can be used to update the content of existing element nodes. xupdate:rename allows attribute or element nodes to be renamed. Both operations need two parameters: the path PATH selecting the nodes to update and the new label V NEW . The following two formulae allow us to derive facts belonging to the new set F after an xupdate:rename operation. Label of nodes which are not addressed by PATH are not updated. Label of nodes which are addressed by PATH are updated to V NEW . Example: Let us consider the operation xupdate:rename which renames all nodes service in From formulae 2 and 3, we can derive the new set F:

		( ) n v, node n, v db ∀∀	∧ ¬	xpath	db	(	, n, v PATH	)	→	node	db new	( ) n, v	(2)
		n v, xpath ∀∀	db	(	, n, v PATH	)	→	node	db new	(	n,	NEW V	)	(3)
	department:
	-PATH = //service
	-V NEW = department
		(	) 12 (		)	(	3	)
	(	) 45 (						)	(	6	)	(	7	)

xupdate:rename: node(/,/), node n ,patients , node n ,franck , node n , , F node n ,otolarynology ,node n ,diagnosis , node n ,tonsillitis , node n ,robert ,

  There are three XUpdate instructions for creating XML fragments: xupdate:insertbefore, xupdate:insert-after and xupdate:append. xupdate:insert-before can be used to insert a new tree as the immediate preceding sibling of existing nodes. xupdate:insert-after can be used to insert a new tree as the immediate following sibling of existing nodes. xupdate:append can be used to insert a new tree as the last child of existing nodes. All these operations need two parameters: a path selecting some nodes and the tree TREE to insert. Let us assume node TREE be the twoplace predicate used to represent the tree to insert.

	( ) nv , n o d e n , v db ∀∀	→	n o d e	db new	( ) n , v

  There is one XUpdate instruction for deleting XML nodes: xupdate:remove. xupdate:remove can be used to delete existing subtrees. It requires one parameter: the path PATH selecting subtrees to delete.The following formula allows us to derive facts belonging to the new set F after an xupdate:remove operation.

	′′	1, 1 , 3, 2 , n == ′′	2, 3, 2 , 7, 3 , n	′′	=	2, 3, 2 , 8, 3 , n	′′	=	3, 7, 3 , 5, 2
	3.5.3 Deleting node operations
		() n v, node n, v db ∀∀	∧	( ) undeleted n	→	node	db new	() n, v

  {position, read, delete, insert, update} if user s holds the position privilege on node n then user s has the right to know the existence of n. if user s holds the read privilege on node n then user s has the right to see node n.if user s holds the insert privilege on node n then user s has the right to add a new sub-tree to node n. if user s holds the update privilege on node n then user s has the right to update node n (i.e. change its label). if user s holds the delete privilege on node n then user s has the right to delete the sub-tree of which node n is the root. Privileges should not be confused with operations. Operations need privileges to complete. For example, both xupdate:append and xupdate:insert-before need the insert privilege to complete.

  10, rule 11 and rule 12 state that doctors can pose/update/delete a diagnosis.

		1. rule(accept,read,//*,staff,10),
		2. rule(deny,read,//diagnosis/*,secretary,11),
		3. rule(accept,position,//diagnosis/*,secretary,12),
		4. rule(accept,read,/patients,patient,13),
		5. rule(accept,read,/pa	[ tients/descendant-or-self::* $USER ,patient,14) ]
	P=	( 6. rule deny,read,/patients/*,epidemiologist,15 ( 7. rule accept,position,/patients/*,epidemiologist,16 )	)
		8. rule(accept,insert,/patients,secretary,17),
		9. rule(accept,update,/patients/*,secretary,18),
		10. rule(accept,insert,//diagnosis,doctor,19),
		11. rule(accept,update,//diagnosis/*,doctor,20),
		12. rule(accept,delete,//diagnosis/*,doctor,21)

  Label of nodes whose parent is not addressed by PATH or for which the current session user does not hold both the update privilege and the read privilege are not updated.Label of nodes whose parent is addressed by PATH and for which the current session user holds both the update and the read privilege are updated to V NEW . We only need to adapt axiom 7:

	() n v s, node n, v db ∀∀∀	( logged(s) perm s, n, update perm(s, n, read) ) ( ) ( ) view view xpath , n , v child n, n ⎛⎞ ′′ ′ ∧ ⎟ ⎜ ⎟ ⎜ ⎟ ∧ ¬∃∃ ⎜ n v , ′′ PATH ⎟ ⎜ ⎟ ⎜ ⎟ ∧∧ ∧ ⎟ ⎜ ⎝⎠	(20)
	→	node	db new	() n, v
	n v n v s, xpath ′′ ∀∀∀ ∀ ∀	view	(	, n , v ′′ PATH	)	∧	child	view	( ) n, n ′	∧	logged(s)
	( perm s, n, update perm(s, n, read) ) ∧∧	→	node	db new	(	n,	NEW V	)	(21)
	n v n v n s, ′′′ ′ ∀∀∀ ∀ ∀ ∀	node	TREE	(	′′ n , v	)	∧	xpath	view	(	) , n, v logged(s) perm s, n, insert ( ) ∧ ∧ PATH
	( ′′ ′ ′ db new create _number(n, n , append, n '') node n , v →	)

xupdate:append:

This work was supported by funding from the French ministry for research under "ACI Sécurité Informatique

[2003][2004][2005][2006]. Projet CASC".

More precisely, it should read, "node identified by number x is a child of node identified by number y".

The procedure in section 3.2.2 describes the insertion of one single node. For the sake of simplicity, we did not give the rule specifying how identifiers are generated when there is a simultaneous insertion of several consecutive nodes at a given level (e.g identifiers n" 2 and n"

)

Appendix A

With the scheme defined in section 3.2, axioms to derive the child and the preceding_sibling relations are the followings:

The root node is the child of the document node From these child and preceding_sibling relations, we can derive all other geometry relations.

( ) ( )

x y, child x, y descendant x, y ∀∀ → () () ()

x y, preceding _ sibling x, y z preceding _ sibling x, z preceding _ sibling z, y immediate _ preceding _ sibling x, y ∀∀ ∧ ¬∃∧

→

We could easily define other tree geometry relations.

Appendix B

We give the logical interpretation of XPath expressions. The reader may refer to [START_REF] Clark | XML Path Language (XPath) Version 1.0[END_REF] for a complete description of XPath (version 1.0). Our interpretation is not complete although it covers a very large subset of the XPath language. We use the following three place xpath predicate to logically interpret XPath expressions: -

xpath p,n,v , reads "node with label v at position n is addressed by path p" In the following axioms, we assume that variables p and p' contain any path different from /.

( )

Path / addresses the document node. (  )

Path //* addresses all nodes. We can derive facts belonging to the position predicate from the following formula:

n l i, findall n , v, xpath p, n , v preceding _ sibling n , n , l length l, i 1 position p, n, i

The three-place findall predicate is a high-order predicate. However, its semantics is well known since it is an ISO standard Prolog predicate. For each n, findall creates the list l of all the n' such that, ) is true. In other words, findall creates the list of all the preceding siblings of n which are addressed by path p. The number of preceding siblings of node n is equal to the length of this list. length is also a built-in Prolog predicate: -, reads "the length of list l is k".

()


A Bonnecaze
email: alexis.bonnecaze@eurecom.fr.

P Liardet
email: liardet@gyptis.univ-mrs.fr.

A Gabillon
email: alban.gabillon@univ-pau.fr.

K Blibech

Improving Time Stamping Schemes: A Distributed Point of View

Keywords: Time Stamping System, Distributed System, One Way Accumulator, Hash Function, Denial of Service

Time stamping is a technique used to prove the existence of a digital document prior to a specific point in time. Today, implemented schemes rely on a centralized server model that has to be trusted. We point out the drawbacks of these schemes, showing that the unique serveur represent a weak point for the system. We propose an alternative scheme which is based on a network of servers managed by administratively independent entities. This scheme appears to be a trusted and reliable distributed time stamping scheme.

I Introduction

The advent of electronic commerce have made the security of communication a major concern. Many governments have chosen to communicate and conduct transactions with citizens, businesses, and other agencies in a secure online environment. The security requirements for electronic document exchange are to ensure the integrity of official communications, to protect constituent privacy, to authenticate people and processes and possibly, to control sensitive information.

Digital signatures help to provide ongoing assurance of authenticity, data integrity, confidentiality and non-repudiation. Time-stamping techniques allow us to certify that an electronic document was created at a certain date. This certification is mandatory for a lot of applications in various domains like patent submissions, intellectual property or electronic commerce.

Numerous time stamping schemes have already been proposed and implemented. The first time-stamping protocol was presented during Crypto '90 by Haber and Stornetta. One year later, Benaloh and de Mare proposed a formal definition for a time-stamping system based on a set of participants and three protocols [START_REF] Benaloh | Efficient Broadcast time-stamping[END_REF]. Since then, a lot of new schemes were proposed and their security analysed [START_REF] Massias | Time and cryptography Technical report[END_REF], [START_REF] Buldas | Time-stamping with Binary Linking Schemes[END_REF], [BulLip], [START_REF] Massias | Timestamps: Main issues on their use and implementation[END_REF], [Jus]. Most of them use the concept of trusted Time-Stamping Authority (TSA) which is supposed to be able to securely time-stamp an electronic document. The Network Working Group specifies, in the Internet X.509 PKI Time-Stamp Protocol (rfc3161), an Internet standards track protocol for time-stamping. This RFC describes the format of a request sent to a TSA and of the response that is returned. It also establishes several security-relevant requirements for TSA operation, with regards to processing requests to generate responses. According to this RFC, the TSA is required:

1. to use a trustworthy source of time, 2. to include a trustworthy time value for each time-stamp token, 3. to include a unique integer for each newly generated time-stamp token, 4. to produce a time-stamp token upon receiving a valid request from the requester, when it is possible, 5. to only time-stamp a hash representation of the datum.

As the first message of this mechanism, the requesting entity (called here the client) requests a time-stamp token by sending a request to the Time Stamping Authority (TSA). As the second message, the Time Stamping Authority answers by sending a response to the requesting entity. The TSA must sign each timestamp message with a key reserved specifically for that purpose. A TSA may have distinct private keys, e.g., to accommodate different policies, different algorithms, different private key sizes or to increase the performance.

Most of the protocols use the concept of trusted third party even though it may be difficult to build a third party server that can be trusted. Indeed a server may be corrupted or victim of denial of service attacks (DoS). Moreover, the problem may not have a malicious origin but a hardware or software origin. As we will see in the next section, one of the aim of existing protocols is to prevent the server from failing.

In fact, we claim that time-stamping schemes relying on a unique third party server, cannot be trusted. Therefore our objective in this paper is to propose a time-stamping scheme using a multiserver architecture. Our protocol can be shortly described as follows: The protocol uses n third party servers. For each timestamping request, k servers among the n servers are randomly chosen to process the request. These k servers are said to be the active servers. The security of our protocol depends on the number n of servers and on the number k of active servers.

The paper is organized as follows. Section 2 describes existing protocols and their security. The main drawbacks of these protocols are pointed out and we formalize the notion of accumulated functions which are used in some linking schemes. In Section 3, we give the required properties of our model. In Section 4, we analyse the "k among n" scheme: among the n servers of the system, only k are chosen at random to handle a given time-stamping request. Our time-stamping scheme is presented in section 5 and finally we propose a new random generator to obtain k servers out of n.

II Existing protocols and their security

The International Organization for Standardization edited a draft which mainly describes a general model on which time-stamping services are based. This work is divided into three parts (ISO/IEC 18014 Parts 1 to 3): the framework, mechanisms producing independant tokens and mechanisms producing linked tokens. Entities involved in a time-stamping scheme are a time-stamping authority (TSA) which is a trusted third party, a requester and a verifier. A TSA provides evidence that a document existed at a certain date. The requester is the entity applying for a time-stamp token and the verifier is the entity confirming the validity of the token.

In this paper, we classify time stamping schemes into three classes: simple, linking and distributed schemes.

II.1 Simple schemes

In the simple scheme, the time-stamping protocol can be described as follows:

• An entity (the time-stamping requester) who wishes a time-stamp token regarding document D transmits to the TSA a request message including a hash value h(D) of D.

• The TSA generates a time-stamp token T S which includes at least the values h(D), T, S and ID, where T represents the time, ID the identifier of the authority, and S the autority's signature on data that includes h(D), T, ID.

• The authority sends T S to the requester.

During the verification process, a verifier has to compute the hash value of D and compare it with the value h(D) included in T S. The verifier also verifies the signature S.

It is important to note that the time-stamp does not include any information regarding an other timestamp. Thus the security of the method depends on authority's reliability. Nobody can detect a possible alteration of the token made by a malicious TSA. Different services are using a simple time-stamping scheme. Among them, the french company "La Poste" (its time-stamping service is developped by Keynectis), or some services available from Internet (like OpenTSA, e-timestamp or authentidate).

II.2 Linking schemes

Linking schemes have been developped in order to be able to detect fake time-stamps produced by a malicious TSA. In its simpler configuration, the method consists in linking the tokens chronologically, forming a chain [START_REF] Haber | How to Time-Stamp a Digital Document[END_REF]. It means that data related to the preceding tokens are included in the current token. The TSA may be implemented so that it maintains a database with two sequences of values, the A values and the S values. For a given time-stamp request at time T (i), the TSA computes a time-stamp info object which includes time value, hash of the document, serial number and TSA name. Then it computes the following two values:

• A(i), computed by hashing the timestamp info object, and

• S(i), computed by hashing over inputs A(i), S(i -1) and possibly multiple other previous values S( j), j < i -1.

The TSA adds A(i) and S(i) to its database of A and S values. It then generates the timestamp token, encapsulating in a digested data object the timestamp info object and the values used for computing S(i). The timestamp token is returned to the requester over a channel providing data integrity and origin authentication (for example, by using keys that do not need to last longer than the transaction lapse).

Periodically (every day or week), a token is published on an unalterable and widely witnessed media like a newspaper. The process of publication must be done in an authenticated manner.

The verification protocol consists in the following steps. First, recomputes a series of hashed values starting from the preceding published value. check whether the value A(i) contained in the time-stamp token matches the time-stamp info object. Then try to reconstruct S(i) from A(i) and S(i -1) (and possibly more S values). The value S(i) must be the one of the TSA's database. After having compared the claimed linking information with the recomputed value, the recomputation goes on to the next published value. The verification succeds when the next published value is correct. Thus the verification is sandwiched by two publications.

This scheme offers the following advantages:

• The publication provides us with an absolute time.

• After a token has been published at time t, the server cannot forge a fake time-stamping token former to time t.

• Since tokens are linked in a chronological chain, one can chronologically order the requests submitted between two publications.

However, this scheme has the following drawbacks:

• The publication step is costly and not convenient.

• Before the next publication, the server can tamper the tokens which have been issued since the last publication.

• The entire chronological chain must be stored for verification.

• Finally, centralized systems are very vulnerable to Denial of Service attacks.

In order to reduce the amount of information to be stored, most of the protocols use a binary tree structure also called Merkle Tree (recall that a Merkle Tree is a construction introduced by Ralph Merkle in 1979 [START_REF] Merkle | Secrecy, authentication, and public key systems[END_REF] to build secure authentication and signature schemes from hash functions). These methods allow us to reduce to a logarithmic factor the amount of information to be stored. They use the notion of round: a round can be a given number of requests, a period of time or a combination of both. During a round r, the TSA receives a certain number of requests (say x ′ ) and constructs a tree using hashes functions (like SHA-1 or MD5). Hashes of documents H 1 . . . H x ′ represent the leaves of the tree. However, in order to make the tree balanced, the number of leaves must be a power of 2. Let l be the smallest integer such that x ′ ≤ 2 l and let define x := 2 l . Then, H 1 . . . H x represent the leaves of the tree where H x ′ . . . H x are some "padding" values used to obtain the required number of leaves. At the first step, TSA makes x/2 pairs from these leaves and hashes them to obtain

H (2i+1)(2i+2) := h(H 2i+1 ||H 2i+2 ), for i = 0 . . . x/2 -1.
where the function h represents a hash function and || represents the concatenation. More generally, at step j, the TSA makes x/(2 j ) pairs by the same process, obtaining

H ((2 j )i+1)((2 j )i+2)((2 j )i+3)...((2 j )i+2 j ) := h(H ((2 j )i+1)...((2 j )i+2 j-1 ) ||H ((2 j )i+2 j-1 +1)...((2 j )i+2 j ) ),
where i = 0 . . . x/2 -1. At step Log 2 (x), TSA computes by the same way the Root Hash Value of the round r: RHV r and at step Log 2 (x) + 1, TSA obtains the token of the round r: T S r := h(T S r-1 ||RHV r ), where T S r-1 denotes the time-stamp token of round r -1. Figure 1 Step 1

Step 2

Step 3=Log 2 (3)

ST r-1 ST r

Round r

Fig. 1: Simple binary tree structure time-stamp of H i includes the date T i , the identity of the token ID i , the hashed document H i to be timestamped and L i which contains the values used for computing RHV r from H i . For example L 1 must contain the values H 2 , H 34 , and H 5678 . The TSA adds T S r to its database and Periodically publishes the the tokens of the rounds. Note that this scheme does not allow to know the order of requests processed in a same round. Depending on the implementation, T i may not be exactly equal to the time of the round.

The verification is as follows: first, check whether the hash of the document equals the value H i included in the time-stamp. Second, check the consistency between the value T S r stored in the TSA's database and the one generated from the time-stamp token.

There exist some other schemes based on trees which are slightly different like the one proposed by Buldas et al. [BulLipSch2000]. This scheme uses a special tree called threaded authentication tree which makes the time-stamping protocol more complex. The aim of this scheme is to provide a relative datation of documents. Time-stamp tokens do not include a time parameter but an evidence of their chronological order. They provide two informations: the identity of the round they belong and their order in this round. The verification procedure consists in deciding, given two time-stamp tokens, which has been generated first. As usual, hash values of documents and signatures must be checked and some values are to be reconstructed and compared to the ones included in the token and the ones published in a newspaper. Thus, a verifier does not have to communicate with the TSA in order to carry out the verification.

Notice that a scheme using a balanced binary tree is not efficient when the number of documents is not close to a power of 2. The worst case being reached when this number is 2 n + 1. Even though linking schemes do not have to use a tree structure, it is hard to find in the literature an other structure. In fact, tree structure is not always accurate and efficient. This is the case when the number of time-stamped documents is very small while the frequency of publication is very low (typically a week). In that case, the accuracy of the time-stamp may not satisfy the client who wishes an absolute datation.

Recently, Blibech et al [START_REF] Blibech | Authenticated dictionary based on Skip Lists for time stamping systems[END_REF] proposed to use a new structure called skip-list (originately developped by Bill Pugh [START_REF] Pugh | Skip Lists: Skip lists: A probabilistic alternative to balanced trees[END_REF] as an alternative to balanced trees). A skip-list is a probabilistic data structure that can be used in place of a balanced tree. Algorithms for insertion and deletion in skip lists are simpler and faster than equivalent algorithms for balanced trees.

Apart from the preceding schemes, there exists an other linking scheme which is based on the use of accumulator functions [START_REF] Benaloh | One-Way Accumulators: A Decentralized Alternative to Digital Signatures Advances in Cryptology-EUROCRYPT'93[END_REF]. Accumulator functions represent a very interesting (algebraic) alternative to these above data structures. Using these functions, the verification process can be done in just one operation. Moreover, the amount of information that has to be stored does not depend on the number of time-stamped documents. For Benaloh and de Mare, accumulator function has two properties. It is a one way function which is quasi commutative. A function h : X ×Y → X is quasi commutative if for all x ∈ X and for all y 1 , y 2 ∈ Y , h(h(x, y 1 ), y 2 ) = h(h(x, y 2 ), y 1 ).

In this paper, we prefer to define a one way accumulator in the following way: Let Λ and E be two sets and define a map F : E × Λ → E, called a kernel accumulator which defines the following two dual families of maps

T y : E → E x → T y (x) := F(x, y) and x T : Λ → E y → x T (y) := F(x, y).
Note that x T is defined to be a one way function. For any word a = a 1 . . . a s , a i ∈ E, we set

T a = T a 1 •• • ••T a s .
Suppose that l requests r 1 , . . . , r l have been received during round t. The global time-stamp token CG t of the round t is defined by

CG t := T ρ (t),
where ρ := r 1 • • • r l , and the time-stamp token corresponding to the request r i is defined by:

CG t,r i := T ρ r i (t),
where

ρ r i := r 1 • • • r i-1 r i+1 • • • r l .
Hence, CG t,r i is the accumulation of all the requests but r i . The verification is very simple: the verifier just has to check whether the following equality holds

CG t = T ρ r i • T r i (t).

A. Bonnecaze et P. Liardet et A. Gabillon et K. Blibech

For time-stamping purposes, modular exponentiation is the only used accumulator function. This is so because no better function has been found since then. The scheme can be described as follows: first, an integer s has to be selected and agreed by all parties (this value plays the role of an RSA modulus, and can be defined according to the recommandations of [START_REF] Benaloh | One-Way Accumulators: A Decentralized Alternative to Digital Signatures Advances in Cryptology-EUROCRYPT'93[END_REF]). Then a started value x 0 has to be chosen. This value may possibly be a representation of the current date. Let us now define x = x 2 0 mod s. Using the same notations as above, we define T r i (x) := x r i mod s. In particular, we must have (r, φ(s)) = 1, where φ denotes the well known Euler function. Notice that x T : r i → x r i mod s plays the role of a one way function since finding r i is finding the discrete logarithm of x T (r i ) = x r i mod s which is known as a hard problem. Moreover, the equality x ab = x ba mod s also holds. With the previous notation, let us define the values z := ∏ x j=1 r j and z i := ∏ x j=1 r j /r i . Then, the global and partial time-stamp tokens are CG t := t z mod s and CG t,r i := t z i mod s. The equation used for verification is now

CG t = (CG t,r i ) r i mod s.
A party who would like to demonstrate the correctness of the datation needs only produce the values z and z i . In their paper, Benaloh and de Mare discuss the security of such a method. They conclude, saying: the only claim which we can make about forgery is that a user cannot produce a valid time stamp for a document that was not anticipated at the time indicated by the stamp. They also notice that forging unanticipated documents is infeasible. An important drawback of the scheme is that the generation of the RSA modulus must be done by a trusted third party.

Protocols based on simple binary tree have been really used in existing projects or services. Academic or national projects abroad tended to use linking protocols as follows.

• TIMESEC (Federal Office for Scientific, Technical and Cultural Affairs in Belgium: 1996-1998) developped a linking protocol using tree structure with hash functions such as SHA-1 and RIPEMD-160.

• Cuculus (Estonia: 1997) proposed a linear linking protocol based on hash function and digital signature.

• PKITS (Public Key Infrastructure with Time Stamping Authority is a project of European Trusted Services, 1997-1998) deploys a linking protocol in which not a single but multiple TSAs operate. Each of the TSAs periodically sends its linking information to an other randomly selected TSA in order to obtain a time-stamp of the linking information. Digital signature is not used.

Generally, commercial services use simple protocols. Note however that the protocol of Digital Notary (Surety.com, USA: 1992-) is a linking protocol based on a tree structure. All these methods, based on Merkle tree, take aim at preventing the TSA from forging a time-stamp. If a TSA is willing to maliciously alter a certain time-stamp, it has to alter all the tokens related to it. However, the TSA may be the victim of a denial of service attack or of a breakdown of hardware/software origin. It therefore represents a single point of failure in the scheme. Moreover, these schemes may not be scalable and may not provide a satisfactory time granularity. Reducing the size of a round may increase the cost of a token.

II.3 Distributed scheme

Unavailability and loss of data problems can be solved using a multiserver scheme. Hence, multiserver time-stamping schemes represent a very interesting alternative to mono-server schemes even though they have not been studied a lot. Distributed schemes are composed by a set of servers which may be managed independently. They are more robust against breakdowns or network attacks. Moreover, depending on the scheme, the capacity of the system in term of number of requests may be improved. The idea of using a distributed system is not new. A distributed solution to archive documents has been studied in [START_REF] Maniatis | Enabling the Long-Term Archival of Signed Documents through Time Stamping Computer Science Department[END_REF] and distributed time-stamping systems have also been studied, for example in [START_REF] Benaloh | Efficient Broadcast time-stamping[END_REF], [START_REF] Haber | How to Time-Stamp a Digital Document[END_REF] or [START_REF] Takura | A Secure and trusted Time Satmping Authority[END_REF]. However, these studies were neither able to design a secure and efficient system, nor able to give a viable solution to the problem of denial of service.

Designing a distributed scheme, one has to solve specific problems like:

1. how to select the active servers?

2. how many servers should be selected?

3. should the servers be synchronized?

4. how to minimize the number of interactions between the servers? 5. how to construct the time-stamp from the received token fragments?

6. how to minimize the size of the time-stamp? (this size should not depend on the number of servers)

In Section V, we propose a protocol which represents a solution to these problems. More generally, we think that modern cryptography has the potential to provide efficient solutions to some of the above questions. This will probably be an attractive topic of research in the near future.

III Design requirements

Our aim is to design a multi-server time-stamping system which has to meet the following requirements:

1. resistance against a Distributed Denial of Service (DDoS);

2. resistance against material failures;

3. robustness against an attack involving less than n/3 servers. It is known that any protocol can be made provably secure (without any cryptographic assumptions) if and only if less than one third of the involved parties are corrupted;

4. the security must not depend on a particular componant of the system; 5. the system has to deliver an absolute time with an a priori fixed error of ∆t; 6. the system must be robust, simple and with an efficient verification protocol.

IV k among n scheme

In this section, we discuss the security of a general scheme lying on a distributed network of n servers where only k servers are involved in the calculation of a particular time-stamp. In the next section, we present our distributed scheme which does not have the security flaws of the general scheme presented in this section.

The k servers are the active servers. They are randomly chosen. The two values n and k depend on the required security level.

The complete time-stamp, used to verify and to prove the datation, is built from the k time-stamping fragments delivered by the active servers. The number of active servers is defined in order to maintain the required security level as well as to minimize the traffic inside the network. The model has n servers. Among them, f are supposed to be failed (fs). Among these f servers, we assume that f m servers are in Malicious Collusion (MC). Their aim is to create time-stamps with the same incorrect time. Each of the other f e = ff m servers independently delivers a fake time-stamp without colluding. For a given document, active servers are randomly chosen in order to reduce the probability of DDoS: the attacker must attack the whole n to be sure to succeed. Following Requirement 4 , we assume that the number f of failed servers is bounded by n/3. Let us now focus on a configuration where k servers time-stamp a given document. Each of these servers issues a time-stamping fragment and a vote allows them to obtain a certified complete time-stamp: a complete time-stamp is certified when more than k/2 servers propose the same date t. Of course, two servers may correctly time-stamp the document with two different but very close values. There exist many solutions to solve the problem of determining t from a cloud of values. We may assume that two values represent the same date if they belong to a fixed range ∆t. Another solution is to ask the client to time-stamp its document locally and submit this time-stamp for acceptance to the distributed system. These methods do not affect the security analysis of the scheme.

Let us now analyse the probability that an attack succeed, assuming that the servers are chosen in a uniform way. The probability P 0 that the k servers use the f failed servers is

P 0 ( f ) := n-f k-f n k (k ≥ f ).
However, all the f servers do not need to be used to forge a time-stamp. In the case where f m ≥ k/2, f m MC servers, when active, may contribute to forge a certified stamp. The probability that k/2 MC servers be active (k even) is

Q( f m ) :=    0 if k > 2 f m ; ( fm k/2 )( n-fm k/2 ) ( n k )
otherwise.

Simple calculation shows that this value is greater than P 0 if k > 2 f m . The graphs of Figure 2 compare probabilities P 0 ( f ) and Q( f ). They are calculated by Maple and are drawn continously because of the use of the Γ function instead of the factorial function (n! = Γ(n + 1)). With the following numerical values : For k < n/2, let us take the same values but with k = 12 instead of 18 (and f = 12). Calculation of Q( 12) gives a value close to 1/10. This scheme does not provide a satisfactory security since an attacker colluding with the MC servers could successfully backdate a document after a relatively small number of requests (about 10), without being discovered. This is due to the diffusion property of hash functions: a modification of one bit in the document leads to very different hashes. Therefore, the attacker may submit several times (almost) the same document until his request is processed by the MC servers.

n = 36, k = 18, f m = 12 = f , probability Q is about 3.1 10 -2 (P 0 = 1.4 10 -5 ). Note that P 0 (k/2) = Q(k/2). Obviously, P 0 ( f ) is stricly decreasing for 0 ≤ f ≤ k and Q( f ) is nondecresing in the range [k/2, . . . , n - k/2]. We have indeed Q m ( f ) Q m ( f + 1) = 1 - (n -1 -2 f )k/2 -f 2 + f ((n -k/2) -1) + (n -k/2) with -f 2 + f ((n -k/2) -1) + (n -k/2) > 0 for -1 ≤ f ≤ (n -1)/2.
Even though k among n scheme cannot be used alone to design secure time-stamping schemes, it can however be used in combination with linking methods. This is the subject of the next section.

V A time-stamping scheme

In this section, we propose a time-stamping scheme which is not vulnerable to the attack presented previously. The main parties involved in the scheme are the following:

• The client needs to time-stamp some documents.

• The box is given to each client. Depending on the required security level, it can either locally timestamp a document or randomly determine k active servers for a distributed time-stamping.

• The network of servers builds a time-stamp for each document, using time-stamping protocol S.

• The replicated database serves as a publication media. Each server of the network records the time-stamps of all the clients. Therefore each server holds an entire copy of the time-stamp database.

• The verifier runs verification protocol V in order to check the correctness of the time-stamp of a given document.

Next paragraph describes in details this scheme.

V.1 The time-stamping scheme

Each client c has a calculation box B to which she submits the document D to time-stamp. Two levels of security are provided. The time-stamping can either be performed locally by the box thanks to classical protocol (level 0), or by the distributed system of n servers (level 1). The box 1. calculates the hashed value of D, denoted h(D);

2. level 0 : locally time-stamps the document; end of the protocol. level 1 : determines randomly the k active servers;

3. signs the hash on behalf of the client c to form the request r := (h(D)) c ; 4. sends the request r to the k servers and waits for an acknowledgment from each of them.

When level 1 is chosen, the document D is time-stamped in accordance with a scheme which can be described in the following way. Time is discretized in rounds of length ∆t. Servers are synchronized regularly with reliable temporal sources. Each round is identified by an absolute date. For example, a round can be identified by: January 1 st 2005 at 9.05am. During a round t, each server receives a number of requests which is approximately the same if this number is large enough, since active servers are chosen randomly.

Suppose that the server S i receives p i requests. Let T S i denote the array formed by the p i requests during the round identified by t. At the beginning of the next round (identified by t + 1), the server S i signs the concatenation of t with T S i to obtain CS i,t . This is the stamp of the server S i for the round t. Define CS i,t := (T S i ||t) S i . This stamp is then broadcasted to every node in the network. Hence, each server knows the list of all the distinct x requests r 1 , . . . , r x , which have been submited during round t.

At the beginning of the next round (identified by t + 2), the server S i calculates the global time-stamp of the round t, CG t and records it in its database. CG t serves as a published value and is defined using one way accumulator functions that have been defined in subsection II.2.

The global time-stamp CG t of the round t is defined by

CG t := h(T ρ (t)),
where ρ := r 1 . . . r x . For each of its clients in the round t, the server calculates and signs the client timestamp, which is composed by the following values:

r r , t, CG t , CG t,r := T ρ r (t),
where r r is the request of the client to whom the stamp is to be sent, t is the round identifier, CG t is the global stamp and ρ r := r 1 . . . r r-1 r r+1 . . . r x . Hence, CG t,r is the accumulation of all the requests but r r . For a given document, each box receives k stamps. If all the requests are received by the server during round t, then all the k stamps are the same. However, it may be possible that some servers receive the request during round t while some others receive it during the round t + 1. This situation does not constitute a problem. Indeed, the proof that the document has been time-stamped during round t can be done as long as at least one client time-stamp has been created.

V.2 Verification scheme

Server databases are to be consulted by verifiers. Each database record consists of the values CG t , r r , and t. The verification of the time-stamp is as follows:

1. The request r has been involved in the construction of the global time-stamp if

CG t = h(T ρ r • T r r (t)).
2. If required, the verifier can check that CG t is the published value corresponding to the round t.

The accuracy of the datation depends on ∆t, on the time t ′ of propagation in the network. The range of error of the time-stamping is then less than ∆t + t ′ .

V.3 Robustness of the scheme

Attacks can be arranged into two categories:

• Attacks performed on existing time-stamps.

• Attacks performed during the construction of time-stamps.

The first type of attack consists in modifying the stamp while keeping its provability property. The success of such attacks depends on the robustness of the cryptographic functions that the system uses. The choice of the cryptographic functions is essential since time-stamps are to be valid for a long time (a few years). Let us now study the robustness of our scheme against attacks of the second category. The number of failed servers being less than n/3, an audit is always able to detect either an error or an attack. Backdating is impossible since the time-stamp would not be provable. Postdating (which can be seen as a form of denial of service) is possible. It requires that the k active servers, in malicious collusion, wait during λ rounds before handling the request. The probability of such an attack is not negligible. It is equal to P n,k := n/3 k / n k . With the following parameters: n = 24, k = 5, we obtain a probability of P 24,5 = 1.3 10 -3 . In order to reduce the consequence of this attack, the client is requested to send again the time-stamping request to k new active servers when no acknowledgement has been received after a time of ∆t. In this case, time-stamping is performed after a delay of ∆t and the precision of the time-stamp is reduced. This solution also holds for a pure DoS attack. This study is resumed in Table 1, where the last column represents, in case of successful attack, the difference between the correct date and the date of the time-stamp. Our protocol makes use of three types of cryptographic functions. Hash functions, signatures, and accumulators. Accumulator functions may be a simple modular exponentiation and the RSA modulus may be computed in a distributed way. In this case, using the same notation as above, we have T r r (x) := x r r mod s, and, CG t := h(t ∏ x j=1 r j mod s) and CG t,r := t ∏ x j=1 r j /r r mod s. Hence the equation used for verification is However, public key algorithms of RSA type being not efficient, accumulators based on this technique may not represent a viable solution. We recommand to use new algorithms like XTR (Efficient Compact Subgroup Trace Representation) or algorithms based on elliptic curves. In the case of elliptic curves, we use an additive group instead of a multiplicative group. We have T r (t) := r.t, where t is a point of the curve and r an integer. In this case, accumulators and signatures may use common parameters (same curve, same field, ...) in order to simplify the scheme. This study, furthermore very interesting, is outside the scope of this paper.

V.4 A mixed architecture

Our scheme is based on two main protocols. A local time-stamping protocol and a distributed one. This "mixed architecture" represents an interesting aspect of the scheme since it has some valuable advantages for practical applications: 1. in order to reduce costs, a company may want to locally time-stamp some documents and use the distributed protocol as a publication. In this case, the local protocol is a classical linking scheme and regularly, a round stamp is time-stamped and published;

2. a mobile device may use its local protocol while it is off-line and use the distributed protocol as soon as the connection to the system is available;

3. a client which the network has failed is able to time-stamp locally its document, waiting the connection to the distributed system; 4. a high secure system which is never connected to external systems may locally time-stamp its documents and regularly submit (in a secure way) a round stamp to the distributed system.

This list of applications is not exhaustive.

VI Random generators

Our scheme requests a generator to randomly select k distinct elements from a set E of n elements. Hence, we seek for a uniform generator, cryptographically secure and which satisfies some requirements particularly on the time of execution but also on the memory space. There exist severals generating algorithms. The simplest way to build such a uniform random generator is to select an element a 1 ∈ E and then select an new element, distinct from the preceding one, and repeat the process until we get k elements. We consider two classical cases:

• Each selected element is dropped from the set E. Consequently, we have to build k random generators of q symbols, with nk + 1 ≤ q ≤ n. This leads to a possible bias if we use a binary source generator.

• Selected elements are kept in the set. In this case, only one generator is used and the problem of possible bias concerns just this generator. However, it may take a lot of draws before we obtain k elements since in our model, k is not very small compare to n. Therefore, the probability to draw an already selected element is not negligible. Recall that the average number of draws is approximately n log n (see for example [START_REF] Knuth | The Art of Computer Programming[END_REF]).

One of the most famous generating algorithm is probably RANKSB of H. Wilf (see [START_REF] Nijenhuis | Combinatorial Algorithms for Computers and Calculators[END_REF] for details).

Its execution time, in average, is O(k), when k << n. But in our case, it will be around O(n) and execution time is not constant. Now, we propose an algorithm based on the notion of random walks on a finite group G. We refer the interested reader to the basic surveys of N. Sloane [START_REF] Sloane | Encrypting by Random Rotations[END_REF] and D. Aldous [START_REF] Aldous | Random walks on finite groups and rapidly mixing Markov chains[END_REF]. Let Q (m) be the distribution on G determined by the issue of the walk after m steps starting from the identity element. The initial distribution is Q (the probability to go from g to h in the group is Q(g -1 h)). Let U be the uniform distribution on G. When Q (m 0 ) > cU for an integer m 0 and a constant c > 0 (mixing case), the total variation distance d(m) := max A⊂G |Q (m) (A) -U(A)| between Q (m) and U tends to 0 at an exponential rate. But this majoration is generally not numerically useful. Consider the case where G is the permutation group of E. We choose the walk represented by the mixing of a deck of n cards by the following method: insert equally likely the topmost card within the deck. From [AlDi86] (Theorem 1), d(n log n + γn) ≤ e -γ for all γ > 0 and n ≥ 2. Let us apply this result for n = 24. An explicit version of Stirling formula gives d(1393+17s) ≤ 1 2 s 24! . This method does not provide us with a uniform generator, but the bias, represented here by the quantity d(m), can be made negligible by using enough computing power. Moreover, the fluctuation of performances of the binary source generator can be corrected by increasing the number of iterations.

VII Conclusion

In this paper, we described the different methods to digitally time-stamp a document. Then, we evaluated the k among n scheme and finally, we proposed a new scheme based on both notions of k among n and linking schemes. Our scheme represents an alternative solution to classical monoserver schemes. The level of security and reliability can be achieved by carefully adjusting the k and n parameters. The distributed publication allows us to avoid a costly publication in a (not electronic) newspaper. This scheme also offers the possibility to time-stamp documents in an off-line mode. In that case, the system may locally adopt a classical linking scheme and the publication would be done by the n servers when on-line. It may find applications where clients are not to be continuously connected to the system like, for example, in spontaneous networks.

  Fig. 2: Graph of ( m 9 )( 36-m 9 ) ( 36 18 ) and ( 36-m 18-m ) ( 36 18 ), m = 9...11

  illustrates the process for the case x = 8. A

				PH r
		H 1234				H 5678
	H 12		H 34		H 56		H 78
	H 1	H 2	H 3	H 4	H 5	H 6	H 7	H 8

† This work was supported by ACI Sécurité Informatique CHRONOS (http://acisi.loria.fr/).