During the past years, achieving interoperability, i.e. creating identity federations, between di erent eID systems has gained relevance. A key problem of identity federations is the missing harmonization between di erent attribute providers (APs). In closed eID systems, ontologies allow a higher degree of automation in the process of aligning and aggregating attributes from di erent APs. This approach does not work for identity federations, as each eID system uses its own ontology to represent attributes. Moreover, providing attributes to intermediate entities required to align and aggregate attributes potentially violates privacy rules. To tackle these problems, we propose the use of combined ontology alignment approaches and locality-sensitive hashing (LSH) functions. We assess existing implementations of these concepts by means of criteria that are speci c for identity federations. Obtained results show that suitable implementations of these concepts exist and that they can be used to achieve interoperability between eID systems on attribute level.
Electronic identities (eID) have become a crucial concept of electronic services from both the private and the public sector. For instance, e-government solutions use eIDs to identify and authenticate citizens in governmental online processes.
An eID process involves several entities. The Identity Provider (IdP) establishes and veri es the identity of the user. The Relying Party (RP) makes transaction decisions based on receipt and validation of a user's authenticated credentials within the Identity System (IS). For instance, a Service Provider (SP) can assume the role of the RP.
In most ISs, identity attributes are used together with the eID of a user. For instance, the RP might additionally be provided with the user's name and date of birth. From a conceptual perspective, identity attributes are provided by
Attribute Providers (APs). In practice, IdP and AP can also be represented by one and the same entity.
Several attempts have been made recently to achieve interoperability between ISs, i.e. to establish an eID federation. In Europe, the EU large scale pilots STORK1 and STORK 2.02 have successfully established eID interoperability between EU member states (MS). As a result, citizens from MS A can use their national eID to identify and authenticate at SPs from MS B and vice versa.
Note that in most cases interoperability of eID attributes is implicitly assumed. In scenarios that involve multiple ISs this assumption is usually not valid and attributes cannot be easily exchanged between entities. In this paper, we address this issue. We propose the use of ontology-alignment (OA) solutions and locality-sensitive hashing (LSH) functions to aggregate attributes in eID federations. We survey existing implementations of these two technologies and assess them. This way, this paper represents a signi cant step towards privacypreserving attribute aggregation in federated eID systems. 2
Ontologies are a useful concept to facilitate the use of attributes from di erent APs. To cope with di erent ontologies from di erent ISs, the AE can follow an OA approach. This enables the AE to create an alignment describing the relation between di erent ontologies.
To achieve a reliable OA, the AE potentially needs to request more attributes from APs than originally requested by the RP. Unfortunately, this can violate minimum-disclosure rules and hence reduce privacy. To address this issue, we propose the use of LSH functions. In contrast to ordinary hash functions, LSH functions re ect the similarity of input values to derived hash values. This way, relevant information for OA purposes can be exchanged without violating privacy rules.
For both technologies employed, various implementation already exist. In the following subsections, we survey these implementations to provide a solid foundation for subsequent assessments. 2.1
The OA solutions are used to obtain a common knowledge representation among entities. Two or more ontologies are aligned to enable involved entities to use a common vocabulary to communicate with each other. In the following, three of the most commonly used solutions that can be applied in OA are brie y sketched.
{ AlignAPI: The Alignment API (AlignAPI3), available in Java, can be used
for representing OAs and for the development, integration and composition of
matchers. It provides examples and the basic tools for manipulating OAs [
5 http://www.labged.net/index.php?rubrique=mapage38
LSH functions map similar objects into the same hash buckets with high
probability. LSH functions ensure that the collision probability is higher for closer
objects (objects with similar values) than for farer objects (objects with di erent
values) [
Digests with a distance > 100 are considered as not similar [
To determine the best existing implementations of OA solutions and LSH functions, we conduct assessments on all solutions surveyed. In the following, relevant assessment criteria are derived and obtained assessment results are presented. 3.1
Assessment of the surveyed implementations has been based on a set of assessment criteria. All criteria have been de ned such that they enable assessment of the surveyed solutions with regard to their e ectiveness and ease of integration.
Some of the criteria de ned are relevant for both LSH functions and OA solutions. Most of them are non-technical, but still relevant especially with regard to a solution's ease of integration. This includes the following criteria: { Documentation (Doc): related to the amount and quality of resources that are available; { Implementation (Imp): the programming language (PL) used or interfaces provided; and { Processing Time (PT): describes the time required to execute a given task.
In addition to the criteria that are relevant for both OA solutions and LSH functions, several criteria can be identi ed that are relevant for LSH functions only. This includes the following criteria: { Function Score (F-S) and Clear-Text Score (CT-S): The F-S and Ct-S provide the function's obtained score (between signatures) and the absolute similarity score (between clear texts) in a given test. The values are computed using the Levenshtein Distance (LD) between the values provided as input and are normalized considering the signature length. { Similarity Scale (SSca): describes SSca used by the evaluated implementation.
Finally, speci c assessment criteria can also be de ned for OA solutions. They include the following aspects: { Similarity Scores (SSco): provides the values, considering the SSca of the evaluated solution, obtained on the assessment; { Mappings Identi ed (MI): describes the absolute number of correspondences on both evaluated ontologies.
Based on these criteria, all surveyed implementations have been assessed. Results obtained from these assessments are summarized in the following. 3.2
Mapping the de ned assessment criteria to the implementations surveyed has yielded interesting results. These results are presented in this section.
solutions have diverse sources of documentation. The surveyed implementations are available either as Java API or as Protege Plugin and have been published under LGPL or MPL. Table 1 summarizes all results concerning available documentation and implementation. We ran some tests to compare the implementations' Solution Doc. Imp. License AlignAPI Web Page, Tutorial Java API LGPL PROMPT Wiki Java API, Protege Plugin MPL
XMAP Web Page (last update 2011) Protege Plugin N/A e ectiveness and e ciency. Tests were performed by loading two ontologies, O1 and O2 (available online as storkPerson7 and storkPerson18), and by verifying obtained matches. The two ontologies used had the same concepts, but four of
them had been written with similar terms, namely: eMail $ e-mail; dateOfBirth $ birthDay; surname $ lastName; and givenName $ name.
Since the ontologies O1 and O2 present previously known similar terms, we were able to verify the accuracy of each OA solution. Results obtained are summarized in Table 2.
Solution PT SSco MI AlignAPI 1.467s 0.96807 22 PROMPT 4.036s Not provided 1
XMAP Not nished N/A N/A
We also investigated the PT on the surveyed solutions. Running the test with the ontologies O1 and O2 revealed that the AlignAPI was 2.75x faster than PROMPT.
The tests also showed signi cant di erences between AlignAPI and PROMPT solutions regarding the number of matchings found. Running the tests with O1 and O2 yielded 22 matchings found by AlignAPI, and only one matching found by PROMPT. Table 2 illustrates these results.
Summarizing the results obtained, it can be concluded that AlignAPI is the most suitable solution. This solution outperforms other alternatives with regard to performance and ease of integration.
lutions, all surveyed LSH functions provide diverse sources of documentation and are available in several PLs. All surveyed solutions are available under the Apache License (AL). The SSca of each solution was evaluated as well. Obtained results are summarized in Table 3.
Solution Doc. Imp. License SSca MinHash GSCW Group 1 AL 0 - 10 Nilsimsa GSCW Group 1 + Group 2 AL 128 - (-128)
TLSH GitHub Python, Java, JS AL 0 - 200 / 0 - 400
We also ran tests to assess the performance of the di erent solutions. Note that the TLSH9 function is unable to produce results on inputs with a size
smaller than 256 bytes. This constraint makes this solution unsuitable for use cases related to eID attributes, as they are potentially very short. For this reason, TLSH was precluded from further performance assessments.
Four tests have been de ned and run to assess the performance of the remaining two LSH solutions. The tests compute the similarity between the hash values from user names (HN1 and HN2), i.e. a typical eID attribute. We generated and used a set of 1,000 records with random data (i.e.: given name, family name, birthday, etc.) to run these tests. For each test, slightly di erent input values have been used as de ned below: 1. Test 1: HN1 and HN2 received the same full user name (F-UN); 2. Test 2: HN1 received the F-UN and HN2 received the same F-UN provided but used some abbreviation. 3. Test 3: HN1 and HN2 received the same set of 1,000 F-UN. 4. Test 4: HN1 received a set of 1,000 F-UN and HN2 received a set of 1,000 F-UN provided but used some abbreviation.
Execution of Test 1 provided the metrics of each function performing the analysis of just one element (record) with a full match. Test 2 provided a similar metric, but considered similar values. Test 3 used 1,000 records with full matches, a scenario close to a real-world. The same applied to Test 4, which combined the speci cs of Test 2 and Test 3. Table 4 shows the results obtained. Solution
Time MinHash 90:73 Nilsimsa 2:074
Test 1
F-S Ct-S Time 0:941 0 94:08 0 0 3:169
Test 2
F-S Ct-S Time 0:941 5 597:4 0:56 5 278:5
Test 3
F-S Ct-S Time 0:847 0 518:7 0 0 327:0
Test 4 F-S 0:847 0:667
Ct-S 0:288 0:288
Regarding the PT, Nilsimsa was from 43x (Test1) to 1.6x (Test 4) faster than MinHash . We used the LD to gauge the similarity of input values and output values. Results showed that Nilsimsa yielded closer values to the LD of input text than the MinHash . For Test 1 and Test 3, the result was exactly the same. For Test 4, the result of Nilsimsa was 25% closer than the outcome of MinHash.
Table 4 summarizes assessment results of the surveyed LSH Functions. From the results obtained, we conclude that Nilsimsa is the winner, as it outperforms other solutions and complies best with relevant assessment criteria. 4
In this paper we have proposed the use of ontology alignment and LSH functions
to leverage attribute interoperability in eID federations. A survey conducted has
revealed that implementations of these two technologies already exist but are
not tailored to the use case given. We have hence applied systematic
assessments of available solutions by means of relevant criteria. These assessments
have revealed that AlignAPI [
In future work, we will use results obtained to realize an AE as illustrated in Figure 1. This AE will nally enable attribute interoperability in eID federations. The work presented in this paper is a fundamental basis, as it assures that the two most relevant building blocks of the AE, i.e. ontology alignment and LSH functionality, are implemented in the most e ective and e cient way. Acknowledgment. This work was partially supported by CAPES Proc. Num. BEX 9096/13-2 and EU project Stork 2.0 CIP-ICT-PSP-2011-5-297263.