Conclusion

• auditor 1: KN₆

• auditor 2: KN₇ and KLconf idential

• auditor 3: KN₄ and KLconf idential

• auditor 4: KN₂ EP1 EP2

EP3

EP4 EP5

EP6 EP7

EP1 EP2 EP3

EP4 EP5

EP6 EP7

EP1 EP2 EP3

EP4 EP5

EP6 EP7

EP1 EP2 EP3

EP4 EP5

EP6 EP7

(1) (2)

(3) (4)

Figure 4.4: An example of the access control policy

As shown in the example above, to grant access to only an assertion and its ancestor, we need to provide theKN andKL keys, however, the trace is stopped when the auditor reaches the assertions whose label key KL are not applicable.

4.5.6 Performance Analysis

In Appendix A, we performed experiments to measure the computation costs of the encryption mechanisms. As shown in Table A.2, the complexity of the en-cryptions are linear (with small growth) to the size of the provenance nodes. This result is predictable because the complexity of AES encryption (that is used in the experiments) is also linear to the size of the data. As of the complexity to access the provenance nodes, it is also linear to the number of nodes that are accessed by the auditors.

graph model of the provenance by allowing access policy definition to restrict the auditors tracing the relationships between the provenance nodes in the provenance graph. By combining the trace-based access control with multilabels method, we show that our access control method can be used to enforce the minimum access policy principle in the provenance recording systems. We also showed an alterna-tive access control mechanism by using encryption for better security.

A Signature Scheme for a

Sequence of Digital Documents

5.1 Introduction

A digital signature scheme (i.e., an RSA signature), takes inputs of a document and a signer private key, creates a small sequence of bytes that can prove the document is indeed originated to the signer, by assuming nobody except the signer can generate the signature for the document [83]. Anybody who have access to the correct public key (which is normally available and can also be authenticated publicly) can verify the authenticity of the document. The standard security model for a digital signature scheme is the existential unforgeability where we prove that the problem to forge the signature can be reduced to a known difficult/intractable problem.

5.1.1 Problem Description

In this chapter, we are concerned about the method to sign a sequence of digital documents (created by a party) that consists of many distinct documents (i.e., a sequence of messages M ={m₁, m₂, . . . , m_n}) that are created sequentially. The signature of the sequence of a digital documents should prove two facts about the documents: the authenticity of each member of the documents (i.e., whether mi

is the member of the sequence and truly created by the party), and the order of 101

the documents in the sequence (i.e., whether m_i is included before or after m_j in M). We identify two main differences of signing this type of documents with the signature scheme for a single document:

1. A new member of the sequence can be added later after signing the current (existing) members, so that one of the requirements is the signature for the sequence should also be created sequentially.

2. During verification of the members, we cannot assume that we have access to all documents in the sequence. We can only assume that we have access to the documents that will be verified.

5.1.2 Usage of the Proposed Scheme

An example of the usage of the signature scheme is to sign a data stream. The signer cannot sign all data in the stream in one procedure, so we need to sign the data sequentially. A possible charateristics of the data stream is that part of the data of the stream (because of several reasons) may be inacessible in the future.

Another usage of the signature scheme is to sign a large message or a large sequence of messages where some parts of the messages may be confidential, so that during verification, we need to provide a limited access to each user. We cannot create one fix signature for all documents (by combining all documents into a bigger document) because to verify a part of the document we need to have access to all parts the document. Although the user cannot access all parts of the documents, the users still need to prove these two facts (the authenticity of each member of the documents, and the order of the documents in the sequence) for the accessible documents.

5.1.3 The Basic Method and Our Previous Attempts

The basic method and our first attempt to sign the documents with the above requirements is first by simply appending a consecutive counter to each member of the sequence and then signing each consecutive member of the sequence with a standard signature. LetSignbe a standard signature scheme (for example an RSA signature) with a signing keyk andc_i be a counter that represents the order of the

documents in the sequence, we can generate the signature on m_i as Sign_k(m_ikc_i), so that the signatures on M = {m₁, m₂, . . . , m_n} be Sign_k(m₁k1), Sign_k(m₂k2), . . ., Sign_k(mnkn). This method can prove each member and also the order of the members without having access to other members of the sequence. However, there are some disadvantages of this approach:

1. To sign many sequences, the signer needs to include another information (i.e a unique id) to identify each sequence, and includes the id along with the counter. The problem is, in practice, it is error-prone and not natural to keep the information of each sequence, rather than signing the sequence directly.

The signer and the verifier should track the id of the sequence, otherwise, there are possibility the collision of theid. If the signature should be created in different systems, it is not easy to manage the id of each sequence.

2. The counter does not represent a “hard-proof” about the order of the mem-bers in the sequence, so that it is possible to sign the documents out-of-order by using out of order counters. For example, the signer may sign the first member, the third member and after then the second member. Without a trusted party who provide a correct consecutive counter, the signature cannot convince the verifier that the document signed as the order.

3. A rather minor disadvantage: we need to store a full signature for each member of the sequence. We cannot combine (i.e., by aggregating) the sig-natures without changing the characteristics of the signature: the possibility to verify a member without having access to the other members.

Our second attempt was by using the method similar to the scheme proposed in this chapter, but used the plain RSA as the primitive instead of the modified RSA with message recovery. However, the scheme could not be proved secure in Existential Unforgeability under Chosen Message Attack (EUF-CMA).

5.1.4 Contributions

In this chapter, we propose an alternative method to sign a set of digital documents where the signature scheme can prove two properties (the authenticity and the order of each member) of the documents without having access to all documents.

Our method is basically by employing signature-chaining and using a signature with message recovery as the primitive. Concretely, our contributions are:

1. We define a signature scheme for a sequence of digital document by including more features to the standard signature, so that it can be used to generate the signature sequentially and also verifying the order of the members in the sequence.

2. We propose a variant of the signature with message recovery originally pro-posed by Bellare et al.

3. We propose a signature scheme for the sequence of digital documents using a signature with message recovery as the primitive.

4. We propose the security model of the scheme in the form of Extended Ex-istential Unforgeability under Chosen Message Attack (EEUF-CMA) and Order Unforgeability Under Chosen Message Attack (OUF-CMA).

5. We prove the security of the scheme in the random oracle model.