Abdelberi Chaabane

Emiliano De Cristofaro

Mohamed Ali Kaafar

Ersin Uzun

Privacy in Content-Oriented Networking: Threats and Countermeasures

Keywords: C, 2, 1 [Computer communication networks]: Network Architecture and Design; K, 4, 1 [Computers and society]: Public Policy Issues-Privacy Content-Oriented Networking, privacy

As the Internet struggles to cope with scalability, mobility, and security issues, new network architectures are being proposed to better accommodate the needs of modern systems and applications. In particular, Content-Oriented Networking (CON) has emerged as a promising next-generation Internet architecture: it sets to decouple content from hosts, at the network layer, by naming data rather than hosts. CON comes with a potential for a wide range of benefits, including reduced congestion and improved delivery speed by means of content caching, simpler configuration of network devices, and security at the data level. However, it remains an interesting open question whether or not, and to what extent, this emerging networking paradigm bears new privacy challenges. In this paper, we provide a systematic privacy analysis of CON and the common building blocks among its various architectural instances in order to highlight emerging privacy threats, and analyze a few potential countermeasures. Finally, we present a comparison between CON and today's Internet in the context of a few privacy concepts, such as, anonymity, censoring, traceability, and confidentiality.

INTRODUCTION

In the last few years, the increasing penetration of the Web in our society has prompted a tremendous growth of data routed in the Internet, to such an extent that global IP traffic is expected to increase 3-fold over the next 5 years [START_REF]Cisco Visual Networking Index: Forecast and Methodology[END_REF]. Besides exceeding its expectations, the Internet has also stretched many of the initial assumptions, creating issues that challenge its underlying communication model. Applications increasingly operate in terms of content, making it difficult to conform to IP's requirement to communicate by discovering and specifying hosts and locations.

Coping with massive amounts of traffic becomes arduous due to a number of issues deep-rooted in the network design. As a result, the quest for improving scalability and (cost) efficiency of content delivery has led to the design of overlay networks, such as, Peer-To-Peer (P2P) and Content Distribution Networks (CDNs). However, overlay networks often complicate network management and application development. Further, endpoint authentication mechanisms (whereby an endpoint can only authenticate the counterpart, but not the message) have been challenged by frequent attacks against SSL [START_REF] Duong | Here come the ⊕ ninjas[END_REF][START_REF] Georgiev | The most dangerous code in the world: validating SSL certificates in non-browser software[END_REF] and the hacking of certification authorities [START_REF] Keizer | Hackers may have stolen over 200 SSL certificates[END_REF].

Motivated by these issues, new architectures have been proposed, in the last few years, aiming to redesign the Internet [START_REF]NSF Future Internet Architecture Project[END_REF] and accommodate content-oriented applications. In particular, Content-Oriented Networking (CON) [START_REF] Cho | Content-oriented networking as a future internet infrastructure: Concepts, strengths, and application scenarios[END_REF] has set to decouple contents from hosts, at the network layer, by relying on the publish/subscribe paradigm. CON shifts identification from host to content, so that this can be located anywhere in the network. The content-centric communication paradigm introduced by CON relies on naming the content itself, rather than its location. Content is self-contained, has a unique name, can be retrieved by means of an interest for that name, cached in any arbitrary location, and digitally signed to ensure its integrity and authenticity.

CON comes with a potential for several advantages, including reduced congestion and improved delivery speed through content caching, simpler configuration of network devices, and security at the data level. However, it remains an interesting open question whether or not, and to what extent, this emerging networking paradigm bears new privacy challenges. While some features, such as, lack of source/destination addresses, might help privacy in CON, a closer look to some of the design choices unveils a number of open questions. This paper studies privacy in CON as a generic paradigm and shows that it introduces several worrisome issues.

First, we analyze the implications of caching -one of the crucial features in CON used to reduce traffic and improve delivery speed -on user privacy and show that, as nodes cache frequently requested content, they can infer content consumed by others using timing information. Next, we focus on content privacy: since publicly available content is not encrypted in CON and, as routers now handle content, any router can easily inspect content. Furthermore, as content in CON is retrieved using names that most likely are semantically related to the content itself, an attacker could infer sensitive information about a user, by monitoring her requests: we refer to this issue as name privacy. Finally, we look at signature privacy: since digital signatures of CON packets need to be publicly verifiable, the identity of a content signer may be easily inferred by looking at the signature.

In this paper, we discuss different attack scenarios that threaten privacy in CON. For each setting, we describe the attacker capabilities and related impact on user privacy. We suggest several ideas that could serve as countermeasures and detail their strengths and weaknesses, and make sure that they would bear minimal changes to the CON architecture. To the best of our knowledge, this represents the first step toward a thorough analysis of CON privacy issues. In the process, we also highlight a number of challenging open problems that call for further research.

CONTENT-ORIENTED NETWORKING

This section provides a high-level description of Content-Oriented Networking (CON). A few future Internet architectures have been proposed so far that realize CON. The most prominent ones include DONA [START_REF] Koponen | A Data-Oriented (and beyond) Network Architecture[END_REF], NetInf [START_REF] Ambrosio | Second NetInf Architecture Description. 4WARD Deliverable D6[END_REF], CCN [START_REF] Jacobson | Networking Named Content[END_REF], LANES [START_REF] Visala | LANES: An Inter-Domain Data-Oriented Routing Architecture[END_REF], TRIAD [START_REF] Gritter | An Architecture for Content Routing Support in the Internet[END_REF], CBCB [START_REF] Carzaniga | A Routing Scheme for Content-Based Networking[END_REF]. We now review their building blocks:

1. Named content: In CON, objects are always named to facilitate data dissemination and search. Consequently, the security model is also shifted from host to content authentication.

2.

Content-based routing: Content routing in CON relies on content rather than hosts, aiming to handle increased amounts of network traffic and be more resilient to network bursts and users' mobility. 3. Content Delivery: Content is efficiently delivered using multi-path routing and leveraging in-network caching, in order to minimize network bandwidth and delivery delay, and transparently handle mobile users. 4. In-network storage: All CON network components provide caching capability. Note that this is different from packet buffers in today's routers, as cache size is expected to be several orders of magnitude bigger in CON.

Network Model. CON involves several entities (see Fig. 1). End users express interests and fetch data using a wide range of devices.

Interests represent the willingness of the user to retrieve certain data, independently of its location. Content routers are responsible of forwarding interests and forwarding back the associated data. Each router is assumed to have a built-in cache. Cache size as well as caching algorithm may differ from one router to the other. Finally, content producers (or publisher) generate the content-either static (time-independent) or dynamic (generated upon request). Although data-centers or/and geographically distributed servers may be used to serve content, we simplify the model by considering a single source machine.

In the following, we overview CON's architecture design. For further details, we refer the reader to [START_REF] Choi | A Survey on Content-Oriented Networking for Efficient Content Delivery[END_REF][START_REF] Ahlgren | A survey of Information-Centric Networking[END_REF], and to the full version of this paper [START_REF] Chaabane | Privacy in Content-Oriented Networking: Threats and Countermeasures[END_REF].

Caching.

A key feature used to increase overall network efficiency in CON is caching. All nodes in the network are expected to participate in the caching effort, from core routers to mobile devices. Caches provide in-network storage and are assumed to be several orders of magnitude larger than today's buffers. This capacity allows to store content for longer periods and enhance network performance. There is a number of efforts aiming at optimizing caching strategies in CON -see, e.g., [START_REF] Ardelius | On the effects of caching in access aggregation networks[END_REF][START_REF] Psaras | Probabilistic in-network caching for information-centric networks[END_REF][START_REF] Rossini | On sizing CCN content stores by exploiting topological information[END_REF][START_REF] Rossini | A dive into the caching performance of content centric networking[END_REF]. Content Naming. The main abstraction in CON architecture is the Content Object (CO). All kinds of content, ranging from web pages to documents, and even interactive content, such as VoIP, are abstracted as a CO. An object is always identified by a name, which must be unique as it serves as identifier for searching and disseminating associated content. Moreover, since content can be fetched from anywhere, there should be a secure binding between content name and content data (i.e., name-data integrity) as well as object authenticity. Finally, objects retrieved from cache should carry information about the object owner (publisher). Two naming approaches have been proposed so far -flat and hierarchical.

Flat naming. Flat names are self-certifying, i.e., CO's name-data integrity is bounded to its name, thus, it can be verified without any PKI. In its simplest form, the name is expressed as the cryp- tographic hash function of the content. Although one can assess the validity of the content, it is impossible to verify its provenance and relevance. However, a few techniques have been proposed to enable provenance verification, by allowing the publisher to have more control on the naming by adding a label (e.g. [START_REF] Kubiatowicz | Oceanstore: an architecture for global-scale persistent storage[END_REF][START_REF] Koponen | A Data-Oriented (and beyond) Network Architecture[END_REF]). Unfortunately, these solutions do not guarantee binding between the name and the content. Thus, we will assume the use of secure binding, as proposed by [START_REF] Smetters | Securing Network Content[END_REF], whereby content is made available as a triple M (N,P,C) = (N, C, SignP (N, C)), where N is the content name, C the content, and SignP producer's signature.

Hierarchical naming. With hierarchical naming, name structure resembles that of today's URLs, where the '/' symbol delimits the name components. In some cases (e.g., CCN [START_REF] Jacobson | Networking Named Content[END_REF] and TRIAD [START_REF] Gritter | An Architecture for Content Routing Support in the Internet[END_REF]), the name is human-readable, which makes it easier for the user to access the content. The major benefit of adopting a hierarchical structure is to enable aggregation, thus, improving routing scalability. Note that, similar to flat naming, we assume the use of secure binding, as proposed by [START_REF] Smetters | Securing Network Content[END_REF].

Content Routing and Forwarding. As illustrated in Fig. 1, routing in CON is performed in two phases: (1) routing of CO requests ("interests"), and (2) routing the content back to the user. Naturally, this depends on the naming schema and, in particular, on whether or not name aggregation is possible. For flat-naming based CON, a Name Resolution Service (NRS) is used to retrieve topological information (such as, the data location) based on object name. Structured routing algorithms are often used to exploit structured network topologies, such as trees or DHT-s. For example, DONA [START_REF] Koponen | A Data-Oriented (and beyond) Network Architecture[END_REF] maintains a tree topology and lets each router store routing information of all his descendants. Thus, any content (re)publication, deletion, or modification is propagated up to the root. With hierarchical naming, efficient routing and discovery is possible without any external service. Request/data aggregation may also facilitate network scalability. This approach may resemble unstructured routing in IP, where IP addresses are replaced with content name and route advertising is achieved through flooding.

CCN/CCNx overview. To ease presentation, in the rest of the paper, we will refer to technical details of one specific CON in-stance, namely, CCNx [START_REF]CCNx: Open-Source Implementation and Documentation[END_REF], the open-source project that implements Content-Centric Networking (CCN) [START_REF] Jacobson | Networking Named Content[END_REF]. CCNx is considered one of the most mature examples of CON in the research community, with multiple platform implementations, documentations, and implementations, supported by a relatively large community.

In CCNx, whenever a router receives an interest for name X, it performs a longest prefix match lookup on its three main tables as follow: First, it looks whether the interest exits in the Content Store (i.e., the main cache), if so, a copy is forwarded back to the user and the routing process terminates. Otherwise, a lookup is launched on the Pending Interest Table (PIT). This table keeps track of all interests waiting to be resolved by upstream nodes. If there is a match, the router collapses the present interest (and any subsequent ones for X) storing only the interface on which it was received. Finally, if no match is found, the router searches for the most suitable interface in his Forward Information Base (FIB) to forward the interest and then creates a PIT entry for that interest.

PRIVACY CHALLENGES IN CON

We now present a systematic analysis of privacy in Content-Oriented Networking (CON) by identifying threats and, when possible, discussing possible solutions. Multiple proposals [START_REF] Koponen | A Data-Oriented (and beyond) Network Architecture[END_REF][START_REF] Ambrosio | Second NetInf Architecture Description. 4WARD Deliverable D6[END_REF][START_REF] Jacobson | Networking Named Content[END_REF][START_REF] Visala | LANES: An Inter-Domain Data-Oriented Routing Architecture[END_REF][START_REF] Gritter | An Architecture for Content Routing Support in the Internet[END_REF][START_REF] Carzaniga | A Routing Scheme for Content-Based Networking[END_REF] have been presented in the last couple of years to instantiate CON, with relatively minor differences in their proposed design. As mentioned above, we will discuss technical details while considering the CCNx instance [START_REF]CCNx: Open-Source Implementation and Documentation[END_REF], however, threats and proposed countermeasures discussed in this paper apply to CON in general. That is, issues are about fundamental features in CON (such as, caching, naming, data delivery and provenance assurance) and not about the specifics of one implementation.

Cache privacy

We start our analysis with cache privacy. Recall that caching is a fundamental component of CON as it benefits both latency and bandwidth consumption. However, it also introduces a fundamental challenge to user privacy. An adversary may use a router's cache to infer content exchanged (consumed) by users in the downstream and possibly link it to a specific user depending on its relative location to the user in the topology. There are different types of attacks that can occur on cache privacy -we review them below. Timing attacks. By measuring time [START_REF] Felten | Timing Attacks on Web Privacy[END_REF], an adversary Adv can determine if a content has been cached at a particular router by measuring the delay to retrieve it. To do so, Adv measures the RT Ts to retrieve any content from the source, the delay RT Tc to get cached content from the closest router, and the delay RT Tt to fetch targeted content. Then, Adv compares the RT T as follow:

• If |RT Tt -RT Tc| < (for negligible ): Adv concludes that target content has been cached at the closest router (i.e., has been fetched by a neighboring consumer connected to the same router). • If RT Tt > RT Tc and RT Tt < RT Ts: Adv knows that target content has been fetched from the source recently and cached in the network, but not by one of its immediate neighbors. Based on the difference between RT Tt and RT Tc, Adv can still predict how close the consumer of that content was to his location in the network topology. • Otherwise (|RT Tt -RT Ts| < ), Adv concludes that target content has not been consumed recently. Such an attack allows Adv to check whether or not content has been recently fetched, but not when. Launiger et al. [START_REF] Lauinger | Privacy Implications of Ubiquitous Caching in Named Data Networking Architectures[END_REF] describe the timing attacks in the context of CON, and show that the cache replacement policy has only a small impact on the attacks' success. Finally, observe that, since in-network caches are shared by all CON designs, this attack is inherent to all CON proposed architectures.

Protocol attacks. Without a careful design, content retrieval protocols and their features in CON architectures can make access to cache content even easier. After investigating such issues in CCNx [START_REF]CCNx: Open-Source Implementation and Documentation[END_REF], we found out that a number of features and options in interest packets [START_REF]Project CCNx: Interest Message[END_REF], and how they are matched with content packets, are particularly worrisome:

• Prefix-based matching: CCNx considers a content with name X to satisfy an interest for name Y if Y is a proper prefix of X. This can facilitate easy extraction of cache content without knowing exact names. Due to multiple types of content potentially satisfying an interest, an exclusion option is also conveniently provided in CCNx interest packet format to allow exclusion of previously acquired content from subsequent queries. • Scoping: In CCNx, scope for interest packets is used to determine the maximum number of hops it will travel. Such a feature makes it easy to query the caches of particular routers as it controls where (i.e., how many hops away) an interest packet can travel to. For instance, setting the scope to 2 would restrict an interest to propagate to only neighbouring router(s) and allow convenient querying of their caches without relying on any timing information. As a result, Adv can monitor the access to sensitive content within a certain scope or easily dump nearby caches' content. The former attack is achieved by periodically issuing an interest Im for target content m and setting the scope accordingly (e.g., setting scope to 2 to monitor the caches of immediate neighbors). If Im times out, Adv concludes that m has not been fetched yet. Whenever a consumer within the scope accesses m, Im is satisfied, thus, allowing Adv to be notified. Hence, Adv is able to infer when the file was fetched for the first time. Dumping attacks can be achieved by sending an interest for the root prefix / or short prefixes, repeatedly, and excluding what has been already received on successive interests. Combined with scoping, this method can easily be used to dump cache contents from nearby caches.

We believe that the above attacks are quite worrying, however, observe that the attack success depends on the relative location of the adversary to the victim in the network topology. Thus, we distinguish two classes of adversaries:

• Immediate Neighbor: if an attacker is sharing the first hop CON router with his potential victim, the privacy risk is maximized as it would not only be easy to singularly monitor or dump a close-by router, but also victim's anonymity set would be very small, due to the limited number of users sharing that router. • Distant Neighbor: Considering the tree-like topology in content distribution from its original source to its consumers (where the source is the root, consumers are the leaves, and the intermediate routers are nodes in between), the path from an adversary and a consumer to the root will intersect at least one node. Therefore, the privacy risk decreases as the number of leaves in the sub-tree rooted at that node increases (i.e., anonymity set gets larger).

Potential Solutions

Different algorithms have been proposed to enhance the hit ratio [START_REF] Ardelius | On the effects of caching in access aggregation networks[END_REF][START_REF] Psaras | Probabilistic in-network caching for information-centric networks[END_REF][START_REF] Rossini | On sizing CCN content stores by exploiting topological information[END_REF][START_REF] Rossini | A dive into the caching performance of content centric networking[END_REF] on caches, however, none of them takes into consideration potential related privacy issues. In the following, we discuss some potential countermeasures to mitigate such privacy threats at a high level. Although the detailed design and security analysis for these methods are not within the scope of this paper, we expect the research community to further investigate them in future work.

Wait before reply. A simple solution to the cache privacy problem is to delay all requests: when the router fetches content m, it should store the corresponding RTT tm. Then, whenever a user requests m, the router waits tm before sending the data back. Note that, independently from our work, Acs et al. have recently proposed a similar solution [START_REF] Acs | Cache Privacy in Named-Data Networking[END_REF]. Wait before reply has three main advantages: (1) it provably achieves perfect privacy since Adv cannot distinguish between cached and not cached data [START_REF] Acs | Cache Privacy in Named-Data Networking[END_REF]; (2) it does not make any assumptions about content correlation, network topology, or consumers, and (3) it achieves reduced bandwidth thanks to caching. Unfortunately, however, this approach has the main drawback of eliminating the positive effect of caching on content retrieval delay.

Delay the first k. An alternative to the above solution is to delay the first k requests for content m to ensure that only popular content is cached on edge routers serving small number of customers, similar to what Acs et al. have recently (and independently from our work) proposed in [START_REF] Acs | Cache Privacy in Named-Data Networking[END_REF]. Note that k should be chosen randomly by routers, otherwise an adversary could break this schema by issuing k requests and timing responses. The main advantage of this approach is that consumers accessing popular content are unlikely to experience any delays introduced by routers. However, k should be carefully and randomly chosen for each content. High values of k result in delaying most of the requests, whereas, a small value will have a negative impact on user's privacy by reducing the anonymity set. Furthermore, the delay on the retrieval of not so popular content will still be high. Finally, we note that Acs et al. [START_REF] Acs | Cache Privacy in Named-Data Networking[END_REF] provide a formal model that allows to quantify the tradeoff between privacy offered by various caching algorithms and the latency.

Collaborative caching. Multiple nearby caches could collaborate to create a distributed cache that is serving a bigger set of users. Such an integration would create an illusion of a single cache of bigger size and would also increase the anonymity set for customers. Several algorithms have been proposed in this context [START_REF] Laoutaris | Meta Algorithms for Hierarchical Web Caches[END_REF][START_REF] Wessels | Internet Caching Protocol -RFC2186[END_REF] and can be categorized as hierarchical or mesh based. The latter refers to a flat structure while the former is used for caches that have a tree-like structure. In a simple mesh scenario, two routers R1 and R2 collaborate as follows: the hash universe (e.g., 256 bits) is divided in two subspaces s1,s2 where R1 and R2 stores the elements in s1 and s2 respectively. Based on computed hash (of the routable prefix of the content name), the router decides whether to cache that content or transmit it to his neighboring router. Similarly, interests are first forwarded to the router responsible for caching the corresponding subspace. Collaborative caching has two main advantages: first, users are likely to fall into larger anonymity sets even if the requested content was found in cache. Second, hit rates for caches will increase as the collaboration would remove redundancy between nearby caches and effectively simulate a cache that is much bigger in capacity. Due to this second property, there may be some economic incentive to deploy this solution besides protecting user privacy as well [START_REF] Wessels | Configuring Hierarchical Squid Caches[END_REF].

Probabilistic caching. Introducing randomness in the caching procedure may impact the accuracy of attacks. One possible approach could be probabilistic caching [START_REF] Psaras | Probabilistic in-network caching for information-centric networks[END_REF], where a router decides to cache content based on his position on the forwarding path as well as the available space in the cache. Since this decision is based on internal states of routers, it would not be known to an adversary. However, not caching a random subset of content can provide only a very limited privacy protection as the cached subset would still violate user privacy.

Content privacy

Unencrypted communication over IP networks can be spied upon using Deep Packet Inspection (DPI) [START_REF] Bendrath | The End of the Net as We Know It? Deep Packet Inspection and Internet Governance[END_REF] by an adversary on the endto-end communication path. However, in CON, content privacy becomes an even more serious threat due to the presence of persistent memory (caches) within the network.

Monitoring and Censorship: DPI tools are already commonly used by certain governments or Internet Service Provider (ISP) for classifying and censoring content (e.g., based on keywords). However, DPI on IP networks requires powerful adversaries that are strategically located on the main communication path and with enough computation power to perform DPI on line speed. As CON stores data packets for long time and makes it available to anyone that asks for it, neither of these assumptions about the adversary holds. In fact, the adversary might retrieve content from caches for DPI based monitoring, classification and censorship.

Potential Solutions

As the problem is caused by the lack of data confidentiality, encryption would be the de-facto solution. Naturally, the encryption mechanism should provide the best balance between security and efficiency. Also, it should be preserving the benefits of caching mechanism.

Symmetric/Asymmetric encryption. A trivial approach might be to use similar mechanisms to SSL/TLS, where a client generates a session key and encrypts it using the producer public key. After receiving this key, the producer use it to encrypt the content and send it back to the user. The main consequence of such approach is disabling caching mechanism as only one user can decrypt the content.

Broadcast encryption [START_REF] Fiat | Broadcast Encryption[END_REF][START_REF] Boneh | Collusion-resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF] allows a "broadcaster" to send an encrypted message to a set of receivers n, each of which has a different private key. Given any subset of n, the broadcaster can construct an encrypted message so that only the receivers in the subset can decrypt it. Using broadcast encryption to guarantee confidentiality in CON presents several advantages. First, the publisher of a content can encrypt it only once, for a known subset of users. Also, the publisher can precompute and store, or generate new decryption keys on the fly, for already published content. Further, since encrypted content can be consumed by many users, the benefit from caching can be preserved in the network. However, the publisher should generate and store as many keys as the number of clients (n). Also, producer's public key and ciphertexts would be of size O( √ n) [START_REF] Boneh | Collusion-resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF], which may result into a significant communication overhead.

Proxy re-encryption [START_REF] Blaze | Divertible protocols and atomic proxy cryptography[END_REF] allows a third-party (called proxy) to (re)encrypt a ciphertext which has been encrypted for Alice, so that it can be decrypted by another user, e.g., Bob. The proxy is considered "semi-trusted" because it does not see the content of the messages being translated. In the CON scenario, the content provider could generate a pair of public/private key (P KP /SKP ) for each content object. The content, m, is then encrypted as ms = EN C(M, SKP ). Whenever a client C (with public/private key pair P KC /SKC ) retrieves the content ms, it queries the content publisher to generate a re-encryption key by sending P KC .

C then receives a transformation key P KP C from the publisher that allows him to re-encrypt content ms so that he can decrypt it (i.e., DEC(RE -EN C(ms, P KP C ), SKC ) is the original content m). This allows the message to be encrypted only once and lets the producer retain control over the decryption since he can refuse the delivery of the transformation key. Also, key management is simplified as the producer creates transformation keys on the fly and does not have to store any additional keys besides his P KP /SKP . The encrypted content is disseminated as ms to all users and allows them to benefit from nearby caches. However, it requires both asymmetric encryption and re-encryption (key transformation), which are computationally more expensive than commonly used symmetric-key encryption algorithms. Nonetheless, as the data is encrypted only once, this overhead can be acceptable in many cases.

Cover files. Arianfar et al. [START_REF] Arianfar | On preserving privacy in Content-Oriented Networks[END_REF] described an algorithm to mix legitimate content with so-called "cover files". The content publisher selects a cover content to mix with legitimate content. Cover files are known to both user and the adversary Adv. All files are cut in equally-sized blocks and padding is used when necessary. For all k tuples, composed of cover and legitimate blocks, the publisher computes the exclusive-or and publishes the result. For instance, if k=2 and given the blocks c1, c2, l1 and l2 (c for cover and l for legitimate), the publisher computes c1 ⊕ c2, c1 ⊕ l1, c1 ⊕ l2, c2 ⊕ l1, c2 ⊕ l2 and l1 ⊕ l2 and publishes them. Using a secure side channel, the user retrieves meta information, such as the content hash and length in blocks, cover blocks and the algorithm generating the names of each block. To retrieve the content, the user requests chunks per name and uses belief propagation or Gaussian elimination to reconstruct the original file. However, this technique requires the cooperation of producers who have to generate large amounts of data and xor them. In fact, as pointed out in [START_REF] Arianfar | On preserving privacy in Content-Oriented Networks[END_REF], the publisher must produce all the chunks in advance and thus, must perform O((α + β) k ) operations where α represents the number of legitimate blocks, β the number of cover blocks, and k the possible number of permutations. Hence, this method incurs several drawbacks that make it unpractical for real-world use.

Name privacy

Name privacy arises from the semantic correlation between human-readable content name and the content itself. Unlike IP, where addresses represent hosts in the network and are not semantically correlated with the content, CCNx [START_REF]CCNx: Open-Source Implementation and Documentation[END_REF] names the content itself and routes data based on content names. Unfortunately, such a property creates an imminent privacy threat as the content names are not only visible but also expected to be semantically related to the content itself (e.g., /US/WebMD/AIDS/Symptoms/html). Although this appears similar to an HTTP connection over IP, it is actually more fundamental in CCNx, as content names cannot be encrypted like the URLs in HTTPS connections. Unlike CCNx, some other architectural proposals such as [START_REF] Koponen | A Data-Oriented (and beyond) Network Architecture[END_REF][START_REF] Ambrosio | Second NetInf Architecture Description. 4WARD Deliverable D6[END_REF] use flat names that are not human-readable. However, all of these proposals rely on a Name Resolution Service (NRS) that performs the translation from human-readable names. Since NRS information is public and accessible to an adversary, even architectures with non humanreadable names create the same inherent threat, due to the naming of content pieces.

Potential Solutions

Bloom filters. The main name privacy challenge in CONs is keeping the name private while ensuring accessibility and routability. A possible solution is to use Bloom filters [START_REF] Broder | Network Applications of Bloom Filters: A Survey[END_REF] tent. The resulting architecture would be composed of three main blocks:

1. A hierarchical bloom filter used as the routing table.

2. A counting bloom filter for each interface used as a PIT table [START_REF] You | Realistic Storage of Pending Requests in Content-Centric Network Routers[END_REF]. 3. A hierarchical bloom filter used as the router storage. Fig. 2 shows an example architecture for a routing table. Rather than sending the request in the clear for a hierarchically named content, a client would compute the corresponding hierarchical bloom filter as HB = (B1, B2, ..., Bn) where Bi is the bloom filter of name components up to the i-th component. For instance, when asking for /NYtimes/article/green-econmy, the client computes a bloom filter B1 of /NYtimes/, B2 of /NYtimes/article and B3 of /NYtimes/article/green-econmy. This scheme would work on CCNx as follows: a router checks whether the last filter (Bn since it contains the exact content name) is in its content store, if so, the content is returned to the customer. If not, the router verifies whether Bn exists in any PIT table. If a match is found, the counting Bloom filter of the corresponding PIT is updated (add one) and the interest is dropped since a request has already been forwarded. Finally, if the interest is not available in the content store nor in any PIT table, the routing process starts: the router checks for longest prefix match on its routing table by starting from Bn going all the way to B1 until it finds a matching routing entry. This approach would enjoy from the obfuscation of content name resulting from transforming it into a random looking string of bits. Also, it can reduce the size needed for storing PIT tables [START_REF] You | Realistic Storage of Pending Requests in Content-Centric Network Routers[END_REF], content storage, and routing table, depending on the parameters for the filters and the size of the content name domain. However, Bloom filters introduce false positives and periodically require resetting.

Signature privacy

One of the main goals of CONs is to decouple content from its location and allow retrieving from nearby caches. In order to trust fetched data, some CON architectures, such as, CCNx [START_REF]CCNx: Open-Source Implementation and Documentation[END_REF], use digital signatures to provide guarantees on provenance and integrity. Although signatures are powerful tools that bind content to its producer, ordinary digital signatures may leak sensitive identity information about the signer. 1 This is problematic, especially when considering censorship and monitoring, as content from certain publishers can be easily and conveniently identified from the signing key, which is explicitly stated at every data packet in CCNx.

Potential Solutions

Confirmer signatures. A first approach to prevent an adversary from verifying a signature would be to use confirmer signatures. Confirmer signatures are undeniable signatures [START_REF] Chaum | Desinated-confirmer signature systems[END_REF] where the signer delegates the verification to a third party (the confirmer), thus, signatures cannot be verified without interacting with this party. Using this method, multiple producers may delegate the verification to a third party and increase the anonymity set for publishers. Although this method would be easy to implement [START_REF] Chaum | Desinated-confirmer signature systems[END_REF][START_REF] Galbraith | Invisibility and anonymity of undeniable and confirmer signatures[END_REF] and would not require any modification to the CCNx schema, it requires a third party as a confirmer and introduces an another round of communication for signature verification.

Group signatures [START_REF] Chaum | Group signatures[END_REF] allow the signer to hide in a set of potential signers, thus, providing signer-ambiguity. As such, the client can verify that the signature was generated by a member of the group but is unable to tell whom. For instance, a company with multiple employees may use a group signature so that a signature cannot be publicly tracked back to a single user but only to the company. Group signature is efficient since the size of the signature does not depend on the size of the group. However, it assumes the presence of a trusted group manager admitting group members, distributing keys, and revoking anonymity within the group, thus, making it appropriate only in limited settings with collaborating users.

Ring signatures [START_REF] Rivest | How to Leak a Secret[END_REF]. As cooperation between users is not always achievable, ring signatures [START_REF] Rivest | How to Leak a Secret[END_REF] simplify group signatures by removing both group manager and members interaction. Therefore, there is no need to prearrange group of users, nor for special procedures for group management and key distribution. Also, the anonymity of the actual signer is always protected. For instance, a company X could collect the public keys of n other trusted companies Y1, Y2, ..., Yn, as these keys are publicly available. Then, X can generate a signature σ for content m that keeps the signer unidentifiable among X and other trusted companies. When a client fetches a content m, he is able to verify that the content was produced by one of {X} {Y1, Y2, ..., Yn} without knowing which one it is. This schema allows customers to trust content as long as all possible signers are trustworthy, while making anyone observing their traffic unable to singularly discern the signer. However, the communication overhead introduced by ring signatures is linear in the size of the ring. Also, it would still be possible to enforce censorship based on signatures by blocking all content that list certain entities as one of potential signers.

Ephemeral identities. Any content producer can create ephemeral keys to sign content. This would effectively prevent identifying the publisher of content by looking at its signature. However, this would also prevent customers from verifying the source/publisher of a content without an additional mechanism to authenticate it. Luckily, CCNx allows creating unforgeable links by including the hash of a content object in the link and allows these links to be signed. This would allow publishing content signed with ephemeral keys that are not traceable to a long-lived identity, but would still allow users to establish transitive trust when they fetched it, by following link that is published by a trusted party. For instance, a link to a sensitive content might be published and signed by a trusted blog (ms) but the actual content (ma) might be published and signed with a one-time indentity and be served through an anonymous hosting service (e.g., rapidshare.com). Any user trusting the blog author can trust ms, and thus (ma), but an eavesdropper observing ma is unable to link it to its publisher. This approach is very easy to deploy and does not need any modification of the current architecture, however, it cannot hide the access to the link and prevent leakage through its signature.

THE POTENTIAL OF CON PRIVACY

In this section, we compare CON to today's Internet in the con-text of a few privacy concepts, such as, anonymity, censoring, traceability, and confidentiality. (A more detailed discussion is included in the full version of this paper [START_REF] Chaabane | Privacy in Content-Oriented Networking: Threats and Countermeasures[END_REF].) Anonymity. A few techniques are possible today to provide anonymous communications. One naïve solution is to rely on a trusted anonymizing proxy relaying traffic while removing identifying information [START_REF] Boyan | The Anonymizer -Protecting User Privacy on the Web[END_REF]. However, this introduces a single point of failure and trust, thus, proxy-less techniques have been proposed, relying on mix networks [START_REF] Chaum | Untraceable electronic mail, return addresses, and digital pseudonyms[END_REF]. Tor [START_REF] Dingledine | Tor: The Second-Generation Onion Router[END_REF] is the best-known, and most widely used, low-latency anonymizing tool. Using onion routing and layered encryption, Tor builds a multi-hop circuit, composed of at least three random nodes.

In CON, proxy-based anonymity could be obtained without the need for an external entity: CON architectures would actually provide, natively, the removal (or substitution) of source and destination addresses. A neighboring CON router could actually be seen as an anonymizing proxy. In reality, however, a local active adversary could monitor all connectivity (see Section 3.1). Regardless, the research community has already started investigating whether or not onion routing-like techniques can be used in CON: a first answer has been provided by ANDāNA [START_REF] Dibenedetto | Andana: Anonymous named data networking application[END_REF], a Tor-like low-latency anonymizing tool for CCN [START_REF] Jacobson | Networking Named Content[END_REF]. Compared to Tor, it only requires two hops and it is resilient against "hijacking" attacks (i.e., attacks where the adversary hijacks and modifies server's answers e.g., [START_REF] Blond | One bad apple spoils the bunch: exploiting P2P applications to trace and profile Tor users[END_REF]) since data is signed. However, due to data encryption, CON caching mechanism could not be used. Also, ANDāNA inherits some of Tor weaknesses, e.g., the difficulty of circumventing censorship while retrieving the directory with all participating nodes. Moreover, the portability of ANDāNA to architectures other than CCN depends on the routing protocol. For instance, PSIRP [START_REF] Visala | LANES: An Inter-Domain Data-Oriented Routing Architecture[END_REF] routers do not store any routing information and rely on a Forwarding Identifier (FI) 2 provided by the client to route back the content, thus, guaranteeing anonymity is very challenging since the routing protocol itself leaks information. As the FI carries information about the user, it should be anonymized while ensuring that data is correctly forwarded. Whereas, in Dona [START_REF] Koponen | A Data-Oriented (and beyond) Network Architecture[END_REF] and Net-Inf [START_REF] Ambrosio | Second NetInf Architecture Description. 4WARD Deliverable D6[END_REF], the routing protocol is similar to that used in CCN [START_REF] Jacobson | Networking Named Content[END_REF], hence, it is safe to assume that ANDāNA [START_REF] Dibenedetto | Andana: Anonymous named data networking application[END_REF] can be used on top of them to provide anonymous communications.

Censorship. Internet censorship appears to be easier in CON architectures. First, and foremost, naming content facilitates keyword filtering. Then, as CON routers have bigger computational and memory resources, content blocking could be carried more effectively, without the need for (expensive) dedicated hardware. Finally, data-monitoring is easier since both interests and data are not encrypted. Therefore, an attacker only needs to modify the routing protocol so that any "unwanted" interest is dropped. However, if CON traffic is exchanged using ANDāNA [START_REF] Dibenedetto | Andana: Anonymous named data networking application[END_REF], there would be a couple of features making it harder for the attacker to censor content. First, both interests and content are encrypted, and, second, as the exit node is usually out of the attacker's control, the latter cannot delete content. Nonetheless, the effectiveness of ANDāNA (or other techniques in CON) to counter Internet censorship remain an open question that calls for further research.

Traceability. Today, a number of techniques are employed to track users, the most widespread of which are cookies. While it seems straightforward to port cookies to CON, this is not without obstacles. In fact, while in current architectures browsers automatically send cookies to Web servers when fetching data, following so-called same-origin policy, it is not clear how cookies will be im-plemented for static content in CON, since data can be fetched from anywhere. Cookies could be transmitted to the source only when fetching dynamic data and, as such, cookie-based tracking mechanisms in CON will be less aggressive as only dynamic content can be tracked. Similar arguments apply for Javascript-based tracking, Supercookies, and Evercookies. However, more aggressive tracking techniques have recently emerged. For instance, Stateless tracking uses both user IP address and browser fingerprint to uniquely track users on the web [START_REF] Yen | Host fingerprinting and tracking on the web: Privacy and security implications[END_REF]. Mitigating browser fingerprinting can be achieved by using plug-ins, e.g., NoScripts, however, it is still hard to hide user's IP address, unless using techniques for anonymous communications. However, as CON architectures remove, by design, both parties' identifiers (i.e., source and destination addresses), it would be harder to actually implement IPbased tracking. The lack of traceability might improve user privacy, however, it naturally raises both security and economic challenges. The former are related to the lack of source address: for instance, following a security incident (e.g. DoS attacks), this information is often crucial to identify/counter the attacker. Whereas, economic challenges stem from changes that CON might impose on the advertisement model: ads are usually delivered based on website popularity and user location and estimating website popularity based on the number of visits is ineffective in CON as caching will "hide" a significant amount of traffic.

Finally, observe that, as discussed in Section 3, a few CON network components (including the role played by neighboring routers) can actually be used to better track users.

Data authenticity and confidentiality. While today's Internet requires a "one-size-fits-all" trust model, trust in CON is end-to-end, between data producer and data consumer, and does not depend on any physical or temporal frame. This modularity has two main advantages. (1) Different consumers may easily implement different levels of security, and (2) on CON, one can employ both widely accepted and new trust management models as data is independent from the deployed model. However, these features also prompt some challenges. First, we need to identify a set of usable trust mechanisms that can be deployed and used by most users. Second, as all content is signed, it is crucial to assess (and potentially improve) efficiency of signature generation, transmission, verification, and possibly storage. Finally, we believe that providing data confidentiality while keeping caching mechanism is one of the major open challenges in CON.

RELATED WORK

Propelled by the increasing interest for next-generation Internet architectures and, in particular, Content-Oriented Networking (CON), the research community has produced a large body of work dealing with CON building blocks [START_REF] Jacobson | Networking Named Content[END_REF][START_REF] Koponen | A Data-Oriented (and beyond) Network Architecture[END_REF][START_REF] Visala | LANES: An Inter-Domain Data-Oriented Routing Architecture[END_REF][START_REF] Ambrosio | Second NetInf Architecture Description. 4WARD Deliverable D6[END_REF][START_REF] Gritter | An Architecture for Content Routing Support in the Internet[END_REF], performance [START_REF] You | Realistic Storage of Pending Requests in Content-Centric Network Routers[END_REF][START_REF] Rossini | A dive into the caching performance of content centric networking[END_REF][START_REF] Cho | WAVE: Popularity-based and collaborative in-network caching for Content-Oriented Networks[END_REF][START_REF] Psaras | Probabilistic in-network caching for information-centric networks[END_REF], and scalability [START_REF] Rossini | On sizing CCN content stores by exploiting topological information[END_REF][START_REF] Borst | Distributed Caching Algorithms for Content Distribution Networks[END_REF]. However, the quest for analyzing and enhancing security in CON is only at the beginning -in particular, very little work has focused on privacy and anonymity. In this section, we review relevant prior work. Security in CON. Wong and Nikander [START_REF] Wong | Secure Naming in Information-Centric Networks[END_REF] address security of naming mechanisms by constructing content name as the concatenation of content provider's ID, cryptographic ID of the content and some meta-data. Dannewitz et al. [START_REF] Dannewitz | Secure Naming for a Network of Information[END_REF] adopt a similar approach where content name is defined as the concatenation of the hash of the public key and a set of attributes. Both schemes rely on cryptographic hash functions to name the content, which results in a human-unreadable flat naming. Smetters et al. [START_REF] Smetters | Securing Network Content[END_REF] show that these schemes have several drawbacks, including the need for an indirection mechanism to map and the lack of binding between name and producer's identity. To resolve these shortcomings, they propose to keep hierarchical human readable names while signing both content name and the content itself, using producer's public key. Gasti et al. [START_REF] Gasti | DoS and DDoS in Named-Data Networking[END_REF] study DoS and DDOS in CCN [START_REF] Jacobson | Networking Named Content[END_REF] by presenting attacks and proposing some initial countermeasures. In another context, Burke et al. [START_REF] Burke | Securing Instrumented Environments over Content-Centric Networking: the Case of Lighting Control[END_REF] propose a secure lighting systems over Named-Data Networking (NDN), providing control access to fixtures via authorization policies, coupled with strong authentication.

Privacy Issues in CON. To the best of our knowledge, the only related privacy study is the recent article by Lauinger et al. in [START_REF] Lauinger | Privacy Implications of Ubiquitous Caching in Named Data Networking Architectures[END_REF][START_REF] Lauinger | Privacy risks in named data networking: what is the cost of performance?[END_REF], that covers security and privacy issues of CCN [START_REF] Jacobson | Networking Named Content[END_REF]. Specifically, they highlight a few Denial-of-Service (DoS) vulnerabilities as well as different cache-related attacks. From the privacy perspective, work in [START_REF] Lauinger | Privacy Implications of Ubiquitous Caching in Named Data Networking Architectures[END_REF][START_REF] Lauinger | Privacy risks in named data networking: what is the cost of performance?[END_REF] identifies the issue of information leakage through caches in CCN. It proposes a few simple countermeasures, following detection and prevention approaches. The former can be achieved using techniques similar to those addressing cache pollution attacks in IP [START_REF] Deng | Pollution attacks and defenses for internet caching systems[END_REF], although such an approach can be difficult to port to CON due to the lack of source address. The latter can actually be global, i.e., treating all traffic as sensitive, delaying all traffic, or deploying a shared cache to circumvent the attack. Alternatively, a selective prevention approach may try to distinguish between sensitive and non-sensitive content, based on content popularity and context (time, location), and then delay or tunnel sensitive content. Our work extends that in [START_REF] Lauinger | Privacy Implications of Ubiquitous Caching in Named Data Networking Architectures[END_REF][START_REF] Lauinger | Privacy risks in named data networking: what is the cost of performance?[END_REF] by encompassing all privacy aspects: caching, naming, signature, and content. Also, it is more general as it does not only consider CCN [START_REF] Jacobson | Networking Named Content[END_REF], but CON in general, independently of the specific instantiation. Furthermore, when suggesting countermeasures, we only propose techniques that can be applied with a minimal change to the architecture. Anonymity in CON. ANDāNA [START_REF] Dibenedetto | Andana: Anonymous named data networking application[END_REF] proposes a Tor-like anonymizing tool for CCN [START_REF] Jacobson | Networking Named Content[END_REF] to provide provable anonymity. It also aims to privacy protection via simple tunneling. However, ANDāNA is an "all-in-one" solution that introduces latency and impedes caching. Whereas, fine-grained privacy solutions are needed, since a widespread use of tunneling would inherently take away most of CON benefits in terms of performance and scalability.

CONCLUSION

Content-Oriented Networking (CON) proposes a major transition from today's Internet to a new content-based architecture. This radical change calls for a thorough analysis of both security and privacy guarantees. CON comes with a potential benefit to security, including a security-by-design approach based on digital signatures that provides data integrity and origin authentication, as well as trust support. However, prior to our work, it remained an open question whether or not, and to what extent, this emerging networking paradigm bears new privacy threats.

This paper presented a first-of-its-kind, systematic analysis of privacy issues in CON as a generic paradigm, discussing different attacks and detailing their impact on user privacy. We also proposed several countermeasures while attempting to balance the trade-off between privacy, performance, and changes to the architecture. In the process, we identified a number of interesting research challenges that call for further work in the area.

Naturally, our work does not end here: first, and foremost, we are working toward further evaluating the feasibility of our proposed countermeasures and their effective deployment; next, we plan to provide an in-depth study of multiple encryption and signature techniques and their impact on network performance; finally, we intend to analyze the impact of privacy-enhancing and CONnative technologies on Web economy and advertisement models.

Table Figure 2

 Figure to identify con-: Routing Table using hierarchical bloom filter.

	/prefix1 /prefix2 /prefix3
	Encoder
	Value	Interface
	Hash

CCNx currently offers two choices, RSA and ECDSA, as signature algorithms.

FI is a Bloom filter-based technique used by routers to select the forwarding interface.


Shyr-Yu Theorem

Pál D Öm Ösi

Horv Géza
email: geza@inf.unideb.hu

Áth

Laurent Vuillon
email: laurent.vuillon@univ-savoie.fr

On

Keywords:

An alternative proof of Shyr-Yu Theorem is given. Some generalizations are also considered using fractional root decompositions and fractional exponents of words.

Introduction

A word is primitive if it is not a power of another word. A well-known unsolved problem of theoretical computer science asks whether or not the language of all primitive words over a nontrivial alphabet is context-free or not [START_REF] Ösi | On the connection between formal languages and primitive words[END_REF][START_REF] Ösi | Formal languages and primitive words[END_REF]. Among others, this (in)famous problem motivates the study of the combinatorial properties of primitive words. In addition, they have special importance in studies of automatic sequences [START_REF] Allouche | Automatic sequences. Theory, applications, generalizations[END_REF][START_REF] Lothaire | Combinatorics on Words[END_REF]. The Shyr-Yu Theorem [START_REF] Shyr | Non-primitive words in the language p + q +[END_REF] is a well-known classical result in this direction. The known proof of this result is rather involved [START_REF] Shyr | Non-primitive words in the language p + q +[END_REF]. The aim of this paper is to give a new simple proof of this well-known theorem, using some simple observations. In addition, we give the decomposition of words in the language p + q + , in particular we find fractional root decompositions and fractional exponents of the words appearing in the language.

Preliminaries

A word over Σ is a finite sequence of elements over some finite non-empty set Σ. If there is no danger of confusion, sometimes we omit the expression "over Σ". We call the set Σ an alphabet, the elements of Σ letters. Σ is called trivial if it is a singleton. Otherwise we also say that Σ is nontrivial. We also define the empty word λ consisting of zero letters. The length |w| of a word w is the number of letters in w, where each letter is counted as many times as it occurs. Thus |λ| = 0.

If u = x 1 • • • x k and v = x k+1 • • • x ℓ
are words over an alphabet Σ (with x 1 , . . . , x k , x k+1 , . . . , x ℓ ∈ Σ) then their catenation (which is also called their product

) uv = x 1 • • • x k x k+1 • • • x ℓ
is also a word over Σ. In addition, for every word u

= x 1 • • • x k over Σ (with x 1 , . . . , x k ∈ Σ), uλ = λu = u (= x 1 • • • x k ). Moreover, λλ = λ. Obviously, for every u, v ∈ Σ * , |uv| = |u| + |v|.
Clearly, then, for every words u, v, w (over Σ) u(vw) = (uv)w. In other words, uu ′ = w ′ w whenever u ′ = vw and w ′ = uv. Therefore, catenation is an associative operation and the empty word λ is the identity with respect to catenation. Let u, v, w be words with u = vw. Then we say that v is a prefix of u and w is a suffix of u. Two words u, v are said to be conjugates if there exists a word w with uw = wv. In particular, a word z is called overlapping (or bordered) if there are u, v, w ∈ Σ + with z = uw = wv. Otherwise we say that z is non-overlapping (or unbordered). Proposition 2.1 [START_REF] Lyndon | The equation a M = b N c P in a free group[END_REF] u, v are conjugates if and only if there are words p, q with u = pq and v = qp. Theorem 2.2 [START_REF] Lyndon | The equation a M = b N c P in a free group[END_REF] Let u, v ∈ Σ + with uv = vu. There exists w ∈ Σ + with u, v ∈ w + . Lemma 2.3 [START_REF] Levi | On semigroups[END_REF] If uv = pq and |u| ≤ |p| for some u, v, p, q ∈ Σ + , then p = ur and v = rq for some r ∈ Σ * . Lemma 2.4 [START_REF] Lyndon | The equation a M = b N c P in a free group[END_REF] If uv = vq, u ∈ Σ + , v, q ∈ Σ * , then u = wz, v = (wz) k w, q = zw for some w ∈ Σ * , z ∈ Σ + and k ≥ 0.

If u, v, w, z are words over Σ having z = uvw, then v is called a subword of z. The nonempty prefix, suffix, subword are also called a proper (or nontrivial) prefix, suffix, subword.

By the free monoid Σ * generated by Σ we mean the set of all words (including the empty word λ) having catenation as multiplication. We set Σ + = Σ * \ {λ}, where the subsemigroup Σ + of Σ * is said to be the free semigroup generated by Σ. Σ * and Σ + have left and right cancellation, i.e. for every elements u, v, w of Σ * or Σ + , uv = uw implies v = w and uv = wv implies u = w.

Subsets of Σ * are referred to as languages over Σ. In particular, subsets of Σ + are referred to as λ-free languages over Σ.

Given a word u, we define

u 0 = λ, u n = u n-1 u, n > 0, u * = {u n : n ≥ 0} and u + = u * \ {λ}. Thus u n with n ≥ 0 is the n-th power of u, while u * is the Kleene closure, moreover, u + is the semigroup closure of u.
Given a list c 1 , . . . , c n of integers, let gcd(c 1 , . . . , c n ) denote the greatest common divisor of c 1 , . . . , c n . Theorem 2.5 [START_REF] Fine | Uniqueness theorems for periodic functions[END_REF] Let u, v ∈ Σ * . u, v ∈ w + for some w ∈ Σ + if and only if there are i, j ≥ 0 so that u i and v j have a common prefix (suffix) of length |u| + |v| -gcd(|u|, |v|).

A primitive word (over Σ, or actually over an arbitrary alphabet) is a nonempty word not of the form w m for any nonempty word w and integer m ≥ 2. Thus λ is a nonprimitive word because of λλ = λ. The set of all primitive words over Σ will be denoted by Q(Σ), or simply by Q if Σ is understood. Let u = λ and let f be a primitive word with an integer k ≥ 1 having u = f k . We let √ u = f and call f the primitive root of the word u.

Theorem 2.6 [11] Let u, v ∈ Σ * . w i = uv for some w ∈ Σ * , i ≥ 1 if and only if there are p, q ∈ Σ * w = pq, (qp) i = vu. Furthermore, uv ∈ Q for some u, v ∈ Σ * if and only if vu ∈ Q.
The next statement shows that, for every nonempty word, the primitive root is unambiguously determined. We have a direct consequence of Theorem 2.8 as below.

Theorem 2.9 Let f, g ∈ Q, f = g. Then f m g n ∈ Q for all m ≥ 2, n ≥ 2. Lemma 2.10 [3] Let u, v ∈ Q, such that u m = v k w for some k, m ≥ 2, and w ∈ Σ * with |w| ≤ |v|.
Then exactly one of the following conditions holds: (i) u = v and w ∈ {u, λ}; (ii) m = k = 2 and there are p, q ∈ Σ + , s ≥ 1 with √ p = √ q, u = (pq) s+1 p 2 q, v = (pq) s+1 p, w = qp 2 q.

Theorem 2.11 [START_REF] Ösi | Alternative proof of the Lyndon-Schützenberger Theorem[END_REF] Let u, v ∈ Q, such that u m = v k w for some prefix w of v and k, m ≥ 2. Then u = v and w ∈ {u, λ}.

Theorem 2.12 (Shyr-Yu Theorem) [START_REF] Shyr | Non-primitive words in the language p + q +[END_REF] Let f, g ∈ Q, f = g. Then |f + g + ∩ Σ + \ Q| ≤ 1. Moreover, if f and g are also non-overlapping, then f + g + contains only primitive words.

Results

The next statement is an extended version of the first part of Theorem 2.9.

Theorem 3.1 Let f, g ∈ Q, f = g and n ≥ 1. If f g n / ∈ Q then f g n+k ∈ Q for all k ≥ 1.
Proof: Suppose the contrary and let u i = f g n , v j = f g n+k for some u, v ∈ Σ + , i, j > 1, k ≥ 1. We may assume without any restriction u, v ∈ Q. By our conditions, v j = u i g k .

First we assume k ≥ 2. Hence, by Theorem 2.8,

√ v = √ u = √ g, i.e. u = v = g. By u i = f g n , this results f = g i-n leading to √ f = √ g. Then,
by f, g ∈ Q, we have f = g, a contradiction. Now we suppose k = 1. By Theorem 2.6, there are w, z ∈ Q with w i = g n f, z j = g n f g. Then z j = w i w 1 , where w 1 is a prefix of w. Applying Theorem 2.11, w = z, which, by Theorem 2.6, implies u = v. But then k = 0, a contradiction.

Proof of Theorem 2.12 : Let f, g ∈ Q be distinct primitive words.

First we prove that the language f + g + contains at most one non-primitive word. Suppose f m g n / ∈ Q. By Theorem 2.9, m, n ≥ 2 is impossible. Therefore, we may assume either f m g / ∈ Q for some m ≥ 1 or f g n / ∈ Q for some n ≥ 1.

By Theorem 3.1, there exists at most one pair m, n ≥ 1 of positive integers with

f m g, f g n / ∈ Q. In addition, if f g / ∈ Q, then f m g, f g n ∈ Q, m, n ≥ 2.
Therefore, it is enough to prove that for every pair m, n ≥ 2, f m g / ∈ Q implies f g n ∈ Q. Suppose the contrary and let f m g = u i , f g n = v j for some m, n, i, j ≥ 2, u, v ∈ Q and let, say, |g| ≤ |f |. Using Lemma 2.10, this is possible only if m = i = 2 and there are p, q ∈ Σ + , s ≥ 1 with √ p = √ q and u = (pq) s+1 p 2 q, f = (pq) s+1 p, g = qp 2 q. By Theorem 2.5 and v j = f g n = (pq) s+1 p(qp 2 q) n , this is impossible if either |pq| + |v| ≤ |(pq) s+1 p| + |qp|, or |qp 2 q| + |v| ≤ |(qp 2 q) n |. On the other hand, if |pq| + |v| > |qp(pq) s+1 p| and |qp 2 q| + |v| > |(qp 2 q) n | simultaneously hold, then using again v j = f g n = (pq) s+1 p(qp 2 q) n , we obtain

|v 2 | + |pq| + |qp 2 q| > |v j | + |qp|. Hence |v 2 | > |v j | -|qp 2 q| which leads since |qppq| < |v| to j = 2. By v 2 = f g n , this implies v 2 = (pq) s+1 p(qp 2 q) n . By the assumptions |pq| + |v| > |qp(pq) s+1 p| and |qp 2 q| + |v| > |(qp 2 q) n |, we can reach |(qp 2 q) n-2 | < |(pq) s+1 p| < |(qp 2 q) n |. Thus 2n -5 ≤ s ≤ 2n -2 which means v = (pq) 2n-4 r 1 = r 2 (qp 2 q) n-2 , |r 1 | = |r 2 | such that r 1 r 2 = (pq) t p(qp 2 q) 2 , t ∈ {0, 1, 2, 3}. Note that, because of v ∈ Q, √ p = √ q is impossible. We distinguish the following four cases. Case 1. t = 0, r 1 = pqpz 1 , r 2 = z 2 p 2 q, z 1 z 2 = pq 2 , |z 1 | = |z 2 |. Then v = (pq) 2n-4 pqpz 1 = z 2 p 2 q(qp 2 q) n-2 . Thus z 1 is a suffix and z 2 is a prefix of pq. Hence, by |z 1 | = |z 2 | = 1 2 |p| + |q|, we get z 1 = p 2 q, z 2 = p 1 q ′ with p = p 1 p 2 , |q ′ | = |q|, |p 1 | = |p 2 | for appropriate q ′ , p 1 , p 2 ∈ Σ + . Obviously, then z 1 z 2 = p 2 qp 1 q ′ =
pq 2 . This implies p 2 = p 1 and q ′ = q. This leads to

z 1 = z 2 = p 1 q. Thus z 1 z 2 = (p 1 q) 2 = p 2 1 q 2 implying qp 1 = p 1 q. Applying Theorem 2.2, √ p 1 = √ q. By p = p 2 1 , this implies √ p = √ q, a contradiction. Case 2. t = 1, r 1 = (pq) 2 z 1 , r 2 = z 2 qp 2 q, z 1 z 2 = p 2 q, |z 1 | = |z 2 |. Then v = (pq) 2n-2 z 1 = z 2 (qp 2 q) n-1 . Thus z 1 is a suffix and z 2 is a prefix of of pq. Hence, by |z 1 | = |z 2 | = |p| + 1 2 |q|, we get z 1 = p ′ q 2 , z 2 = pq 1 with q = q 1 q 2 , |p ′ | = |p|, |q 1 | = |q 2 | for appropriate p ′ , q 1 , q 2 ∈ Σ + .
Obviously, then z 1 z 2 = p ′ q 2 pq 1 = p 2 q. Hence we get p ′ = p and q 1 = q 2 . In other words, z 1 z 2 = (pq 1 ) 2 = p 2 q 2 1 leading to q 1 p = pq 1 . By Theorem 2.2, we get

√ q 1 = √ p which is impossible because of q = q 2 1 . Case 3. t = 2, r 1 r 2 = (pq) 2 p(qp 2 q) 2 . Then r 1 = (pq) 3 p 1 , r 2 = p 2 pq 2 p 2 q with p = p 1 p 2 , |p 1 | = |p 2 |.
But then, either n = 2 or n > 2, p 2 is simultaneously a prefix and a suffix of p. Therefore, p 1 = p 2 which implies p = p 2 1 . Thus, we can write v = (p 2 1 q) 2n-4 (p 2 1 q) 3 p 1 = p 3 1 q 2 p 4 1 q(qp 4 1 q) n-2 which implies qp 1 = p 1 q either n = 2 or n > 2. By Theorem 2.2, this means

√ q = √ p 1 such that p = p 2 1 . Therefore, √ p = √ q, a contradiction.
Case 4. t = 3, r 1 r 2 = (pq) 3 p(qp 2 q) 2 . In this case, r 1 = (pq) 3 pq 1 , r 2 = q 2 p 2 q 2 p 2 q with q = q 1 q 2 , |q 1 | = |q 2 |. We observe that, either n = 2 or n > 2, q 1 is simultaneously a prefix and a suffix of q. Therefore, q 1 = q 2 with q = q 2 1 . Thus, we can write v = (pq 2 1 ) 2n-4 (pq 2 1 ) 3 pq 1 = q 1 p 2 q 4 1 p 2 q 2 1 (q 2 1 p 2 q 2 1 ) n-2 which implies pq 1 = q 1 p, if n = 2 and pq 2 1 pq 1 = q 1 p 2 q 2 1 , if n > 2. Both equalities lead to pq 1 = q 1 p. By Theorem 2.2, this leads to √ q 1 = √ p such that q = q 2 1 . Therefore, √ p = √ q, a contradiction.

It remains to show that, for every distinct pair f, g ∈ Q of unbordered primitive words, f + g + ⊆ Q. By Theorem 2.9, m, n ≥ 2 implies f m g n ∈ Q. Thus it is enough to prove that for every m, n ≥ 2, f m g, f g n ∈ Q.

Suppose that, contrary of our statement, there are u ∈ Q, i > 1 with f m g = u i . Consider u 1 , u 2 ∈ Σ * , j ≥ 0 with u = u 1 u 2 such that f m = u j u 1 and g = u 2 u i-j-1 . By Theorem 2.11, j ≤ 1. If j = 0, then g = u 2 u i-1 with i -1 > 0. Then g is bordered, a contradiction. Thus we get j = 1. Therefore,

f m = u 1 u 2 u 1 , g = u 2 (u 1 u 2 ) i-2 . If u 1 = λ, then f is bordered, a contradiction. Hence f m = u 2 , g = u i-1 2 . Clearly, then f = √ f = √ u 2 = √ g = g, a contradiction. Now we assume that, contrary of our statement, f g n = v k , v ∈ Q, k > 1.
By Theorem 2.6, there exists a word z ∈ Q having g n f = z k . We have already proved that this is impossible. This completes the proof. Definition 3.2 Let w be a finite word over the alphabet Σ. We define the fractional root of w as the shortest word noted f √ w with the property that ( f √ w) (n+α) = w where n is a positive integer and α is a positive rational number.

Example for w = abaabaab, we find (aba) (2+ 23 ) = abaabaab, thus the fractional root of w = abaabaab is f √ w = aba.

Definition 3.3 If f √ w =
√ w = w then we say that w is purely primitive (or aperiodic).

For example w = aababbb is purely primitive. The first part of Shyr-Yu Theorem could be refined in three cases according to the following statement: Theorem 3.4 Consider the language of p + q + . Then (i1) If there exists k such that p = (xq k ) i-1 x then the non-primitive factor is

W i = pq k = (xq k ) i or W i = p k ′ y(p k ′ y) i-1 .
For this case, we could find finite classes of primitive words with fractional roots constructed as pq (i2) There is a non-primitive word in the language and no finite class, thus we have infinite classes constructed by p m = p ′ y and q n = y ′ p ′ with |p ′ | maximal and m, n ≥ 1. Furthermore, if |p ′ | = 0 then the infinite classes have only purely primitive words.

= (xq k ) i-1 xq, pq 2 = (xq k ) i-1 xq 2 , • • • , pq k-1 or pq = py(p k ′ y) i-1 , p 2 q = p 2 y(p k ′ y) i-1 , • • • , p k ′ -1 q = p k ′ -1 y(p k ′ y) i-
(ii) There is no non-primitive word in the language, thus we have only infinite classes constructed by p m = p ′ y and q n = y ′ p ′ with |p ′ | maximal and m, n ≥ 1. Furthermore, if |p ′ | = 0 then the infinite classes are purely primitive.

In this variation of the first part of the Shyr-Yu Theorem, we find in each case an infinite class with words written in the form w = ( f √ w)

(1+ |p ′ | | f √ w| ) .
In fact, if |p ′ | = 0 the form remains the one used in the Shyr-Yu theorem and we can deduce that w = f √ w thus each words are purely primitive words.

Theorem 2 . 7 [ 9 ]

 279 If u = λ, then there exists a unique primitive word f and a unique integer k ≥ 1 such that u = f k . Let a m b n = c k be an equation such that a, b, c ∈ Σ * and m, n, k ≥ 2. We say that a m b n = c k has only trivial solution if a m b n = c k holds only if there exists a w ∈ Σ * with a, b, c ∈ w * . Theorem 2.8 (Lyndon-Schützenberger Theorem) [9] The equation a m b n = c k with a, b, c ∈ Σ * has only trivial solutions.

1

 1 which are primitive and not purely primitive. And infinite classes constructed by p m = p ′ y and q n = y ′ p ′ with |p ′ | maximal and m, n ≥ 1. Furthermore, if |p ′ | = 0 then the infinite classes have only purely primitive words.

This work was supported by research grants of French National Foundation for Research ( ÉGIDE) and Hungarian National Office for Research and Technology (NKTH) (Balaton F-30/04), and the Hungarian National Foundation for Scientific Research (OTKA 49409).

Examples :

1) p = a and q = b lead to only purely primitive words in the language p + q + . 2) p = ab and q = abb lead also to purely primitive words.

3) p = aba and q = abaab give a longest prefix of p m which is also suffix of q n namely abaab for m = 2 and n = 1.

That is for m ≥ 2 and n ≥ 1 the word w = p m q n could be written as

)

) . And for m = n = 1 we find pq = abaabaab = (aba)

Proof of Theorem 3.4 : In case of (i1), we know that there exists a unique non-primitive word, namely W i , in p + q + . We can write the general form of

In both cases we can find finite classes of words :

In each case, we can find an infinite class of words with the form w =

) where p m = p ′ y and q n = y ′ p ′ with |p ′ | maximal. We prove this fact by contradiction. Suppose that there is no p ′ which is maximal. That is we have an infinite sequence of words indexed by distinct couples (m i , n i ) with increasing length of p ′ (m i ,n i ) such that p m i = p ′ (m i ,n i ) y and q n i = y ′ p ′ (m i ,n i ) . As the sequence is infinite, we find a starting point in q = ss ′ such that we could extend the rigth part of the word to an infinite by p ω = (s ′ s) ω . By using Theorem 2.5, we have that p = z ℓ and s ′ s = z ℓ ′ . Thus p is not primitive. A contradiction.