Hossein Shafagh
email: shafagh@inf.ethz.ch

Anwar Hithnawi
email: hithnawi@inf.ethz.ch

Lukas Burkhalter
email: burkhalter@inf.ethz.ch

Pascal Fischli
email: fischli@inf.ethz.ch

Simon Duquennoy
email: simonduq@sics.se

Secure Sharing of Partially Homomorphic Encrypted IoT Data

Keywords: Secure Sharing, Encrypted Data Processing, Homomorphic Encryption ACM Reference format:

IoT applications often utilize the cloud to store and provide ubiquitous access to collected data. This naturally facilitates data sharing with third-party services and other users, but bears privacy risks, due to data breaches or unauthorized trades with user data. To address these concerns, we present Pilatus, a data protection platform where the cloud stores only encrypted data, yet is still able to process certain queries (e.g., range, sum). More importantly, Pilatus features a novel encrypted data sharing scheme based on reencryption, with revocation capabilities and in situ key-update. Our solution includes a suite of novel techniques that enable efficient partially homomorphic encryption, decryption, and sharing. We present performance optimizations that render these cryptographic tools practical for mobile platforms. We implement a prototype of Pilatus and evaluate it thoroughly. Our optimizations achieve a performance gain within one order of magnitude compared to stateof-the-art realizations; mobile devices can decrypt hundreds of data points in a few hundred milliseconds. Moreover, we discuss practical considerations through two example mobile applications (Fitbit and Ava) that run Pilatus on real-world data.

INTRODUCTION

The Internet of Things (IoT), through embedded devices and wearables, is enabling a whole new spectrum of applications. One of the Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. SenSys '17, November 6-8, 2017, Delft, Netherlands © 2017 Copyright is held by the owner/author(s). Publication rights licensed to ACM. ACM 978-1-4503-5459-2/17/11. . . $15.00 https://doi.org/10.1145/3131672.3131697 The cloud has access to no keys nor any plaintext. It is able to process encrypted data (e.g., range, sum queries), as well as to re-encrypt it, enabling crypto-protected sharing. We also address revocation, in situ re-keying, and group sharing.

prominent offerings in this domain is the emerging field of health and fitness tracking with over 150k [START_REF]Things are looking app[END_REF] applications listed in the two major smartphone app stores. Examples of such applications include wristbands that can infer stress level from skin conductance, sport trackers that can log physical activities, and fertility apps.

The collected data typically consists of sensor readings (e.g., body temperature, conductance response), activity meta-data (e.g., duration, type), or health-related symptoms (e.g., migraine headaches, pain). For scalability, ubiquitous access, and sharing possibilities, the data is most often stored in the cloud. Transparent and secure data sharing (e.g., sharing with friends or domain experts) is considered a key requirement for the practicality and success of typical IoT systems [START_REF] Jernigan | Data Sharing and Analytics Drive Success With IoT[END_REF][START_REF] Shafagh | Privacy-preserving Quantified Self: Secure Sharing and Processing of Encrypted Small Data[END_REF]. Moreover, securing the cloud storage is of utmost importance, as the data can be used to infer privacy-sensitive information, such as heart diseases, personal well-being, and fertilityrelated data [START_REF]Fertility Tracking Bracelet[END_REF][START_REF] Buxton | Hormonal Factors Involved in the Regulation of Basal Body Temperature During the Menstrual Cycle and Pregnancy[END_REF]. The privacy risks of today's data collection model are many, including systematic unauthorized disclosure of personalized data on clouds [START_REF] Ballano Barcena | How safe is your quantified self?[END_REF], for personal advertising [START_REF] Olson | For Google Fit, Your Health Data Could Be Lucrative[END_REF], trading with insurances [START_REF] Dredge | those Free Health Apps are Sharing your Data with other Companies[END_REF], and due to external [START_REF]Data Breach Industry Forecast[END_REF] or internal data breaches (e.g., curious cloud employees [START_REF]Data Breach Industry Forecast[END_REF]).

Partially Homomorphic Encryption (PHE) and in particular additive homomorphic schemes. These are practical solutions that enable an important set of queries [START_REF] Tu | Processing Analytical Queries Over Encrypted Data[END_REF], such as the sum query on encrypted data -a common operation in IoT applications when history data needs summing or averaging. Also note that with limited involvement of the client side, more complex computations (e.g., linear regression) can also be achieved [START_REF] Tu | Processing Analytical Queries Over Encrypted Data[END_REF].

How to bring cryptographically guaranteed sharing to the IoT ecosystem? The current PHE approaches are either targeted at single-key encrypted data [START_REF] Raluca | CryptDB: Protecting Confidentiality with Encrypted Query Processing[END_REF][START_REF] Shafagh | Talos: Encrypted Query Processing for the Internet of Things[END_REF][START_REF] Tu | Processing Analytical Queries Over Encrypted Data[END_REF] (no support for sharing) or consider only text-based data [START_REF] He | ShadowCrypt: Encrypted Web Applications for Everyone[END_REF][START_REF] Raluca | Building Web Applications on Top of Encrypted Data Using Mylar[END_REF] (of limited use in an IoT context). Talos [START_REF] Shafagh | Demo Abstract: Talos a Platform for Processing Encrypted IoT Data[END_REF][START_REF] Shafagh | Talos: Encrypted Query Processing for the Internet of Things[END_REF] is specifically tailored for IoT scenarios and has demonstrated PHE on embedded devices, but it does not offer any sharing features. Existing protocols for sharing, such as OAuth [35], fall short in providing strong assurances about the policy enforcements. Crypto-based sharing approaches [START_REF] Wang | Sieve: Cryptographically Enforced Access Control for User Data in Untrusted Clouds[END_REF], on the other hand, support no query processing over encrypted data.

In short, existing solutions either support encrypted query processing or secure sharing but not both. Moreover, due to their heavy computational overhead, PHE schemes have been considered unsuitable for low-power mobile and IoT devices. In this paper, we tackle the challenges of cryptographically-protected and efficient sharing of PHE data, as illustrated in Figure 1. Our system is the first to combine encrypted sharing with encrypted query processing. Furthermore, our system is tailored towards mobile platforms, improving the state-of-the-art performance by more than one order of magnitude.

Approach. We introduce Pilatus, which extends Talos [START_REF] Shafagh | Talos: Encrypted Query Processing for the Internet of Things[END_REF] with sharing capabilities. We enable efficient sharing of PHE data based on a re-encryption scheme [START_REF] Ateniese | Improved Proxy Re-encryption Schemes with Applications to Secure Distributed Storage[END_REF]. This means that data is (PHE) encrypted at the client (IoT device/gateway) and uploaded to the cloud. When data owner Alice intends to share her data with Bob, she computes a token that enables the cloud to re-encrypt her data for Bob (without decrypting it first). The same process is used for Alice to share her data with a group. With only public keys and tokens (no secret keys nor plaintext information), the cloud is able to perform query and sharing operations directly on ciphertexts. Users can decide between sharing their individual data points (necessary for complex analytics) or aggregated results, both in encrypted form.

Further, we design a key revocation mechanism that allows users to terminate their data sharing at any time. We also propose an in situ key-update at the cloud, such that old data becomes protected with the owner's new key, without trusting the cloud with any private keys.

Our solutions build on the Elliptic Curve (EC)-based partially homomorphic encryption. Hence, a major challenge is to minimize the decryption time of our EC-based cryptosystems, for both sharing and encrypted processing. We address the performance optimization with the Chinese Remainder Theorem, which enables smaller, faster, and parallel computations. We keep the induced overheads low enough to preserve the user experience (i.e., below 1 s response time [START_REF] Nielsen | Usability Engineering[END_REF], including network latency) such that users can interact with their remotely stored data seamlessly.

Contributions. In summary, this paper makes the following contributions:

• We introduce a practical construction for sharing of PHE IoT data, with a sharing revocation mechanism that also allows in situ re-keying of the ciphertexts in the cloud; • We improve the underlying cryptosystems' decryption time by one order of magnitude compared to state-of-the-art realizations such as Talos [START_REF] Shafagh | Talos: Encrypted Query Processing for the Internet of Things[END_REF] and CryptDB [START_REF] Raluca | CryptDB: Protecting Confidentiality with Encrypted Query Processing[END_REF]; • We design and implement Pilatus, a system that extends Talos with the above sharing schemes and with the necessary features for a practical sharing-enabled cloud storage; • We assess the efficiency of Pilatus through end-to-end and micro benchmarks, in Amazon cloud, on mobile devices, and to a lesser extent on low-power sensor devices. We also present two case study apps running Pilatus: the Fitbit fitness tracker and the Ava fertility tracker [START_REF]Fertility Tracking Bracelet[END_REF]. We make our prototype implementation of Pilatus publicly available1 .

THREAT MODEL

We focus on IoT applications where data from wearables/smartphones are stored on third party clouds. We consider the following parties: the cloud (consisting of a front-end server and the database), clients (apps), and an Identity Provider (IDP) to certify the public key of each user.

Threats. Pilatus considers the cloud service to be honest-butcurious, such that it will follow the protocol correctly, but tries to learn as much as possible from the stored data. This is a valid model, as protocol violations, once detected, could penalize the service provider. At the same time, the adversary might be eager to learn more about user data without being noticed (i.e., passive). External adversaries can also gain access to the encrypted data as a consequence of system compromise. In summary, we consider cloud-side threats which are due to system compromise (e.g., data theft), financial incentives (e.g., unauthorized trades with users data), or malicious insiders (e.g., curious admins).

Assumptions. In addition to the honest-but-curious cloud assumption, Pilatus assumes that the IDP correctly verifies users' identitykey pairs. The IDP is a standard requirement in multi-user systems and can be a known and trustworthy external entity or an internal unit. Group members of shared data are semi-trusted, in that they do not collude with the cloud to leak the group data or key. This is a reasonable assumption for small groups where members are acquainted with each other. Moreover, Pilatus assumes that the applications behave correctly and do not hand out user keys to malicious parties. Finally, we assume state-of-the-art security mechanisms to be in place for device security and that all parties communicate over secure channels.

Guarantees. Pilatus protects the confidentiality of users data stored in the cloud in the presence of passive adversaries (e.g., compromised servers). In case the user device is compromised and group keys are disclosed, only data of the compromised user and the affected group are disclosed. Pilatus cryptographically prevents unauthorized data access. Pilatus provides user authentication mechanisms but does not guarantee freshness or correctness of the retrieved data. In order to provide such guarantees, one could complement our system with integrity protection frameworks such as Verena [START_REF] Karapanos | Verena: End-to-End Integrity Protection for Web Applications[END_REF]. Pilatus does not hide access patterns, which can potentially reveal sensitive information [START_REF] Saiful Islam | Access Pattern Disclosure on Searchable Encryption: Ramification, Attack and Mitigation[END_REF].

PILATUS OVERVIEW

We briefly introduce the requirements of the applications we target and then present the architecture of Pilatus.

Applications

Pilatus focuses on applications collecting sensitive data that require processing and sharing. Examples of such applications include fitness or health trackers. These applications store private data in the cloud that can reveal privacy-sensitive information, e.g., illness, lifestyle, or location. For instance, Fitbit wristbands collect a user's heart rate, step counts, and location data. Similarly, certain health tracking applications and wearables, such as Ava [START_REF]Fertility Tracking Bracelet[END_REF], allow women to track their menstrual cycle, predict (in)fertile phases, and detect potential health issues. Though insightful, logging such private information raises serious privacy concerns. Secure and transparent sharing plays an essential role in bringing such fitness-and health-related apps to their full potential. When users are willing to share data with experts (e.g., medical practitioners), analytical services, or just casually with friends, they must be in full control over who can access and what can be accessed. Moreover, there is a need for query processing capabilities directly in the cloud, since downloading the entire data volume for on-device processing becomes impractical as the data grows. For instance, in Fitbit and Ava, the mobile apps typically display total sums or averaged values (e.g., heart rate) over a given period of time.

To satisfy the above requirements, Pilatus facilitates storing encrypted IoT data in the cloud, while enabling processing and cryptographically-protected sharing of encrypted data. In §7.2, we show that our Pilatus-based app prototypes Ava and Fitbit induce only a modest overhead (i.e., a maximum of 130 ms) while interacting with encrypted data. Note that while the focus of this paper is on health and fitness applications, our system design and application discussions apply as well to other IoT applications (smart homes, connected cars, etc.).

Architecture

Pilatus, as an extension of Talos, uses Partially Homomorphic Encryption (PHE) schemes to enable query processing over encrypted data in the cloud. It offers a new scheme for secure sharing of PHE data among users and groups, based on re-encryption techniques. Our sharing feature includes access revocation with in situ re-keying. We optimize the performance of the underlying cryptographic schemes by one order of magnitude to make them practical on mobile devices. Note that Pilatus inherits the order-preserving encryption from Talos for range queries. Together with PHE, this enables querying a sum/average over a range of timestamps or any other relevant combination of metadata 2 .

Pilatus consists of three main components: the client engine, the cloud engine, and an identity provider, as depicted in Figure 2. 2 We apply range queries to data types that are of high entropy from a sparse domain to avoid any data leakage due to inference attacks [START_REF] Naveed | Inference Attacks on Property-Preserving Encrypted Databases[END_REF]. Cloud Engine. The cloud engine is application-agnostic and provides the basic database interface and features. It stores data and processes queries from the client engine. The cloud engine has only access to data in encrypted form. It supports the algorithms required for processing encrypted data, i.e., homomorphic addition, re-encryption, and in-situ re-keying. Our design is currently targeted for structural databases (i.e., MySQL) and uses User-Defined Functions to replace the default routines with crypto-enabled ones (see §6 for details).

Identity Provider. The IDP is an independent party responsible for verifying the user identity to public key bindings. The IDP is used by the client engine to search for the public key of another user or group. Pilatus is independent of the IDP and outsources this role to systems such as Keybase [START_REF] Keybase | Publicly Auditable Proofs of Identity[END_REF], that provide provable identity-key bindings, by utilizing prevalent social media channels and online accounts (i.e., users prove their identity by posting an individual token on Twitter, Facebook, Github, etc.).

CRYPTOGRAPHIC BACKGROUND

We present here the necessary cryptographic background to help understand the Pilatus design.

Partial Homomorphic Encryption

Partial Homomorphic Encryption (PHE) schemes allow the computation of certain mathematical operations over encrypted data. For instance, additive homomorphic schemes, such as the Paillier cryptosystem [START_REF] Paillier | Public-key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF], support the addition of ciphertexts, such that the result is equal to the addition of the plaintext values (i.e., ENC (m The Elliptic Curve (EC) version of the ElGamal cryptosystem is an alternative additive homomorphic scheme, used in Talos and Pilatus. EC-ElGamal's security is based on the EC Discrete Logarithm Problem (ECDLP) [START_REF] Smart | Cryptography: an Introduction[END_REF]. It provides semantic security (i.e., IND-CPA under the assumption of decisional Diffie-Hellman). A challenge in making practical use of EC-ElGamal is that it operates over EC points rather than arbitrary messages. Hence, one needs a scheme that maps an integer to an EC point (and back), while preserving the homomorphic property of EC-ElGamal.

1 ) o ENC (m 2 ) = ENC (m 1 + m 2 )).
Talos, which focuses on IoT data, uses a theoretical method [57] that becomes practical for small integer data, e.g., 32-bit (frequent in IoT scenarios, to represent an integer or fixed point number) [START_REF] Shafagh | Talos: Encrypted Query Processing for the Internet of Things[END_REF]. The process is as follows: to map an integer m to an EC point M, m is multiplied by a publicly known point G on the curve: M = mG. After decryption, M must, however, be mapped back to m. This requires solving an ECDLP. Although this is computationally infeasible for large numbers, solving it for smaller than 32-bit integers can be realized in a reasonable time with, e.g., the Baby-Step-Giant-Step (BSGS) algorithm (this is equivalent to breaking 32-bit security). Note that this mapping procedure, as depicted in Figure 3, does not affect the overall security: the ECDLP is solved to obtain m from M, but M itself is protected with strong cryptography, in this case, 80-bit or 128-bit security.

Pilatus inherits this scheme from Talos, but presents additional optimizations to speed up the process by one order of magnitude, as discussed in §5.2.

Re-Encryption

Re-Encryption (RE) enables a proxy to convert ciphertexts under Alice's key to ciphertexts under Bob's key, without disclosing the plaintext. Hence Alice can share data with Bob, without sharing her private key nor performing any encryption for Bob on her personal device.

The AFGH [START_REF] Ateniese | Improved Proxy Re-encryption Schemes with Applications to Secure Distributed Storage[END_REF] RE scheme relies on pairing-based cryptography. AFGH defines next to the standard functions key generation, encryption, and decryption, two additional functions: re-encryption-token generation and re-encryption. The former is used by Alice to generate the re-encryption token for Bob, based on her own private key and Bob's public key. The latter performs the re-encryption from Alice to Bob given the ciphertext is encrypted under Alice's public key.

At a higher abstraction, pairings (or bilinear maps) establish a relationship between two cryptographic groups. In AFGH, reencryption consists in transforming a ciphertext from the first group to the second group. The underlying pairing in AFGH is essentially a bilinear map [START_REF] Boneh | Identity-Based Encryption from the Weil Pairing[END_REF] which, given a cyclic group G of prime order q, has the following property for a, b ∈ Zq and д, h ∈ G: e (д a , h b ) = e (д, h) ab . Such maps can be realized with the Weil and Tate pairings, which are efficiently computable with Miller's algorithm [START_REF] Victor | The Weil pairing, and its efficient calculation[END_REF]. However, designing efficient pairings is an ongoing research topic [START_REF] Aranha | Faster Explicit Formulas for Computing Pairings over Ordinary Curves[END_REF].

C a = (mZ r , д ar ) ( 1
)
where r is a random number. Note that the ciphertext C a is composed of two components, similar to the EC-ElGamal ciphertext.

A proxy with access to Token a→b performs the re-encryption by transforming the second component of C a :

C b = (mZ r , Z br ), with Z br = e (д ar , д b /a ) (2)
Bob can now decrypt the ciphertext C b with his private secret sk b = b and the pairing Z as:

m = mZ r (Z br ) 1/b (3)
In §5.1.2, we show how to employ AFGH in an efficient additive homomorphic context. The cloud serves as the proxy, in charge of re-encrypting data of a user to another user or group.

PILATUS DESIGN

This section presents our EC-based encryption for sharing of PHE data and discusses aspects such as performance optimization, revocation, and authorization.

Processing and Sharing Encrypted Data

We present Pilatus's two modes of operation: Standard Mode and Data Sharing. The former covers the single-key case, while the latter enables cryptographically-protected sharing. Both modes exhibit additive homomorphic properties, as illustrated in Figure 4.

Standard Mode.

When uploading data that is not intended for sharing, the Pilatus client engine selects the standard mode. The standard mode is mostly inherited from Talos and uses EC-Elgamal as an additive homomorphic encryption scheme ( §4.1). However, the decryption in Talos suffers from an exponential increase of computational costs for larger integer values, as shown in Figure 6. In §5.2, we introduce our optimizations to overcome this shortcoming and accelerate decryption and enable the use of integers larger than 32-bit as plaintext. Alice generates a token, from her private key and Bob's public key. The cloud uses the token to re-encrypt Alice's data as Bob's data. Bob can in turn decrypt with his private key. The same mechanism is used for group sharing. Note that re-encryption is non-transitive, i.e., the result can not be re-encrypted again.

5.1.2 Data Sharing. In Pilatus, we construct an efficient additive homomorphic interpretation of AFGH (presented in §4.2). This enables cryptographically-protected (as opposed to policy-based) sharing of PHE data, without the need to disclose any private keys to the cloud. All the cloud needs is a token generated by the owner, from the owner's private key and the target user/group's public key, as illustrated in Figure 5.

To realize the homomorphic additive property, we use the algebraic structure of elliptic curves over finite fields, similar to [START_REF] Wang | A Tale of Two Clouds: Computing on Data Encrypted under Multiple Keys[END_REF]. Note that bilinear-map-based cryptosystems, such as AFGH, leave the selection of the underlying pairing-friendly elliptic curve to implementation. In the recent years, research on optimal paring curves [START_REF] Freeman | A Taxonomy of Pairing-Friendly Elliptic Curves[END_REF] has further progressed. In Pilatus, we rely on the optimal Ate pairing [START_REF] Vercauteren | Optimal Pairings[END_REF] 3 .

To enable the additive homomorphic property, we represent message m as M = Z m , with Z as the pairing. Given the public key pk a = д a of Alice with д as a generator point in G and the random r , we encrypt as:

C a = (Z m Z r , pk r a ) = (Z m+r , д ar ) (4
) and re-encrypt for Bob as:

C b = (Z m+r , Z br ), with Z br = e (д ar , д b /a ) (5)
With access to the private key b, Bob can decrypt as:

M = Z m+r (Z br ) 1/b = Z m+r Z r = Z m (6)
Note that in the final step of decryption, we still need to map back M to m (i.e., solving a discrete log problem), which similar to the standard mode benefits from our performance optimization, presented in the next section.

The homomorphic addition of two ciphertexts C b1 and C b2 (encrypted under Bob's key) is performed as follows:

C b1 + C b2 = (Z m1+r 1 , Z br 1 ) ⊙ (Z m2+r 2 , Z br 2 ) = (Z m1+r 1 Z m2+r 2 , Z br 1 Z br 2 ) = (Z m1+r 1+m2+r 2 , Z br 1+br 2 ) = (Z m1+m2+r 1+r 2 , Z b (r 1+r 2) ) (7)
Because AFGH is key-optimal, Pilatus's storage size for a user remains constant regardless of the number of users/groups it shares

Performance Optimization

At decryption, the EC mapping proposed by Talos (see §4.1) requires solving an ECDLP problem to convert a plaintext EC point to the original plaintext integer. As discussed earlier, using the Baby-Step-Giant-Step (BSGS) algorithm we can solve the ECDLP for small integer values (i.e., ≤32-bit) within a few milliseconds. However, the performance of this algorithm decreases exponentially with larger integers, as depicted in Figure 6 (e.g., already 15 s for decryption of 38-bit integers). This is because with each additional bit the search space is doubled until it becomes too large to efficiently find the solution (i.e., computing the discrete logarithm). This technique has two major shortcomings with regards to our design: (i) batch decryption can harm user experience, exceeding 1 s with as few as 25 decryptions (32-bit values); (ii) with larger numbers, e.g., 64-bit integers, this approach becomes impractical. This demands an optimization that also maintains the homomorphic property of these schemes.

Approach. Our optimization is based on combining the Chinese Remainder Theorem (CRT) [START_REF] Hu | Enhanced Flexibility for Homomorphic Encryption Schemes via CRT[END_REF] with the BSGS algorithm. It is applicable for decryption in both the standard and sharing modes. With CRT, we reduce solving one difficult ECDLP problem (i.e., a large integer) to solving several smaller ECDLP problems, for which the BSGS algorithm performs efficiently, as illustrated in Figure 7. As BSGS exhibits an exponential cost, our approach can provide drastic performance improvements.

CRT is used in many cryptographic constructions [START_REF] Ding | Chinese remainder theorem: applications in computing, coding, cryptography[END_REF][START_REF] Smart | Cryptography: an Introduction[END_REF] and Hu et al. [START_REF] Hu | Enhanced Flexibility for Homomorphic Encryption Schemes via CRT[END_REF] present a formal treatment on how to leverage CRT for homomorphic encryption schemes. We are the first to utilize the general CRT optimization in combination with the BSGS algorithm for an efficient computation of discrete logarithms in a pairingbased re-encryption.

The CRT technique is based on the simple idea of representing a number X uniquely by its remainders a i from the following congruence equations, where n i are co-primes (i.e., gcd Hereby, N which is the product of all co-primes n i (i.e., N = n i ) should be larger than X . With regards to our encryption schemes (i.e., EC-ElGamal and pairing-based re-encryption), X corresponds to the plaintext value which can now be represented with the remainders a i . Since the remainders are significantly smaller than X , the decryption is performed more efficiently. Given the co-primes n i and the remainders a i , X can be efficiently computed, as:

(n i , n j ) = 1, ∀ i, j): X a i mod n i (8)
X = r i=1 a i N i y i (mod N ) (9)
where N i = N /n i and y i = N -1 i mod n i . Note that y i and N i remain unchanged for a given set of co-prime values n i and hence can be pre-computed in advance.

Realization. To utilize CRT to our benefit, we first compute the remainders a 1 and a 2 (assuming two congruences) for a given value X (i.e., as defined in Equation 8). Now instead of encrypting X , we encrypt a 1 and a 2 . Note that the co-prime values n 1 and n 2 are public information.

Utilizing CRT has the side effect of increased encryption cost and ciphertext-size (linearly by the number of congruences). For instance, with 160-bit ECC (80-bit security), the ciphertext-size of EC-ElGamal increases for 32-bit values from 42 bytes (2 compressed EC-points) to 84 bytes (4 compressed EC-points), which is still lower than the ciphertext-size in the Paillier cryptosystem (256 bytes with 80-bit security).

The advantage of CRT becomes apparent while performing decryptions. Instead of solving ECDLP for a large X (which can take seconds to hours for larger values), we now solve it efficiently for the remainders (i.e., a 1 , a 2 ). The larger the plaintext value, the higher the performance gain due to CRT (i.e., several orders of magnitude for large values). For instance, the 15 s decryption time for a 38-bit value is reduced to less than 10 ms for EC-ElGamal (see §7.1.2).

Homomorphism. We discuss here how we keep the additive homomorphic property with our CRT extension. To add two large integers X a and X b , we add their remainders (a i and b i respectively) in the corresponding congruences, as follows:

X a + X b = r i=1 (a i + b i )N i y i (mod N ) (10)
This is possible due to modular arithmetic (X a + X b = a i + b i mod n i ). Since our underlying encryption schemes are additive homomorphic, we can compute the addition of the corresponding encrypted remainders, as follows:

ENC (X 1 ) + ENC (X 2 ) = (ENC (a 1 ), ENC (a 2 )) + (ENC (b 1 ), ENC (b 2 )) = ENC (a 1 + b 1 ), ENC (a 2 + b 2 ) (11)
Hence, EC-ElGamal and our pairing-based re-encryption remain additive homomorphic.

Key Revocation

To authorize data sharing, a data owner issues a cryptographic token, used by the cloud to re-encrypt users data towards the destination user. We address here the challenge of terminating such a data sharing, cryptographically. Key Update. In Pilatus, when users decide to revoke a data sharing, they simply begin using new keys for new data. This renders previously issued tokens obsolete and prevents new ciphertexts cryptographically from being re-encrypted with the old token. Once new keys are in place, valid sharing relationships are updated with new tokens such that the sharing flow can be maintained. We discuss in §5. [START_REF] Ateniese | Improved Proxy Re-encryption Schemes with Applications to Secure Distributed Storage[END_REF] in more details how the data sharing authorization works with regards to joining and leaving groups. Note that a key revocation event can as well occur, when the encryption key of the user is compromised.

We consider two cases for the key update: malicious cloud and semi-honest cloud. In the former case, we leave old data protected with old keys. We consider such old data to be in the wild, since already shared and possibly cached at sharing parties. However, in the latter case, it is desirable to update the encryption keys of the old data to the latest keys, for consistent access. Hence, it is important to devise a secure solution that allows the semi-honest cloud to perform the re-keying without access to any private key.

In Situ Re-keying. To construct our re-keying mechanism, we leverage the fact that user Alice has access to both old and new private keys (a and a ′ , respectively), neither of which is disclosed to any party 4 . Hence, at the time of re-keying, the private keys of Alice are not compromised.

(ID initiator @group, Pk initiator ) signed-by-IDP (ID user-1 @group, Pk user-1 ) signed-by-initiator (ID user-2 @group, Pk user-2 ) signed-by-initiator (ID user-3 @group, Pk user_3 ) signed-by-user-1 (ID user_4 @group, Pk user_4 ) signed-by-user-1

…

Figure 9: Access graph for group membership.

The re-keying (see Figure 8) is carried out on data, at the cloud, prior to sharing (i.e., ciphertexts in level-1, as represented in Equation 4). To this end, Alice issues a key-update token δ = a ′ /a and the cloud performs the re-keying as follows (only the second component of the ciphertext is adjusted):

C a ′ = (C 1 , δC 2 ) = (C 1 , ra ′ G) (12)
After re-keying, all ciphertexts on the cloud are encrypted with the latest key a ′ . Note that re-keying, unlike re-encryption, is transitive, i.e., the re-keying can be applied multiple times to the same item. The scheme would, however, be poorly suited for sharing, as it requires both the source and target private keys.

Note that since both old and new keys are only known to Alice, a curious cloud cannot learn anything about the private keys from δ . However, a malicious cloud could use the reverse of the keyupdate token (i.e., a/a ′ ) and downgrade ciphertexts encrypted under newest keys to old keys. This is why we only enable re-keying in case a semi-honest cloud or a trusted proxy is present.

Group Sharing Authorization

Data in Pilatus can be shared either directly with a user or a group. We describe a simple sharing authorization mechanism for grouprelated operations. The construction of the authorization is crucial as it ensures that a joining group member (i) issues the reencryption token for the authentic group; and (ii) retrieves the correct group key. These two aspects are related, since the correct group key is necessary for the process of generating the reencryption token.

Access Graphs. In our construction, we leverage access graphs, which are similar to certification paths in the public key infrastructure, in combination with our re-encryption scheme. We form an access graph for each group. The root node holds the initiator's ID concatenated with the group identity (e.g., "runners") and the public key of the initiator, as depicted in Figure 9. The joining members of the group compose the access graph nodes. Each node, except for the root, is signed by the immediate parent node. The root is signed by the IDP. The access graph allows group members to vouch for the membership of other members.

Joining. Group membership is authorized by a group member in two steps: (i) signing the extended identity (i.e., ID@group name) and the public key of the new member, e.g., Alice, (after verifying the key correctness over the IDP); and (ii) issuing a re-encryption Token д→a which is then stored in the cloud. After joining the group, Alice provides the re-encryption Token a→д , required for sharing with the group. To issue this re-encryption token and later be able to access (i.e., decrypt) group data, Alice needs the public (PK д ) and private (SK д ) keys of the target group. This information is stored signed and partly encrypted on the cloud:

(ID д , PK д , ENC д (SK д )) siдned -by-init iator
Note that the initiator's signature on the key information prevents a malicious entity in deceiving Alice into issuing a token for a fake group with the same name. Currently, group members are authorized to add new members. We can restrict this authority to the initiator only by encrypting the group's private key with the initiator's key. A new member would require the initiator's authorization which is expressed in the Token init iator →a to access the group key.

Leaving. To leave a group, Alice initiates our revocation procedure (c.f. §5.3). After revocation, new coming data is encrypted with new keys and can no longer be transformed with the expired Token a→д . Her previous data, however, remains in the wild and can still be accessed by the group members, unless Alice decides to trigger our in-situ re-keying feature. Note that disclosure of the group's secret key SK д and Alice's Token a→д does not expose Alice's private key.

Security Analysis

Our main security goals are to defy passive attacks targeted at data on the cloud as well as to prevent access of unauthorized users (see §2). Pilatus achieves these goals such that data on the cloud remains strongly encrypted (i.e., semantic security) at all times. The cloud never gains access to any decryption keys. We rely on the IDP to prevent fake user creations.

To protect the data from unauthorized access, we cryptographically restrict data access to users with decryption keys (i.e., either individual or group keys). With the re-encryption token, the cloud can only re-encrypt the stored data towards the authorized group/service. Moreover, we prevent a malicious cloud from performing unauthorized re-encryptions towards a malicious user (thanks to the one-hop property of the re-encryption scheme).

The disclosure of group keys does not affect the security of the corresponding private keys of the group members. This is because our underlying re-encryption scheme is key-private. After such an incident, members can perform a revocation to terminate the data transformation into group data.

Our in situ key-update technique assumes a semi-honest cloud. In other cases, re-keying can either be disabled or delegated to a trusted proxy.

Mode

IMPLEMENTATION

We implemented a prototype of Pilatus for mobile platforms (user/client devices) and the cloud (structured data storage). The client engine (Android) consists of a REST client for interactions with the cloud. Application developers can use the Pilatus API which internally calls their previously defined SQL procedures. The client engine handles data encryption before performing requests and decryption after retrieving the data from an API call.

For the EC-ElGamal encryption, we utilize the ECC module of the OpenSSL library (v1.1.0). We implemented the data sharing components (i.e., re-encryption) based on the RELIC toolkit [START_REF] Aranha | RELIC is an Efficient LIbrary for Cryptography[END_REF][START_REF] Aranha | Faster Explicit Formulas for Computing Pairings over Ordinary Curves[END_REF]. We support 80-bit and 128-bit security levels. Our BSGS algorithm implementation relies on hash-map (i.e., klib library) for the look-up table.

The cloud engine supports a MySQL database, for which we implemented the corresponding User Defined Functions (UDF). We use UDFs to replace the default routines with crypto-enabled ones, without the need of recompiling the database. Incoming queries indicate the UDF to be used, e.g., SELECT SUM_EC_ELGAMAL(column-x) FROM table-y, where the standard SUM is replaced with the dedicated homomorphic addition sum for EC-ElGamal. Moreover, the cloud engine is equipped with a REST engine (i.e., Restlet library).

The implementation of Pilatus consists of 2000 sloc of C/C++, 10000 sloc of Java, and another 4000 sloc for testing, setup scripts, and benchmarking. Our prototype Android applications Fitbit and Ava consist of 2400 and 2500 sloc, respectively.

Example Applications. To show the feasibility of Pilatus and evaluate its end-to-end performance, we developed two example mobile applications that integrate Pilatus, where the cloud components are hosted on Amazon's cloud services. Our Android activity tracking app operates on data collected by our personal Fitbit device. It fetches the data from Fitbit servers and stores it encrypted in our cloud instance. For our Ava fertility tracking app, we received anonymized data from the Avawomen startup [START_REF]Fertility Tracking Bracelet[END_REF]. In both apps, the users can interact with the data similar to the original apps. Our applications do not cache any data locally which allows us to study the worst-case performance while interacting with remote data. The cloud and the client communicate over HTTPS and data is encoded in JSON format, as a compact data representation form. For authentication, we rely on the OpenID Connect [35], where we currently support Google accounts [START_REF]Google Sign-In[END_REF] as a proof-of-concept.

Constrained IoT Devices. We implemented a prototype of Pilatus for more constrained IoT devices, where the client-engine only accommodates the encryption logic in the standard mode. We based our implementation on Contiki [START_REF] Dunkels | Contiki -a Lightweight and Flexible Operating System for Tiny Networked Sensors[END_REF], an open-source low-power operating system for IoT devices. For cryptographic processing, we utilize both software libraries (i.e., RELIC toolkit [START_REF] Aranha | RELIC is an Efficient LIbrary for Cryptography[END_REF]) and the hardware crypto accelerator.

EVALUATION

This section presents a thorough evaluation of Pilatus, both on the cloud and on client sides (mobile device and, to a lesser extent, constrained IoT device).

Evaluation Setup. Our evaluation setup consists of the client engine running on a smartphone and the cloud engine running at Amazon cloud services (AWS). We use an LG Nexus 5, equipped with a 2.3 GHz quad-core 64-bit processor and 2 GB RAM, running Android 5.1.1. Our AWS account provides 25 GB of storage and one instance of Intel Xeon 3.3 GHz CPUs with 1 GB RAM. For micro-benchmarks of homomorphic addition, we additionally use a MacBook Pro equipped with 2.2 GHz Intel Core i7 and 8 GB of RAM.

For the client engine, we also present results on constrained IoT devices with our Contiki implementation. We select OpenMotes as the hardware platform, which utilize the same class of MCU as activity trackers such as Fitbit. OpenMotes are based on the TI CC2538 microcontroller [START_REF]CC2538 System-on-Chip for 2[END_REF], i.e., 32-bit ARM Cortex-M3 at 32 MHz, with a public-key crypto accelerator running up to 250 MHz. They are equipped with 802.15.4-compliant RF transceivers, 32 kB of RAM and 512 kB of ROM.

Metrics. We rely on the following metrics to report on the overheads and performance of Pilatus:

• Computation time indicates the CPU time required to perform a certain operation. The computation time has a direct impact on the application delay and energy consumption of mobile platforms. • Ciphertext size is an important metric considering network bandwidth. It measures the impact of Pilatus on the communication requirements. • System throughput is the rate of operations on encrypted data performed in the cloud. • Application latency reflects the time from a client initiating a query to the client receiving and decrypting the results. It accounts for query processing at the client side, plus network latency and cloud processing time. In the next sections, we continue with discussing the results of the system components benchmark and then elaborate on the end-to-end evaluation results. Table 2 summarizes the evaluation results.

Micro-Benchmark

In this section, we discuss the performance of our crypto primitives.

Methodology. We instrument our client engine app to run the operations in isolation. We generate plaintext inputs uniformly at random for three input sizes: 16, 32, and 64-bit integers. We repeat each experiment at least 1000 times, except for expensive key generation operations which are repeated 100 times. For the time measurements, we rely on the Google Guava Stopwatch class 5 with nanoseconds accuracy. We only enable multi-threading support of Android for batch decryptions. All other reported numbers are measured while running on a single thread.

We first assess CRT in detail and then proceed to evaluating the standard and data sharing modes on mobile devices. 7.1.1 CRT Optimization. With our CRT optimization (see §5.2), we represent a larger value through its smaller remainders (i.e., congruences). We discuss here the tradeoff between decryption performance and ciphertext size due to CRT.

Typical integer values are either 16, 32, or 64-bit. Note that for selecting the size of congruences, the sum of congruence sizes must be larger than the integer value to be represented. [START_REF] Ding | Chinese remainder theorem: applications in computing, coding, cryptography[END_REF]-bit values can be calculated efficiently without CRT (Figure 6). For 32-bit values, we can either select two 17-bit or three 11-bit congruences. For 64bit values, we can also use three 22-bit or four 17-bit congruences.

Table 3 shows the decryption time as a function of the number of congruences, compared to the state-of-the-art Talos, which does not use the CRT optimization. In the 32-bit case, we can improve the 42 ms from Talos to 2 ms. In the 64-bit case, decryption is plain infeasible in Talos, but becomes feasible to less than 10 ms with 5 Guava: Google Core Lib for Java: https://github.com/google/guava CRT. The price to pay for more congruences is increased encryption time (by few milliseconds) and ciphertext size (e.g., 126 bytes for three congruences). Note that the performance gains of CRT plateau and a higher number of congruencies do not yield further gains (Table 3). Considering all these parameters, we select (for both standard and sharing modes) two and three congruences for 32resp. 64-bit values, as a tradeoff between ciphertext expansion and encryption/decryption times.

Memory. Pilatus requires two separate look-up tables (hash tables) for standard mode and data sharing, as we use two different underlying elliptic curves. The former accounts for 67 Mbyte and the latter for 69 Mbyte, with 80-bit security. The tables are shared among all applications served by Pilatus which amortizes the memory requirements among them.

Standard Mode.

In the standard mode, we utilize EC-ElGamal to process data encrypted under a single key (no data sharing). While the focus of our benchmark is on EC-ElGamal's performance, we also compare it to the more conventional Paillier cryptosystem, used for instance in CryptDB [START_REF] Raluca | CryptDB: Protecting Confidentiality with Encrypted Query Processing[END_REF]. Key Generation. Table 1 shows the average setup time on the Nexus 5 device. EC-ElGamal requires less than 0.3 ms to generate keying material with 80-bit security. This is significantly lower than the 1623 ms required for Paillier, even though our key generation additionally includes finding the corresponding primes for the congruences in the CRT. Anyhow, key generation does not frequently occur, compared to encryption and decryption, detailed next.

Ciphertext Size. Figure 10(a) shows the ciphertext sizes for different integer sizes and security levels. In the standard mode, we support 16, 32 and 64-bit integers. Each integer size requires a different number of congruences, leading to a ciphertext size between 42 and 126 bytes in the 80-bit security case. In contrast, Paillier requires 256 bytes, regardless of the integer size. The difference is even more pronounced as the security level increases, negatively impacting network bandwidth and cloud storage. [START_REF] Shafagh | Talos: Encrypted Query Processing for the Internet of Things[END_REF] is reduced here to 42 ms with multithreading.

Encryption/Decryption.
Paillier has constant computation times due to its large padding, while EC-ElGamal sees its performance increase for smaller plaintext. EC-ElGamal outperforms Paillier for encryption with a factor of 3 and more. For decryption, EC-ElGamal is the fastest in all settings but the case of 80-bit security and 64-bit integers. Paillier's sharp decrease in performance with 128-bit security is due to larger key sizes (from 1024 to 3072-bit) and the resulting big number operations. Figure 10(c) shows the batch decryption time at the mobile device. Even for 64-bit integers, hundreds of items can be decrypted in some hundred milliseconds. This is an important factor for the responsiveness of smartphone applications.

Note that the good performance of EC-ElGamal lies to a large part in our CRT optimization, as discussed in §7.1.1. Moreover, the benefits of an efficient encryption are particularly important in an IoT context, since IoT applications tend to encrypt more data items than they decrypt (all measurements are stored in the cloud, only a subset or aggregates are downloaded for display).

Homomorphic Addition. We measure the homomorphic addition in isolation on a MacBook Pro, thus exclude the bootstrapping overhead of the database's UDF. The homomorphic addition in the standard mode requires between 27 and 82 µs for 16 and 64-bit integers, respectively (see Table 2). This is higher than Paillier (8 µs), which is mainly due to the underlying structure of EC-ElGamal where the ciphertext consists of two EC points. Note that parallelizing the homomorphic addition on the cloud would potentially result in considerable performance gain. In §7.2, we discuss the impact of this overhead on sum queries. 7.1.3 Data Sharing Mode. We evaluate the data sharing mode, where the client encrypts data and issues a token such that the cloud can re-encrypt a ciphertext to the target user or group. The key setup is with 4 ms similarly efficient to EC-ElGamal (see Table 1).

Ciphertext Size. Note that we use the same number of congruences as in standard mode. Since our re-encryption scheme is based on bilinear maps, we have to select the parameters such that we achieve at least 80-bit (i.e., subgroup size 160 and extension field size 1024) or 128-bit security. This results in larger ciphertext sizes compared to standard mode (i.e., between 186 and 558 bytes as depicted in Figure 11(a)). This is four times larger than in standard mode, but still comparable with Paillier. After sharing (i.e., re-encryption) the ciphertext sizes expand by a factor of 1.7 due to pairing.

Encryption/Decryption. Figure 11(b) shows the performance of encryption and decryption in the sharing mode, for different integer sizes and security levels. Overall, the sharing mode is slower than standard mode by a factor of 2.2 to 3.3, but remains within acceptable bounds, that is, below 30 ms.

Note that this overhead is, to some extent, offset by the performance gains of offloading the re-encryption operation to the cloud. To enable sharing, the client only needs to generate a token (takes 2.5 ms) and then encrypt the data in sharing mode. As depicted in Figure 11(c), a client can issue a few hundred re-encryption tokens within 500 ms. Issuing a large number of re-encryption tokens becomes relevant after access revocation, as discussed in §5.4. The performance of re-encryption at the cloud is evaluated in §7.2.

Homomorphic Addition. The homomorphic addition with the data sharing mode is more efficient than the standard mode. Note that with data sharing, we have two types of additions: prior share and post share, which amount to 31 and 15 µs per CRT, respectively (see Table 2).

7.1.4 Constrained IoT Devices. We now turn our attention to constrained IoT devices and evaluate encryption performance with the OpenMote's hardware accelerator. For the time and energy measurements, we rely on a dedicated hardware timer with an accuracy of 1 µs and a mixed signal oscilloscope, respectively. Paillier in 80-bit security requires 1.8 s to encrypt a 16-bit value. The same encryption with EC-ElGamal is significantly more efficient with 126 ms (corresponds to 6.85 mJ). Table 2 compares the results of constrained devices to smartphones. Although the encryption time on constrained devices is more than one order of magnitude higher than encryption on the more powerful IoT gateways, it is still feasible with only 10% of the daily energy budget of a typical Fitbit (400 mAh lithium-polymer battery) to encrypt at a rate of 0.24 Hz. To put this number into context, assuming heart rate tracking at 1 Hz during sport and six times per hour otherwise 6 , we can encrypt the heart-rate of a person with 6 hours of sports activity per day.

System Benchmark

This section evaluates Pilatus as a full system: processing throughput, end-to-end latency, and our two case study applications: Fitbit and Ava. Methodology. We utilize our client and cloud engines for the system benchmark. The client engine has an average ping time to the Amazon cloud of 22 ms, or it can be co-located at the cloud, neglecting network latency in favor of more isolated throughput measurements. Similar to micro-benchmarks, we rely on the Stopwatch class for the time measurements, instrumented at the client engine. To compute the system's throughput at the cloud engine, we initiate SQL sum queries over a varying number of values from our client module. For the end-to-end evaluation, the ciphertexts are additionally decrypted and provided to the corresponding application.

Encrypted Query Processing. Figure 12(a) and Figure 12(b) depict the performance of the cloud engine on AWS when performing sum SQL queries, over either plaintext or encrypted data. We create queries with variable lengths (i.e., summands) and measure the time to process each, and compute the average system throughput of the cloud engine for a single connection. In Figure 12(a), we initiate the requests locally from the cloud (no network latency) and in Figure 12(b) from the client engine over the Internet. Without consideration of network communication, plaintext sum operations are about two orders of magnitude faster than the homomorphically encrypted sums. With network communication, the relative performance loss is lower, in particular when only a few items are added and network delay is the bottleneck. However, the larger the number of items, the more the overhead of homomorphic additions impacts the performance, e.g., with 1000 values to be added, the performance loss reaches a factor 2.7. Note that such queries are highly parallelizable, allowing for better performance; plaintext operations already benefit from parallelization. Our current evaluation results show the lower bound performance and in future work, we plan to parallelize our routines at the database.

For data sharing, the computations take place offline in the cloud, without user interaction. The throughput of re-encryptions per data item amounts to 1136 re-encryptions per second, with a single thread (see Figure 12(a)). Note that re-encryption is the most expensive operation as it involves expensive pairing. The re-encryptions should also be parallelized in the cloud to reach the best performance. End-to-end Latency. Figure 12(c) depicts the end-to-end latency for varying sum queries. The latency values follow a similar trend as the throughput values, as depicted in Figure 12(b). For lower range sum queries, the average performance of data sharing and standard mode are close to queries over plaintext. For larger ranges, the average latency increases by a factor of 2 and 2.7, respectively.

App

To guarantee a smooth user interaction with encrypted data, the latency should be below 1 s, which is the case even for larger ranges (i.e., below 50 ms for 1000 items).

Applications. Our two Android applicationsrun Pilatus on realworld collected data and allow the user to upload encrypted data and interact with them similarly to the original apps (see Table 4).

Our FitBit app adds an overhead of 1.3 s for uploading data of one day -an operation that takes place in the background. While rendering different views of the app (e.g., daily, weekly, detailed graphs), we measure a maximum overhead of 32 ms due to decryptions. Note that we use no local caching to emulate worst case scenarios. Our Ava fertility tracking app collects data from a more diverse set of sensors at a higher granularity during sleep and hence produces more data points. Additionally, we discuss the numbers in the context of the more expensive data sharing mode. Our Ava app induces an overhead of 31 s for uploading one day worth of data.

For rendering different views after sharing, the maximum overhead is 127 ms. For both apps, the overhead due to decryption is well below the 1 s requirement. Hence, the user experience with Pilatus remains unaltered.

Conclusion.

Our evaluation shows the practicability of Pilatus, especially for mobile platforms which play a vital role in the IoT ecosystem (i.e., as the gateways). The end-to-end latency results show that Pilatus succeeds in preserving the user experience while interacting with encrypted data. Pilatus induces a moderate overhead for an increased level of data privacy and security.

RELATED WORK

In the following, we discuss important research directions in relation to Pilatus.

Encrypted Search. Recent advancements of fully homomorphic encryption [START_REF] Gentry | Fully Homomorphic Encryption Using Ideal Lattices[END_REF] have resulted into implementable schemes [START_REF] Brakerski | Leveled) Fully Homomorphic Encryption Without Bootstrapping[END_REF][START_REF] Gentry | Implementing Gentry's Fully-Homomorphic Encryption Scheme[END_REF][START_REF] Shafagh | Toward Computing Over Encrypted Data in IoT Systems[END_REF], which are however presently too slow for real world applications. Searchable encryption schemes support only a limited set of operations, but can be efficiently used in specialized domains. Song et al. [START_REF] Song | Practical Techniques for Searches on Encrypted Data[END_REF] introduced the first encrypted search scheme for text files, where the metadata is encrypted deterministically and hence searchable. Their idea is based on deterministically encrypting the meta information of files, and hence being able to search over them. Follow-up schemes address other problems such as encrypted data de-duplication [START_REF] Keelveedhi | DupLESS: Server-Aided Encryption for Deduplicated Storage[END_REF], deep packet inspection [START_REF] Sherry | Blind-Box: Deep Packet Inspection over Encrypted Traffic[END_REF], and private network function virtualization [START_REF] Jameel Asghar | SplitBox: Toward Efficient Private Network Function Virtualization[END_REF]. More capable search schemes [START_REF] Boneh | Private Database Queries Using Somewhat Homomorphic Encryption[END_REF][START_REF] Raluca | CryptDB: Protecting Confidentiality with Encrypted Query Processing[END_REF][START_REF] Sanamrad | Randomly Partitioned Encryption for Cloud Databases[END_REF][START_REF] Shafagh | Toward Computing Over Encrypted Data in IoT Systems[END_REF][START_REF] Shafagh | Talos: Encrypted Query Processing for the Internet of Things[END_REF][START_REF] Shi | Multi-Dimensional Range Query over Encrypted Data[END_REF], targeted for structured databases, employ additional techniques such as partially homomorphic and order-preserving encryptions. Among these, CryptDB has early adopters in industry [START_REF]Encrypted Bigquery Client[END_REF][START_REF]Always Encrypted (Database Engine)[END_REF]. Monomi [START_REF] Tu | Processing Analytical Queries Over Encrypted Data[END_REF] improves the performance of CryptDB and extends supported queries. In CryptDB, the application server has access to keys and carries out en-/decryptions. Hence, it can leak information if compromised. Talos [START_REF] Shafagh | Demo Abstract: Talos a Platform for Processing Encrypted IoT Data[END_REF][START_REF] Shafagh | Talos: Encrypted Query Processing for the Internet of Things[END_REF] tailors CryptDB for IoT devices and eliminates the need to trust the application server. Mylar [START_REF] Raluca | Building Web Applications on Top of Encrypted Data Using Mylar[END_REF] introduces encrypted text file search with multiple keys. Shi et al. [START_REF] Shi | Privacy-preserving Aggregation of Time-series Data[END_REF] propose private aggregation for time series data, which blends secret sharing with homomorphic encryption. Access patterns to encrypted data still leak sensitive information about the plaintext data. This shortcoming can be addressed with Oblivious RAM approaches [START_REF] Ren | Constants Count: Practical Improvements to Oblivious RAM[END_REF][START_REF] Stefanov | Path ORAM: an extremely simple oblivious RAM protocol[END_REF]. Pilatus is the first practical system to support processing of multi-key encrypted data and is tailored for constrained devices. This opens practical encrypted data processing to a new space of applications that existing systems do not support.

MPC.

In traditional Secure Multi-Party Computation (MPC) [START_REF] Andrew | Protocols for Secure Computations[END_REF], private functions are computed among a set of users without a trusted party. Hereby individual values from participating users are kept confidential, while the outcome can be public. This requires high interaction between users, which would drain the limited resources of mobile platforms. With the rise of cloud computing, server-aided/outsourced MPC approaches have emerged. However, these schemes are either only of theoretical interest [START_REF] López-Alt | On-thefly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption[END_REF] or require at least two non-colluding servers, where for instance one server has only access to encrypted data and the other server has access to the keys [START_REF] Nikolaenko | Privacy-Preserving Ridge Regression on Hundreds of Millions of Records[END_REF][START_REF] Peter | Efficiently Outsourcing Multiparty Computation under Multiple Keys[END_REF].

Trusted Computing. An orthogonal approach to encrypted computing assumes a trusted computing module on an untrusted cloud environment [START_REF] Bajaj | TrustedDB: A Trusted Hardware-Based Database with Privacy and Data Confidentiality[END_REF][START_REF] Baumann | Shielding Applications from an Untrusted Cloud with Haven[END_REF][START_REF] Mccune | TrustVisor: Efficient TCB Reduction and Attestation[END_REF]. The data remains encrypted at rest and is decrypted in the trusted module for computations. This approach is appealing to data center operators, due to control over hardware. However, it implies that users consider the trusted computing module trustworthy. Autocrypt [START_REF] Tople | AU-TOCRYPT: Enabling Homomorphic Computation on Servers to Protect Sensitive Web Content[END_REF] combines PHE and trusted computing to enable encrypted computing on sensitive Web data on virtual machines.

Re-Encryption. The idea of Re-Encryption (RE) has been initially proposed for email forwarding. The initial schemes [START_REF] Blaze | Divertible Protocols and Atomic Proxy Cryptography[END_REF][START_REF] Ivan | Proxy Cryptography Revisited[END_REF] have the bi-directional property and are not resistant against collusion. Moreover, the parties need to exchange their private keys. The later schemes [START_REF] Ateniese | Improved Proxy Re-encryption Schemes with Applications to Secure Distributed Storage[END_REF][START_REF] Green | Identity-Based Proxy Reencryption[END_REF] address these weaknesses and are uni-directional and non-interactive. Pilatus utilizes the RE scheme by Ateniese et al. [START_REF] Ateniese | Improved Proxy Re-encryption Schemes with Applications to Secure Distributed Storage[END_REF] to allow transformation of encrypted data for data sharing. More importantly, we extend this scheme with the CRT technique, to render it efficient. The symmetric-key RE based on the keyhomomorphic PRF scheme [START_REF] Boneh | Key Homomorphic PRFs and Their Applications[END_REF] lacks our required homomorphic property and master-secret secrecy. Sieve [START_REF] Wang | Sieve: Cryptographically Enforced Access Control for User Data in Untrusted Clouds[END_REF] utilizes this keyhomomorphic scheme to provide cryptographically enforced access control for cloud data. Sieve's key revocation assumes that the cloud does not yield access to compromised shared keys. Otherwise, the new key will be automatically compromised as the cloud can use the old key to compute the new key from the re-keying delta. In Pilatus, even with access to the revoked key of Bob and re-keying delta, the cloud cannot learn the new key of Alice.

CONCLUSION

We presented Pilatus, a new practical system tailored for the IoT ecosystem. We empower the user with full control over their data, despite it being stored in third-party clouds. In Pilatus, the cloud does not have access to any secret keys and stores only encrypted data. It can though process queries on encrypted data and re-encrypt it for sharing. Our sharing scheme comes with cryptographic guarantees and the possibility of revocation. We have optimized the underlying cryptographic operations towards mobile platforms.

Our implementation and case studies on Fitbit and Ava show that Pilatus has reasonable overhead in processing time and end-to-end latency. We anticipate the presented cryptosystem and open-source platform to be helpful for the design of secure mobile applications and to enable further research in this field.

1 Figure 1 :

 11 Figure 1: Pilatus can both query and share encrypted data.The cloud has access to no keys nor any plaintext. It is able to process encrypted data (e.g., range, sum queries), as well as to re-encrypt it, enabling crypto-protected sharing. We also address revocation, in situ re-keying, and group sharing.

Figure 2 :

 2 Figure 2: Pilatus architecture. The client engine performs en-/decryptions, such that the cloud only stores encrypted data. The cloud engine performs encrypted query processing and necessary re-encryptions for data sharing.

Figure 3 :

 3 Figure 3: Plaintext to EC point mapping before encryption and after decryption.

Figure 4 :

 4 Figure 4: Encrypted query processing. The data is encrypted with Alice's public key. Computations take place in the cloud, on ciphertexts. The result is decrypted with Alice's private key.

Figure 5 :

 5 Figure 5: Data sharing (re-encryption).Alice generates a token, from her private key and Bob's public key. The cloud uses the token to re-encrypt Alice's data as Bob's data. Bob can in turn decrypt with his private key. The same mechanism is used for group sharing. Note that re-encryption is non-transitive, i.e., the result can not be re-encrypted again.

Figure 6 :

 6 Figure 6: Decryption in EC-ElGamal with the Baby-Step-Giant-Step algorithm, 80-bit security and 4 threads on Nexus 5. Smaller plaintexts (23-bit) are decrypted efficiently (<3 ms), larger plaintexts cause an exponential slowdown.

Figure 7 :

 7 Figure 7: We optimize the decryption in both standard and sharing modes, with a technique based on the Chinese Remainder Theorem (CRT) where a larger value is represented by several smaller ones.

Figure 8 :

 8 Figure8: Data revocation (in situ re-keying). Alice builds a token from both her old and new private keys (none of which is leaked). The cloud uses the token to re-key Alice's data, such that they can now be decrypted with the new key. Alice can re-key multiple times and apply re-encryption to re-keyed data.

  Paillier vs. our optimized EC-ElGamal with 80-bit and 128-bit security levels. Batch decryptions of varying size with 80-bit security and 4x threads on Nexus 5.

Figure 10 :

 10 Figure 10: On-device Standard Mode evaluation. Compares Paillier (utilized in CryptDB) with our optimized EC-ElGamal. With the CRT technique, our standard mode can differentiate between different input lengths.

  Figure 10(b) shows the encryption and decryption time with EC-ElGamal vs. Pailler, for different integer sizes, with both 80-bit and 128-bit security.

  Batch token generation (for re-encryption) with 80-bit security and 4x threads.

Figure 11 :

 11 Figure11: On-device Data Sharing evaluation. The Client engine performs encryptions and decryptions of data. After revocation, new re-encryption tokens are issued for valid sharing relationships. Note batch encryption/decryption with multithreading (e.g., 4 threads) yields a factor of 3 performance improvement, e.g., decryption of 64-bit integers is reduced to 5.5 and 10 ms, for 80-bit and 128-bit security, respectively.

  Operations in the cloud, initiated locally at the cloud. Operations in the cloud, initiated by the client over the network (22 ms ping). End-to-end latency including decryption.

Figure 12 :

 12 Figure 12: Cloud evaluation of Standard Mode and Data Sharing, with our cloud engine running on Amazon, with 80-bit security. Pre-and post-sharing sum refer to sum queries before and after sharing.

Table 1 :

 1 Average setup time on Nexus 5 for 80-bit and 128-bit security levels.

	Cryptosystem	Setup time [ms]
		80-bit sec. 128-bit sec.
	Paillier	1623	42190
	Standard	0.28	0.61
	Sharing: Key setup	4.15	6.72
	Sharing: Token gen.	2.5	4.7

Table 3 :

 3 CRT optimization. Performance of Pilatus (EC-ElGamal with CRT) on Nexus 5 with 80-bit security, compared to Talos (i.e., no CRT). *The reported 190 ms in Talos

		Encryption time [ms]		Decryption time [ms]		Ciphertext size [bytes]
	Integer size [bits] Talos	Pilatus, #congruences	Talos	Pilatus, #congruences Talos	Pilatus, #congruences
			2	3	4	5		2	3	4	5		2	3	4	5
	32 64	1.1 1.2	2.4 3.3 4.4 5.4 2.5 3.5 4.7 5.7 infeasible 139 6.4 4.2 5.0 42* 2.0 2.9 4.0 5.0	42	84 126 164 210

Table 4 :

 4 Fitbit and Ava enhanced with Pilatus. Encryption overhead when uploading one day worth of data and decryption overhead at visualization for the most costly view. Security is set to 80-bit, all data items are 32-bit values, and multithreading enabled.

	(mode)	Upload (encrypt) View (decrypt)
		[s]	[# items]	[ms] [# items]
	Fitbit (Standard) 1.3	1500	30	50
	Ava (Sharing)	31	9000	127	50

Pilatus is available at https://github.com/Talos-crypto/Pilatus

The optimal Ate pairing is over Barreto-Naehrigopera curves[START_REF] Aranha | Faster Explicit Formulas for Computing Pairings over Ordinary Curves[END_REF][START_REF] Barreto | Pairing-Friendly Elliptic Curves of Prime Order[END_REF], which are pairingfriendly elliptic curves of prime order, with embedding degree 12.

Note that in contrast to key homomorphic PRFs (i.e., Pseudo Random Functions)[START_REF] Wang | Sieve: Cryptographically Enforced Access Control for User Data in Untrusted Clouds[END_REF], where a symmetric key is shared between parties, our re-keying scheme is key-private.

Microsoft Band:http://www.windowscentral.com/ how-often-microsoft-band-checks-your-heart-rate

ACKNOWLEDGMENTS

The authors would like to express their gratitude to David Wu, Philip Levis, and Srdjan Capkun for the insightful discussions during the design phase of Pilatus. We thank Friedemann Mattern and Alexander Viand for their comments on earlier versions of this paper. Moreover, we are thankful to the anonymous reviewers and our shepherd, Xiuzhen Cheng, for their valuable feedback. This work was partly supported by a grant from CPER Nord-Pas-de-Calais/FEDER DATA and VINNOVA, Sweden's innovation agency.


Leonhard Mayrhofer

Milena Grifoni

The low energy spectrum of finite size metallic SWNTs

Keywords: numbers: 73.63.Fg, 71.10.Pm, 71.70.Gm, 73.23.Hk

The electronic spectrum of metallic finite-size single-wall carbon nanotubes at low energies is derived. It is based on a tight-binding description for the interacting pz electrons. Not only the forward scattering parts of the Coulomb interaction, which are diagonalized by bosonization, are considered, but also all other processes becoming relevant for small diameter tubes. As a consequence of the substructure of the underlying lattice, a spin 1 triplet is found as ground state if the exchange splitting is larger than the branch mismatch, a spin 0 singlet otherwise. Moreover the excitation spectrum is calculated.

Single-walled carbon nanotubes (SWNTs) are one of the most prominent examples for the realization of 1D electronic systems with orbital degeneracy in nature. A proper description of the low energy regime has to take into account the Coulomb interaction between the electrons and the corresponding correlation effects. Luttinger Liquid behaviour, leading to power-law dependence of various transport quantities, has been predicted theoretically for metallic SWNTs of infinite length [1,2] and was confirmed experimentally [3,4]. Considering tubes of finite length, Kane et al. [5] have derived the discrete energy spectrum of the collective spin and charge excitations and its dependence on the forward scattering part of the Coulomb interaction. Moreover, for SWNTs a charging energy of the order of the level spacing is found, leading to the observation of Coulomb blockade in SWNT quantum dot devices [6,7,8,9,10]. The accompanying two-or fourfold periodicity of the Coulomb diamond size can be understood by including the spin and band degrees of freedom. A theory of transport through SWNT quantum dots incorporating the mentioned forward scattering interaction processes was worked out in [11]. As discussed below, the restriction to forward scattering terms is justified for large diameter tubes only, whereas the remaining interaction processes become more and more important for decreasing tube diameters. They lead to exchange effects and a modification of the excitation spectrum. Within a meanfield approach Oreg et al. [12] predicted exchange effects favouring spin alignment. The size of the exchange splitting on the SWNT ground states was measured by recent experiments [8,9,10].

A fundamental question regards the nature of the ground state and excited spectrum of correlated 1D systems. In a milestone theorem Lieb and Mattis [13] demonstrated that for a 1D Hubbard model with nearest neighbour hopping, the ground state must have spin 0 or 1/2. They left open the question for systems with orbital degeneracy. This is the case for SWNTs due to the substructure of the underlying honeycomb lattice.

In this work we go beyond the mean field approach and derive the electronic structure of metallic SWNTs in the low energy regime from a microscopic model. Beside the long ranged forward scattering terms of the Coulomb interaction, which are exactly diagonalized by bosonization, we take into account all other processes becoming relevant for small diameter SWNTs away from halffilling. Because of scattering processes involving the orbital degree of freedom, we predict a spin 1 triplet as ground state, if the exchange energy exceeds the energy mismatch between the two electron branches and if 4m + 2 electrons occupy the SWNT. Moreover the excitation spectra are calculated. The large degeneracies of the discrete energy levels, as obtained by only including forward scattering terms, are partly lifted and the spectra become quasi-continuous when going to higher energies.

The low energy Hamiltonian of metallic finite size SWNTs Without loss of generality we focus on armchair SWNTs [START_REF] Odintsov | For the other types of metallic nanotubes only the magnitudes of the effective 1D interaction potentials change marginally[END_REF]. As basis of our future discussion let us recall the minimal model Hamiltonian to describe finite size armchair SWNTs at low energies derived in [11]. It is based on p z electrons localized on the graphene honeycomb lattice which contains two carbon atoms, p = ±, per unit cell. Let the SWNT axis be along the x direction and ignore for the moment interactions. Then, by imposing periodic boundary conditions along the circumference and open ones along the tube length, eigenfunctions are standing waves ϕ rκ ( r) with the branch or pseudo-spin index r = ±. The wave number κ describes the slowly varying oscillations of ϕ rκ ( r). The finite tube length L leads to the quantization condition κ = π(m κ + ∆)/L, m κ ∈ Z, |∆| ≤ 1/2. The parameter ∆ is responsible for a possible energy mismatch between the branches r = ±; its value depends on the length and on the type of the considered SWNT [15]. Explicitly, ϕ rκ ( r) can be decomposed into its contributions from the sublattices p = ±, ϕ rκ ( r) = 1 √ 2 p=± f pr F =±K0 sgn(F )e isgn(F )κx ϕ pF ( r), where

f + r = 1/ √ 2 and f -r = -r/ √ 2.
The functions ϕ pF ( r) describe fast oscillating Bloch waves at the two independent Fermi points F = ±K 0 of the honeycomb lattice, ϕ pF ( r) = N -1/2 L R e iF Rx χ( r -Rτ p ), where χ( r -Rτ p ) is the p z orbital at lattice site R on sublattice p and N L is the total number of lattice sites. The non-interacting Hamiltonian then reads

H 0 = v F rσ r κ κc † rσκ c rσκ ,
where v F ≈ 8.1•10 5 m/s is the Fermi velocity of graphene and c rσκ annihilates an electron in the state |ϕ rκ |σ .

Introducing the slowly varying 1D operators ψ rσF (x) [11] defined along the tube axis,

ψ rσF (x) = 1 √ 2L κ e isgn(F )κx c rσκ , (1)
and integrating over the coordinates perpendicular to the tube axis, the interaction part of the Hamiltonian becomes effectively one dimensional. We find

V = 1 2 σσ ′ {[r],[F ]} 4 i=1 sgn(F i ) dx dx ′ U [r][F ] (x, x ′ ) × ψ † r1σF1 (x)ψ † r2σ ′ F2 (x ′ )ψ r3σ ′ F3 (x ′ )ψ r4σF4 (x). ( 2
)
Here

{[r],[F ]} denotes the sum over all quadruples [r] = (r 1 , r 2 , r 3 , r 4 ) and [F ] = (F 1 , F 2 , F 3 , F 4 ).
Assuming that the wave functions ϕ p,F ( r) and ϕ -p,F ( r) do not overlap, the effective 1D Coulomb interaction potential

U [r][F ] (x, x ′ ) = 1 4 U intra [F ] (x, x ′ ) (1 + r 1 r 2 r 3 r 4 ) + U inter [F ] (x, x ′ ) (r 2 r 3 + r 1 r 4 ) , (3)
can be separated into an interaction for electrons on the same (intra) and on different sublattices (inter), where

U intra/inter [F ] (x, x ′ ) = L 2 d 2 r ⊥ d 2 r ′ ⊥ × ϕ * pF1 ( r)ϕ * ±pF2 ( r ′ )ϕ ±pF3 ( r ′ )ϕ pF4 ( r)U ( r -r ′ ),
and U ( rr ′ ) is the Coulomb potential. For the actual calculations we model U ( rr ′ ) by the so called Ohno potential. Measuring distances in units of Å and energy in eV, it is given by U

( r -r ′ ) = U 0 / 1 + (U 0 ǫ | r -r ′ | /14.397) 2 eV [16]. A reasonable choice is U 0 = 15 eV [12]. The dielectric constant is given by ǫ ≈ 1.4 -2.4 [1].
The relevant scattering processes To proceed, it is convenient to introduce the notion of forward Sσ =f V Sr SF Sσ , where

V SrSF Sσ := 1 2 {[r]S r ,[F ]S F ,[σ]S σ } dx dx ′ U [r][F ] (x, x ′ ) × ψ † r1σF1 (x)ψ † r2σ ′ F2 (x ′ )ψ r3σ ′ F3 (x ′ )ψ r4σF4 (x). ( 4
)
We start with the S r scattering types. From (3) it is evident, that the effective interaction potential is only nonzero for r 2 r 3 = r 1 r 4 . Hence we have to distinguish between the following two cases,

a) r 1 = r 4 , r 2 = r 3 and b) r 1 = -r 4 , r 2 = -r 3 .
In case a) we have S r = f and U

[r] f [F ] (x, x ′ ) is the sum of intra-and inter-lattice interaction. Case b) comprises S r = b and S r = u, with U [r] b/u [F ] (x, x ′
) being the difference of the two types of sublattice interactions. Now we look at the allowed S F processes. Although not dealing with an infinite system, after the integrations along the tube axis in (2), only terms with F 1 + F 2 -F 3 -F 4 = 0, i.e. the S F = f and S F = b processes, dominate as a consequence of the approximate conservation of quasi momentum. All other processes, including S F = u, have very small amplitudes. Finally, regarding the spin index, only S σ = f terms are allowed, since the Coulomb interaction is spin independent.

Additionally, away from half filling, only terms with (2), due to conservation of the quasi momentum, arising from the slow oscillations of the 1D electron operators.

r 1 F 1 + r 2 F 2 -r 3 F 3 -r 4 F 4 = 0 are relevant in
Since U intra

[F ] and U inter

[F ]
differ only at the length scale of the lattice spacing [1], the interaction potential for case b) (→ S r = b, u) is generally short ranged compared to the slowly varying electron operators ψ rσF , whereas in case a) (→ S r = f ), this is only true for the S F = b terms. Hence for S r = b, u or S F = b the corresponding interactions become effectively local:

V SrSF Sσ := Lu Sr SF {[r]S r ,[F ]S F ,[σ]F S } × L 0 dxψ † r1σF1 (x)ψ † r2σ ′ F2 (x)ψ r3σ ′ F3 (x)ψ r4σF4 (x), ( 5
)
where the coupling constants are given by u

Sr SF = 1/ 2L 2 dx dx ′ U [r]S r ,[F ]S F (x, x ′ ).
It holds u b SF = u u SF =: u ∆ SF and we define u + := u f b . The ratio u Sr SF /ε 0 is independent of L but scales like 1/d where d is the tube diameter, such that these processes become negligible for large diameter tubes. Numerically we find

u + ≈ u ∆ b = 0.22 [0.28] ε0 d Å and u ∆ f = 0.14 [0.22] ε0 d Å for ǫ = 1.4 [2.4].
Density-density interactions In the next step we introduce the quantities V ρρ and V nρρ that collect all interaction processes that are of density-density and nondensity-density form, respectively, such that in total H = H 0 + V ρρ + V nρρ . Since the short ranged interactions are treated as local, we obtain

V ρρ := V f f f + V f + b f + + V b f + /b f + ,
where the dominating part of the interaction away from half filling is the long-ranged term V f f f . Using bosonization techniques [START_REF] Delft | For an introduction to bosonization[END_REF], the Hamiltonian H 0 + V ρρ can be diagonalized and we find

H 0 + V ρρ = jδ q>0 ε jδq a † jδq a jδq + 1 2 E c N 2 c + 1 2 rσ N rσ N rσ ε 0 -u + + rε ∆ - J 2 N -rσ , (6)
where we have defined J := 2(u ∆ f + u ∆ b ). The first term describes discrete excitations created/annihilated by the bosonic operators a jδq /a † jδq . The four channels jδ = c+, c-, s+, s+ are related to total and relative (with respect to the r index) charge and spin excitations. With the level spacing of the free electrons, ε 0 := v F π L , and ε 0q := ε 0 n q , q = n q π L the relations

ε c+q = ε 0q 1 + 8W q /ε 0 , ε s/c-q = ε 0q (1 -u ∆ b /ε 0 ) and ε s+q = ε 0q (1 + u ∆ b /ε 0 ) hold.
Due to the dominating V f f f contribution, the ratio g q := ε 0q /ε c+q is strongly reduced for small q (g q ≈ 0.2) and for large q, g q tends to 1 [11]. Small corrections due to the coupling constants u + and u ∆ f have been omitted. Finally,

W q = 1 L 2 L 0 dx L 0 dx ′ cos(qx) cos(qx ′ )U [r] f [F ] f (x, x ′ ).
The remaining terms in (6) Non-density-density processes In the following we concentrate on the situation away from half-filling, where the non-density-density processes V nρρ can be treated as a small perturbation to the Hamiltonian H 0 + V ρρ . We calculate the low energy spectrum and the corresponding eigenstates of the full Hamiltonian H 0 + V ρρ + V nρρ by evaluating the matrix elements N , m|V nρρ | N ′ , m ′ and by truncating the Hilbert space at a certain eigenenergy of H 0 + V ρρ . Near half-filling the strength of V nρρ is highly enhanced and the truncation procedure therefore questionable. We obtain

V nρρ = V f + b f -+ V b f + /b f -+ V u f -/b f . ( 7
)
Low energy spectrum Our truncation scheme to find the low energy spectrum is to only retain the energetically lowest lying states of H 0 +V ρρ which have no bosonic excitations. Using ( 1) and ( 5), we get for the matrix elements of the contributions on the r.h.s of (7),

N , 0 |V Sr SF Sσ | N ′ , 0 = 1 4 u Sr SF {[r]S r ,[F ]S F ,[σ]F S } × κ1,...,κ4 N , 0 c † r1σκ1 c † r2σ ′ κ2 c r3σ ′ κ3 c r4σκ4 N ′ , 0 × δ 2 i=1 sgn(Fi)κi-4 i=3 sgn(Fi)κi,0 , (8)
where the Kronecker-δ results from the integration along the tube axis in (5). Note that the states | N , 0 are eigenstates of H 0 + V ρρ and not of H 0 alone. Hence the evaluation of (8) in general is not straightforward. But for the processes relevant away from half-filling we get the same result and physical insight if we consider for the calculation of (8) | N , 0 as the Fermi sea filled up with N rσ noninteracting electrons in the branch rσ, i. e. as an eigenstate of H 0 , as we will discuss elsewhere [18].

In the following we focus on the case N c = 4m + 2. As truncated basis we use the states | N , 0 with N = (m + 1, m + 1, m, m) and permutations. In the following we denote |(m + 1, m + 1, m, m), 0 by |↑↓,etc. Using ( 6) and ( 8) the interacting Hamiltonian, restricted to the states |↑, ↑ , |↓, ↓ , |↑, ↓ , |↓, ↑ , |↑↓,and |-, ↑↓ , is

H = E 0,4m+2 +         -J 2 0 -J 2 0 -J 2 -J 2 0 u + -ε ∆ J 2 0 J 2 u + + ε ∆         , (9)
with

E 0,4m+2 = 1 2 E c N 2 c + (2m 2 + 2m + 1) (ε 0 -u + ) - J(m 2 + m) + 2u + m.
Diagonalizing H, we find that its eigenstates are given by the spin

1 triplet |↑, ↑ , |↓, ↓ , 1/ √ 2 (|↑, ↓ + |↓, ↑ ), the spin 0 singlet 1/ √ 2 (|↑, ↓ -|↓, ↑ ) and the two states (c 2 1/2 + 1) -1/2 c 1/2 |↑↓, -± |-, ↑↓ , where c 1/2 = J 2 / ε 2 ∆ + (J/2) 2 ± ε ∆ .
Relatively to E 0,4m+2 , the eigenenergies are -J/2 for the triplet states, J/2 for the singlet state and u + ± ε 2 ∆ + (J/2) 2 for the remaining two states.

Thus, under the condition J/2 > ε 2 ∆ + (J/2) 2u + , i.e. for a small band mismatch ε ∆ J/2, the ground state is threefold degenerate and formed by the spin 1 triplet, otherwise by (c 2 2 +1) -1/2 (c 2 |↑↓, --|-, ↑↓ ). The low energy spectra for the two cases ε ∆ = 0 and ε ∆ ≫ J/2 are shown in Fig. 1 for a (6,6) armchair nanotube (corresponding to d = 0.8 nm) with an assumed dielectric constant of ǫ = 1.4. The obtained values of J = 0.09ε 0 and u + = 0.03ε 0 are in good agreement with the experiments [8,10], where nanotubes with ε ∆ ≫ J 2 were considered. In accordance with the discussion above, Moriyama et al. [10] could identify the ground state to N c = 4m + 2 as a spin 0 singlet and also a spin 1 triplet was found. Not observed so far has been the spin 1 triplet as ground state and the mixing of |↑↓,and |-, ↑↓ , as predicted by our calculation for nanotubes with ε ∆ J/2. We emphasize that all the exchange splittings here result from non-forward scattering processes with respect to the band index r. In the considerations of Lieb and Mattis [13] such an additional pseudo-spin degree of freedom is missing and so we conjecture that this is the reason why their theorem can not be applied in our case. The meanfield result of Oreg et al. [12] for the ground state structure to N c = 4m + 2 essentially can be obtained by setting the off-diagonal elements in (9) to zero. Therefore if ε ∆ ≫ J 2 , the meanfield approach yields the same ground state spectrum as our work, but with different degeneracies: Instead of having a threefold degeneracy of the spin 1 triplet and no degeneracy for the spin 0 singlet, a twofold degeneracy of the states |↑, ↑ , |↓, ↓ and |↑, ↓ , |↓, ↑ respectively, is obtained. Additionally for ε ∆ J/2, the meanfield theory is not capable of predicting the mixing of the states |↑↓,and |-, ↑↓ with the accompanying exchange splitting. The ground states of H 0 + V ρρ to the charge states N c = 4m + 2 do not mix via V nρρ and thus the corresponding energies can be determined easily by using eqs. ( 6) and ( 8) for N = N ′ .

Excitation spectrum So far no bosonic excitations were involved in our ground state examination. In order to discuss the excitation spectrum of H = H 0 +V ρρ +V nρρ , the matrix elements of N , m|V nρρ | N ′ , m ′ must be determined. The detailed calculation, based on bosonizaton techniques, will be given in a longer article [18]. After truncating the Hilbert space at sufficiently high energies and diagonalizing H we obtain for N c = 4m + 2 the spectrum as shown in Fig. 2. For comparison we also show the spectrum of the "standard" theory [1,5,11] as obtained by only retaining the dominating forward scattering processes of V ρρ . Most striking is the partial lifting of the huge degeneracies and the formation of a quasi continuum at higher energies.

In conclusion we have derived a microscopic low en- For ε∆ ≫ J/2 the ground state is given by the spin 0 state |↑↓, -. The spin 0 singlet is indicated by ⊗. The interaction parameters are J = 0.09ε0, u + = 0.03ε0. ergy theory for finite size metallic SWNTs away from half filling, including non-density-density interaction processes, which become relevant for small diameter tubes. The ground state and excitation spectra have been determined. In particular, we predict a spin 1 triplet as ground state for N c = 4m+2, if the energy mismatch ε ∆ between the different pseudo-spin branches is much smaller than the exchange energy J, a spin 0 singlet otherwise. For ε ∆ J/2 we furthermore find that the pseudo-spin is not conserved and the corresponding degeneracy is lifted. We notice that in [10] an energy mismatch ε ∆ ≫ J 2 was used to fit the data and, in agreement with our theory, a singlet ground state has been inferred from magnetic field measurements. Observation of the triplet ground

  (f )-, back (b)-, and Umklapp (u)-scattering for an arbitrary index quadruple [I] associated to the four electron operators in (2). With S I being the type of scattering process for the quantity I, we denote a quadruple [I, ±I, ±I, I] by [I] SI =f ± , while [I] b is equivalent to [I, -I, I, -I]. Finally Umklapp scattering means [I] u = [I, I, -I, -I]. As we will show in the sequel the interaction part V of the Hamiltonian is of the form V = Sr =f,b,u SF =f,b

  are fermionic contributions, accounting for the energy cost of changing the number of electrons in the different branches (rσ). The operators N rσ count the electrons in (rσ) and N c = rσ N rσ . The single summands account for (in the order of appearance) the Coulomb charging energy E c = W 0 , the shell filling energy (because of Pauli's principle), a possible energy mismatch ε ∆ = sgn(∆)ε 0 min(2 |∆| , 2 |∆| -1) between the r branches if |∆| = 0, 1/2, and a favourable spin alignment of electrons with different r due to V b f + /b f + . Note also that the shell filling energy is modified by the attractive contribution -u + due toV f + b f + . The eigenstates of H 0 + V ρρ are | N , m := jδq a †jδq m nδq / m jδq !| N , 0 , where | N , 0 has no bosonic excitation and N = (N -↑ , N -↓ , N +↑ , N +↓ ) defines the number of electrons in each of the branches (rσ).

Figure 1 :

 1 Figure 1: Low energy spectrum of a (6, 6) SWNT for Nc = 4m + 2. (a) For ε∆ = 0 the ground state is formed by the spin 1 triplet (→ ⊕). The states |↑↓, -and |-, ↑↓ mix. (b)For ε∆ ≫ J/2 the ground state is given by the spin 0 state |↑↓, -. The spin 0 singlet is indicated by ⊗. The interaction parameters are J = 0.09ε0, u + = 0.03ε0.

Figure 2 :

 2 Figure 2: Excitation spectrum of a (6.6) SWNT including only forward scattering processes (→ ×) and for the total Hamiltonian H = H0 + Vρρ + Vnρρ (→ ♦). Note the logarithmic scale of the x-axis. The energy of the lowest c+ excitation is 4.3 ε0. All other interaction parameters are as for Fig. 1.

state is within experimental reach.