Tobias Pulls
email: tobias.pulls@kau.se

(More) Side Channels in Cloud Storage Linking Data to Users

Public cloud storage services are gaining in popularity and several commercial actors are offering their services for users, however, not always with the security and privacy of their users as the primary design goal. This paper investigates side channels in public cloud storage services that allow the service provider, and in some cases users of the same service, to learn who has stored a given file and to profile users' usage of the service. These side channels are present in several public cloud storage services that are marketed as secure and privacy-friendly. Our conclusions are that cross-user deduplication should be disabled by default and that public cloud storage services need to be designed to provide unlinkability of users and data, even if the data is encrypted by users before storing it in the cloud.

1 Deduplication can take place on the block-or file-level. In this paper we talk about files, but everything discussed can equally well be applied to blocks. 2 With the assumption, or hope rather, that there will be no hash collision.

Introduction

The setting for this paper is that of cloud storage services, where a service provider offers a service for users to store their data in the cloud. Commercial cloud storage services such as Dropbox [START_REF]Dropbox: Dropbox -simplify your life[END_REF], SpiderOak [START_REF] Spideroak | Zero-knowledge data backup, sync, access, storage and share from any device -spideroak.com[END_REF], Tarsnap [START_REF]Tarsnap: Tarsnap -online backups for the truly paranoid[END_REF], and Wuala [START_REF]Wuala: Wuala -secure online storage -backup. sync. share. access everywhere[END_REF] provide storage for millions of users and are gaining in popularity. These cloud storage services are all public clouds, that is, they are available to the general public over the Internet [START_REF] Mell | The NIST definition of cloud computing[END_REF]. For so called private clouds [START_REF] Mell | The NIST definition of cloud computing[END_REF], in the case of all infrastructure being completely operated by the entity using the infrastructure, the issues raised in this paper are in part or completely nonissues. The focus in this paper is on public clouds, and in particular cloud storage services offered by one party (the service provider) to other parties (users).

For cloud storage to be widely adopted, there has to be assurances towards users that their data remain private, and that uploading their data to the cloud has limited effect on what an adversary can learn about them [START_REF] Harnik | Side channels in cloud services: Deduplication in cloud storage[END_REF][START_REF] Kamara | Cryptographic cloud storage[END_REF]. In other words, the security and privacy of the users of cloud storage services need to be preserved; otherwise some users will not make the move to the cloud.

Our contributions are as follows:

-We formalise an attack that, when cross-user deduplication (explained in Section 2) takes place, has serious privacy implications for users of cloud storage services. The implication of the attack is amplified when storage is distributed among the users of the service. -We investigate the impact of the attack on a number of different storage services and related systems of particular interest. -We consider the implications of linkability of users and their data alone (such as can be the case when cross-user deduplication is not performed and encryption is done prior to uploading a file to a storage service) and what threats there still are to the users' privacy, for example for users of CS2 [START_REF] Kamara | CS2: A semantic cryptographic cloud storage system[END_REF], SpiderOak [START_REF] Spideroak | Zero-knowledge data backup, sync, access, storage and share from any device -spideroak.com[END_REF], or Tarsnap [START_REF]Tarsnap: Tarsnap -online backups for the truly paranoid[END_REF].

Ultimately, we hope that our overall contribution provides a compelling case for (i) that cross-user deduplication should be disabled by default and (ii) that there needs to be, by design, unlinkability of users and their data in cloud storage services.

The following three sections describe the deduplication technique, related work and our adversary model. Section 5 describes an attack, first in general terms, then its implications for distributed storage services such as Wuala [START_REF]Wuala: Wuala -secure online storage -backup. sync. share. access everywhere[END_REF]. We also investigate the impact of the attack on a number of different systems. The section ends with a summary of the attack. Next, in Section 6, we look at the effects of linkability of users and data on the privacy of the users of cloud storage services. Finally, we conclude the paper in Section 7.

Deduplication

We follow the terminology used by Harnik et al. [START_REF] Harnik | Side channels in cloud services: Deduplication in cloud storage[END_REF]. Deduplication is a technique used by, among others, storage providers to save storage and bandwidth. Instead of storing multiple copies of a file 1 only the original file is kept and links are created to the original when further uploads of the same file are made. Crossuser deduplication is when deduplication takes place across users, for all users of a service or within some set of users. Deduplication can be either target-or sourcebased. In the target-based approach the service provider performs deduplication, resulting in saved storage space but no savings in bandwidth usage. For sourcebased duplication, the users perform the deduplication (aided by client software) and both storage space and bandwidth usage are saved, since the user checks with the storage provider whether a file has already been stored before uploading. This check can be, and commonly is, done by calculating the hash of the file and sending it to the storage service 2 .

Figure 1 shows a conceptual overview of source-based cross-user deduplication taking place for Alice and Bob. They have both uploaded the same file (seen at the bottom of the figure), but only one actual copy resides in the storage service. What they both have can be viewed as a folder at the storage service with links to the files they have uploaded. The very first upload of the file to the storage service would naturally involve storing a full copy of the file at the storage provider. However, for later uploads of the same file, by for example Eve, the only change in the service would be that her folder would get a new link to the previously uploaded file. No identical copy of the uploaded file would actually be stored.

When a file is to be stored in the storage service there is some sort of mapping taking place, represented in the figure as µ. This mapping can be as simple as encoding the file to the appropriate format, but it might also involve some form of encryption.

Client-side encryption and source-based cross-user deduplication at the same time is made possible ultimately by carefully selecting how, within the set of users for which deduplication is to take place, the encryption key is derived for each file. The function that determines the encryption key for a file has to be based on information that all of the users (for which deduplication is to take place for) has access to. A simple and common approach is to have the encryption key for a file be determined by the hash of the file. In this way, every user that wishes to upload a file will generate the same encryption key and thus produce the same ciphertext3 that can easily be deduplicated as described earlier. To be able to decrypt any encrypted file in such a system you would need access to the plaintext in the first place to generate the corresponding key. In Figure 1 the mapping of a file to its representation in the storage service involves some form of encryption. If Eve does not have access to all the information needed to generate the same encryption key as Alice and Bob used, then her encryption of the same file will result in a different ciphertext and appear to the storage service as a different file, preventing cross-user deduplication from taking place.

Related Work

Kamara and Lauter [START_REF] Kamara | Cryptographic cloud storage[END_REF] provide an overview of what currently can be accomplished by using cryptography when constructing a secure cloud storage service. They also present a practical and provably secure cryptographic cloud storage system named CS2 [START_REF] Kamara | CS2: A semantic cryptographic cloud storage system[END_REF]. In general, cryptographically secure cloud storage services do not use deduplication (we will later explore some exceptions). Deduplication is a technique, as described earlier, to save resources in the form of storage and bandwidth. As with most things in life, there is no such thing as a free lunch. This trade-off was first discussed in academia, to the best of our knowledge, in [START_REF] Douceur | Reclaiming space from duplicate files in a serverless distributed file system[END_REF]. Further discussions on the subject can be found online, for example on The Cryptography Mailing List4 , initiated by one of the authors of Tahoe-LAFS [START_REF] Wilcox-O'hearn | Tahoe: the least-authority filesystem[END_REF] (Tahoe-LAFS is discussed later in this paper). A relatively recent academic paper on the potential security and privacy issues with deduplication was published by Harnik et al. [START_REF] Harnik | Side channels in cloud services: Deduplication in cloud storage[END_REF]. Discussion on this trade-off has also led to some storage providers taking an active stance against cross-user deduplication. A prime example is SpiderOak [START_REF] Spideroak | Zero-knowledge data backup, sync, access, storage and share from any device -spideroak.com[END_REF] that in a blogpost5 described in essence the work of Harnik et al. [START_REF] Harnik | Side channels in cloud services: Deduplication in cloud storage[END_REF] and what a large part of this paper discusses; namely that cross-user deduplication coupled with legal requests to the service provider puts the privacy of the users of the service at risk. Our contribution is, however, more comprehensive: we formalise the attack in question, break it down into its two main components, investigate how it is applicable to more services and systems than SpiderOak, and furthermore describe privacy issues in services, such as SpiderOak, only due to linkability of users and data in Section 6.

When source-based cross-user deduplication takes place, Harnik et al. identified that the storage service in essence is an oracle that answers the query "did any user previously upload a copy of this file?" Utilising this, they presented three side channels in cloud storage, summarised briefly as follows:

1. Identifying Files. By simply uploading a file and observing if deduplication takes place it is possible to tell if the file has been previously uploaded or not. 2. Learning the Contents of Files. By applying the first attack on multiple versions of the same file, an attacker can essentially perform a brute-force attack over all possible values of a file's content. 3. A Covert Channel. By uploading specific files deduplication can act as a covert channel for communication for two or more users.

In the same paper, the authors present a solution that mitigates the attacks for a fraction of the files on a storage service by introducing dummy uploads for files up to a randomly selected threshold of copies. The size of the fraction of files mitigated depends on the size of the space the threshold is selected from. For uploads up to the threshold target-based deduplication is used. This mitigation comes at the cost of bandwidth but with no negative impact on the storage gain from deduplication for the storage provider.

Adversary Model

Soghoian [START_REF] Soghoian | Caught in the cloud: Privacy, encryption, and government back doors in the Web 2.0 era[END_REF] describes the legal precedent in the US for how service providers offering cloud computing services can be forced to turn against their users. This includes obligations to covertly backdoor their software to aid government agencies, as Hushmail was compelled to do in 2007, or enable logging of data available to the service provider, as TorrentSpy was forced to in 2007. Another prime example is the USA PATRIOT Act [START_REF]Public Law 107 -56 -Uniting and Strengthening America by Providing Appropriate Tools Required to Intercept and Obstruct Terrorism (USA PATRIOT ACT) Act of 2001[END_REF]. It provides law enforcement in the US with the legal right to, among other things, search through electronic communication information and other transaction information at service providers with little restrictions. In Europe, the Data Retention Directive 2006/24/EC [START_REF]EUR-Lex -Access to European Union law[END_REF] requires that communication service providers retain traffic and location data about their users. These examples do not consider what, for example, totalitarian regimes, military organisations or intelligence agencies are capable of. Therefore adversaries to a user include the service provider, and also the other users of the same service. The service provider can itself turn malicious, be honest but curious, or forced through legal means to turn against its users [START_REF] Soghoian | Caught in the cloud: Privacy, encryption, and government back doors in the Web 2.0 era[END_REF]. A service provider could also be required to retain some data by law that could negatively affect the security or privacy of the user [START_REF] Berthold | Data retention and anonymity services[END_REF]. Other users may exploit the design of the storage service offered by the service provider, as shown in [START_REF] Harnik | Side channels in cloud services: Deduplication in cloud storage[END_REF]. These are all tangible threats to a user of a service, even if the service provider has the best of intentions.

In essence, the goal is to limit the amount of information adversaries can deduce about a user. Any channel that increases the information an adversary has about the user needs to be addressed. Solutions need to be technological in nature and not based upon regulations or policies, since our definition of an adversary includes entities that are obliged by law to invade or restrict the privacy of a user. One, if not the primary, reason for performing deduplication is that it saves significant storage space for the storage provider. This again is presumably greatly enhanced if the deduplication takes place across users (cross-user deduplication). As a consequence of deduplication, the amount of copies stored at the provider of a specific file is reduced, optimally (from a storage point of view) only unique files need to be stored. To accomplish deduplication in storage services, two operations have to be deterministic; the mapping of a file to its representation in the storage service and the function that determines the storage location of a file. If the mapping is non-deterministic, then two uploads of the same file will potentially result in different representations of the file in the storage service. Similarly, if the same representation of a file is not stored at the same place then there will be several copies of the same file stored in the storage service.

In this section, we formalise an attack that, when cross-user deduplication takes place, has serious impact on the privacy of the users of the storage service, by allowing an adversary to link files to users. This attack is not mitigated by the solution presented in [START_REF] Harnik | Side channels in cloud services: Deduplication in cloud storage[END_REF]. Which adversaries are capable of performing this attack depends on the design of the storage service. After describing the attack we will investigate its applicability in and relation to Wuala, BitTorrent, Freenet and Tahoe-LAFS.

A Formalised Attack

We denote the mapping of a file f to its representation f in the storage service as µ : f → (κ f , f ), where κ f is the lookup key for f in the storage service. This is the same mapping as was described earlier in Section 2. The storage location for f in the storage service is denoted as λ f and the function that determines the location in the storage service as σ : κ f → λ f . Figure 2 visualises the notation. First the file is mapped by µ into its internal representation (which may involve encryption, as discussed in Section 2). The lookup key for the mapped file is given to the function σ to determine the storage location for the file in the storage service.

Using the notation we just defined, there are two steps involved in being able to link files and users:

1. Acquire a copy of the file f and its mapping µ : f → (κ f , f ). 2. Obtain the ability to observe requests by users for f . This can be done, for instance, by monitoring requests to (a) the function σ : κ f → λ f for the storage location of f , or (b) the actual storage location λ f of f .

The mapping µ has to be the same among the users for which deduplication is taking place, otherwise the same file will map to different files within the storage provider and deduplication will be impossible. In other words, for a file f if two different mappings µ 1 and µ 2 are used, then µ 1 (f ) = (κ f 1 , f 1 ) and

µ 2 (f ) = (κ f 2 , f 2 ), where κ f 1 = κ f 2 and f 1 = f 2 .
Since the function σ determines the storage location, and different files should be stored at different locations, then σ(κ f 1 ) = σ(κ f 2 ) and deduplication does not occur. So, as a consequence of deduplication, step 1 is always possible within the set of users where deduplication is done. Note that this is independent of whether deduplication is target-or source-based. If cross-user deduplication is enabled by default, this means that all users by default use the same mapping and thus can all perform the first step of the attack. Presumably this is also the case for the service provider, who can simply take the role of a user of its service to learn the mapping.

Performing the second step of the attack depends on the setting and design of the storage service. In what is probably the most common setting, where the storage service is being offered by a centralised provider, the storage provider determines where each file should be stored (step 2a) and has the capability of monitoring requests to the actual storage location (step 2b), since it is the entity doing the actual storage. While a storage provider might make claims of not saving this information, if it remains technically possible, a provider might be forced to, as discussed in Section 4.

We have broken down the steps in linking files and users for storage services in terms of and in relation to the essential functionality for storage services performed by the two functions µ and σ. Next, we will look at how feasible it is to link files and users in several settings, starting with the storage service Wuala [START_REF]Wuala: Wuala -secure online storage -backup. sync. share. access everywhere[END_REF] where storage is distributed among users.

Wuala -Distributed Storage Among Users

Wuala's distributed storage is an abstraction of a DHT (Distributed Hash Table), broken down into client, storage and super nodes. Super nodes perform all routing by being connected to client and storage nodes. According to available sources, users are client nodes and can only become storage nodes by opting-in to share some local storage. Super nodes are run by Wuala. When a file is uploaded to Wuala it is first encrypted (the key is the hash of the file) and then split into n redundant fragments using erasure codes such that any m < n fragments can be used to reconstruct the file. The fragments are then uploaded to storage nodes and Wuala's own servers. Information on the design of Wuala is limited to what can be found on Wuala's homepage [START_REF]Wuala: Wuala -secure online storage -backup. sync. share. access everywhere[END_REF], in a published paper on their cryptographic tree structure [START_REF] Grolimund | Cryptree: A folder tree structure for cryptographic file systems[END_REF] and in a Google Tech Talk6 . Wuala publicly states 7 that it performs source-based cross-user deduplication, which we verified using the procedure outlined in [START_REF] Harnik | Side channels in cloud services: Deduplication in cloud storage[END_REF].

The next step is translating what we now know about Wuala into the notation used in Section 5.1. Since Wuala performs source-based cross-user deduplication the mapping µ is available and shared by all users. The function σ is run by the super nodes which in turn are run by Wuala exclusively to the best of our knowledge. However, users can query σ to learn λ f , where λ f represents the storage locations for all the fragments (or a large enough subset) needed to reconstruct f . In addition, users can by opting-in become the actual storage location for fragments of files in Wuala.

Since Wuala controls σ and also stores enough fragments to recreate every file uploaded to Wuala, it is clear that they, as the storage provider, have the ability to link any given file in the system to its users. The challenge for a user that wants to perform the same linking lies in becoming a storage node for fragments of the specific file it wants to link. Note that Wuala has an incentive to spread the file fragments among as many storage nodes as possible for the sake of increasing availability, to provide faster downloads for its users and reduce operational costs. We have not attempted to perform this attack on Wuala. The investment in storage and bandwidth required for an attacker is probably feasible for organisations that have a vested interest in linking users that access specific files, such as the media industry fighting piracy.

BitTorrent -Efficient File Sharing and Linkability

BitTorrent, while not a storage service but a peer-to-peer file sharing protocol, is interesting in relation to the attack described earlier. Le-Blond et al. [START_REF] Le-Blond | Spying the world from your laptop -identifying and profiling content providers and big downloaders in bittorrent[END_REF] describe how to spy on most BitTorrent users on the Internet from a single computer. They accomplish this by querying popular BitTorrent trackers8 or the DHT used by BitTorrent clients. In essence, this can be viewed as querying σ to learn λ f , where λ f is a list of all users with parts, or the entirety, of f . This highlights the danger of providing full access to σ and a shared µ to users at the same time. Naturally, when trackers are involved they are able to link users of the tracker and the files they are accessing. The main purpose of using a DHT in BitTorrent is to eliminate the need for a tracker. As a consequence users, beyond the ability they already had to query σ, take part in actually running the functionality σ provides towards other users.

In later paper [START_REF] Le-Blond | I know where you are and what you are sharing: Exploiting P2P communications to invade users' privacy[END_REF], Le-Blond et al. used the ability to spy on BitTorrent users together with an information leakage in Skype to determine where users are, who they are and what they are sharing. The linkability of users and data, later enriched by correlating with another source of information, turned into a very real privacy threat.

Freenet -Anonymous Distributed and Decentralised Storage

Freenet is a distributed and decentralised data store that provides a high degree of anonymity [START_REF] Clarke | Protecting free expression online with freenet[END_REF]. All the users that participate in the system act as distributed storage nodes and are connected, depending on configuration, in a peer-to-peer or friend-to-friend network 9 . Files stored in Freenet are identified by a key and mapped (encrypted) based upon the type of key selected within Freenet. Performing step 1 in the attack described in Section 5.1 is straight forward for any static file (content hash keys in Freenet) but requires knowledge of the generated address for dynamic files (signed subspace keys in Freenet). However, when attempting to perform step 2 of the attack the design of Freenet mitigates both step 2a and 2b. Monitoring requests for the storage location of a file (σ : κ f → λ f ) is fruitless, since nodes in Freenet only communicate with their peers. A request from a peer for the storage location of a file is the same as if it was a peer of the requesting peer that requested the file. In the same way, monitoring requests to the actual storage location of a file (λ f ) is ineffective because one can only tell which peer, and not user, that requested the file. Furthermore, files are replicated to other users in Freenet when they are requested or inserted into the system, making the number of storage locations for a popular file increasingly large.

Tahoe-LAFS -Multiple Storage Providers

Tahoe-LAFS is an open-source storage system that uses multiple storage providers to provide what they refer to as "provider-independent security" [START_REF] Wilcox-O'hearn | Tahoe: the least-authority filesystem[END_REF]. By spreading data over multiple storage providers, using erasure encoding of encrypted data like Wuala, Tahoe-LAFS becomes resistant to compromise of a subset of the providers being used. This resilience comes at the cost of introducing redundancy in storage, which degree can be configured by users. To reduce this redundancy further, Tahoe-LAFS can be configured to enable cross-user deduplication within a set of users by setting the same "convergence secret". The convergence secret can be viewed as a salt to the hash of the file used to generate the encryption key for a file. So, by default in Tahoe-LAFS cross-user deduplication is disabled and files are encrypted with unique encryption keys, thus provide different mappings (µ) for each user. Furthermore, the convergent secret is not known to any of the storage providers, so even if cross-user deduplication is enabled by a set of users, as long as they do not share their convergent secret with any service provider a provider will be unable to obtain a mapping of a file, thus preventing the provider from linking any files. To make matters worse for a storage provider that wishes to link files and users, since multiple storage providers are used obtaining the convergent secret of a user is not enough since the provider in question may not be the provider storing a particular file of interest for the user.

Summary

When cross-user deduplication takes place the number of storage locations for a file is minimised to save storage. Furthermore, the mapping of a file to its representation in the storage service has to be the same for all users that crossuser deduplication is taking place for. When cross-user deduplication is enabled by default presumably the storage provider is aware of this mapping as well. This means that the storage provider, unless specifically designed to prevent it, has the ability to link a given file to all users with that file in the storage service. It can do this by simply observing the requests for the given file's storage location or requests to the actual storage location of the file. Also, when storage is distributed among users they can gain the ability to link a given file to users, unless the service has been designed with preventing this in mind, such as is done in Freenet at the cost of bandwidth and storage for all users.

BitTorrent is an efficient peer-to-peer file sharing protocol, with little to no privacy by design for its users. The ease with which users and files are linkable are at the center of its efficiency. This highlights the danger (for users) of prioritising efficiency over security and privacy. The Tahoe-LAFS system puts the security and privacy if its users first by (i) not trusting storage providers, (ii) having cross-user deduplication disabled by default and (iii) letting the users decide about the trade-off between privacy, security and efficiency on their own.

Profiling Users' Usage

Even if cross-user deduplication is not performed, linkability is still a privacy problem. We first describe how a storage provider can profile its users by simply observing their stored data and then discuss how to best mitigate this profiling.

Observing Storage

Cross-user deduplication is not performed (or even possible) when the mapping of a file to its representation in the storage service is different for different users. For example, this is the case when the user encrypts the file with a key that only they posses before uploading it to the storage service. Then neither the storage provider nor other users can link a given file to users using the side channels described earlier. However, unless users take special precautions and the storage service is designed to prevent it, the storage provider can link stored (potentially encrypted) data and users. This allows the storage provider to profile their users in terms of when data is accessed, how much data is stored, and what action did they take. Also, unless the user takes special precautions, the storage provider can determine from where the user accesses the service. Figure 3 shows an example of the kind of profiling a service provider could do by simply observing storage utilisation over time, which together with knowledge of who performed these actions and from where is non-negligible information. Encryption only hides the actual information stored. As is shown in Figure 3, if the storage provider can tell that a user uploaded a file with the size 1491834576 bytes prior to the release of the Wikileaks insurance file at the end of July 2010 [START_REF]Wikileaks posts mysterious 'insurance' file -threat level wired[END_REF] it may pose a threat to that user. Asking who, what, when, where, how and why is a concept from journalism known as the Five Ws; a fundamental concept in gathering information [START_REF]Wikipedia: Five ws -wikipedia, the free encyclopedia[END_REF]. In fact, observing storage utilisation is similar to performing traffic analysis; both deal with analysing non-content data [START_REF] Danezis | Introducing traffic analysis[END_REF]. Just as traffic patterns may reveal sensitive information so may storage patterns. The need for hiding this kind of activity information in the cloud setting is a known problem for businesses, and may leak, or in and of itself be, confidential business information [START_REF] Chen | What's new about cloud computing security?[END_REF].

Mitigating Profiling

How much data a user has stored, and what is done with it, can be hidden by the user at the cost of storage and bandwidth, by for example using padding or encrypting a full container of data. When data is accessed can be hidden by introducing dummy traffic and uploads. From where the user is accessing the service can be hidden by using proxies or other anonymisation services. Concealing who the data belongs to on the other hand, which is arguably the most important thing with the user's privacy in mind, requires that the service is designed to support it. Recent work by Slamanig [START_REF] Slamanig | Efficient schemes for anonymous yet authorized and bounded use of cloud resources[END_REF] is a good example of a scheme for a service where who a resource (such as storage) in the cloud belongs to is cryptographically hidden. Another, however costly, approach to mitigation is to use multiple service providers, as is done in Tahoe-LAFS. Freenet goes a step even further (in terms of cost) and gets rid of the storage provider altogether.

One could argue that most storage services targeting regular users today do not require any proper identification of users to take place (so being pseudonymous is possible), but any significant storage capacity requires the user to pay for the service. In the absence of any widely available way to pay anonymously online (such as using anonymous prepaid cards, like those offered by paysafecard [START_REF] Paysafecard | Discover the prepaid solution for the internet : paysafecard[END_REF], or carefully spending Bitcoins [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF]), this enables the service provider to link the user's storage with their payment details, unless designed to prevent this very linking.

Addressing the linkability on its own may not be enough, since observing the storage utilisation of data stored at the service provider correlated with other information (like identified users performing some action that should lead to changes being made to their storage) may in and of itself be enough to link data and users. However, the effort for the service provider to profile users increases significantly if they first have to determine who the data they are storing belongs to.

Conclusion

Without strong assurances to users that their data is private and secure in the cloud, storage services will not be as widely adopted as they could be [START_REF] Harnik | Side channels in cloud services: Deduplication in cloud storage[END_REF][START_REF] Kamara | Cryptographic cloud storage[END_REF]. Cloud storage services should be designed to provide unlinkability of users and data, even if the data is encrypted by users, and cross-user deduplication should be disabled by default. Cross-user deduplication leads to side channels in cloud storage which can be mitigated by sacrificing bandwidth and storage; the main reasons for performing deduplication in the first place. Furthermore, if the service provider can link the data it stores to users that in and of itself opens up side channels that leak information about the users' usage of the service. Service providers might make claims of not storing, using or sharing information about users, but as long as it remains technically possible they may be compelled to hand over all information they can technically produce to authorities.

Harnik et al. [START_REF] Harnik | Side channels in cloud services: Deduplication in cloud storage[END_REF] presented a mitigation strategy for their identified side channels. It is possible to conceive of complementary mitigation to the side channels we have described in this paper by using anonymous credentials [START_REF] Camenisch | An efficient system for non-transferable anonymous credentials with optional anonymity revocation[END_REF], or the scheme by Slamanig [START_REF] Slamanig | Efficient schemes for anonymous yet authorized and bounded use of cloud resources[END_REF], together with the use by users of some anonymisation service, such as Tor [START_REF] Dingledine | Tor: The second-generation onion router[END_REF], for accessing a storage service. This might be sufficient for having cross-user deduplication enabled by default. There is a need to further investigate the trade-off imposed by cross-user deduplication, but until then, the only sensible approach is to leave it off by default for the sake of privacy.

Fig. 1 .

 1 Fig. 1. Source-based cross-user deduplication taking place for Alice and Bob, where the mapping µ of the file to the storage service involves encryption. Only one encrypted copy of the uploaded file is kept by the service provider, and future uploads of the same file by users will only result in references to the previously uploaded file.

Fig. 2 .

 2 Fig. 2. A visualisation of the notation used to describe the linkability attack. The figure shows how a file is mapped into its internal representation in the storage service by the mapping µ, and then its storage location is determined by the function σ.

Fig. 3 .

 3 Fig.3. By observing storage utilisation over time a storage provider can profile a user.

Assuming that a deterministic encryption algorithm is used. There are of course other options to this part of the problem, but we opt to exclude all the details and focus on capturing the essence for the sake of clarity.

http://www.mail-archive.com/cryptography@metzdowd.com/msg08949.html, accessed 2011-11-09.

[START_REF] Danezis | Introducing traffic analysis[END_REF] https://spideroak.com/blog/20100827150530, accessed 2011-11-10.

http://www.youtube.com/watch?v=3xKZ4KGkQY8, accessed 2011-05-17.

http://wualablog.blogspot.com/2010/10/top-ten-questions-and-their-answers-how. html, accessed 2011-05-17.

A BitTorrent tracker can be viewed as a key-value store run as a dedicated service, where keys are hashes of files and values are users that are downloading the file.

A friend-to-friend network is a peer-to-peer network where connections are only made between friends and not to all potential peers[START_REF]Wikipedia: Friend-to-friend -wikipedia, the free encyclopedia[END_REF].

Acknowledgments We would like to thank Simone Fischer-Hübner, Stefan Lindskog, Stefan Berthold, Philipp Winter, all the attendees of the IFIP Summer School 2011, and the reviewers for their valuable feedback. This work is funded by a Google research grant on "Usable Privacy and Transparency Tools".


Oleksandr Bodriagov

Sonja Buchegger

P2P Social Networks With Broadcast Encryption Protected Privacy

Keywords: P2P Social Network, Provider-independent, Encryption-based access control, Broadcast Encryption

Users of centralized online social networks (OSN) do not have full control over their data. The OSN provider can collect and mine user data and intentionally or accidentally leak it to third parties. Peerto-peer (P2P) social networks address this problem by getting rid of the central provider and giving control to the users. However, existing proposals of P2P social networks have many drawbacks: reliance on trust, expensive anonymization or encryption techniques, etc. We propose to use broadcast encryption for data protection because of its efficiency and ability to not disclose information about who can decrypt what. We present an architecture of a P2P social network that uses a composition of public-key cryptography, broadcast encryption, and symmetric cryptography. The architecture provides confidentiality and limited integrity protection. It defines privacy-preserving profiles that allow users to quickly find data encrypted for them while preventing attackers from learning who can access which data.

Introduction

Existing centralized, provider-dependent networks do not provide users with mechanisms to fully protect their data. The provider has complete control of the service, and users have to rely on security mechanisms provided by the service. There is no guarantee that the trusted provider will enforce the privacy preferences of the users. Besides, there can be data mining, targeted advertisements, and even disclosure of users data to third parties.

Our aim is to give full control of the data to the users in order to prevent any misuse by third parties. While laws provide an important deterrent, relying on legal protection (or, alternatively on trust relationships) is not enough to prevent a determined misbehaving third party or social networking service provider from getting access to the data and using it in some way. Laws and regulations give incentives for appropriate treatment of personal data in terms of a potential post factum punishment to follow the rules. Cryptographic mechanisms, on the other hand, can prevent unwanted access to data in the first place by technical means. Therefore, the PeerSoN project1 was started to design a peer-to-peer (P2P) provider-independent architecture with cryptographically protected privacy.

One of the main problems of P2P social network architectures is to achieve secure, efficient, 24/7 access control enforcement and data storage. None of the current P2P architectures for social networks manages to fully cope with this problem. For example, Safebook [START_REF] Cutillo | Safebook: A privacy-preserving online social network leveraging on real-life trust[END_REF] relies on trusted peers for data storage and profile data retrieval, and uses an expensive anonymization technique based on asymmetric cryptography; Diaspora [START_REF] Grippi | Diaspora. a little more about the project[END_REF] has quite high expectations on the users' willingness to run their own servers or have their data served and stored on servers of other users (a fully P2P variant of Diaspora requires users to run and manage their own servers); Persona [START_REF] Baden | Persona: an online social network with user-defined privacy[END_REF] relies on a ciphertext-policy attributebased encryption (CP-ABE), and current ABE schemes are very computationally intensive and produce ciphertexts that are linear in the number of attributes (too expensive for the P2P storage). Besides, CP-ABE schemes by definition support only open access structures, which can be considered as a security flaw since it is easy to infer who can decrypt what using that information.

In complex systems such as social networks, with many subjects and objects, with fine-grained access control (with objects encrypted differently and separately), the efficiency of encryption/decryption schemes is very important as usability depends on it. To achieve an efficient encryption-based access control with high performance encryption and decryption regardless of the number of identities/groups we use broadcast encryption (BE) schemes. The storage is assumed to be a P2P untrusted storage with multiple replicas, so that data is stored on a profile owner's computer/mobile phone (primary copy) and on chosen peers (replicas). The data is encrypted and everyone can download it, i.e. access control is encryption based. Even if the content is encrypted, there are consequent privacy implications of inferences from traffic analysis such as access patterns or properties of the stored files. Therefore, the architecture includes mechanisms to mitigate this threat.

Both the encrypted data and the broadcast encryption private keys for decrypting the data are stored at the profile owner's storage. These private keys are encrypted under public keys of intended recipients. Besides encrypted data and the BE keys, there is also public information (unencrypted) that allows others to find a user's profile. Broadcast encryption is used for data dissemination to groups and public key cryptography is used for user-to-user messaging. A multicast messaging (one message for several users) is realized via BE.

The rest of the paper is organized as follows. At first we explain the broadcast encryption, then we describe which changes we made to the chosen BE scheme and how it works. We continue by describing the architecture of the system in more detail. Then we discuss the security issues and define an attacker model. We finish by drawing the conclusions.

Broadcast encryption (BE) schemes are used to distribute encrypted data to a dynamic set of users in a cost-effective way. In general, BE scheme consists of a sender and a group of recipients. Each recipient has his/her own private decryption key to decrypt encrypted data sent by the sender.

BE schemes can either be symmetric or public key based. In the first case, only a trusted source/broadcaster of the system that generated all the private keys can broadcast data to receivers. If the system is public key based, then anyone who knows a public key of the system can broadcast.

The efficiency of BE schemes is measured in terms of transmission cost, user storage cost, and computational cost. Besides efficiency, one of the main requirements for BE schemes is that it should be easy to revoke a key/group of keys. Other important security concepts are collusion resistance and statelessness. A fully collusion-resistant scheme is robust against collusion of any number of revoked users. A BE scheme is said to be stateless if after revocation of some subset of users the remaining users do not have to update their initial private keys. A BE is called dynamic [START_REF] Delerablee | Fully collusion secure dynamic broadcast encryption with constant-size ciphertexts or decryption keys[END_REF] if new users can join without a need to modify existing users' decryption keys, if the ciphertext size and the system's initial key setup do not depend on the number of users, if the group public key should be incrementally updated with complexity at most O(1).

Suitable candidates for application to a social network scenario are BE schemes with the following properties: stateless, fully collision resistant, with hidden set of receivers, dynamic, with constant size ciphertexts and keys, with computationally efficient decryption.

We use a dynamic identity-based broadcast encryption (DIBBE) scheme that meets all these requirements [START_REF] Jiang | An efficient dynamic identity-based broadcast encryption scheme[END_REF]. Although identity-based schemes involve a thirdparty authority -a Private Key Generator (PKG), this role is given to the profile owner when adjusting this IBBE scheme for the social network scenario. Thus, the profile owner is responsible for creating a group of receivers and assigning private BE keys to receivers. The IBBE scheme is formaly defined as a tuple of algorithms IBBE = (Setup, Extract, Encrypt, Decrypt) [START_REF] Delerablee | Identity-based broadcast encryption with constant size ciphertexts and private keys[END_REF]. Although the DIBBE scheme defined in [START_REF] Jiang | An efficient dynamic identity-based broadcast encryption scheme[END_REF] has the same structure, there are some differences in the algorithms' input parameters that reflect a dynamic nature of the scheme. The algorithms of the used DIBBE scheme have the following form:

Setup(λ)→ (MK, GPK): This algorithm takes as input a security parameter λ and constructs a secret master key MK, a group public key GPK.

Extract(MK, Id)→ Sk Id : A user's private key Sk Id is generated by this algorithm that takes as input a user Id and a secret master key MK known only to the profile owner.

Encrypt(S, MK, GPK)→ (Header,K): The used scheme is constructed as a Key Encapsulation Mechanism (KEM) which means that the encryption algorithm Encrypt takes as input the set of receivers S, the master key MK, and the group public key GPK and outputs a pair (Header,K), where K is a symmetric secret key to encrypt data and Header is an encryption of this symmetric key for the set of receivers S. Data is stored in the form (Header, encrypted data), and Header reveals no information about the set of receivers or any other parameters. Only a user whose ID is in the set can decrypt the Header using his/her private key. Users that are not members of the group cannot encrypt to the group even if they know GPK, because the master key MK is required for the encryption process.

Decrypt(Id, GPK, Sk Id , Header)→ K: The Decrypt algorithm takes GPK, Header, the private key, and the user Id as input and outputs a symmetric key K.

Revocation of users from a group is a simple though computationally intensive operation. Revocation of the group membership for stateless BE schemes does not require re-keying for other group members, only re-encryption of the data with a new symmetric key and consequent regeneration of Headers for the new set of receivers. Addition of a user to a group in dynamic schemes requires re-encryption of Headers for the new set of receivers in addition to creating a private key for a new user.

Architecture: privacy preserving profiles

All objects in the profile that are not public are encrypted using a symmetric cipher and stored without any kind of header. The links that lead to these objects are encrypted using the broadcast encryption and stored in the form (Header, encrypted link). To access the data the user has to decrypt the Header and get the symmetric key, use this key to decrypt the link, follow the link, and decrypt the data using the same key. The Header contains an implicit access control list (ACL) with identities of those who can decrypt it, and a user cannot know whether he/she can decrypt the object without trying. Therefore, for performance reasons users should be able to determine whether they can decrypt particular object without actually trying to decrypt it. At the same time, one of the aspects of privacy is to prevent other users from learning who can access which objects. Therefore, in the proposed architecture explicit ACLs are not stored alongside encrypted objects. Instead the privacy preserving profile contains for each of the contacts a folder with values that represent the BE groups in which that contact is a member and, possibly, links to encrypted objects that can be decrypted by that contact.

The links folder is encrypted under a shared symmetric key known only to the user and the profile owner. The links folders have random identifiers in order to prevent anyone from seeing all profile owner's connections. Any two users that want to form a connection should explicitly state to each other an identifier for the proper links folder during connection establishment. Identifiers of the links folders should be changed on the regular basis. The new identifier can be securely communicated to the contact in multiple ways. To hide the total number of contacts from other users, a profile contains a set of dummy links folders that are also updated from time to time. A padding should be used to make dummy folders indistinguishable from the real. To hide a real number of objects in the profile dummy objects are created and updated on the regular basis. Thus, no user can calculate which percentage of objects he/she can access.

Figure 1 depicts the described user profile. The records that have the same colour of the key are encrypted under the same encryption key. The storage stores all profile data. The privacy preserving profile consists of special purpose folders Incoming, Notifications and general purpose folders for posting (e.g. wall) to which other users can only add messages, comments folder, links folders for the contacts, and other folders that cannot be modified by other users. The comments folder contains subfolders with comments for each of the objects with allowed commenting.

The general purpose folder contains a list of BE encrypted links. These links are encrypted for different sets of receivers and their Headers contain values that represent the BE groups (the set of receivers) that can decrypt these links.

Users that can decrypt the links can get access to the data. Along with a link to the object itself, there can be another link that leads to a comments folder for this object. So, if the user decrypts the links file and finds also the comments link, then he/she can create comments in that comments folder using the same symmetric key obtained after decrypting the Header.

Architecture: operations

The properties of the encryption function of the used BE scheme make it more efficient to encrypt a message for one big group of users than for several small. Therefore, all contacts should be put into one BE group. Since there is only one broadcast group per profile, each contact receives one private BE key. The profile owner creates also one public-private key pair for the group and gives each user the private key for authenticating to replica holders. Replica holders are assumed to know the public key of the public-private key pair for the group and also the public key of the profile owner.

The division of users into security groups is abstract: each abstract security group corresponds to some set of receivers S that can be easily modified during encryption. This flexibility allows us to create as many groups as required without affecting efficiency or manageability. Besides, only one parameter in the Header depends on the set of receivers, and it is always the same for the same set of receivers. Thus it can be cached to increase encryption speed. This parameter is put into links folders of the security group members. It is used to search general purpose folders for decryptable items.

The profile owner is the only entity that determines the access rights to the encrypted links and, consequently, objects. The other users when they want to post something in some general purpose folder should decrypt the symmetric key used for making posts in that folder. Access rights are defined when the profile owner BE encrypts this key for a particular set of receivers.

The profile owner's computer/mobile phone has an overlay security system for the local profile that reduces complexity of rights management using abstract groups instead of a list of identities. This local profile can store ACLs with abstract groups and separate IDs alongside with objects. The overlay security system is responsible for authentication and authorization of users in case of direct end-to-end communication.

The architecture contains the following operations: Establish connection: A user creates a new links folder and runs a Extract algorithm to generate a BE private key for the new connection. The BE key, as well as the private key for the group, is encrypted under the public key of the new connection and is put in the newly created links folder. Then the two users exchange links folder identifiers and symmetric keys to decrypt these folders. All communication in this phase goes through the encrypted channel.

Add to a group: A user adds the ID of the new connection to a list of identities of some abstract security group and recalculates a value that depends on the set of identities in the Header. Then the profile owner adds this value to the links folder of the new member and updates this value for all other members of the group.

Publish data( by the profile owner): The owner defines a set of contacts who will have access to the published data. Then he/she runs the broadcast encryption algorithm Encrypt that outputs a symmetric key to encrypt the link to the data and the data, and the Header (encryption of this key for the defined set of contacts). The profile owner encrypts the data with the generated symmetric key and stores it in the folder for encrypted objects, the link is also encrypted and stored along with the Header in some general purpose folder (e.g. Wall). Before going off-line the profile owner should synchronize all the changes with replicas.

Publish data( by a contact): If the profile owner's computer/mobile phone is online, then a contact communicates directly with the overlay security system of the profile owner via protected channel. If the security system determines that the contact has rights to publish data, it accepts the data, stores it on the local storage, and starts information update mechanism with peers. In case the profile owner is off-line, the steps are as follows. General purpose folders like Wall contain BE encrypted links and BE encrypted symmetric keys for posting in those folders. The encryption of the links in the general purpose folder determines who can read/comment on data. When the user who has rights to access the general purpose folder wants to add some message, he/she creates a new message and encrypts it with the symmetric key that is used for this folder, uploads this message to the Incoming folder of the profile, encrypts a link to the newly created message with the folder's symmetric key, signs it using the group private key, and adds this encrypted link to the general purpose folder. Then he adds an encrypted notification which informs the profile owner about the new message to the Notifications folder. The replicas are supposed to keep the integrity of the special purpose folders Incoming and Notifications, and general purpose folders by allowing only additions. Any message sent to replicas by any user except the owner should be signed by the group private key and the signature should be checked by the replica.

Comment( by a contact): If the profile owner's computer/mobile phone is online, then a contact communicates directly with the overlay security system of the profile owner via protected channel. If the security system determines that the contact has rights to comment on a particular object, it accepts the comment, stores it on the local storage, and starts information update mechanism with peers. In case the profile owner is off-line, the steps are as follows. General purpose folders like wall contain BE encrypted links and BE encrypted symmetric keys for posting in those folders. The encryption of the links in the general purpose folder determines who can read/comment on data. When the user who has rights to comment to some object wants to add a comment, he/she creates a new comment and encrypts it with the symmetric key that is used to encrypt the object and the link to the object, follows the link to the folder where the comments for this object are stored, signs the comment using the group private key, and uploads this comment to the comments folder of this object. Then he/she adds an encrypted notification which informs the profile owner about the new comment to the Notifications folder. The replicas are supposed to keep the integrity of the comments folders by allowing only additions. Any message sent to replicas by any user except the owner should be signed by the group private key and the signature should be checked by the replica.

Send notification: Notifications are sent for messages published by the sender on the receivers profile and for the information published on the sender's profile. Notifications are encrypted under the public key of the receiver and signed with the group private key and uploaded to the Notifications folder of the receiver's profile if the receiver is off-line. When the receiver is on-line, the notification is sent directly to the receiver.

A contact can send the profile owner a notification asking to delete that user's post/comment. Only the profile owner should be able to do it, replicas are supposed to protect integrity of the profile from everyone else by allowing only additions.

Security considerations

The owner's local computer stores the primary copy of the profile and replica holders store only copies with limited modification possibility. Replica holders are assumed to enforce an "only addition" policy for the special purpose folders Incoming and Notifications and the general purpose folders, and the "no modification" policy for the rest of the folders for any user other than the owner. A user (other than the owner) can upload encrypted links to the general purpose folders (comments to the comments folder) and add messages to the special purpose folder only if they contain correct group signatures. The group signature check does not reveal any identities and protects from resource exhaustion attacks from external entities. Even if the general purpose folder is modified in some way by a malicious user, it can be easily recovered via notifications.

The profile owner keeps the primary copy of the profile and synchronizes it with replicas. We assume that any peer that takes part in the social network can be a replica. Communication between the profile owner and replicas goes through a protected channel. The channel is encrypted and authenticated using public-key authentication schemes.

We define a capability-based model of an attacker for the system as following. The attacker is an active entity, external to the system (does not receive any keys from the profile owner), that can direct attacks against the replica storage, the local computer/mobile phone of the profile owner and the computers of profile owner's friends. The attacker cannot perform computationally infeasible calculations in the reasonable time. The attacker can sniff and tamper all communication channels and send arbitrary messages to all participants.

If the attacker can compromise the primary copy of the profile (e.g. by breaking the security of the operating system or the overlay security system), then the attacker has full control of this profile. It is plausible that in case of such an attack the attacker learns private keys given by other profile owners to the compromised owner. Then the attacker would be able to completely impersonate the user, read data intended for this profile owner from the profiles of other users, and would be able to exhaust replica's resources. If replicas keep integrity of the folders, the attacker will not be able to delete or modify old messages.

Secret keys used in encryption are prone to ageing. Re-encryption of data with a new underlying symmetric key is a relatively straightforward operation, but may be time consuming for big amounts of data. If each new encrypted file is encrypted with a separate symmetric key, then symmetric keys do not age. When a user publishes data on someone's else wall, he has to decrypt the symmetric key used for making posts in that folder first, and then use it to encrypt the data. This symmetric key should be changed regularly to prevent key ageing. However, if symmetric keys are changed very often, then the secret master key MK, which is used by the profile owner for encryption (to generate a symmetric key, see Section 2), will age very fast and will require frequent refreshments. Thus there is a trade-off between ageing of symmetric keys and the master key.

The key refreshment issue is very important, but we do not address it in this work.

Conclusions

A P2P provider-independent architecture with cryptographically protected privacy is a straightforward solution to give full control over their data to the end-users and guarantee its protection.

Although broadcast encryption schemes were intended for a multi-recipient broadcasting, their properties make them suitable candidates for application to a social network scenario. We evaluated existing schemes for the suitability looking at the several criteria (efficiency, recipient privacy, etc.) and defined properties that are crucial for the BE schemes to be used in the social network scenario. We found one BE scheme that meets all the requirements, transformed it from the Identity-based BE scheme to the ordinary BE scheme, and adapted to the social network scenario.

With efficiency in mind, we proposed a P2P social network architecture that uses a composition of public-key cryptography, broadcast encryption schemes, and symmetric cryptography. The architecture provides confidentiality and limited integrity protection from an external attacker. The architecture defines a privacy preserving profile that allows users to quickly find data encrypted for them while preventing both the external attackers and malicious insiders from learning who can access which data.

Fig. 1 .

 1 Fig. 1. System architecture: user profile

http://www.peerson.net/

Acknowledgments

This research has been funded by the Swedish Foundation for Strategic Research grant SSF FFL09-0086 and the Swedish Research Council grant VR 2009-3793.


Davide Ceolin
email: d.ceolin@vu.nl

Archana Nottamkandath
email: a.nottamkandath@vu.nl

Wan Fokkink
email: w.j.fokkink@vu.nl

Automated Evaluation of Annotators for Museum Collections using Subjective Logic

Museums are rapidly digitizing their collections, and face a huge challenge to annotate every digitized artifact in store. Therefore they are opening up their archives for receiving annotations from experts world-wide. This paper presents an architecture for choosing the most eligible set of annotators for a given artifact, based on semantic relatedness measures between the subject matter of the artifact and topics of expertise of the annotators. We also employ mechanisms for evaluating the quality of provided annotations, and constantly manage and update the trust, reputation and expertise information of registered annotators. 1

Introduction

Cultural and heritage preserving organizations such as museums are rapidly digitizing their collections, and at the same time migrating digitized collections to the Web. Thus, there is a growing need for seeking experts world-wide for providing high quality annotations for digitized artifacts. This paper presents an architecture for finding such experts.

Unlike online content collaboration sites such as Wikipedia, museums cannot risk anyone say anything about a particular topic. Annotations should be provided only by trusted sources, and should be validated by museum experts or peers who have sufficient proven expertise in the same topic. We assume that a generic initial classification of the artifact is already available in the form of specific set of tags or keywords by digital curators, (e.g. indicating the period of production or the type of artifact). Most museums use a standard thesaurus (such as Iconclass [START_REF]IconClass. A multilingual classification system for cultural content[END_REF]), which serves as a basis for deriving relations between the various artifacts, and forms a controlled vocabulary for annotations. The selection of experts who can provide an annotation for a certain topic is based on a proper average of an expert's reputation and the "semantic similarity" between the requested topic and the recorded expertise areas of the expert. Thus we select experts who can be trusted to provide quality annotations.

Moreover, we employ mechanisms for evaluating the quality of provided annotations. We constantly manage and update the trust, reputation and expertise information of registered annotators by employing trust algorithms based on subjective logic [START_REF] Jøsang | A logic for uncertain probabilities[END_REF], which is a probabilistic logic that takes into account uncertainty and belief ownership, to model and analyze situations that involve incomplete knowledge. This work extends previous work on determining the quality of annotations using (Semantic) Web sources [START_REF] Ceolin | A trust model to estimate the quality of annotations using the Web[END_REF] by combining subjective logic with measures of semantic relatedness, thereby providing an extensive model for managing annotations.

Related work

Cultural heritage organizations are opening up their archives to external user contributions mainly classified as: (1) Social tagging, where users link artifacts with "tags", i.e, words generically related to them (see for instance the "Steve Social Tagging Project" [START_REF]Steve Social Tagging Project[END_REF] and the "Uncovering Nation's Art Collection" project [START_REF]Uncovering Nation's art collection[END_REF] from BBC); (2) Collaborative authoring, mainly in case of encyclopedias (see [START_REF] Emigh | Collaborative authoring on the web: A genre analysis of online encyclopedias[END_REF]); (3) Annotations, where the requested "tags" specifically describe one aspect of the artifact [START_REF] Ceolin | A trust model to estimate the quality of annotations using the Web[END_REF].

Recommender systems are widely employed in media-related systems to provide valuable suggestions to the users (e.g. [START_REF] Hollink | Patterns of semantic relations to improve image content search[END_REF][START_REF] Wang | Using semantic relations for contentbased recommender systems in cultural heritage[END_REF]). In collaborative communities such as Wikipedia, the correct allocation of tasks is done by intelligent task routing systems [START_REF] Demartini | Finding experts using wikipedia[END_REF]. User participation increased up to four-fold when online tasks were mapped to user interests (see [START_REF] Cosley | SuggestBot: using intelligent task routing to help people find work in wikipedia[END_REF]). In cultural heritage organizations, the quality and trustworthiness of contributions play a vital role. There is a considerable amount of research on finding experts (as trustworhty contributors) in online communities such as Wikipedia [START_REF] Breslin | Finding experts using internet-based discussions in online communities and associated social networks[END_REF] and online forums [START_REF] Zhou | Routing Questions to the Right Users in Online Communities[END_REF].

Semantic relatedness is a concept where sets of terms are assigned a metric based on the likeness of their meaning/semantic content. User interests are recorded and various thesauri are employed for deriving semantically related interests in content-based recommender systems for museums (e.g. [START_REF] Wang | Recommendations based on semantically-enriched museum collections[END_REF]). Recent standardization efforts, such as SKOS [START_REF] W3c | SKOS Simple Knowledge Organization System Primer[END_REF], have lowered the technical boundaries to publish thesauri on the Web.

Adopted methods and technologies

Semantic Relatedness This is a measure that indicates how closely two concepts relate in a taxonomy, given all existing relations between them. We use a WordNet [START_REF]A lexical database for English[END_REF] based similarity relatedness measure. WordNet is a large lexical database of English, often used by museums and similar to the models that they use to categorize and describe their artifacts.

Semantic Web technologies They include a wide range of formats and technologies aimed at enhancing the Semantic Web vision (which may be summarized with the slogan "moving from a Web of documents to a Web of data"). We use some of them, in particular:

-URIs: Uniform Resource Identifiers offer unique references to any possible entity (e.g.: annotators, artifacts, concepts). -RDF: the Resource Definition Framework is basically a language for representing graphs. RDF statements are "triples" (Subject, Predicate, Object), where each of these elements can be either a URI or a literal value (with some restrictions). -Ontologies: defined using RDFS/OWL language, ontologies define types, properties, etc., of URIs in particular contexts. For example, they allow to distinguish URIs referring to sets of users from those representing concepts. We use the following ontologies:

• Friend Of A Friend (foaf) [START_REF] Brickley | Foaf vocabulary specification 0.98[END_REF]: for representing people and connections among them. • Simple Knowledge Organization System (skos) [START_REF] W3c | SKOS Simple Knowledge Organization System Primer[END_REF]: for representing "concepts" and semantic relations among them. • Hoonoh (hoonoh) [START_REF] Heath | The hoonoh ontology for describing trust relationships in information seeking[END_REF]: for representing expertise.

• RDF Data Cube (qb) [START_REF] Cyganiak | The RDF Data Cube vocabulary[END_REF]: for representing multi-dimensional data.

• Dublin Core Terms (dcterms) [START_REF]Dublin Core Metadata Initiative. Dcmi metadata terms[END_REF]: for representing meta-data.

• PROV (prov) [START_REF] W3c | The PROV Ontology: Model and Formal Semantics[END_REF]: for representing provenance information.

Subjective logic Evidence about the expertise and reliability of annotators is handled by means of a probabilistic logic named subjective logic which represents the estimated truth value of propositions by means of subjective opinions. An opinion ω object subject (belief , disbelief , uncertainty, apriori ) is defined by ( 1) and ( 2). belief

+ disbelief + uncertainty = 1, apriori ∈ [0...1] (1) belief = p p+n+2 disbelief = n p+n+2 uncertainty = 2 p+n+2
(2)

E = belief + apriori • uncertainty (3)
p and n are the amount of positive and negative evidence respectively. apriori is the prior knowledge owned about the expertise, which does not change over time; its influence on the trust value computation lowers as we collect new evidence.

In case of a lack of prior knowledge, the default value for apriori is 0.5, which is equally far from zero (false) and one (true).

The expected value of an opinion (3), which corresponds to the trust value we want to represent, is an expected value in the statistical sense, since it is the expected value of the Dirichlet distribution equivalent to the opinion. The distribution describes the probability of each value between zero and one to be the right trust value and its shape depends on the value of the opinion.

Model

Our model aims at obtaining trustworthy annotations through crowdsourcing. It is composed of two parts, strongly interlinked: data representation and algorithm. These two parts are connected by subjective opinions: the first part provides a representation for the expertise, i.e., the "object" of our opinions, whereas the algorithm computes the trust levels and outputs the most trustworthy annotations.

Data representation

The expertise of each annotator is recorded, through the hoonoh ontology, by linking the URI representing the user to the one representing the concept of expertise. In RDF statements, it is represented as follows: eg : item1 dcterms : s u b j e c t eg : T1 .

eg

Trust (expertise) management

We are interested in determining the user expertise about a given topic, so, if eg:E1 is of type hoonoh:ExpertiseRelationship, an opinion is:

expertise(user, T 1) = ω eg:E1 hoonoh:from eg:user eg:E1 hoonoh:toTopic eg:T1

(b, d, u, a) (4)
We assume that users are evaluated (e.g. through a questionnaire) when registered. This evaluation is represented by the apriori component, which provides an initial indication of the user expertise. As the user provides candidate values for annotations and these are evaluated, the weight of the apriori on the trust value will decrease. When evaluating the expertise of the user about a topic T1, the opinion is computed as in (2) but, before summming them, each piece of evidence is weighed on its semantic similarity with T1.

Algorithm

We introduce a pseudo-code algorithm that computes the trust levels and outputs the most trustworthy annotations, and we provide a qualitative description of it. for all request do users ← select users(request) for all users do result ← append value(user , request) end for output ← evaluate results(result) update expertise(users) return output end for select users This function selects a set of annotators to whom we forward an input request. A request should contain:

-A reference to the artifact to be annotated.

-A first, high-level classification of the item, that facilitates the annotators selection (e.g., the century when it was made) -The requested "facet", necessary to obtain comparable candidate values (e.g., the "what" facet, i.e. the artifact content). The selection procedure depends on internal policies of the museum deploying the system, so we do not make it explicit. Some examples:

-Select the n highest ranked experts about the requested topic.

-Consider all the experts. Weigh their reputation with regards to the distance from the request. Order and select them. -Consider also the belief and uncertainty (and impose some conditions on them) when selecting annotators. append value Collects the contributions obtained from the selected annotators. result is a list of couples like (value, annotators opinions). evaluate results Aggregates results and takes a decision about them. Subjective logic's cumulative fusion operator is a possible aggregation function. A possible decision strategy is to choose the highest-rated value. A decision strategy has to select a candidate value, while reducing the risk of taking a wrong decision and solving possible controversies, such as when multiple candidate values all share the highest rank.

update expertise After having evaluated the candidate values for the annotation, annotators will be "rewarded" (if their candidate was selected) or "penalized" (otherwise). In principle, this means adding a positive evidence to the first ones and a negative evidence to the last ones, but once again, this may depend on museum policies. Output The annotation selected can be directly accepted by the museum, or ranked qualitatively according to its trust level (e.g. "accept" when trust level is higher than 0.9, "review" otherwise), so that appropriate actions are taken.

Evaluation

This section describes some analyses performed on the "Steve Social Tagging Project" [START_REF]Steve Social Tagging Project[END_REF] dataset, for validating our proposed approach. For this experiment, we computed the semantic relatedness by using the Wu & Palmer measure [START_REF] Zhibiao | Verbs semantics and lexical selection[END_REF] on WordNet using an online service [START_REF]Wordnet::Similarity[END_REF]. This gave us a measure ∈ ]0..1].

The "Steve Social Tagging Project" is a collaboration of museum professionals and others aimed at enhancing social tagging. We used the small portion of the data available as part of a 2006 project entitled "Researching social tagging and folksonomy in the ArtMuseum". This dataset comprises 1784 images from the museums which are open for tagging by the users. Each image is tagged by a single user with multiple tag words. There are 15,167 distinct tags. The 45,859 tag reviews of only 11 users are available as open source. Tag evaluations from the museum (e.g. "useful", "non-useful") are used as evidence in the training part and as a gold standard in the prediction evaluation.

A first empirical overview of the dataset hinted at the presence of possible semantic clusters. We then manually selected the candidate set of single words and proved that the semantic relatedness among those words is high. An example of clusters found is available in Fig. 2. After having shown the existence of these semantic clusters, we compared the expertise of people using words from those clusters and noticed that people having a high amount of positive (or negative) evidence regarding one word in a particular cluster also had a high amount of positive (or negative) evidence about the other words in the same cluster. Positive and negative evidence is derived from the evaluation by the museum: tags evaluated as useful are counted as positive evidence, non-useful as negative. This manual and empirical analysis gave us a first concrete evidence about the relatedness between reputation based on evidence and semantic similarity. We also built each user's reputation using a subset of the evaluations made by the museum and, based on this, we predicted the usefulness of future tags inserted by each user2 . The prediction is performed as described in Section 4.2. Tags having a trust level of at least 0.7 are labelled as "useful". As a side effect of weighing, uncertainty of reputations rises, since weighing reduces the amount of evidence considered. However, often, this consequence did not worsen our results, especially when the reputation was already quite high (e.g., the reputation of an annotator reduced to 0.92 from 0.97). On the contrary, our approach allowed us to be prudent in our evaluations, so we could avoid accepting as useful tags with high uncertainty. Weighing improved the performance of subjective logic in a statistically significant manner, as proven by applying the sign test with a confidence interval of 95% on the compared errors.

Conclusion and Future Work

We demonstrate the potentials of combining subjective logic, semantic relatedness measures and Semantic Web technologies for handling users expertise and annoations trustworthiness.This work is an initial step in a promising direction that will be further explored. For instance, we plan to extensively deploy the described architecture and to extend the range of semantic relatedness measures and vocabularies adopted.

Fig. 2 .

 2 Fig. 2. Cluster and corresponding positive/negative evidence per user.

  : T1 a hoonoh : Topic , skos : Concept . eg : u s e r a f o a f : Person . eg : E1 a hoonoh : E x p e r t i s e R e l a t i o n s h i p ;

hoonoh : from eg : u s e r ; hoonoh : t o T o p i c eg : T1 .

We define a data structure representing a subjective opinion, we link it to the corresponding hoonoh:ExpertiseRelationship and then populate it with observations, i.e., opinion instances:

eg : Opinion a qb : D a t a S t

r u c t u r e D e f i n i t i o n ; qb : component [ qb : measure eg : b e l i e f ; ] , [ qb : measure eg : d i s b e l i e f ; ] , [ qb : measure eg : u n c e r t a i n t y ; ] , [ qb : measure eg : a p r i o r i ; ] . eg : d a t a s e t a qb : DataSet ; qb : s t r u c t u r e eg : Opinion ; dcterms : s u b j e c t eg : E1 . eg : obs1a a qb : Observation , prov : E n t i t y ; qb : d a t a S e t eg : d a t a s e t ; prov : wasAttributedTo eg : Museum ; eg : b e l i e f 0 . 4 ; eg : d i s b e l i e f 0 . 2 ; eg : u n c e r t a i n t y 0 . 4 ; eg : a p r i o r i 0 . 5 . Museum artifacts are annotated objects of type skos:Concept. E.g.:

This research is carried out as part of a Dutch FES COMMIT project entitled Socially Enriched Access To Linked Cultural Media (SEALINC).

The complete set of analyses is available at: http://bit.ly/y3uzlP