Sheikh Emmanouil Vasilomanolakis

Mahbub Habib

Pavlos Milaszewicz
email: pavlos.milaszewicz]@stud.tu-darmstadt.de

Rabee Sohail

Max Mühlhäuser

Towards Trust-aware Collaborative Intrusion Detection: challenges and solutions

Collaborative Intrusion Detection Systems (CIDSs) are an emerging field in cyber-security. In such an approach, multiple sensors collaborate by exchanging alert data with the goal of generating a complete picture of the monitored network. This can provide significant improvements in intrusion detection and especially in the identification of sophisticated attacks. However, the challenge of deciding to which extend a sensor can trust others, has not yet been holistically addressed in related work. In this paper, we firstly propose a set of requirements for reliable trust management in CIDSs. Afterwards, we carefully investigate the most dominant CIDS trust schemes. The main contribution of the paper is mapping the results of the analysis to the aforementioned requirements, along with a comparison of the state of the art. Furthermore, this paper identifies and discusses the research gaps and challenges with regard to trust and CIDSs.

Introduction

With the continuous growth of cyber-attacks, Intrusion Detection Systems (IDSs) are nowadays considered a mandatory line of defense for any type of network [START_REF] Mitchell | A survey of intrusion detection techniques for cyberphysical systems[END_REF]. However, as isolated IDSs do not scale and are not capable of detecting distributed and highly sophisticated attacks, more collaborative approaches have emerged. The term Collaborative IDS (CIDS) describes systems that exhibit such a cooperative approach [START_REF] Vasilomanolakis | Taxonomy and Survey of Collaborative Intrusion Detection[END_REF]. In a CIDS, a plethora of different sensors (e.g., honeypots, firewalls, IDSs, etc.) collaborate by exchanging alert data with the scope of creating a holistic picture of the monitored network. As sensors exchange data and correlate information, it becomes feasible to detect a larger portion of attacks. Moreover, in contrast to isolated IDSs that do not scale, these systems can monitor very large networks.

However, a big challenge in CIDSs is the ability to manage the various sensors in an efficient and productive manner. In this context, the aspect of trust is of high importance for CIDSs. First, with the usage of computational trust it is possible to deal with insider attacks [START_REF] Fung | Collaborative intrusion detection networks and insider attacks[END_REF]. Such attacks refer to cases in which a number of sensors, inside the CIDS, are infected or compromised. In such an event, rogue sensors can significantly reduce the accuracy of the overall system by contaminating the alert exchange process with fake alerts. Second, apart from insider attacks, trust mechanisms are valuable for assessing the quality and thus the weight of importance that different sensors ought to have. For instance, in a large CIDS, a multitude of heterogeneous sensors is to be expected; from highly trusted IDSs to honeypots and/or to third party untrustworthy sources of alert data. In all cases, the CIDS needs to be able to assess which sources are more relevant and/or reliable.

In this paper, we attempt to bridge the areas of computational trust and collaborative intrusion detection, discuss the state of the art, and identify the respective research gaps. We firstly propose a number of requirements for reliable Trust Management (TM) in CIDSs. Afterwards, we carefully investigate the related work for the most dominant and promising CIDS trust schemes. The trust components of the identified systems are discussed separately on the basis of the aforesaid requirements. Furthermore, we compare all the trust mechanisms by mapping them to the requirements. In addition, based on our analysis, we identify and discuss research gaps and challenges with regard to trust and CIDSs.

The remainder of this paper is organized as follows. In Section 2, we propose a number of requirements for trust mechanisms in CIDSs. On this basis, Section 3 provides a brief description and analysis of the most prominent CIDS trust mechanisms. Furthermore, Section 4 contains a detailed comparison of these mechanisms by mapping them to the requirements and provides future directions. Lastly, Section 5 concludes the paper.

Requirements

Managing trust in a CIDS is a complex problem which has many conflicting requirements for which an acceptable tradeoff has to be chosen. In our previous work, we have examined the related work in both CIDSs [START_REF] Vasilomanolakis | Taxonomy and Survey of Collaborative Intrusion Detection[END_REF] and computational trust [START_REF] Habib | The Cloud Security Ecosystem -Technical[END_REF]. On this basis, along with an additional study of the state of the art in trust mechanisms for CIDSs, we propose the following requirements. These will be utilized along the discussion of the different approaches in Section 3 and will be more extensively analyzed in Section 4.

-Global view: Some approaches for managing trust require a global view of the monitored network, in which an administrator has full control over the sensors or sensors have full-fledged information about the entire network. This is not always realistic; for instance, fully distributed CIDSs usually cannot guarantee such a global view. Hence, approaches that do not require global view can be applied to a larger variety of CIDSs. -Minimum overhead: The overhead associated with the computing and managing of trust in a CIDS should be kept to a minimum. In particular, the overhead can be either communicational or computational. Communicational overhead refers to the need of the trust mechanism to generate additional messages. Computational overhead is associated with the computational power required to compute the various trust values.

-Incentive mechanism: An incentive mechanism refers to the ability of a trust system to motivate and reward sensors for behaving in a trustworthy manner. An example of such an incentive can be the ability to give alert data feedback only to sensors with high trust values. -Initial trust: Assigning a reasonable initial trust value to a sensor that has recently joined the CIDS is a challenging task [START_REF] Perez | Building a reputation-based bootstrapping mechanism for newcomers in collaborative alert systems[END_REF]. As historical data do not always exist for newcomers, the trust mechanism has to choose between assigning random values, a probation period approach or the assignment of high/low initial trust values. Each approach has certain advantages and disadvantages that will be discussed in the following sections. -Forgetting factor: The forgetting factor (or aging) is a parameter that ensures that the most recent feedback, given by nodes, carries more weight than less recent feedback. This is desirable as it allows a more accurate and up-to-date calculation of trust values. -Performance history: The performance history describes how a sensor has performed based on historical data (e.g., old transactions).

CIDS Trust Management

In this section, we analyze and discuss four trust approaches for CIDSs. The selected systems were identified by analyzing the state of the art. In particular, the emphasis of our analysis lies on the collaboration framework or architecture, the TM mechanisms, and the utilized evaluation methods.

Dirichlet-based Trust Management

Fung et al. proposed a TM model to facilitate an effective trust-aware CIDS [START_REF] Fung | Dirichlet-based trust management for effective collaborative intrusion detection networks[END_REF].

The system consists of three main components: the Collaboration component, the TM component and Acquaintance Management component. The Collaboration Framework connects different hosts in a network and allows them to communicate in a fair and scalable manner. The TM framework leverages the collaboration framework to establish trust among networked hosts based on the history of their performance. It uses Bayesian statistics to calculate the trustworthiness of hosts. Finally, the Acquaintance Management is used to manage a list of trustworthy acquaintances using test messages. Each of these components is described in the following.

Collaboration component This component has an incentive mechanism for hosts to share information and manage their acquaintances. Each host maintains a list of acquaintances, peers (i.e., other sensors in the CIDS) that it trusts and collaborates with. Each sensor sends two types of requests to its peers, intrusion consultation messages and test messages. Intrusion consultation messages are sent when a host needs feedback to determine whether an alarm should be raised or not. The amount of information that a host shares with a peer depends on the trustworthiness of that peer; more trustworthy peers receive more information than less trustworthy ones. Additionally, each host sends test messages periodically. The nature of the test message is known to the sender beforehand. Test messages are used by a sensor to establish the trust levels of its peers. Such messages can be generated artificially using a knowledge database.

Trust Management component To establish trust, hosts send requests to peers and evaluate the satisfaction levels of the reply. The alert ranking raised by a host lies in the interval [0,1] where 0 is harmless and 1 is highly dangerous.

The satisfaction level of a reply from an acquaintance is a function of three parameters, the expected answer (r), the received answer (a) and the difficulty level (d) of the test message. The values of these three parameters also lie in the interval [0,1]. The function Sat(r, a, d)(∈ [0, 1]) (see Equation 1) represents the satisfaction level of the given feedback. The value of c 1 determines the level of penalization of a wrong estimate. Parameter c 2 controls sensitivity of the satisfaction level to the distance between the expected and received answer.

Sat(r, a, d) =      1 - a-r max(c1,r,1-r) d/c2 a > r 1 - c1(r-a) max(c1,r,1-r) d/c2 a ≤ r (1)
Bayesian statistics, and specifically the Dirichlet distribution, is used to model the distribution of past satisfaction levels from the acquaintances of each peer. The Dirichlet distribution is utilized since the authors are modeling multivalued satisfaction levels; it is a continuous, multivariate probability distribution, which is a generalization of the Beta Distribution for multivariate values. This prior distribution is then used to estimate the posterior distributions, i.e. satisfaction levels of future answers.

If X is the random variable representing the satisfaction level of feedback from a peer, then X can take values χ = {x 1 , x 2 ...x k } of the supported levels of satisfaction where each value lies in the interval [0,1].

-→ P = {p 1 , p 2 ...p k } is the probability distribution vector of X such that P {X = x i } = p i . The cumulative observations and beliefs of X are represented by -→ γ = {γ 1 , γ 2 ...γ k }. Using the Dirichlet distribution, the vector -→ p is modeled as:

f ( - → p |ξ) = Dir( - → p | - → γ ) = Γ ( k i=1 γ i ) k i=1 Γ (γ i ) k i=1 p γi-1 i ( 2
)
where ξ is the background information which is represented by -→ γ . Let γ 0 = k i=1 γ i , then the expected value of probability of X to be x i is then given by:

E(p i | - → γ ) = γi γ0
. Moreover, a forgetting factor λ can be used to give recent observations more importance which leads to:

- → γ (n) = n i=1 λ ti × - → S i + c 0 λ t0 - → S 0 . S 0 is
the initial beliefs vector and c 0 is the constant which puts weight on the initial beliefs. t i represents the time elapsed since the i th evidence. When feedback is received from a peer, it is given a score according to equation 1. p uv i denotes the probability that feedback from peer v to peer u has the satisfaction value x i . The sum of P uv over all i is equal to 1.

-→ P uv is modeled using equation 2. Y uv is the random variable such that: Y uv = k i=1 p uv i w i . The following equation then gives the trustworthiness of a peer:

T uv = E[Y uv ] = k i=1 w i E[p uv i ] = 1 γ uv 0 k i=1 w i γ uv i (3)
Where γ uv i is the cumulative evidence that v has replied to u with satisfaction level x i . As soon as the trustworthiness has been calculated, feedback only from peers whose trustworthiness levels exceed a certain level is considered. An upper bound for the trust level is calculated using the covariance of p i and p j . Once feedback from acquaintances has been collected, it is aggregated using the following weighted majority formula:

āu i = T uv l ≥th u ,v∈A u T uv a uv i T uv l ≥th u ,v∈A u T uv (4)
Where āu is the aggregated ranking of alert i. T uv is the trustworthiness of peer v to peer u. This formula is applied only to feedback from peers with trustworthiness higher than a certain threshold. a uv i is the ranking of the alert i given from u to v.

Acquaintance Management

The authors contributed an algorithm to maintain a list of acquaintances in the proposed system. Maintaining such a list is necessary since it is not scalable for the host to keep records for all the peers in the network. Each host maintains a list of trusted nodes, with the length of the list depending on the available resources. Since it takes time to determine the trustworthiness of a peer, a probation list should also be maintained. The host communicates with peers in its probation list to determine their trust levels and if the levels exceed a certain threshold, the relevant nodes can be added to the acquaintance list.

Experiments and Results

The authors simulate an environment in which a host is allowed to have an acquaintance list with 40 dishonest peers, divided equally into 4 groups. Each group uses a different strategies for its dishonesty -complimentary, exaggerate positive, exaggerate negative and maximal harm. Complimentary simply inverts the alert level of a message. For example, an actual alert level of 0.7 will be converted to a 0.3. Exaggerate positives and exaggerate negatives convert low positives and negatives to high positives and negatives [START_REF] Yu | Detecting Deception in Reputation Management[END_REF]. In maximal harm, the peer reports false feedback with the intention of causing the most harm to the host. The trust values of the peers converge after 30 days and, as expected, the trust value of the peers using the maximal harm scheme is the lowest. Fung et al. also conduct an experiment in which a peer behaves honestly for 50 days and then launches a betrayal attack using a maximal harm scheme. The results indicate that the trust value of that peer decreases rapidly due to the forgetting factor used to associate more weight on recent messages. Additionally, once a peer is downgraded from "highly trustworthy" to "trustworthy" the rate of test messages sent to it is increased.

Trust Diversity

Perez et al. [START_REF] Perez | Trustworthy placements: Improving quality and resilience in collaborative attack detection[END_REF] proposed the notion of Trust Diversity (TD) to maximize the information quality and resilience against dishonest behavior of CIDS sensors. TD is defined as the measurement of the dispersion of the trust values of sensors in a given domain. For instance, a low diversity would indicate that the sensors exhibit similar trustworthiness. The goal is to find a placement of sensors such that TD is maximized in all given domains. Thus, all domains will have a roughly equal distribution of trustworthy and untrustworthy sensors, leaving no domain unprotected. Furthermore, when there is high TD, the more reliable sensors can help identifying untrustworthy sensors, making the system more resilient to insider attacks. Finally, higher TD also leads to a system which is more resilient to external attacks.

System Model

The services and resources of a CIDS can be divided into different domains (D). Each domain has a set of requirements (R) for the proper functioning of the entire system. Each sensor has certain properties (P ) to monitor certain requirements, denoted by P (S j ). For each sensor, a reputation value (Rep(S j )) is also maintained. This value is based on the assessment of the sensor's past behavior. The CIDS can be configured to deploy sensors as required in different domains to reach a desired goal.

Sensor Placement Reconfiguring the placement of sensors is important to increase TD which reduces the uncertainty about the nature of events, that is, if they are malicious or not. It also allows the reassessment of trustworthiness in sensors, as the feedback from more trustworthy sensors can be compared with the feedback given from less trustworthy sensors. The authors propose a Trust and Reputation module which uses the past behavior of the sensors to monitor the quality of each domain. The module uses three metrics, the past behavior of a sensor, the past behavior of a sensor's neighbors and the sensor's capabilities. The final result is the trustworthiness value, calculated for a sensor considering these metrics. The value is then used to compute the TD in a given domain.

Once the TD of all the domains has been computed, an optimization algorithm is used to generate the best possible reconfiguration of the sensors.

Trust and Reputation Management System

To compute the trustworthiness of sensors, Perez et al. make use of a trust and reputation management system. The computed trustworthiness can then be used to maximize TD. Computing the inter-quartile range, mean difference and arithmetic difference are some examples of how this diversity can be quantified. TD is computed at three different levels: at the requirement level such that diversity is maximized among sensors assigned to fulfill a certain requirement; at the domain level to ensure that there is a diverse spread of sensors' reputation levels in all domains; and lastly, at the global system level such that no domain is left unprotected. TD at the requirement level, for a requirement R k for a domain Ω, denoted by T D Ω ∈ [0, 1] can be calculated by:

T D Ω (R k ) = max{Rep Ω (S R k )}.ψ(Rep Ω (S j,R k ).µ Ω (R k,Sj )), ∀S j ∈ SP (Ω) (5)
where ψ is the dispersion among the sensors' reputation, max{Rep Ω (S Rk )} denotes the highest reputation value among all sensors in the given domain Ω, Rep Ω (S j,R k ) is the reputation of the j th sensor in Ω fulfilling requirements R k and µ Ω (R k,Sj ) is the risk incurred when R k is not satisfied. Once the TD has been calculated at the requirement level, it can then be calculated at the domain level as: [START_REF] Duma | Carroni: A Trust-Aware, P2P-Based Overlay for Intrusion Detection[END_REF]. φ Ω (R) represents the total number of requirements in Ω. ⊕ is an aggregation operation, for example, arithmetic mean or harmonic mean. Finally, TD at the CIDS level can be calculated as:

T D Ω = ⊕ φ Ω (R) k=1 T D Ω (R k ). T D Ω (R k ) is the TD of the k th requirement calculated in
T D CIDS = ⊕ φ CIDS (D) i=1
T D Di where φ CIDS (D) is the number of domains in the CIDS and T D Di is the TD of each domain.

Upon receiving the alert of a new event, the monitoring system first assesses the trust in the event being true and then updates the reputation levels of all relevant sensors which are configured to report such an event. The trust of an event is the confidence the system places on an event being true. Three factors are used to compute the trust level in an event: the agreement level of all relevant sensors; the number of domains in which the event was detected and the TD in all such domains. Using these three factors, the trust level of an alert can be calculated as follows:

T (E R k ) = ⊕ φ D (E R k ) i=1 |δ Di (E R k )|.T D Di (R k ) (6)
where φ D (E R k ) is the number of domains from which the event alert has been issued. δ Di (E R k ) is the level of agreement of the relevant sensors in the ith domain D i , relevant to the event E R k . T D Di (R k ) is the TD of each domain where the event happened. The agreement of relevant sensors on a given event is calculated using a voting scheme and can be computed as follows:

δ Ω (E R k ) = φ S Ω (E R k ) j=1 Rep Ω (S j,R k ) φ S Ω (E R k ) - φ S Ω (E R k ) j=1 Rep Ω (S j,R k ) φ S Ω (¬E R k ) (7)
Here, Rep(S j,R k ) is the reputation of the j th sensor fulfilling requirement R k , φ S Ω (E R k ) is the number of relevant sensors in domain Ω that have issued a notification for the event, and φ S Ω (¬E R k ) is the number of sensors that did not report it. A neutral agreement with the computed value of 0 indicates total uncertainty about whether a given event is true or not. A value of 1 indicates full confidence that is true and a value of -1 indicates that it is false. Once a trust value is assigned to an event it can be used to update the reputation of the involved sensors as follows:

RepS j (t) = ωRepS j (t-1) + (1 -ω) φ S j (E) k=1 Sat(S j , E k )µ(R E k Sj )ξ(E k ) φ Sj (E) (8)
where φ Sj (E) is the total number of events the sensor j has been involved in. Sat(S j , E k ) is the calculated satisfaction level of the behavior shown by S j with regards to the event E k . Moreover, RepS j (t-1) is the last reputation value of S j , while µ(R E k Sj ) is the associated risk of the requirement affected by E k , and ξ(E k ) is a forgetting factor. Lastly, ω is the weight on each term which determines importance of past behavior. The satisfaction level of the behavior of a sensor with regards to an event is dependent on the trust value of that event and the action of the given sensor. It can be computed as follows:

Sat(S j , E k ) =      |δ(E k )| if (T (E k ) ≥ T σ ∧ S j ⊆ G s (E k )) ∨(T (E k ) < T σ ∧ S j G s (E k )) | -δ(E k )| otherwise (9)
Here, T σ is the threshold which decides whether an event is trustworthy or not. G s (E k ) is the set of all sensors which have issued a notification for the event E k . Therefore, if an event is trustworthy, and its notification has been issued by the sensor, the reputation of that sensor will increase. The opposite is true for when the event is considered not true. When the TD of a requirement, domain or the entire CIDS falls below a certain level, then a new configuration could be found which increases it once again.

Experiments and Results

The authors experiment with a simulation that includes 500 sensors, 20 domains and 10 requirements. The initial reputation of each sensor is assigned a random value. The first experiment assesses events in a domain with higher TD compared to a domain with lower TD. The authors use an optimization algorithm to search for a placement with high TD. They simulated over 2000 events and assessed the trust levels of these events (see Equation 7). The value of agreement level is between 1 and -1. A value close to 1 means that the sensors are in agreement that an event is true while a value close to -1 means that the sensors agree that an event is bogus. For domains with lower TD, the agreement level for honest events and bogus events were 0.3139 and -0.3102 respectively. For the domains with higher TD, the agreement level for the honest and bogus events were 0.7253 and -0.7098 respectively, a significant improvement. Another experiment was to test the effect TD has on the resilience of the system to malicious sensors. The authors incrementally increase the number of malicious sensors in the system and observe the effect this has on the trust values of the malicious sensors. With higher TD, these trust values decrease more rapidly than in domains with lower TD. This can give a clear indication that the system is being compromised by malicious sensors.

A Trust-aware P2P-based CIDS

Duma et al. [START_REF] Duma | Carroni: A Trust-Aware, P2P-Based Overlay for Intrusion Detection[END_REF] proposed a trust-aware Peer-to-Peer (P2P)-based CIDS. The proposed system consists of a trust-aware correlation engine and an adaptive TM scheme. The correlation engine is used to filter sent by untrustworthy peers. The TM scheme works by using past experience to decide if peers are trustworthy or not. The sensors form a P2P network, in which they are interconnected and communicate to detect and prevent attacks.

Trust Management To calculate trust among sensors, each peer has a list of peers that it trusts, and checks for peer trustworthiness before taking any decision regarding a possible threat. To adjust the trustworthiness of a peer, the local peer will evaluate any event according to if it was an incident or not, and adjust its trust regarding other peers. In more details, each peer P i has a list of acquaintance peers, which consists of other peers that P i has interacted with and their trust value. For each peer P j which is present in the acquaintance list, P i keeps two variables: the first one is s ij which represents the number of successful experiences that i had with j. The second one is u ij which represents the number of unsuccessful experiences that i had with j. Having these, peer i computes the trustworthiness of peer j as: t ij = w s sij -uij sij +uij . The w s parameter, is called significance weight and depends on the total number of experiences that are available for the computations regarding trust. If the number of experiences available are too less, then a peer's trustworthiness cannot be computed by this formula. That means that if the total number of experiences s ij +u ij is below a certain minimum number n, then w s = (s ij + u ij )/n, which means w s = 1.

A trust threshold also exists, which is a minimum value of trust that the peers in a list need to have, so that their warnings are taken into consideration. Peers that are below the threshold are marked with a probation flag and have a certain probation period to pass the threshold. If the peer manages to pass the threshold in time, the flag is removed. If not, the peer is removed from the acquaintance list and some new randomly chosen peer will take its place. The new peer will also be flagged and given a probation period to pass the threshold. If it does not, then the aforesaid procedure will take place. This means that for every peer P j in the list, P i has a probation flag pf ij that shows if P j is flagged or not, and a probation time pt ij that shows the time passed since P j was flagged.

To ensure that the acquaintance list is dynamically built (and managed), making sure that only trustworthy peers remain in the list, four different cases can be distinguished:

-If an attack occurred and P j sent a warning then

s ij = s ij + 1, u ij = u ij and pt ij = pt ij + 1.
-If an attack took place and P j did not send a warning then

s ij = s ij , u ij = u ij + 1 and pt ij = pt ij + 1. -If no attack occurred but j sent a warning then s ij = s ij , u ij = u ij + 1 and pt ij = pt ij + 1.
-If no attack took place and P j did not send any warning then s ij , u ij and pt ij remain the same.

Alert Correlation A peer can utilize the knowledge of the trustworthiness of others to perform alert correlation. The confidence level of a correlated alert is computed as follows:

C i = w dir • c i + w ind • 1 N N j=1 c j • t ij (10)
Here, c i is the confidence in the correlated alert as correlated by P i , c j is the confidence of the alert received from peer P j , and N is the number of peers that have not been flagged and have sent alerts used in the correlation. w dir and w ind are the direct and indirect weights (direct for locally generated alerts and indirect for received alerts). Regarding N it is required to be above a certain threshold N min , and if it is lower, then the weight w ind is decreased by N/N min . Hence, dependence on only a low number of peers is avoided. However, even with a high N min problems might also appear, when the number of truthful warnings available for correlation is very small. In the end, if the confidence of a certain correlated alert is above a certain threshold, the peer will activate the incidence response module which will take passive or active action towards the threat.

Experiments and Results

The authors conducted experiments for a virtual network (consisting of 36 clients) that was being attacked by a worm. The clients were grouped in 6 sub-networks. A survival rate was defined, as the number of nodes resisting the worm divided by the number of all nodes in the network. The survival rates for the case when the clients were part of the CIDS and when they were not, were compared. The results showed a significant increase of the average survival rate when the CIDS was utilized. According to the experiments, the more peers are in the CIDS the higher the probability is that the worm will be detected. On the one hand, the survival rate decreases by increasing the number of trusted peers needed for correlation (N min ). On the other hand, the resilience of the network increases with N min as the impact of a malicious peers is diminished (which also means that the false alarm rate decreases). Thus, by configuring N min one of the following can be achieved: either a faster detection system with a higher survival rate but prone to false alarms, or a more robust system with a lower level of false alarms but which (due to lack of trust) could miss some of the real alarms.

A reputation-based bootstrapping mechanism for CIDSs

Perez et al. [START_REF] Perez | Building a reputation-based bootstrapping mechanism for newcomers in collaborative alert systems[END_REF] proposed a reputation management system that addresses the newcomer (bootstrapping) problem in CIDSs. Bootstrapping is a common in P2P networks where newcomers join the networks for the first time. Similarly, reputation bootstrapping is a common issue in reputation systems.

System model

The CIDS is divided into security domains (D 1 ,D 2 ,..., D n ), each of which defines a Collaborative Intrusion Detection Network (CIDN) [START_REF] Fung | Trust management and admission control for host-based collaborative intrusion detection[END_REF]. Each security domain is composed of a multitude of IDSs, one of which is chosen to be its leader (Domain Leader (DL)) acting as the representative of the CIDN in the CIDS. The DL's purpose is to share alerts detected by its CIDN with the CIDNs of other domains, and request recommendations from other CIDNs about a newcomer to compute its initial reputation (trust) score [START_REF] Ortega | Propagation of trust and distrust for the detection of trolls in a social network[END_REF]. The newcomers can be static IDSs (permanently placed), mobile IDSs belonging to users who want to collaborate with security domains, or a security domain that wants to improve its accuracy in detecting distributed threats by exchanging alert data. Trust is computed on the basis of the initial absence of historical data and on the fact that IDSs join and leave the system regularly.

Reputation Management System This section describes the reputation management system focusing on the aforesaid three possible newcomers. Note that the model also depends on the detection skills, that is the usefulness and willingness of a newcomer, as well as the similarity between two domains. The usefulness function of a newcomer's detection unit (DU m ) is denoted as Φ x (DU m ) and its computation can be found in [START_REF] Perez | Building a reputation-based bootstrapping mechanism for newcomers in collaborative alert systems[END_REF]. Similarly, the computations regarding the willingness of the new detection unit which is expressed as ω x (DU m ), and the similarity between two domains (D x and D y ) which is denoted as λ(D x , D y ) can also be found in [START_REF] Perez | Building a reputation-based bootstrapping mechanism for newcomers in collaborative alert systems[END_REF].

Recommendations from the CIDS about a newcomer Whenever a newcomer (NC ) (either a mobile IDS or a security domain), joins a domain D x , the latter can query other trusted domains within the CIDS asking for recommendations regarding the newcomer. The aim is to find the most reputable path leading to the most trustworthy domain having recommendations about the NC's behavior in sharing alerts. The best trust path (T tpi ) built up to the domain D x , which maximizes the confidence that D x can have on the most trustworthy domain D y (which will return its recommendation Rec y (N C)), is computed as:

T tpi (D x , D y ) = 1 |tp i | • |tpi| D f ,D k ∈tpi T (D j , D k ) • ( 1 ∆t+1 ) • δ(D j , D k ) |tp i | (11)
and

δ(D j , D k ) = 1, if D j ,D k ∈AD z j ∈ [0, 1]
, otherwise where (D j , D k ) represents each consecutive pair of domains in the trust path tp i , |tp i | is the length of such a trust path built up to D x and ∆t expresses the amount of time elapsed since the last interaction D j and D k . Essentially, this computes a weighted average of the direct trust values of each subsequent pair of domains, T(D j ,D k ), along trust path tp i . If NC is a mobile IDS joining the domain D x , mIDS i , this D x can also query other mobile IDSs that are currently collaborating with D x (mIDS j s), about their recommendations on mIDS i . Thus, the final recommendation for mIDS i is:

Rec mIDS (D x , mIDS i ) = mIDSj ∈Dx Rec mIDSj (mIDS i ) • ( 1 ∆t+1 ) |mIDS j ∈ D x | (12)
Moreover, for computing the confidence that D x has, on a recommendation gathered from the CIDS, the following formula can be used:

T mIDS (D x , mIDS i ) = mIDSj ∈Dx Rep Dx (mIDS j ) |mIDS j ∈ D x | (13)
Finally, if it is required to compute a single recommendation score by taking into consideration all the recommendations gathered from those sources that maintain behavioral-based information about the newcomer, then the following equation is used:

Rec CIDS,mIDS (D x , N C) = θ tpi • Rec CIDS (N C) + θ mIDS • Rec mIDS (D x , N C) (14)
where θ tpi and θ mIDS are the trust that D x has on the domains providing the NC's recommendation score and those provided by the mobile IDSs currently collaborating with D x . The equations computing them can both be found in the original paper [START_REF] Perez | Building a reputation-based bootstrapping mechanism for newcomers in collaborative alert systems[END_REF]. The proposal for bootstrapping the reputation of a newcomer in a CIDN will be presented bellow, by distinguishing three cases: the reputation bootstrapping model for a static IDS, a mobile IDS, or a new security domain.

Static IDS: The proposed equation to compute the initial reputation score of a newcomer static IDS, namely sIDS i , when it joins the domain D x at time t is:

Rep (t) Dx (sIDS i ) = ( 1 ∆t + 1 ) • Rep ∆t Dx (sIDS i ) + ( ∆t ∆t + 1 ) • Φ Dx (sIDS i ) τ (sIDSi)
(15) where ∆t represents the time elapsed since the last time sIDS i participated in D x , Rep ∆t Dx (sIDS i ) indicates the last sIDS i 's reputation score that D x has stored, and Φ Dx (sIDS i ) is the usefulness of sIDS i from the perspective of D x .

Mobile IDS: The proposed equation to compute the initial reputation score of a newcomer mobile IDS, namely mIDS i , when it joins the domain D x at time t is (a formal definition for f m can be found in [START_REF] Perez | Building a reputation-based bootstrapping mechanism for newcomers in collaborative alert systems[END_REF]):

Rep (t) Dx (mIDS i ) = ( 1 ∆t + 1 )•Rep ∆t Dx (mIDS i )+( ∆t ∆t + 1 )•f (Φ, ω, τ, Rec CIDS,mIDS ) (16)
Security Domain: The proposed equation to compute the initial reputation score of a newcomer security domain D y , that wishes to collaborate with the domain D x at time t is (a formal definition for f d can be found in [START_REF] Perez | Building a reputation-based bootstrapping mechanism for newcomers in collaborative alert systems[END_REF]):

Rep (t) Dx (D y ) = ( 1 ∆t + 1 ) • Rep ∆t Dx (D y ) + ( ∆t ∆t + 1 ) • f d (λ, τ, Rec CIDS ) (17)

Experiments and Results

The authors firstly examined the benefits of including mobile IDSs in the system. Their results suggest an improvement of the detection capabilities required by a CIDN to detect distributed threats. Further testing showed that the reputation bootstrapping model can support around 20% of malicious mobile IDSs before being discarded as valuable detection units. In addition, Perez et al. analyzed the variance of the reputation scores of static and mobile IDSs over time with regard to compromise and misbehavior. It was found that reputation scores are rapidly decremented when there are less than 5% of malicious IDSs. This finding was interesting for mobile IDSs, as they follow a similar pattern with static IDSs although mobile IDSs reputation is computed in each movement across the domains. This accuracy is due to the use of recommendations provided by other trusted parties of the CIDS. Further testing showed that this reputation bootstrapping model maintains its robustness for up to around 20% of malicious IDSs without losing its detection accuracy.

Discussion

This section begins with a comparison overview of the surveyed approaches with respect to fulfillment of the requirements discussed in Section 2. This comparison is also summarized in Table 1. Subsequently, we discuss the lessons learned from the current status of the state of the art and future directions that will advance the intersection of trust and CIDSs.

Comparison

In the following we discuss each requirement and how the different approaches fulfill it or not.

-Global view: The first [START_REF] Fung | Dirichlet-based trust management for effective collaborative intrusion detection networks[END_REF] and third [START_REF] Duma | Carroni: A Trust-Aware, P2P-Based Overlay for Intrusion Detection[END_REF] surveyed systems do not require global knowledge as each node computes its peers' trust values independently. In the second approach [START_REF] Perez | Trustworthy placements: Improving quality and resilience in collaborative attack detection[END_REF], a global view is required as sensors are moved between domains to increase trust diversity. This implies that an administrator who can control where the sensors are deployed is required. For the last approach [START_REF] Perez | Building a reputation-based bootstrapping mechanism for newcomers in collaborative alert systems[END_REF], the entire system is divided into security domains. For each domain, the domain leader must have knowledge of the topology and behavior of the nodes in its domains. For this reason, only partial view of the network is required by domain leaders. -Minimum overhead: The first approach [START_REF] Fung | Dirichlet-based trust management for effective collaborative intrusion detection networks[END_REF] utilizes test messages, which increase the communication overhead. In fact, the confidence of the trust value is dependent to the number of the sent test messages. The second approach [START_REF] Perez | Trustworthy placements: Improving quality and resilience in collaborative attack detection[END_REF] also depends on the sensors being assigned trust values according to their past behavior which also requires the dispatching of test messages. Moreover, the overhead of re-configuring sensors to increase trust diversity also has to be considered. The third approach [START_REF] Duma | Carroni: A Trust-Aware, P2P-Based Overlay for Intrusion Detection[END_REF] has lower overhead than the previous ones as it does not require test messages for the computation of trust values. Instead it only uses the knowledge gained from past interactions to calculate trust values. The last approach [START_REF] Perez | Building a reputation-based bootstrapping mechanism for newcomers in collaborative alert systems[END_REF] has significant overhead, due to the number of steps a newcomer has to take when joining the CIDS. -Incentive mechanism: In the first approach [START_REF] Fung | Dirichlet-based trust management for effective collaborative intrusion detection networks[END_REF], an incentive mechanism is proposed where nodes give more feedback to trustworthy peers while not giving as much to untrustworthy peers. This incentive mechanism is important as it ensures that peers which behave in a trustworthy manner are rewarded while untrustworthy peers are ignored. This also reduces overhead communication and computation overhead as peers do not spend time responding to untrustworthy peers. The rest of the approaches, however, do not make use of any incentive mechanism. -Initial trust: The first system [START_REF] Fung | Dirichlet-based trust management for effective collaborative intrusion detection networks[END_REF] assigns the newcomers with random trust values. Nevertheless, the CIDS mitigates the risk by placing newcomer nodes in a probation list for a certain period of time. The second approach [9] also assigns completely random values and takes no steps to mitigate the risk associated with this scheme. The third system [START_REF] Duma | Carroni: A Trust-Aware, P2P-Based Overlay for Intrusion Detection[END_REF] keeps newcomers under probation for a fixed period of time. The newcomer is not assigned an initial trust value. After the probation time period has elapsed, if the newcomer's trust value is above a certain threshold, it is considered trustworthy. The last approach [START_REF] Perez | Building a reputation-based bootstrapping mechanism for newcomers in collaborative alert systems[END_REF] exhibits the most sophisticated approach for assigning trust values to newcomers. It takes into account many factors and gathers background information about nodes to solve the newcomer problem. -Forgetting factor: The first [START_REF] Fung | Dirichlet-based trust management for effective collaborative intrusion detection networks[END_REF], the second [START_REF] Perez | Trustworthy placements: Improving quality and resilience in collaborative attack detection[END_REF] and the fourth [START_REF] Perez | Building a reputation-based bootstrapping mechanism for newcomers in collaborative alert systems[END_REF] approaches, all make of use of forgetting factors in the calculation of trust, so that more recent messages are given more weight. However, the third approach [START_REF] Duma | Carroni: A Trust-Aware, P2P-Based Overlay for Intrusion Detection[END_REF], does not make use of such a technique. -Performance history: All of the surveyed approaches make use of historical data, in different ways, during the trust calculations.

Requirement Dirichlet-based approach [START_REF] Fung | Dirichlet-based trust management for effective collaborative intrusion detection networks[END_REF] Trust diversity [START_REF] Perez | Trustworthy placements: Improving quality and resilience in collaborative attack detection[END_REF] Trust-aware CIDS [START_REF] Duma | Carroni: A Trust-Aware, P2P-Based Overlay for Intrusion Detection[END_REF] Bootstraping approach [

Challenges and steps ahead

The analysis of the state of the art suggests a plethora of novel ways for managing trust. As we have already described in the previous section, each of the aforesaid mechanisms introduces various advantages. Combining the benefits of each approach is one way towards the fulfillment of the requirements. In addition, we argue that a common methodology for the evaluation of trust in CIDSs is required. A basis for this can be the requirements proposed in Section 2. Furthermore, we envision the following research questions for which we argue that, when answered properly, can improve the output quality of CIDSs:

-Which additional parameters, inside the alert data, can be utilized for the computation of trust? -Is it possible to include more social attributes/parameters inside the overall trust calculations? For example, it might be that two organizations, inside the CIDS, have some special long-term connection that cannot easily depicted formally. -How important is the timeliness of the exchanged alert data? It can be that some sensors in a CIDS do not publish their alerts immediately due to internal security policies or due to the need for anonymization of the data. -How important is the relevance of the received alert data for a sensor? Can it be that a sensor receives valid data from a highly trustworthy sensor which however are irrelevant? For instance, what about an organization which obtains information about a port-specific attack, which however is completely banned from that particular organization's network. -How can uncertainty be included in the trust model? Would it be of benefit to include certainty scores for the trust values? For instance, an approach used in [START_REF] Habib | The Cloud Security Ecosystem -Technical[END_REF] can consider the volume of data utilized for generating a trust score; when sufficient data is not available, the certainty score would be low.

Conclusion

With the continuous growth in both the numbers and the sophistication of cyberattacks, CIDSs are becoming increasingly important. Introducing computational trust techniques in the field of CIDSs can provide substantial benefits for the detection of insider attacks as well as for the creation of highly tailored threat awareness of the monitored network. We proposed requirements for TM in the context of CIDSs. Moreover, we analyzed the most prominent systems with a focus on how they calculate and manage trust in such a context. The paper also provides an overall discussion of the requirements, with respect to their fulfillment in the related work, and highlights the research challenges and gaps that need to be tackled in the future.

Table 1 .

 1 Comparison of surveyed systems with the proposed requirements

	8]

Acknowledgments

This work has received funding from the European Union's Horizon 2020 Research and Innovation Program, PROTECTIVE, under Grant Agreement No 700071.


Anirban Basu
email: basu@kddi-research.jp

Mohammad Shahriar Rahman
email: mohammad@kddi-research.jp

Rui Xu

Kazuhide Fukushima
email: ka-fukushima@kddi-research.jp

Shinsaku Kiyomoto
email: kiyomoto@kddi-research.jp

VIGraph -A Framework for Verifiable Information

Keywords: privacy, hash tree, verifiability, selective disclosure

à la 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

Verifiable user identity information has always been a cornerstone in security and authentication. Most services, both online and offline, require a user to provide information to prove the user's identity. Chronological non-identity related information is also used in other scenarios. For instance, in Japan, users may maintain their medicine prescriptions in a specific logbook that is checked before future consultations or prescriptions to avoid conflicting medications. Financial organisations use a formal process called the know your customer or KYC to obtain and maintain information about their customers. Traditionally, each organisational entity asking for such data has to obtain and verify the data independently, and keep copies of it for future references and legal obligations. The users, on the other hand, do not have a mechanism to selectively control the release of such sensitive information. A centralised or decentralised registry of such information helps with speeding up user identity verification, but it raises questions about privacy of the data in the hands of this third-party registry.

Our contribution: In order to simplify the process for a service provider to collect, verify and maintain user information, a centralised (or distributed) solution works where the user is in charge of providing the information and a trusted third party maintains irreversible proofs of the components of such information. In this position paper, we propose a framework -the Verifiable Information Graph or the VIGraph -based on a generalised hash tree as a data structure. A hash tree enables verifiability of individual sub-trees without the full knowledge of the data contents. From the user's perspective, this very property of the hash tree enables releasing, for verification, parts of the information for specific checks without compromising the privacy of the rest. For the sake of brevity, we focus on user profile data to describe our proposed framework. The framework can also be applied to other types of information with similar verifiability requirements; we leave this as an avenue for future work.

Paper organisation: The rest of the paper is organised as follows. In section 2, we propose the structure of the VIGraph and explain the operations on it. This is followed by a brief discussion and a description of the relevant state-of-the-art in section 3, before concluding with future directions in section 4.

VIGraph: signed hash tree with optional dependency overlay

Hash trees, and the specialised Merkle Trees [START_REF] Merkle | Method of providing digital signatures[END_REF] have a specific property: each sub-tree of the tree can be verified independently of the other. This facilitates obfuscation on the actual contents of the data in sub-trees, which the verifier is not interested in. Our proposed data structure, the VIGraph, is four-levels deep, as illustrated in Figure 1. Starting at the top level (root), the actual data is on the fourth level down in the leaf nodes. VIGraph is based on a generalised hash tree, which means that a non-leaf node can have more than two children, as opposed to a binary hash tree. The structure of the VIGraph closely resembles a tree but is technically a graph due to the optional dependency overlay. However, throughout the paper, we will use terminology akin to trees, such as leaf nodes and root. The purpose of the VIGraph is verifiability and selective information release; and not a fast search from the root. Thus, VIGraph is not to be confused or compared with hash tries or hash array mapped tries (HAMT). The entities involved with the VIGraph are: (a) the user u whose information is being maintained, (b) organisational entities (each represented as o) responsible for endorsing (through digital signatures) various components of the user's information, e.g., the driving license identifier of a user may be signed by the driving license issuing authority, (c) the metadata provider organisation(s) (each represented as p) responsible for maintaining and facilitating verification using the VIGraph; and (d) the service provider or a verifier organisation (represented as v) responsible for verifying information against that stored in the VIGraph.

In short, each user has her VIGraph representing information about her, parts of which are maintained by one or more metadata providers; and the information maintained by the graph may or may not be endorsed by relevant information issuing authorities. Data level: The leaf nodes L0 . . . L9 (refer to Figure 1) are the actual data, L i , such as (using the personal profile example) national identity information, residential addresses, driving license and so on. Each node may also contain optional dependency pointers, described later.

Levels and dependencies

Hashed data level: The hashed data nodes, D0 . . . D9, on the hashed data level, contain the hashes of the data node contents, such that D i = h(L i , r u ) where h(L i , r u ) is some cryptographically secure one-way hash function that computes the hash on data L i along with some random number r u . The random value, r u is different for different users. This ensures that the hash of the same information, e.g., a certain residential address is different for different users, thus thwarting linkability of information if it belongs to two different users. In addition to the hashes, each hashed data node also contains up to two signatures for the corresponding hash value. The mandatory signature is from the user, sig u (h(L i , r u )), while the other optional signature is from the respective organisation, sig o (h(L i , r u )), in charge of issuing the data as shown in Figure 2. For example, in Japan, if L5 denotes the user's current residential address then D5 will contain the hash of L5, the signature from the user and the signature from the respective city or ward office endorsing the information.

Group level: In the group level, the group nodes are defined by the user and are useful for semantic grouping as well as privacy during verification. For instance, national identity information may be in a group with visa information while residential addresses could be in a different group. Each group contains the hash of the concatenation of the hash values (of the actual data) stored in its children data nodes. The newest child in the group appears rightmost in the concatenation. Each group also contains the user's signature of its contents.

Root level: The root level node contains a similar concatenation of its children group nodes. The root node also contains the user-specific random number, r u , a signature from the user and another from the metadata provider maintaining the graph.

Dependency overlay: The dependencies can exist between the data level nodes and the hashed data level nodes, with one-way pointers from the data level to the hashed data level. Dependencies can help retrieve related data, are defined when adding new data and are immutable after that. For example, if a user holding the nationality of country C 1 acquires a work-permit in country C 2 to live and work there, then the data node for the work permit may have an optional pointer to the signed data for the citizenship. This signifies the semantic dependency that the visas depend on a specific nationality. While declaring the optional dependency is the user's choice, the signing authority, o, for the corresponding hashed data level node may reject a certain declared dependency if it is deemed irrelevant, or conversely require the declaration of a specific dependency. The dependencies can be one-to-one, one-to-many, many-to-one, many-to-many and cross-group. All dependencies are backward links, in terms of time.

Storage of the VIGraph

Parts of the VIGraph will be stored by the user as well as the metadata provider(s).

There can be more than one metadata provider, in which case the VIGraph may be stored across multiple metadata providers with erasure coding to ensure reliability. The user will store everything but the root whereas the metadata provider will store everything but any node from the data level -thus, the user is responsible for storing the actual data. This allows the graph to be verified in part or full against the version stored by the metadata provider(s) without having them to also maintain a copy of the actual data, which can contain sensitive information.

Data operations on the VIGraph

Add operation: The add operation enables adding leaf nodes at the data level to an empty graph or an existing one. In both cases, we assume that the user has already generated a public key, private key pair. Figure 3(a) illustrates the steps the user needs to take to add a new data node to an empty, i.e., non-existent graph. The states: Obtain organisational signature and Publication depend on validation from the organisational signatory, o and the metadata provider, p, respectively. The entity o may not provide the optional signature. Figure 3(b) illustrates the steps the user needs to take to add a new data node to an existing graph. Depending on whether the new data is being added to a new group or an existing group, the add operation will require the validation, by the metadata provider, of the optional group hash update and the root hash update. The user must prove to the metadata provider the knowledge of the existing group and root hashes, and the fact that those existing hashes indeed update to the new ones when the new data is added. In both cases of adding a node to a new graph or an existing graph, the metadata provider may not sign the root hash of the graph if it fails to check, including offline mechanisms beyond the scope of this paper, the validity of the information being added.

Delete operation:

The user can only 'remove' a data leaf node from local storage. This does not delete the corresponding hashed data node but it will ensure that the original data node is no longer recoverable. The hashed data node can still be used in verification of other data nodes without compromising the privacy of the actual data that it encapsulates. Removing the organisational signature during the verification process further ensures that the verifier is unable to guess what the original data deleted node was, given its hashed value only.

Group restructuring: Group structuring allows one data leaf node and its corresponding hashed data node to be moved from one group to another. The move operation is effectively a delete operation followed by an add operation. Since the node being moved is not removed from the graph, moving groups may result in inter-group dependencies. Suppose D x denotes the concatenated hashes of all the other sibling data hash nodes (in the hashed data level), i.e., the concatenations of some

D x = h(L i , r u )|| . . . ||h(L k-1 , r u ).
To delete an existing node L k from group G k , the user needs to prove, to the metadata provider, that the hash contained in the existing G k is h(D x ||h(L k , r u )). Once validated, the hash contained in G k that has been updated to h(D x ) is signed by the user. The rest of the move operation is just the same as an add operation to an existing graph, except that h(L k , r u ) will already have the necessary signatures on it.

Data verification

The verification process is illustrated in Figure 4. The verifier, e.g., a service provider, requests two sets of data; one from the user and the other from the metadata provider(s). Note that only the signed root hash and the user-specific random number are the required information from the metadata provider and the rest are optional. The verification process has three stages. Firstly, the verifier computes the hashes on the data provided by the user and cross-checks if those hashes match the ones obtained from the user and the metadata provider(s), and that their signatures are correct. The verifier can also check the optional dependencies at this stage. Secondly, the verifier uses information of all other provided data hashes to compute group hashes, and check if these and their signatures match those obtained from the user and the metadata provider. Finally, it computes and verifies the root hash in the same way and checks against the one obtained from the metadata provider(s). It is evident that in order to verify an information component (in the data level), it is necessary for the user to provide information of the hashed data level of all the other children of the group. The larger the number of children, the more inefficient this is. This shows, as indicated before, that having one or few groups to represent all data is inefficient although the framework will still work.

3 Discussion and the state-of-the-art Blockchains [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF][START_REF] Swan | Blockchain: Blueprint for a new economy[END_REF] have been used [START_REF] Zyskind | Decentralizing privacy: Using blockchain to protect personal data[END_REF] to store anonymised but verifiable information for identity and access control, including commercial work from KPMG 1 and Deloitte2 . Blockchains are considered as the so-called 'trustless' systems that remove the need to trust any entity in particular because a decentralised consensus mechanism provides majority opinion. The idea of a trustless system is questionable because the verifier has to trust the accuracy of the consensus mechanism and the underlying hash function instead of any specific entities. With a public blockchain involving a very large number of participants, the probability of collusion and hence alteration of majority opinion is low but not impossible. With a private blockchain involving a limited number of participants, the risk of collusion is higher. Furthermore, public blockchains are not scalable since all participants have to maintain a very large hash chain, and agree on a consensus. In addition, maintaining the information of every user in a single blockchain may prove wasteful in certain situations. While fault tolerance of blockchains is often attributed to their decentralised nature, it is to be noted that other decentralised means of storage of information, e.g., erasure coding, also achieves fault tolerance without the downsides of the consensus algorithm. In our work, we show that hash trees alone can be sufficient for verifiability of selectively released information.

Selective release of personal information is a well-studied subject. Kiyomoto et. al's work on privacy policy manager [START_REF] Kiyomoto | PPM: Privacy policy manager for personalized services[END_REF] discusses a framework that enables interpreting privacy policies easier for users, which has been standardised by the oneM2M initiative [START_REF] Datta | oneM2M architecture based user centric IoT application development[END_REF]. Sanitizable signatures schemes [START_REF] Ateniese | Sanitizable signatures[END_REF][START_REF] Miyazaki | Invisibly sanitizable digital signature scheme[END_REF][START_REF] Brzuska | Security of sanitizable signatures revisited[END_REF] allow a semi-trusted third party called sanitizer to sign on a modified message using just the public key from the signer without interacting with her. The constraint is that the modifications lie in the predetermined parts of the original message by the signer. This kind of signatures is useful when the message owner wants to release multiple versions of a message. It is applicable in the situation where some sensitive information of the message need anonymisation. However, it can not be directly applied to the case of verification with selective release, which is the concern of our work. Interestingly, sanitizable signatures can be viewed as a work orthogonal to ours. As a future direction, we may utilise it in our VIGraph proposal to provide better privacy protection. Aggregate signatures [START_REF] Boneh | Aggregate and verifiably encrypted signatures from bilinear maps[END_REF] can also be utilised to tackle the requirements of KYC since it allows the addition of signatures. The signatures of n messages from n different signers can be aggregated into a single signature, which can verify the integrity of all the n messages. Attributebased access control [START_REF] Goyal | Attribute-based encryption for finegrained access control of encrypted data[END_REF] can provide fine-grained access credentials to different entities, but is different from verifiability of fine-grained information. Leung and Mitchell [START_REF] Leung | Ninja: Non identity based, privacy preserving authentication for ubiquitous environments[END_REF] proposed a privacy preserving authentication protocol, which allows a service provider to successfully identify the user without breaching the user's private information. Direct Anonymous Attestation (DAA) schemes are special signatures which provide a balance between signer authentication and privacy.

Conclusion and future work

In this paper, we have presented a generalised hash tree based framework for verifying selectively-released information through a trusted third party, which stores different parts of the hash graph but not the actual data. We have discussed how our framework enables selective release of data for verification, thus helping with privacy. Throughout this paper, we have used personal profile as an example but our framework can be applied to other types of data. Beyond what we have identified as future work in the paper, we aim to refine the deletion operation in our framework to make it compliant with right-to-forget. We also plan to implement a prototype, and run user and performance evaluations; and compare our proposal more extensively with blockchain based alternatives.

Figure 2

 2 Figure2illustrate the contents of the nodes at various levels of the VIGraph. Data level: The leaf nodes L0 . . . L9 (refer to Figure1) are the actual data, L i , such as (using the personal profile example) national identity information, residential addresses, driving license and so on. Each node may also contain optional dependency pointers, described later. Hashed data level: The hashed data nodes, D0 . . . D9, on the hashed data level, contain the hashes of the data node contents, such that D i = h(L i , r u ) where h(L i , r u ) is some cryptographically secure one-way hash function that computes the hash on data L i along with some random number r u . The random value, r u is different for different users. This ensures that the hash of the same information, e.g., a certain residential address is different for different users, thus thwarting linkability of information if it belongs to two different users. In addition to the hashes, each hashed data node also contains up to two signatures for the corresponding hash value. The mandatory signature is from the user, sig u (h(L i , r u )), while the other optional signature is from the respective organisation, sig o (h(L i , r u )), in charge of issuing the data as shown in Figure2. For example, in Japan, if L5 denotes the user's current residential address then D5 will contain the hash of L5, the signature from the user and the signature from the respective city or ward office endorsing the information. Group level: In the group level, the group nodes are defined by the user and are useful for semantic grouping as well as privacy during verification. For instance, national identity information may be in a group with visa information while residential addresses could be in a different group. Each group contains the hash of the concatenation of the hash values (of the actual data) stored in its

Fig. 2 .

 2 Fig. 2. Contents of the nodes at various levels of the VIGraph.

Fig. 3 .

 3 Fig. 3. The user-side state diagrams for the add data operation to: (a) an empty graph, and (b) an existing graph.

Fig. 4 .

 4 Fig. 4. The required information and the process for verification.

  Hashed nodes of all other data in the same group as each requested hashed data value Signed group nodes not containing any of the requested data Signed hashes nodes of requested data values

	Metadata provider provides	User provides
	Signed root
	Signed group nodes containing the requested data
	Signed hashes nodes of requested data values
	User-specific random number		Requested data values
	Data hashes ø compute and verify requested data hashes ø optionally, verify dependencies ø verify hashed data signatures	Group hashes ø compute and verify group ø verify group hash signatures hashes	Root hash ø compute and verify root hash ø verify root hash signatures

See: https://goo.gl/oaECro.

See: http://www.deloitte.co.uk/smartid/ and https://github.com/ SmartIdentity/smartId-contracts.