Khabib Mustofa
email: khabib@ugm.ac.idyosuasir@gmail.com

Yosua Albert Sir

Early-Detection System for Cross-Language (Translated) Plagiarism

Keywords: translated plagiarism, sentence-based detection algorithm (SBDA), modified-SDBA, Google API

The implementation of internet applications has already crossed the language border. It has, for sure, brought lots of advantages, but to some extent has also introduced some side-effect. One of the negative effects of using these applications is cross-languages plagiarism, which is also known as translated plagiarism.

In academic institutions, translated plagiarism can be found in various cases, such as: final project, theses, papers, and so forth. In this paper, a model for web-based early detection system for translated plagiarism is proposed and a prototype is developed. The system works by translating the input document (written in Bahasa Indonesian) into English using Google Translate API components, and then search for documents on the World Wide Web repository which have similar contents to the translated document. If found, the system downloads these documents and then do some preprocessing steps such as: removing punctuations, numbers, stop words, repeated words, lemmatization of words, and the final process is to compare the content of both documents using the modified sentencebased detection algorithm (SBDA). The results show that the proposed method has smaller error rate leading to conclusion that it has better accuracy.

Introduction

Since it was first introduced, internet has brought several changes in human life, not to mention in academic environment. The existence of search engines makes students and teachers easy in finding materials for enhancing their knowledge, but in other point of view, it also facilitates any attemps of academic misconduct such as plagiarism.

Generally, academic misconduct and plagiarism may happen within several types:

1. copy-paste : copying part or the whole content of document 2. paraphrasing : changing the grammar, changing the order of constructing sentences, or rewriting the documents' content using synonim 3. translated plagiarism: translating part or the whole content of document from some language to some other language

The above approaches can fall into plagiarism if the writer does not provide correct citation or without mentioning the source document references ( [START_REF] Maurer | Plagiarism -a survey[END_REF]). Plagiarism type [START_REF] Maurer | Plagiarism -a survey[END_REF] or [START_REF] Kent | Web based cross language plagiarism detection[END_REF] can easily be done, and type (3) is little bit more complicated as the writer still needs to translate the source into different language. According to [START_REF] Maurer | Plagiarism -a survey[END_REF], several tools already exist to suspect or detect plagiarism type [START_REF] Maurer | Plagiarism -a survey[END_REF] or [START_REF] Kent | Web based cross language plagiarism detection[END_REF], such as : Turnitin, MyDropBox, Essay Verification (EVE2), WcopyFind, CopyCatch, Urkund, and Docoloc, while plagiarism of type [START_REF] White | Sentence-based natural language plagiarism detection[END_REF] was discussed in ( [START_REF] Kent | Web based cross language plagiarism detection[END_REF]), eventhough without revealing the quantitative accuracy. This paper will discuss a model and establishment of a system for early detecting translated plagiarism. The system works under the following constraints:

source document is written in Bahasa Indonesia.

the system is not a "silver bullet" to translated plagiarism. The output of the system is not an absolute judgement whether a palgiarism does exist. the algorithm used in comparing documents is based on sentence based detection algorithm to enhance the accuracy of detection process, the algorithm is slightly modified by incorporating synonyms of the words constructing sentences. This approach is carried out during stemming and lemmatization process.

Problem Formulation

Suppose there exists a suspect document D q , written in Bahasa Indonesia. On the other hand, there is also a set of vast amount of documents (reference documents), written in other language, Ω, available on the web repository. In this case, for simplicity, we will assume that all documents, ∀d i ∈ Ω, are written in English. When there exist statements in or part of a document D q , whose translation is similar in meaning to statements from some documents in Ω, how can we find and identify such statements, either in suspected document and also in reference documents? Using sentence-based detection algorithm, the target can be obtained by computing similarities which result from comparing each statements in suspected document, ∀s q ∈ D q , with all statements in all reference documents, ∀s r ∈ D r : ∀D r ∈ Ω. Theoretically, the above process is feasible, but in practice, special treatment should be incorporated as the size or dimension of Ω is big enough and also both the D q and D r are in different languages.

The following questions give us guidance in understanding the approach to be discussed further in this paper:

1. How is the system architecture to achieve the goal of detecting translated plagiarism?

2. How to translate D q (in Bahasa Indonesia) into D * q (in English) , where later the statements in D * q will be compared with statements in D r ? 3. How to reduce the size of Ω, for example by constructing Θ, where Θ ⊂ Ω, such that |Θ| ≪ |Ω| and ∀D x ∈ Θ, D x is a document which has similar (not necessarily all) content with D * q 4. How to calculate the similarity between ∀s q ∈ D * q and ∀s r ∈ D x : ∀D x ∈ Θ? Figure 1 shows the architecture of the system as the realization to answer the above questions.

Related Works

In general, the methods for detecting plagiarism on text documents can be categorized into two ways: document fingerprint comparison and full-text comparison [START_REF] White | Sentence-based natural language plagiarism detection[END_REF]. In the first approach, contents of the input documents (both suspected and reference documents) are converted into a more compact form, based on some predefined method, and then the detection process is carried out by comparing the fingerprints without comparing the whole contents.

Kent and Salim ( [START_REF] Kent | Web based cross language plagiarism detection[END_REF]) explored the first approach by forming 4-grams document fingerprinting and then comparing the fingerprints using Jaccard Distance. The result showed that the approach incurred disadvantages:

1. vulnerable against changes in words order or sentence order. Changes in words or sentence order, even just a small changes, may result in significant changes in fingerprints. 2. unable to detect small change that may be aded by plagiarist, such as word insertion or deletion

White and Joy ( [START_REF] White | Sentence-based natural language plagiarism detection[END_REF]) implemented the second approach by using sentencebased detection algorithm. In this method, the detection process on plagiarism between two documents is approached by calculating similarities of all pairs of sentences constructing the documents. This paper will discuss an approach which extends the second approach by adding feature of incorporating synonym to enhance the capability of finding sentences eventhough the sentences have been modified by changing some words with their synonyms. This means, compared to the method implemented by Kent and Salim ( [START_REF] Kent | Web based cross language plagiarism detection[END_REF]), the proposed approach will overcome the disadvantages of using fingerprinting. While compared to White and Joy ( [START_REF] White | Sentence-based natural language plagiarism detection[END_REF]) which implements sentence-based detection algorithm, the proposed approach will enhance the method by adding capability of invetigating synonims of words appearing in the sentences.

Methodology

Documents Similarity Measures

A document can be viewed as a series of tokens which may come in form of letters, words or sentences. If it is assumed that there is a parser capable of parsing the document contents, ignoring puctuation marks, formatting commands and capitalization, then the output of such parser is a canonical sequence of tokens [START_REF] Broder | On the resemblance and containment of documents[END_REF]. In his paper [START_REF] Broder | On the resemblance and containment of documents[END_REF], Broder introduced two metrics for measuring the similairty between documents A and B : resemblance (r(A, B)) and containment (c(A, B)), expressed as follows:

c(A, B) = |d(A) ∩ d(B)| |d(A)| (1) c(B, A) = |d(A) ∩ d(B)| |d(B)| (2) r(A, B) = |d(A) ∩ d(B)| |d(A) ∪ d(B)| (3)
where

-d(X) symbolizes set of token in document X -r(A, B) has value x ∈ , x ∈ [0, 1]. If r(A, B) = 1 then d(A) = d(B) -c(A, B) has value x ∈ , x ∈ [0, 1]. If c(A, B) = 1 then d(A) ⊆ d(B).

Sentence-Based Detection Algorithm

In order to apply this method, in which the comparison of all pairs of sentences from both document should be done, three steps must be performed:

1. Documents Preprocessing. This step includes: decapitalization, removing stop words, removing duplicate words 2. Computing Sentences Similarity. Assume that A and B are documents to be compared, comprised of sentences. we use the following symbols to shorten the upcoming discussion.

d(X) : a set of sentences in document X s x i : i th sentence of document X d(s x i ) : set of words comprising s x i , can also be denoted as s x i = {w x 1 , w x 2 , . . . , w x n } The measure of similarity can be computed from the following equations:

common words = 1 if w a i and w b j is identical 0 otherwise (4) SimScore(A, B) = |common words | × |d(A)| + |d(B)| 2 × |d(A)| × |d(B)| × 100% (5) SimSent(A, B) =    SimScore(A, B) , if SimScore(A, B) ≥ SimT h OR |common words | ≥ ComT h 0 , otherwise (6)
where ComT h represents Common Threshold and SimT h indicates Similarity Threshold 3. Computing Documents Similarity. Whenever the whole pairs of sentences from document A and B have been examined and sentences similarity scores have been obtained, the document similarity score can be calculated by summing all sentences similarity scores.

Modified Sentence-based Detection Algorithm

In the previous section, from equation ( 4), ( 5) and ( 6), it is clear that the exixtence of common words clearly contributes to the similarity scores. Suppose that within the two sentences to be compared there exist words form the first sentence having similar meaning with some words in the second sentence. How if we treat those pairs of words also as common words (with different weight of commonness)?

Assuming the above question works, we can derive the proof that changing some words in the first sentence into their synonyms will affect the similarity measures as long as the synonyms are in the second sentence.

Suppose the first sentence is the i th sentence of document A, denoted by s a i = {w a 1 , w a 2 , w a 3 , . . . , w a n }, and the second sentence is the j th sentence of document B, denoted by Reformulation of equation ( 4) and ( 5) by incorporating synonyms yields slightly different forms:

s b j = w b 1 , w b 2 , w b 3 , . . . , w b m . Then: 1. common OLD (s a i , s b j ) = s a i ∩ s b j 2. Syn(w) =synonym of w 3. Dif f (s a i , s b j ) = s a i -s b j 4. Dif f (s b j , s a i ) = s b j -s a i 5. SynW ORD(s a i , s b j ) = w k |w k ∈ Dif f (s a i , s b j ) ∧ Syn(w k ) ∈ Dif f (s b j , s a i ) 6. |common N EW | = |common OLD | + |SynW ORD(s a i ,
common words =    1 if w a i and w b j is identical 0.5 if w a i is synonym of w b j 0 otherwise (7) SimScore(A, B) = 2 × |common words | |d(A)| + |d(B)| × 100% (8)
In standard Sentence-Based Detection Algorithm, SimScore(A, B) is calculated using asymmetrical average method (equation 5), while in modified algorithm it is expressed using Dice method (equation 8).

The measure or score of documents similarity is then defined as combination of two asymmetric similarity scores [START_REF] Monostori | Comparison of overlap detection techniques[END_REF]:

Sim(A, B) = |d(A) ∩ d(B)| |d(A)| , |d(A) ∩ d(B)| |d(B)| (9)
The same approach is also used in [START_REF] Yerra | Detecting similar html documents using a sentence-based copy detection approach[END_REF] and [START_REF] Smith | Copy detection systems for digital documents[END_REF]. By using this form, two-way similarity score can be obtained and gives better picture of the relationship between the two document. Suppose we have two documents A and B, and

|d

Illustration of Algorithm Usage

In this section, we will look on how both methods (standard Sentence-Based Detection and Modified Sentence-Based Detection) are applied to the same dataset and see the differencces of their usages. Let us assume that document A and B have the following contents:

A : Face detection is one of the crucial early stages of face recognition systems are used in biometric identification. B : Face detection is one of the most important preprocessing step in face recognition systems used in biometric identification.

and assign similarity threshold 80, common threshold 6 and stop words {the, is, on, in, are}. After pre-processing step (decapitalization, removing stop words, removing duplicate words), we have:

1. SentenceObject A = {face, detection, one, crucial, early, stages, recognition, systems, used, biometric, identification} 2. SentenceObject B = {face, detection, one, most, important, preprocessing, step, recognition, systems, used, biometric, identification} 3. common words (A, A) = {face, detection, one, crucial, early, stages, recognition, systems, used, biometric, identification } 4. common words (A, B) = {face, detection, one, recognition, systems, used, biometric, identification}

5. Dif f (SentenceObject A , SentenceObject B ) = {crucial, early, stage} 6. Dif f (SentenceObject B , SentenceObject A ) = {most, important, preprocess- ing, step}.
By pairing each words in Dif f (SentenceObject A , SentenceObject B ) with each words in Dif f (SentenceObject B , SentenceObject A ) and consulting with translation service (such as Google Translate), additional information about synonym is obtained, SynW ord(A, B) = {important, step} (as "important" is synonym of "crucial" and "step" is synonym of "stage").

Calculating Similarity using Sentence-Based Detection Algorithm Based on the summary of preprocessing result above, the following scores can easily be obtained:

1. SimScore(A, A) = 11 × 11+11 2×11×11 × 100 = 100 and SimSent(A, A) = 100 2. SimScore(A, B) = 8 × 11+12 2×11×12 × 100 = 69.70 and SimSent(A, B) = 69.70 3. Similarity between A (as reference) and B is Sim(A, B) = 69.70 100 × 100% = 69.70%

Calculating Similarity using Modified Sentence-Based Detection Algorithm (SBDA) Based on the summary of preprocessing result above, the following scores can easily be obtained:

1. |common N EW | = |common OLD | + |SynW ord(A, B)| × (0.5) = |8| + |2| × (0.5) = 9 2. Based on Eq . 8, SimScore(A, B) = 2×9
11+12 × 100 = 78.26 3. Similarity between A and B is Sim(A, B) = 81.82% : 75% . This score can be interpreted as: 81.82% of sentences in document A can be found in document B, and 75% of sentences in document B can be found in A.

Implementation, Testing and Results

Modules Implementation

The system is built by extending and reusing some existing tools. Based on the architecture given at Figure 1, the following are modules developed and tested against some libraries:

1. Translation Module. As Google Service restricts the length of translated text, this module first splits long text into possibly several chunks of size maximum 4KB. Each chunk is sent to Google as a request and then the result is combined again to construct the whole document translation.

Testing and Results

For the sake of testing, all reference datasets (corpus) used in this research are deterministic, in the sense that the similarity degrees of the datasets have been apriori known.

1. Unit Testing. Reference Dataset used in this unit testing is taken from Microsoft Research Paraphrase Corpus, available at http://research.microsoft. com/en-us/downloads/607d14d9-20cd-47e3-85bc-a2f65cd28042. This dataset consists of 1725 pairs of sentences extracted from thousands documents, having been justified by human annotator to classify whether the pair of sentences is a paraphrase or not, resulting 1147 pairs are identified as paraphrases and 578 are not paraphrases. Based on the dataset, by adjusting several values of similarity threshold or common threshold, as depicrted in Fig. 2, the optimal value for similarity threshold is 50%, and common threshold is 4. 2. Integration Testing. For the integration and functional testing, ten documents from http://pps.unnes.ac.id are taken as samples. These samples document are processed, and then their similarity are calculated. Table 2 shows the result of similarity test, revealing the outperformance of the proposed method (modified SBDA) against the standard method.

Conclusion

Plagiarism is a serious misconduct in academic environment, thus it must be anticipated. The advancement in internet technology and services have been enabling users to more easily conduct plagiarism, but on the other hand, such condition also provides environment to easier check whether any attemp to plagiarism has happened. This paper has shown an approach to early detection of translated plagiarism. The prototype was developed by integrating online services, online repository and implementing modified sentence based detection algorithm. From the result, the following can be concluded:

1. The modified SBDA show higher accuracy compared to standard SBDA. This is indicated by smaller value of error-rate 2. The modification of standard SBDA is carried out by incorporating synonym conversion. Converting words into their synonyms will increase the count of common words between the documents compared, contributing to the better accuracy in document similarity measurement.

Fig. 1 .

 1 Fig. 1. Architecture of the Early-Detection System for Translated Plagiarism

  s b j )| × 0.5, as synonyms are considered common words with different weight of commonness (in this case 0.5) Hence (SynW ORD(s a i , s b j ) = {}) =⇒ (|common N EW | > |common OLD |)

  (A)| = 120 sentences, |d(B)| = 160 sentences and |d(A)∩d(B)| = 80 sentences, then the similarity score of document A and B, Sim(A, B) = 0.667, 0500 which can be interpreted that two third of sentences in A can also be found in B and half of sentences in B can be found in A.

Fig. 2 .

 2 Fig. 2. Accuration versus Similarity Threshold or Common Threshold

Table 1 .

 1 Two documents A and B are said to be identical if and only if the set of all tokens in A is subset of the set of all tokens in B and vice versa. -Assumed that the canonical sequence of token is in form of a sentence, |d(x)| indicates the number of sentences in document X (length/size of the set), and |d(A)∩d(B)| can be considered as common sentences found in document A and B. Example of documenst preprocessing to obtain resemblance and containment

	As an illustration, given that
	Document A : a rose is a rose is a rose
	Document B : a rose is a flower which is a rose
	Both sentences can be pre-processed as shown in table 1, and the value of
	c(A, B) = 87.5%), c(B, A) = 77.78% and r(A, B) = 70%
	A	B	d(A) ∩ d(B) d(A) ∪ d(B)
	a:3	a:3	a:3	a:3
	rose:3 rose:2 rose:2	rose:3
	is:2 is:2	is:2	is:2
		flower:1		flower:1
		which:1		which:1

  2. Document-Searching Module. Searching of documents on the web repository using search engine requires keywords. This module uses Named-Entity Recognition (NER) from Standford, available at http://nlp.stanford. edu/software/stanford-ner-2009-01-16.tgz. The tools will search, identify and extract entities of type person, location and organization. Those types are unique, difficult to plagiarize and suitable to be taken as keywords. This module will perform keyword extraction, look for documents in web repository (based on keywords extracted) and, then download the found PDF documents. 3. Text Extraction from PDF Documents. The contents of PDF documents just downloaded are then extracted using existing tools xpdf version 3.2. 4. Content Preprocessing. This module is responsible for: decapitalization, eliminating stop words and punctuation symbols, eliminating repitition of words and lemmatization.

Table 2 .

 2 Average Asymmetric Similarity and Error Rate between Modified and Standard Method

	Doc ID	Average Asymmetric Similarity Modified Standard Actual Modified Standard Error Rate
	1	56.82	42.66	68.18 129.16	651.53
	2	61.88	44.89	66.31	19.58	458.60
	3	51.24	31.50	65.22 195.30 1136.70
	4	51.23	17.45	70.93 388.29 2860.65
	5	48.04	29.15	70.22 491.73 1686.33
	6	56.97	27.34	68.37 129.85 1683.05
	7	60.58	49.09	80.77 407.84 1003.94
	8	53.35	31.82	69.77 269.45 1439.82
	9	63.20	60.24	72.22	81.45	143.64
	10	46.46	47.51	71.80 641.86	590.00
	Root Mean Square Error (RMSE)	16.60	34.14


Amril Syalim
email: amril.syalim@cs.ui.ac.id

Takashi Nishide
email: nishide@inf.kyushu-u.ac.jp

Kouichi Sakurai
email: sakurai@inf.kyushu-u.ac.jp

Supporting Secure Provenance Update by Keeping "Provenance" of the Provenance

Keywords: Provenance, Provenance Security, E-science, Data lineage

diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Provenance is a documentation of data history. It records the processes that produce the data and relationship between the processes. A simple example of the provenance is the documentation about how to produce a patient record in a hospital [START_REF] Álvarez-Napagao | Applying provenance in distributed organ transplant management[END_REF][START_REF] Deora | Navigating provenance information for distributed healthcare management[END_REF][START_REF] Hasan | Preventing history forgery with secure provenance[END_REF][START_REF] Kifor | Provenance in agent-mediated healthcare systems[END_REF]. The patient record contains the data about the medical treatment or medical test of the patient which is produced by the physicians and laboratory staffs in the hospital. In this case the processes to produce data are executed by the physicians or the laboratory staffs. A process may have relationships with the other processes, for example: to produce a medical treatment, a physician uses the data produced by another physicians (i.e. medical diagnosis) or data used by a laboratory staffs (i.e. a result of blood or urine test of the patient).

Provenance can be represented by a graph [START_REF] Miles | Extracting causal graphs from an open provenance data model[END_REF][START_REF] Paul | The Origin of Data: Enabling the Determination of Provenance in Multi-institutional Scientific Systems through the Documentation of Processes[END_REF][START_REF] Aldeco | Securing provenance-based audits[END_REF][START_REF] Miles | Extracting causal graphs from an open provenance data model[END_REF][START_REF] Braun | Securing provenance[END_REF], where the nodes represent the processes and the data while the edges represent relationships between processes. An example of the graph model for provenance is the open provenance model which is proposed as a standard for provenance [START_REF] Moreau | The open provenance model: An overview[END_REF][START_REF] Moreau | The open provenance model core specification (v1.1)[END_REF]. The open provenance model specification defines some types of the nodes (i.e. actor, process and artifacts), and some types of the relationships between the nodes. Some of the the important research problems with the provenance are related to security [21, 10-12, 19, 20]. The security problems are caused by malicious update and deletion to the provenance. For example in a hospital, if we allow update to the provenance and the patient record, there can be inconsistencies between provenance and data created by a physician with another physician or laboratory staffs. A physician A may decide a medical treatment based on the diagnosis created by physician B, or medical test produced by a laboratory staff C. If B or C updates/deletes the provenance of diagnosis or medical test, the treatment by A may be incorrect because it is based on the previous versions of the diagnosis or medical tests produced by B or C. If the patient who takes the medical treatment complains about a misconduct by A, A cannot refer to B or C to explain why he/she decides the treatment. In an extreme case, it is possible B or C may maliciously/intentionally try to frame A for a misconduct charge.

Problem Definition

As a history record, many researchers argue that the provenance should be immutable (no change is allowed in the history records) [START_REF] Braun | Securing provenance[END_REF][START_REF] Simmhan | A survey of data provenance in e-science[END_REF][START_REF] Moreau | The open provenance model core specification (v1.1)[END_REF][START_REF] Moreau | The open provenance model: An overview[END_REF][START_REF] Groth | Recording process documentation for provenance[END_REF][START_REF] Paul | The Origin of Data: Enabling the Determination of Provenance in Multi-institutional Scientific Systems through the Documentation of Processes[END_REF][START_REF] Muniswamy-Reddy | Foundations for Provenance-Aware Systems[END_REF]. However, without being able to update a submitted provenance, the provenance storage is always growing (indefinitely). In this paper, we try to address the problem on how to allow updates/deletes the provenance to save spaces on the storages, while keeping the provenance consistent. The methods are useful in the case the actors who produce the provenance honestly update the provenance for an accidental/unintentional errors and in the case the storage is limited. The main security requirement is: no actor is allowed to exploit the update/deletion features to do a malicious behaviors or avoid responsibilities for the data produced in the past.

Contributions

The idea of our solution is by keeping the "provenance" of the provenance, where using this method, we allow updates/deletions to the provenance but we keep the history of the previous versions of the provenance in the forms of the signatures of the previous versions. So that, even if an actor has updated the provenance and the data, the actor cannot reject the previous versions of the provenance and data. To save the spaces, we store the signatures in a tree similar to the Merkle-tree and combines the signatures using the aggregate signatures techniques. Using this method, for any number of updates the grow of signatures storage for the previous versions of the provenance and data is much smaller than the normal updates in the provenance (where we should keep all signatures and data of the previous versions).

Related Work

2.1 Hash/signature chain, stamping and countering

The integrity scheme to timestamp digital documents using hash/signature chain was first proposed by Haber el al. [START_REF] Haber | How to time-stamp a digital document[END_REF] . It uses a Trusted Timestamping Service (TTS) that issues signed timestamps and also links two timestamps requested consecutively. The TSS links two timestamps by storing the hash value of the first timestamp in the second timestamp. Any changes to the first timestamp can be detected by checking the hash value in the second timestamp. This method is applied by Hasan et al. [START_REF] Hasan | Preventing history forgery with secure provenance[END_REF] to a chain model of the provenance where the provenance is modeled as a chain. Aldeco-Perez et al. [START_REF] Aldeco | Securing provenance-based audits[END_REF] and Syalim et al. [START_REF] Syalim | Securing provenance of distributed processes in an untrusted environment[END_REF][START_REF] Syalim | Preserving integrity and confidentiality of a directed acyclic graph model of provenance[END_REF] extend the hash/signature chain to the provenance graph model.

To detect the problem of the deletion to a provenance node, Syalim et al. proposed countering provenance [START_REF] Syalim | Securing provenance of distributed processes in an untrusted environment[END_REF]. The basic idea is a Trusted Counter Server (TCS) assigns a unique consecutive counter number for each node in the provenance graph, so that any deletion to the nodes can be detected from the missing counter number in the nodes. To detect deletion of the newest node, the TCS should store the latest counter number in a trusted storage.

Aggregate Signatures

Aggregate signatures is a technique to combine signatures on many different messages into a short signature. Some aggregate signatures have restriction that they can only be verified if there is no duplicate messages or public keys. However, it is possible to develop a scheme that does not have any restriction [START_REF] Bellare | Unrestricted aggregate signatures[END_REF].

Aggregate signatures can be implemented using bilinear maps [START_REF] Boneh | Aggregate and verifiably encrypted signatures from bilinear maps[END_REF], that is with the requirement of the existence of a mapping between groups for example the map e :

G 1 × G 2 → G T where |G 1 | = |G 2 | = |G T | with bilinear (for all u ∈ G 1 , v ∈ G 2 and a, b ∈ Z, e(u a , v b ) = e(u, v) ab
) and non-degenerate (e(g 1 , g 2 ) = 1) properties. A particular aggregate signature scheme proposed by Boneh et al [START_REF] Boneh | Aggregate and verifiably encrypted signatures from bilinear maps[END_REF] is as follows: Key Generation the user picks random secret key x R ← Z p and computes the public key v ← g x 2 Signing to sign a message M , compute h ← H(M ), where h ∈ G 1 , and the signature σ ← h x . Aggregation for a set of signatures

{σ 1 , σ 2 , ..., σ k }, compute the aggregate sig- nature σ ← k i=1 σ i . Aggregate Verification for all users u i ∈ U with public keys v i ∈ G 1 and the original messages M i , computes h i ← H(M i ) and accept if e(σ, g 2 ) = k i=1 e(h i , v i ) holds.

Preliminaries

Definition

Definition 1 (Provenance definition). Provenance related to the data set D = {d 0 , d 1 , ..., d n-1 } stored in a database DB for n > 0 is a set of provenance nodes P = {p 0 , p 1 , ..., p n-1 } and a binary relation E recorded in a Provenance Store P S. A provenance node p i consists of an identification P ID, a process description A, a process executor CID, the list of references to a set of inputs {ref (I i )}, for I ⊆ D and a reference to an output ref (d i ) for d i ∈ D. E is a binary relation in P IDSET where P IDSET is a set of P ID of all provenance nodes. E represents the provenance edges such that for (x, y) ∈ P IDSET × P IDSET and for x = y the process documented in provenance node with P ID y takes the output of process documented in node with P ID x as its input.

In this definition, we store four kind of information about the process execution in the provenance: the description of the process, the information about the process executor, the list of the inputs and an output.

Participants in the provenance system

The provenance system consists of the following participants:

-A data storage DB, where the data is stored -A provenance storage P S, where the provenance of data is stored for a long term storage -Process executors C with identification CID is the actors who execute the process, produce the data, submit data to DB, and submit the provenance to P S -An auditor ADT , is the actor who checks the integrity of the provenance and data

The basic provenance recording method

A simple model of the provenance recording system is as follows. The process executor C i queries the inputs I ⊆ D from DB and a set of {P ID in }, that is the provenance ID of I. C i executes the process that produces the data output d i , creates the provenance node p i and a set of edges, stores d i to DB and submits provenance node p i and edges to P S. The provenance edges are a set of mapping from the P ID of provenance p i to the parents that produce I, so we write the edges as {P ID, P ID in }. We define the simple protocol as follows [Note: we use the index in to refer to the parents that produce the inputs I, for example P ID in is a P ID of the parent, C in is a process executor at the parent]:

DB → C i : I P S → C i : {P ID in } C i → DB : d i C i → P S : node = p i , edge = {P ID, P ID in } 3.

Aggregate Signature Aggr and T reeAggr

We define a function Aggr which aggregates the signatures of different messages created by one or many different parties into one signature. A function T reeAggr aggregates the signatures into a set of signatures where the number of element is less or equal to the total number of the original signatures. The method to aggregate the signatures using T reeAggr is explained in Section 5.

4 Integrity scheme for provenance by keeping "the provenance" of the provenance For a secure provenance recording, when querying inputs I and the provenance of the inputs P ID in , the process executor also queries the collection of signature of inputs, that is the signnode in all parent nodes. In the scheme, we include a new participant, a Trusted Provenance Mediator (TPM), which is a trusted party who mediates the provenance recording. We assume that this party is trusted and will not cheat for any purposes. The complete provenance recording protocol is as follows: The main difference of this scheme with the basic provenance recording method in Section 3.3 is we include signature chain to the provenance, by recording the signature of the node (signnode) and signatures of all edges that connect the node to the parents (signedge -represented by the parent signatures). The signatures are signed by the TPM before submitted to the provenance store P S (signtpm).

DB → C i : I P S → C i : {P ID in , Sign Cin (p in , d in )} C i → DB : d i C i

Provenance update: Allowing update in the signature chain

Update to a node by the same process executor is allowed, but we should keep the aggregate of the previous versions of the node. For example, C i updates p i to p i and d i to d i and no update to the edges, so that no change to signedge. This update will delete the previous version of p i , and change it to p i . However it records the signatures of the previous versions in the form of an aggregate signature.

C i → DB : U pdate(d i ) C i → T P M : U pdate(node = p i , edge = {P ID, P ID in }, signnode = Sign Ci (p i , d i ), signedge = {Sign Cin (p in , d in )}) T P M → P S : node = p i , edge = {P ID, P ID in }, signnode = Aggr{Sign Ci (p i , d i )}, Sign Ci (p i , d i )), signedge = {Sign Cin (p in , d in )}, signtpm = Sign T P M (signnode, signedge)
The second update by C i changes p i to p i and d i to d i and no change to signedge.

C i → DB : U pdate(d i ) C i → T P M : U pdate(node = p i , edge = {P ID, P ID in }, signnode = Sign Ci (p i , d i ), signedge = {Sign Cin (p in , d in )}) T P M → P S : node = p i , edge = {P ID, P ID in }, signnode = Aggr{Sign Ci (p i , d i ), Sign Ci (p i , d i ))}, Sign Ci (p i , d i )) signedge = {Sign Cin (p in , d in )}, signtpm = Sign T P M (signnode, signedge)
We can accept any number of updates, however we only store the signatures of the previous versions of the nodes whose outputs are used by at least one child node.

The case of updates of the parent nodes

In Section 4.2, we assume no updates to signedge which means that no change to the input used by the node. However, a child may update the parent to the newest outputs of the parent. In this case, the child should keep the signature of the previous version of the parent using T reeAggr. For example, C in updates p in to p in and d in to d in . C in does exactly the same update as described in Section 4.2. After C in updates the provenance and data, C i also wants to update the parent to the newest version. So, C i update signedge to {Sign Cin (p in , d in )}. The scheme to update the provenance in this case is as follows.

DB → C i : I P S → C i : {P ID in , Sign Cin (p in , d in )} C i → DB : U pdate(d i ) C i → T P M : U pdate(node = p i , edge = {P ID, P ID in }, signnode = Sign Ci (p i , d i ), signedge = {Sign Cin (p in , d in )}) T P M → P S : node = p i , edge = {P ID, P ID in }, signnode = Aggr{Sign Ci (p i , d i )}, Sign Ci (p i , d i )), signedge = {T reeAggr{Sign Cin (p in , d in ), Sign Cin (p in , d in )}}, signtpm = Sign T P M (signnode, signedge)
In this case, we aggregate all versions of signedge using T reeAggr.

Signature Verification

To verify consistency between a node and all of its children, the auditor ADT queries the signnode on the parent and all signedge(s) on the children. The ADT combines the signedge(s) to get an aggregate signatures of the parent and compares the result with signnode. A detailed example is described in Section 5.

Aggregating Signatures of Previous Versions of a provenance node using T reeAggr

In the provenance, we use the aggregate signature to save the spaces needed for storing the signatures of all previous versions of the provenance nodes. Rather than verifying the aggregate signatures using the messages and the public key of the signers, we verify the signatures by comparing the aggregate signatures stored at a node with the aggregate of all signatures stored at all children of the nodes (we cannot verify the signatures by checking the messages -the previous versions of the provenance -because they have been deleted to save the spaces in each update). The motivation to use T reeAggr is because each child may not store all versions of the parent. So, if we use normal aggregate signatures Aggr to save the spaces, and stores the aggregates in each child, we may not be able to combine the signatures to form a full aggregate of all versions of the parent. Using T reeAggr, at first we represent all versions of the parent in all leave nodes in the signature tree. The child can aggregate the signatures of two consecutive versions (even and odd) in the leave nodes and stores the aggregate in the parent of the leaves. The same method is applied for each level of nodes in the tree to combine the signatures into a smaller number of signatures stored in the nodes at the higher level until we cannot get two consecutive nodes to aggregate.

We give an example of the aggregation as follows. The node Q created by a process executor C has four versions: Q, Q , Q , Q , it has 6 children R, S, T, U, V, W . R and S use the output of the first, second and third versions of Q, while T and U only uses the output of the second version. V and W use the output of the third version of Q. After sometimes, the children nodes S, U and W update the parent version to the latest version (Q ).

In the above case, in Q, we store the aggregate signatures of the previous version of Q, that is Aggr{Sign C (Q), Sign C (Q ), Sign C (Q } and the latest signatures (Sign C (Q )). For each child, we store the T reeAggr of all the parent signatures of the child. So, that for each child we store the signatures as follows:

signedge R = T reeAggr{Sign C (Q), Sign C (Q ), Sign C (Q )} = Aggr{Sign C (Q), Sign C (Q )}, Sign C (Q ) signedge S = T reeAggr{Sign C (Q), Sign C (Q ), Sign C (Q ), Sign C (Q )} = Aggr{Sign C (Q), Sign C (Q )}, Aggr{Sign C (Q ), Sign C (Q )} = Aggr{Sign C (Q), Sign C (Q ), Sign C (Q ), Sign C (Q )} signedge T = T reeAggr{Sign C (Q )} = Sign C (Q ) signedge U = T reeAggr{Sign C (Q ), Sign C (Q )} = Sign C (Q ), Sign C (Q ) signedge V = T reeAggr{Sign C (Q )} = Sign C (Q ) signedge W = T reeAggr{Sign C (Q ), Sign C (Q )} = Aggr{Sign C (Q ), Sign C (Q )}
To check the integrity of the child nodes, we aggregate the signatures in some child nodes and compare the aggregate with the aggregate signatures on the parent. The parent Q stores an aggregate of the previous and the latest versions in signnode = Aggr{Sign C (Q), Sign C (Q ), Sign C (Q }, Sign C (Q ). Because the aggregation can be performed incrementally we may aggregate the signatures into

signnode = Aggr{Aggr{Sign C (Q), Sign C (Q ), Sign C (Q )}, Sign C (Q )} = Aggr{Sign C (Q), Sign C (Q ), Sign C (Q ), Sign C (Q )}
We can compare the aggregate signatures on children with signnode stored at the parent by finding correct combination of the tree-aggregate on the children to form the same aggregate signature as stored in signode. Some examples of the correct combinations are shown as follows (note: we get Sign C (Q ) from signedge U ):

signnode = Aggr{signedge R , Sign C (Q )} = signedge S 6

Security Analysis

To show that a child is a node that uses an output of a version of the parent, the auditor ADT should query all signedge of all children of the node, find a combination of signatures that can reproduce signnode and compare with signnode on the parent. Using the scheme explained in the previous versions, it is always possible to find a combination of signatures in the children of a node which produce exactly the same signature as signnode.

Theorem 1. The Auditor ADT can always find a combination of the signatures singedge on the children which produce signnode in the parent.

Proof. The parent node stores the signatures of the latest version and the signatures of the previous versions of the node, except for the versions that do not have any children. So, that a signature of a previous version of the parent node is stored in at least one child node. Each child only aggregates the signature of two consecutive versions of the parent, so that there are only two cases of the signatures: (1) the signature is not combined with another signature, in this case the signature is stored in its original form (2) the signature is combined with another signature to form an aggregation of two signatures. If a signature σ i is not combined, we should find the other signature of the consecutive version in other children. Because the other signature should be stored in at least one other child, if the other signature is stored as the first case (no combination with other signature), we can combine with σ i to get a combination of two consecutive signatures. If the other signature has been combined, it should have been combined with σ i (the same signatures stored in the other child), so in all cases we can combine elements in all singedge in the children to form signnode at the parent.

Storage Requirements

The storage for signnode is always constant for any number of updates to the node, which is two signatures for each node (one signature for the latest version, and a signature for aggregate of signatures of all previous versions). As of the storage for signedge, in the best case, a child aggregates all the signatures of all versions of the parent, so it only needs to store one signature for each parent. The worst case is if the child does not uses any two consecutive versions of the parent, so we cannot reduce the number of signatures in T reeAggr. In this case, the number of signatures is n/2 where n is the number of updates to parent.

4. 1

 1 Provenance recording: Securing Provenance with signature-chain

  → T P M : Insert(node = p i , edge = {P ID, P ID in }, signnode = Sign Ci (p i , d i ), signedge = {Sign Cin (p in , d in )}) T P M → P S : node = p i , edge = {P ID, P ID in }, signnode = Sign Ci (p i , d i ), signedge = {Sign Cin (p in , d in )}, signtpm = Sign T P M (signnode, signedge)


Youngho Park

Chul Sur

Kyung-Hyune Rhee
email: khrhee@pknu.ac.kr

A Simplified Privacy Preserving Message Delivery Protocol in VDTNs

Keywords: VANET, VDTN, authentication, privacy preservation

In Vehicular Ad Hoc Networks (VANETs), because of high mobility of vehicles and frequent change of road segments, an end-toend communication path between moving vehicles may not exist unfortunately. As a promising solution to this challenge, for non-realtime constrained VANET applications, store-carry-forward paradigm is considered to deliver a message to a remote destination vehicle effectively through a socialspot in city road environments. So, the behavior of VANET can be modeled as Delay Tolerant Networks, and known as Vehicular Delay Tolerant Networks (VDTNs). Therefore, in this paper, we propose a secure message delivery protocol for protecting receiverlocation privacy in socialspot-based VDTNs since location privacy is one of critical security requirements in VANETs. To design a simplified protocol, we eliminate the use of pseudonym-based vehicle identification accompanied with a complex pseudonymous key management. Instead, we introduce an identity-hidden message indexing which enables a receiver vehicle to query a message whose destination is itself to the socialspot RSU without revealing its identity.

Introduction

Vehicular Ad Hoc Networks (VANETs) to support the Intelligent Transportation Systems and Telematics have recently become one of the promising wireless networking research areas. This trend is due to Dedicated Short Range Communications (DSRC) [START_REF]Dedicated Short Range Communications (DSRC)[END_REF] and the GPS-based navigation system incorporating with digital map. Typically, in VANETs, each vehicle equips with an on-board unit (OBU) communication device, which allows Vehicle-to-Vehicle (V2V) communication with other vehicles as well as Vehicle-to-Infrastructure (V2I) communication with a road-side unit (RSU). With these deployments, the VANET enables useful applications in our daily lives ranging from safety related to non-safety related, such as not only cooperative driving and probing vehicle data for better driving environment but also infotainment services by vehicular communications.

However, an end-to-end communication path between moving vehicles may not exist unfortunately because vehicles are constantly moving with frequently changing road segments which, in turn, makes network connectivity change. As a promising solution to this challenge, for non-realtime constrained VANET applications, store-carry-forward paradigm is considered to deliver a message to a multi-hop destination vehicle effectively by utilizing socialspot tactic [START_REF] Lu | Sacrificing the plum tree for the peach tree: A socialspot tactic for protecting receiver-location privacy in VANET[END_REF] in city road environments. Here, the socialspots are referred to the locations in a city road that many vehicles often visit such as intersections around famous shopping malls, restaurants, or cinemas. Hence, we can utilize an RSU installed in the socialspot as a relay node for packet forwarding in an opportunistic way [START_REF] Lu | Sacrificing the plum tree for the peach tree: A socialspot tactic for protecting receiver-location privacy in VANET[END_REF][8] [START_REF] Lin | STAP: A social-tier-assisted packet forwarding protocol for achieving receiver-location privacy preservation in VANETs[END_REF]. So, the behavior of a multi-hop VANET communication can be modeled as a Delay Tolerant Network known as Vehicular Delay Tolerant Networks (VDTNs), and packet forwarding protocols using store-carry-forward manner have been proposed [13][4].

As VANETs have received a lot of attention, security issues, especially privacy of vehicles or drivers, have become one of the most concerns for the successful deployment of VANET. In the same vein, socialspot-based VDTN applications must protect vehicle's privacy even though the locations of socialspots for message dissemination are known. That is, a security mechanism should be able to make it difficult as far as possible for an adversary who knows the locations of socialspots to infer which vehicle receives a message from the RSU at each socialspot.

Related Work

In order to protect receiver-location privacy in VDTNs, Lu et al. proposed socialspot-tactic privacy-preserving data forwarding protocols in [START_REF] Lu | Sacrificing the plum tree for the peach tree: A socialspot tactic for protecting receiver-location privacy in VANET[END_REF] and [START_REF] Lu | SPRING: A social-based privacy-preserving packet forwarding protocol for Vehicular Delay Tolerant Networks[END_REF], respectively. Those protocols are on the basis of pseudonym-based vehicle identification for anonymous message delivery and receiver authentication1 . Therefore, each vehicle has to have pre-loaded pseudonym-set for avoiding vehicle tracking by periodically changing its pseudonym on the road. However, they require complex pseudonym-based cryptographic key management depending on the number of pseudonyms pre-loaded, and all vehicles must know receiver vehicle's pseudonym to send a message to the receiver. What is worse, the protocol of [START_REF] Lu | Sacrificing the plum tree for the peach tree: A socialspot tactic for protecting receiver-location privacy in VANET[END_REF] does not provide message source authentication so this protocol cannot guarantee the non-repudiation if a malicious vehicle sends a bogus message.

On the other hand, the authors [START_REF] Lu | SPRING: A social-based privacy-preserving packet forwarding protocol for Vehicular Delay Tolerant Networks[END_REF] incorporated conditional privacy-preserving authentication based on group signature and universal re-encryption scheme with packet forwarding protocol for protecting vehicle's location privacy from packet analysis attack. However, when a receiver vehicle downloads a message it is required for the receiver vehicle to perform a complex mutual authentication process with RSU at the socialspot due to the much time consuming operation of group signature scheme.

Contribution and Organization

Based on the above observation, in this paper, we propose a socialspot-based secure message delivery protocol for preserving receiver-location privacy. The main design goal of this paper is to simplify the authentication process of a receiver vehicle to a socialspot RSU by eliminating the use of pseudonym-set. The contributions of this paper are summarized as follows.

-Instead of putting vehicles' pseudo-ID to identify a receiver vehicle in anonymous manner, we introduce an identity-hidden message indexing in order for a receiver vehicle to query the message bound for it to the socialspot RSU without revealing its identity. -We establish a unidirectionally authenticated secure message delivery channel from a sender to a receiver for VDTNs in which an interactive message exchange is not always possible because of no simultaneous end-to-end connection. -To simplify the authentication process between a receiver vehicle and a socialspot RSU without presenting receiver's identity-related information, we make the receiver vehicle be implicitly authenticated to the RSU by proving knowledge of the shared secret key with the sender.

To design the proposed protocol, we make use of ID-based non-interactive key agreement scheme [START_REF] Sakai | Cryptosystems based on pairing[END_REF][3] (but the IDs of vehicles are not included in message delivery protocol) to establish a secure channel between sender and receiver vehicles, and cryptographic hash function to generate an identity-hidden message index while binding a specific receiver vehicle at a socialspot is possible. The remainder of this paper is organized as follows. In Section 2, we introduce our system model and security goals considered in this paper. We present the proposed protocol and provide security analysis in Section 3 and Section 4, respectively. Finally, we conclude in Section 5.

System Model

We consider a VDTN environment which consists of vehicles equipping with OBUs, RSUs installed in socialspots and Trusted Authority(TA) for security management as shown in Fig. 1, respectively.

-TA is in charge of issuing ID-based private keys to the registered vehicles and RSUs, and provides public system parameters for security protocol. -Socialspots SS = {ss 1 , ..., ss l } are referred to as roads or intersections around where many vehicles will visit, for example, famous shopping malls, movie theaters, and such like. At each ss j ∈ SS, a huge-storage possessing RSU j subordinated by the TA is installed so that RSU j can temporarily store some messages to be forwarded to the receiver vehicles passing through the ss j . -Each vehicle v i ∈ V = {v 1 , ..., v n } registered to the system equips with OBU for V2V and V2I communications and cooperates with each other to deliver a message for a socialspot in store-carry-forward manner.

In those settings, message forwarding strategy from a sender vehicle to a destination socialspot can be divided into the following two methods.

-Direct carry and forward : If the sender vehicle passes the socialspot, the sender will carry the message and then forward it when it arrives on the socialspot. -V2V forward and carry : Some vehicles driving toward the socialspot will cooperate for store-carry-forward message delivery when the sender vehicle does not pass the socialspot.

As an example scenario, suppose that v s wants to send a message msg to v d which will visit socialspot ss 2 later in Fig. 1 In such a VDTN scenario, we consider the following security goals to design a secure message delivery protocol against a global passive adversary A. The adversary A can overhear V2V and V2I communications, but cannot compromise any vehicle (or RSU) and access the internal information of them. Thus, A tries to identify vehicles or to trace the location of a vehicle by packet analysis.

-Anonymous Channel : An adversary A cannot identify the message sender and receiver from eavesdropping on the message delivery protocol.

-Authentication : Only a valid receiver vehicle specified by a sender can retrieve the message whose destination is itself by authenticating itself to the RSU at a socialspot. -Receiver Privacy : Even though the location of a socialspot is known, it is hard for an adversary A to infer which vehicles retrieved messages at the socialspot.

Proposed Protocol

The proposed protocol consists of setup, message constitution, message forwarding, and message retrieving phases. Table 1 shows the notations and descriptions used in the proposed protocol.

Setup

Let G 1 and G 2 be the bilinear map groups with a prime order q, and P be a generator of G 1 [START_REF] Boneh | Identity-based Encryption from the Weil Pairing[END_REF], respectively. In the setup phase, the TA configures system parameters for bilinear map and issues ID-based private keys to the registered RSUs and vehicles as following steps.

1. TA sets a random number s ∈ Z * q as its master secret key, computes P 0 = sP , and configures public system parameters param={G 1 , G 2 , q, ê, P, P 0 , H 1 , H 2 }, where ê :

G 1 × G 1 → G 2 is a bilinear map, H 1 : {0, 1} * → G 1 and H 2 : {0, 1} * → Z *
q are cryptographic hash functions, respectively. 2. For each v i ∈ V and each RSU j at ss j ∈ SS, TA issues ID-based private keys SK v i = sH 1 (v i ) for v i and SK j = sH 1 (ss j ) for RSU j , respectively.

Message Constitution

When a vehicle v s wants to send a message msg to a receiver vehicle v d which will pass a socialspot ss j sometime, v s executes the following steps to make a packed message.

1. v s chooses a random number r ∈ Z * q and computes P s = rH 1 (v s ), |T ), and W = w -1 P , where k sd and k sj are non-interactively shared keys with v d and with RSU j , respectively. 2. Then, v s constitutes a packed message M to be forwarded to the destination socialspot ss j as follows: M = {ss j , I, P s , W, C|σ, chk}

k sd = ê(rSK v s , H 1 (v d )), k sj = ê(rSK v s , H 1 (ss j )), w = H 2 (k sd
-I = h(v d , ss j , T ) -C = Enc k sd (v s |v d |T |msg) -σ = Sig SK vs (v s |v d |T |msg)
-chk = M AC k sj (ss j , I, P s , W, C|σ) where σ is sender v s 's ID-based signature of [START_REF] Cha | Identity-based signature from gap Diffie-Hellman groups[END_REF], and chk is a message authentication code for integrity check by RSU j .

In step 2, the identity-hidden message index I implies the meaning of a receiver vehicle v d at a socialspot ss j , and will be used for a receiver vehicle to query a message for it in the message retrieving phase.

Message Forwarding

Once the message M is packed, M can be delivered to a destination socialspot ss j by using the forwarding strategy described in Section 2. At this phase, we assume a packet forwarding protocol with store-carry-forward manner, such as VADD [START_REF] Zhao | VADD: Vehicle-assisted data delivery in Vehicular Ad Hoc Networks[END_REF] and TBD [START_REF] Jeong | Trajectory-based data forwarding for light-traffic Vehicular Ad Hoc Networks[END_REF]. Note that the main goal of this paper is to protect receiver's privacy from an adversary, we do not consider compromising of vehicles and message forgery attack by an active adversary during the message forwarding.

When the message M ultimately reaches the RSU j at ss j , RSU j first computes shared key of v s as k sj = ê(P s , SK ssj ) from P s in M . Then, RSU j verifies chk = M AC ksj (ss j , I, P s , W, C|σ) under the key k sj . If chk is valid, RSU j stores {I, P s , W, C|σ} while a receiver vehicle related to the message index I requests the message as passing by it.

Message Retrieving

Fig. 2 shows the message retrieving protocol of a receiver vehicle at a socialspot. When a vehicle v d goes by a socialspot ss j on its way driving, v d can get a message M whose destination is itself as follows.

1. v d , as expecting a message for it on RSU j 's storage, generates its message index at ss j as I = h(v d , ss j , T ), then queries I to RSU j .

Analysis

In this section, we discuss the security of the proposed protocol. The security of the proposed protocol entirely depends on the non-interactive key agreement scheme and cryptographic hash function. We will focus on how the proposed protocol can fulfil our security goals under our adversary model.

Anonymous Channel

In the proposed protocol, the delivered message content {v s |v d |T |msg} from a sender v s to a receiver v d is encrypted under non-interactively shared key k sd , i.e., C = Enc k sd ({v s |v d |T |msg}). Hence, when we assume the secrecy of non-interactive key agreement scheme [START_REF] Dupont | Provably secure non-interactive key distribution based on pairings[END_REF], it is difficult for an adversary A to identify sender and receiver from eavesdropping on the message transmission. Even if A can know that the destination of the message is a socialspot ss j ,

A cannot capture the identities of vehicles which retrieve messages through the socialspot RSU j because no vehicle identity is presented to the RSU j . Therefore, the proposed protocol can guarantee the anonymity of message transmission.

In addition, Kate et al. [START_REF] Kate | Pairing-based onion routing with improved forward secrecy[END_REF] presented that they could construct an onion routing for anonymity network on the basis of non-interactive key agreement scheme. If we encrypt the packed message M again under key k sj instead of M AC ksj in Message Constitution phase, the path v s → ... → RSU j → v d can be regarded as an onion path based on Kate et al.'s observation.

Authentication

In order to obtain a message temporarily stored in a RSU j in Message Retrieving phase, a receiver vehicle must be authenticated to the RSU j which checks if the requesting vehicle is the designated receiver by a sender vehicle. In our protocol, for a vehicle v d to be authenticated as a valid receiver, v d should present the proof of knowledge W = H 2 (k sd |T )P for the secret key k sd shared with a sender v s . The consistency of the keys ê(rSK vs , H 1 (v d )) generated by v s and ê(P s , SK v d ) by v d can be proven as ê(rSK vs , H

1 (v d )) = ê(rH 1 (v s ), sH 1 (v d )) = ê(P s , SK v d ).
Only if the verification of ê(W, W ) = ê(P, P ) holds, RSU j will send {C|σ} to v d as regarding v d is the receiver who can agree with the message sender. Then, v d can recover original message {v s |v d |T |msg} by decrypting C, and authenticates the sender v s as verifying v s 's signature σ.

Receiver Privacy

As mentioned before, the proposed protocol does not put vehicle's identity for message transmission nor receiver's identity is given to the RSU j at a socialspot ss j in message retrieving phase. Instead, a receiver v d can be bound by identityhidden message index I = h(v d , ss j , T ) which is the result of cryptographic one-way hash function. Therefore, it is hard for an adversary A to decide which vehicle receives a message from I at the socialspot even though the location of the socialspot is publicly known.

Moreover, we can generate a different message index I ( = I) for different time period or different socialspot, i.e., I = h(v d , ss j , T ) for T = T , due to the functionality of cryptographic hash function. Hence, the proposed protocol can guarantee the unlinkability for a receiver vehicle because it is infeasible for A to distinguish that the given indexes I and I are linked to the same receiver.

However, one feasible attack for A is to prepare possible message index set I S from arbitrarily chosen vehicles identities V A = {v 1 , ..., v m } by A for a given time period T , and check if an I ∈ I S occurs at the socialspot ss j or not. If it occurs, then A can decide the matching identity v i ∈ V A such that I = h(v i , ss j , T ). For this scenario, let P r{k} be the probability that k among N V vehicles passing through the socialspot ss j for the given time period T are found by the index matching attack. Suppose that N R is total number of registered vehicles and N C is the number of elements in I S . The probability P r{k} can be represented as follow distribution:

P r{X = k} = N C k N R -N C N V -k N R N V , k ≥ 1
As a result, the probability that a target vehicle v d can be linked to I S is P r{k = 1}. Fig. 3 shows such link probability under chosen message index matching attack by A assuming N R = 10, 000 for evaluation. From this result, we can figure out that the link probability decreases as the number of vehicles N V passing through a socialspot increases. Therefore, we can conclude that putting a special area where many vehicles frequently visit in city road environments as a socialspot is helpful for privacy preservation for secure message delivery in VDTNs.

Conclusion

In this paper, we proposed a secure message delivery protocol with the help of socialspots in Vehicular Delay Tolerant Networks to provide anonymous message transmission and vehicles privacy preservation assuming a global passive adversary. To design a simplified protocol, we eliminated the pseudonym-based receiver vehicle identification accompanied with a complex pseudonymous key management. Instead, we made use of identity-hidden message indexing for a receiver vehicle to prevent vehicle's identity from being disclosed or linked by an adversary, and proof of knowledge for non-interactively shared key between sender and receiver to authenticate the receiver implicitly by a socialspot RSU.

In addition, we showed that it is infeasible for an adversary to link a specific vehicle to a message index at a socialspot.

Fig. 1 .

 1 Fig. 1. System model for socialspot-based VDTN.

Fig. 2 .

 2 Fig. 2. Message retrieving protocol of a receiver vehicle at a socialspot.

Fig. 3 .

 3 Fig. 3. Link probability for k = 1 under chosen message index matching by A.

. 1 .

 1 At time t 1 , v s asks v 1 which drives toward the ss 2 for forwarding the msg. 2. v 1 carries the msg and arrives on the socialspot ss 2 at time t 2 (t 2 > t 1 ), then forwards the msg to the RSU 2 . 3. When v d passes the ss 2 at time t 3 (t 3 > t 2 ) while RSU 2 stores the msg, v

d requests msg bound for it then RSU 2 provides v d with msg.

Table 1 .

 1 Notations and descriptions.

	notation	description
	SKi	ID-based private key of an entity i
	k ij	shared secret key between i and j
	T	valid time period of a message
	Enc k (•)	encryption under key k
	Dec k (•)	decryption under key k
	Sig SK i (•)	ID-based signature under signing key SK i
	V rf i (•)	ID-based signature verification for a given ID i
	h(•)	cryptographic hash function
	M AC k (•)	message authentication code under key k

When we say sender and receiver, they are end-to-end message source and destination vehicle in this paper, respectively.

This research was supported by Basic Science Research Program (No. 2012-0001331), and partially supported by Next-Generation Information Computing Development Program (No. 2011-0029927) through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology.


Nisreen Alam Aldeen

Gerald Quirchmayr
email: gerald.quirchmayr@univie.ac.at

Nisreen Alam

Enhancing Privacy Protection in Distributed Environments through Identification and Authentication-Based Secure Data-Level Access Control

Keywords: Privacy Protection, De-perimeterisation (De-P), Data-level Access Control, Self-Protecting Data, X.509 certification

établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Perimeter protection represented by system-level access control was the earliest framework to provide and support privacy protection and handle control. Despite the great implementation features of system-level access control there are various limitations helped to raise awareness related to the problems of perimeter protection, and to promote De-perimeterisation (De-p) protection [START_REF] Palmer | Benefits and limitations[END_REF]. The main purpose of De-p protection is to attain continuous and modifiable access control to the information shared beyond the system's boundaries [START_REF] Andre Van Clee | De-perimeterisation as a cycle: tearing down and rebuilding security perimeters[END_REF]. Digital rights management (DRM) with its security processes can be considered as a non-perimeter security model, where the control can be applied to the resource outside the system's boundaries. DRM access control still is static, not modifiable, and a fine-grained classification scheme is missing [START_REF] Burnap | Self Protecting Data for De-perimeterised Information Sharing[END_REF].

The JISC funded SPIDER project (Self-Protecting Information for De-Perimeterised Electronic Relationships) [START_REF] Burnap | Self-Protecting Information for Deperimeterised Electronic Relationships (SPIDER)[END_REF] is one of the currently very promising solutions based on the De-p principle. It aims to provide a set of tools including classification scheme, persistent and modifiable access control and enforcement mechanisms for information shared in collaborative distributed work environments. However, there are specific limitations, related to identification and authentication issues, which restrict its efficiency and put a stop to its reliability. The aim of this paper is to attempt to bridge the gap between the SPIDER project and DRM techniques, using modifiable digital certification construction. More specifically, in this paper we suggest an extended X.509 certificate [START_REF]Authentication Framework[END_REF] to be compatible with modifiable and continuous data level access control in distributed environments, in addition to a modified SPIDER application that allows shifting the emphasis from system as controller to user-definable policies. Starting with an overview of existing technologies the paper identifies the most interesting gaps and then explains the own research approach, its expected benefits and limitations, it concludes with a reflection of the current state of the work and outlook to future work.

Existing Access Control Technologies

System-level access control is the traditional strategy of existing access control systems. The central theme of this strategy is perimeter protection which means the application of control to information access requests within the system's boundaries using previously assigned access rights. System-level access control provides a sufficient access control and authentication infrastructure for entities. However, it has various limitations [START_REF] Burnap | Self Protecting Data for De-perimeterised Information Sharing[END_REF] such as a lack of information classification schemes, and a Lack of continuous and modifiable control behind the secure network boundaries. Furthermore, the emergence of many new variables and environments in the context of digital communication (e.g., global corporate, cloud computing, and online business) highlighted the problem of system-level access control, and showed the inability of the perimeter protection to be compatible with the new environments [START_REF] Olovsson | The Road to Jericho and the myth of Fortress Applications[END_REF]. Growing problems of level access control associated with disappearing boundaries between networks have raised an important question: What is the alternative? And how can we extend the control on our data beyond the system's boundaries?

De-perimeterisation Protection as a Key

The first description of the De-p protection was in the Jericho forum [5] [7]. It suggests shifting from protecting data from the outside (system and applications) to protecting data from within. Mainly it aims to apply continuous control to data outside the system's boundaries using data-level access control (i.e., Information-centric security) and including some access control policies into the information itself [START_REF] Andre Van Clee | De-perimeterisation as a cycle: tearing down and rebuilding security perimeters[END_REF].

Some Existing Approaches for De-perimeterisation Protection

Many methods have been presented in order to solve the problems of perimeter protection, and they can be viewed as partial solutions towards de-p achievement. Partly we can look at digital rights management DRM as non-perimeter security model as it provides a continuous control beyond the system's boundaries. However DRM access control is static, not modifiable and doesn't provide a fine grained classification scheme. In 2001 and 2002, two selective access approaches for information sharing in distributed environments via the Web have been presented [8] [9]. These two approaches aim to protect information using XML's Properties to allow the fragmentation of content, and to apply different controls to the same resources. The major drawback of these approaches is the lack of persistent and modifiable access controls. The SPIDER project [START_REF] Burnap | Self Protecting Data for De-perimeterised Information Sharing[END_REF] [2] being led by Cardiff University combines the advantages of previous methods. It provides a practical way to modify the existing models of information classification based on access control requirements, with a live URL link which allows the possibility to enforce and modify the access control policy beyond the system boundaries. The SPIDER Project represents a valuable approach towards solving the Perimeter protection problems, certainly, the problem of non-continuous and non-modifiable control. However, a few aspects of SPIDER are still under development, and there are considerable gaps effect on SPIDER performance and efficacy.

Building on Existing Work

With the SPIDER project [START_REF] Burnap | Self-Protecting Information for Deperimeterised Electronic Relationships (SPIDER)[END_REF] already covering the core functionalities, we can focus on closing the following interesting gaps:  Trusted computing: With the application of SPIDER, the entire resource is encrypted with the same key for all security levels; then the whole resource in memory is open to attack in case of key disclosure. In addition, a trusted computing module to ensure confidentiality during decryption encryption is required.  Identity management is still under development, there is a trend to use a digital certificate (not yet defined). Our previous description of the SPIDER limitations highlights the need for confidentiality, authentication and identity management mechanisms.

Towards a Solution Model

Following on from this, a set of requirements based on the drawbacks of the previously mentioned methods will be derived, then used to implement a solution that considers these requirements using a modified application of SPIDER [START_REF] Burnap | Self Protecting Data for De-perimeterised Information Sharing[END_REF], in order to provide a solution that enhances the access control process in widely distributed and expanding collaborative working environments, and to improve the information exchange privacy by providing X.509 extension to allow fine grained access controls. Taking advantage of the X.509 standard certificate [START_REF]Authentication Framework[END_REF] which can be viewed as one of the DRM processes, and taking into account the requirements of data-level access control architecture such as SPIDER project [START_REF] Burnap | Self-Protecting Information for Deperimeterised Electronic Relationships (SPIDER)[END_REF], using X.509 certificate to enhance the confidentiality and authentication is not sufficient. Despite the high level of confidentiality achieved by X.509 there are significant drawbacks affecting X.509 adoption in distributed structures:

 The user is not a controller; everything is done by a trusted third party.  Doesn't provide a classification scheme for access control  The access control depends on previously assigned rights; thus, it is not modifiable.

On the other hand, SPIDER doesn't provide authorization credentials or authentication mechanisms. In addition, we still have to deal with the crisis of using one key to encrypt the entire resource. Therefore, in order to enhance access control process reusing the De-p structure of the SPIDER, we suggest a new vision as follows:

 Combining the advantages of digital certification and the SPIDER project.  Mixing a centralized strict hierarchical structure with a stand-alone structure.  Using various keys to encrypt the resource for different levels of security.  Suggesting a modified X.509 digital certificate ISAC (Identification and Secure Access Control Certificate) for the purpose of identification, authentication and secure data-level access control.

Suggested Digital Certificate

The suggested certificate is generated centrally by a trust authority and contains the original structure of the X.509 [START_REF]Authentication Framework[END_REF], in addition to a new annex contains compatible fields for secure data-level access control process (as figure.1 shows). At the time of issuing an extended X.509 certificate, the center applies its electronic signature on the main part of the X.509. The special annex should later be signed by the resource's owner if he wishes to grant access privileges without referring to the authority center. The underlying idea for a process is illustrated in figure.2, when the user wishes to access the resource; he will send an access request including his certificate. The owner side will check the identity and connect the database to extract the policies and keys which match this identity; then it will fill the fields of the annex with the required information, sign it with the private key of the owner and encrypt it using the public key of the user before sending it back to the user. The SPIDER application in the user side will verify the access control annex, parse the resources for the classifications labels that match the security label returned for the user and generate a dynamic subset of the original resource in unencrypted form for the user to access.

Fig. 2.

Basic structure of the process

Advantages and Limitations of the Suggested Solution

The suggested solution exploits the high level of security in X.509, gaining the advantages of the hierarchical structure in confidentiality and authentication. Including access rights in the extended certificate enables the use of classification methods and partial access rights, these rights are continuous and modifiable by drilling down to the level of data using SPIDER project. The suggested X.509 extension allows this certificate to be used in distributed environments and paves the way for building a standards-based for de-p approach in the future. Furthermore, the use of different keys for encrypting the resource protects the encrypted resource existing in memory in case of key disclosure. The suggested solution has some well-known limitations, including limiting data-level access control operations to X.509 holders, and using various keys to encrypt the resource, which takes us back to the key management problem, for which we should measure the efficiency of our suggestion in reality.

Conclusions and Future Work

The inability of perimeter protection and system-level access control mechanism to match new significant developments in digital communications made it a must to come up with a new flexible and secure access control method. In this paper we have provided a brief description of the SPIDER project as the currently most advanced and practical method based on De-perimeterisation protection and data-level access control. We have investigated the X.509 standard certification and highlighted its disadvantages focusing on the difficulties of applying this standard to distributed environments to be completed in our current research. Later in the paper we have introduced our suggestion aiming at two improvements:  Strengthening the authentication and identification mechanism of SPIDER project  Making the X.509 standard certificate applicable and more efficient in a distributed environment by adding a data-level access control annex. A deeper security analysis of this extended certificate is planned and experiments will be conducted to test the viability of this approach in realistic settings.

Fig. 1 .. 2 Basic

 12 Fig. 1. The essential fields of the suggested annex

1 -verifies the access control annex according to the previously stated steps. 2 -parse the resources for the classifications labels that match the security label returned for the user 3 -

 123 generate a dynamic subset of the original resource in unencrypted form for the user to access.