ENS Fabrice Benhamouda
email: fabrice.benhamouda@ens.fr

M Joye

B Libert

A New Framework for Privacy-Preserving Aggregation of Time-Series Data

Keywords: CCS Concepts:, Security and privacy → Cryptography, •Theory of computation → Cryptographic primitives, Cryptographic protocols, Private aggregation, aggregator-oblivious encryption, smart metering, smooth projective hashing, security reduction ACM

Aggregator-oblivious encryption is a useful notion put forward by Shi et al. in 2011 that allows an untrusted aggregator to periodically compute an aggregate value over encrypted data contributed by a set of users. Such encryption schemes find numerous applications, in particular in the context of privacy-preserving smart metering.

This paper presents a general framework for constructing privacy-preserving aggregator-oblivious encryption schemes using a variant of Cramer-Shoup's paradigm of smooth projective hashing. This abstraction leads to new schemes based on a variety of complexity assumptions. It also improves upon existing constructions, providing schemes with shorter ciphertexts and better encryption times.

INTRODUCTION

Since the introduction of electricity into the home, its use has been recorded by an electricity meter attached to the exterior of the homes. This situation is however gradually changing with the progressive deployment of smart meters [START_REF] Mcdaniel | Security and Privacy Challenges in the Smart Grid[END_REF]. In addition to the basic service offered by its predecessor, a smart meter comes with extra useful features aiming at reducing energy costs. For example, a smart meter can turn down momentarily high-energy electrical appliances during peak hours. For the utility company, one of its most appealing features is its ability to report in almost real-time the power consumption of their consumers. This fine-grained information is very helpful as it allows the electricity provider to better adapt the load or forecast the supply. Moreover, it allows the electricity provider to quickly react when anomalies are detected on the grid. The resulting savings are also beneficial to the consumers as they give rise to better pricing. But there is a downside. Frequent usage reports leak information about the consumer habits and behaviors -for example, when a certain consumer turns her TV on and what programs she is likely to watch. These seemingly unimportant issues should not be underestimated as they may have unintended consequences from the inference of some private information (attributes or data).

In most cases, there is no need for the utility company (except for preparing the monthly bill) to get the fined-grained energy usage of each customer. For example, in the previous scenario, an aggregate suffices. The goal of this paper is to mitigate the privacy issues that arise from smart metering by computing aggregates rather than individual energy consumption. More generally, we are seeking efficient privacypreserving methods for the aggregation of time-series data. The entity computing the aggregates is not necessarily trusted. We are interested in solutions that affect the existing infrastructure as little as possible. In particular, in the above scenario, we do not require smart meters to interact with each other nor the existence of a return channel. We note that the billing issue is separate. In practice, smart meters report their monthly energy consumption to the energy provider separately.

Related work. The above setting is the one considered in [START_REF] Shi | Privacy-Preserving Aggregation of Time-Series Data[END_REF]] and [START_REF] Joye | A Scalable Scheme for Privacy-Preserving Aggregation of Time-Series Data[END_REF]. Each smart meter encrypts its actual energy consumption and sends the result at regular intervals to an aggregator (which can be an entity different from the energy provider). In the case of electricity metering, a typical time period is 15 minutes. Upon receiving the encrypted values from a predetermined set of users, the aggregator combines the received values and therefrom deduces the total energy consumption over the population of these users for the current time period. This operation involves a secret key known only to the aggregator. Further, computing the sum over the predetermined set of users is the only operation the aggregator can perform -it cannot learn anything beyond what is revealed by the aggregate value. Following [START_REF] Shi | Privacy-Preserving Aggregation of Time-Series Data[END_REF], such a scheme is termed an aggregator-oblivious encryption scheme.

Like [START_REF] Shi | Privacy-Preserving Aggregation of Time-Series Data[END_REF]] and [START_REF] Joye | A Scalable Scheme for Privacy-Preserving Aggregation of Time-Series Data[END_REF]], all our schemes can serve as a building block for the fault tolerant solution of [START_REF] Hubert Chan | Privacy-Preserving Stream Aggregation with Fault Tolerance[END_REF]] while enjoying the benefits of our construction. In fact, all the extensions of [START_REF] Shi | Privacy-Preserving Aggregation of Time-Series Data[END_REF]] are also possible with our system. In particular, although the focus of this paper is put on the encryption, the proposed schemes are compatible with the differential-privacy framework [START_REF] Dwork | Differential privacy: A survey of results[END_REF][START_REF] Dwork | Our Data, Ourselves: Privacy Via Distributed Noise Generation[END_REF]]. In this case, the smart meters simply need to add some appropriately-generated noise to their data prior to encryption Two other protocols in settings similar to the one of aggregator-oblivious encryption are the low-overhead protocol of [START_REF] Benhamouda | Privacy-Friendly Aggregation for the Smart-Grid[END_REF]] and the protocol of [START_REF] Ács | I Have a DREAM! (DiffeRentially privatE smArt Metering)[END_REF]. These protocols however have the drawback of requiring each smart meter to store as many keys as there are users, which can be impractical for a large set of smart meters.

We also note that recent results on multi-input functional encryption [START_REF] Shafi Goldwasser | Multi-input Functional Encryption[END_REF]] imply non-interactive constructions of aggregator-oblivious encryption. However, due to their inevitable use of indistinguishability obfuscation candidates [START_REF] Garg | Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits[END_REF], they are really far from being practical and should only be seen as feasibility results.

Many other settings than the one we consider have been studied in the literature. For example, the protocol of [START_REF] Dwork | Our Data, Ourselves: Privacy Via Distributed Noise Generation[END_REF]] allows the aggregation of more complex functions, but requires communication between the smart meters. The setting of [START_REF] Rastogi | Differentially Private Aggregation of Distributed Time-Series with Transformation and Encryption[END_REF] and of [Garcia and Jacobs 2010] require A New Framework for Privacy-Preserving Aggregation 10:3 bi-directional channels between the smart meters and the aggregator, while we only require a uni-directional channel from each smart meter to the aggregator. The protocols of [START_REF] Leontiadis | Private and Dynamic Time-Series Data Aggregation with Trust Relaxation[END_REF] as well as [Jawurek and Kerschbaum 2012] suppose the existence of an additional semi-trusted party, who cannot collude with the aggregator. In addition, in the second paper, the smart meter should be able to receive data from this third party.

For more information on aggregation schemes, we refer the reader to the detailed survey of Jawurek, Kerschbaum, and Danezis [Jawurek et al. 2012].

Our contributions. While applicable to our framework, the solutions offered in [START_REF] Shi | Privacy-Preserving Aggregation of Time-Series Data[END_REF]] and [START_REF] Joye | A Scalable Scheme for Privacy-Preserving Aggregation of Time-Series Data[END_REF] are not fully satisfying, but for different reasons. Table I gives a rough idea of the expected gains for our basic aggregator-oblivious encryption scheme (a more detailed analysis with concrete implementation numbers is provided in Section 3).

Table I. Reduction loss and typical parameter size for existing schemes and our basic scheme (for T = n = 2 20 , based on ECRYPT 2 recommendations, s -1 (α) is the minimal number of bits of a modulus which cannot be factored in time 2 α , see Section 3.3 for details)

≈ T n 3 2(λ + log 2 (T n 3 )) 2(λ + log 2 (T n 3 )) 2(λ + log 2 (T n 3 )) λ bits [Joye and Libert 2013] T ≤ 2s -1 (λ+log 2 (T )) ≤ 2s -1 (λ+log 2 (T )) ≤ 2s -1 (λ+log 2 (T )) λ bits This work T ≤ 2(λ + log 2 (T )) ≤ 4(λ + log 2 (T )) ≤ 2(λ + log 2 (T ))
Joye-Libert's scheme supports large plaintext spaces and a large number of users. However as it is built over Paillier's encryption scheme, the involved parameters are somewhat large. Back to our example of smart meters, this in turn implies that these are likely equipped with crypto-processors for modular arithmetic over large integers and possess sufficient memory for storing intermediate computations. Larger ciphertexts also mean more bandwidth for their transmission. Shi et al.'s scheme provides a cheaper solution as it is ElGamal-based and relies on the Decisional Diffie-Hellman assumption (DDH). In particular, it can be implemented using elliptic-curve groups with much shorter parameters. It requires the computed aggregated sum to lie in a relatively small predetermined set. In the case of smart meters, this does not really constitute a limitation for most practical settings, as the sum should be less than 30 bits long.

A reductionist security proof of a cryptographic scheme consists in an efficient algorithm, called a reduction, that uses an attacker against the scheme as a subroutine to solve a problem supposed hard. If ε and ε respectively denote the success probability of the attacker and of the reduction algorithm, the security proof is said tight when ε ≈ ε and loose otherwise. The tightness gap is measured by the ratio ε/ε and captures the security loss. This ratio is an important parameter as it defines the exact security [START_REF] Bellare | The Exact Security of Digital Signatures: How to Sign with RSA and Rabin[END_REF][START_REF] Bellare | Practice-Oriented Provable Security[END_REF]] of a scheme. It quantifies the amount by which the security parameters defining the scheme need to be increased to accommodate the tightness gap.

But as already pointed out in [START_REF] Joye | A Scalable Scheme for Privacy-Preserving Aggregation of Time-Series Data[END_REF], one drawback of [START_REF] Shi | Privacy-Preserving Aggregation of Time-Series Data[END_REF]] is that the security reduction from the underlying complexity assumption is very loose. If the scheme is set up for n users and if the number of time periods is at most T , there is a multiplicative gap of O(T n 3 ) between the adversary's advantage and the reduction's probability to solve the DDH problem. Moreover, using a meta-reduction, we show in Appendix C that a degradation factor of at least Ω(n 2 ) is unavoidable in the scheme of [START_REF] Shi | Privacy-Preserving Aggregation of Time-Series Data[END_REF]].

An important contribution of this paper is a new DDH-based aggregator oblivious encryption scheme (cf. Section 3) with a much tighter security reduction. While the security loss is O(T n 3 ) in Shi et al.'s scheme, our basic scheme reduces this gap to roughly O(T ) in the worst-case scenario (this worst-case scenario is illustrated by the figures given in Table I).

In Section 4, we generalize our basic DDH-based construction. We propose a generic framework for the privacy-preserving aggregation of time-series data featuring a tighter reduction. This framework is based on smooth projective hash functions [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF] (SPHFs) with an extra additively homomorphic property over the key space. Note that all SPHF realizations given in [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF] are natively additively key-homomorphic. As shown in Section 5, our framework encompasses our basic scheme as well as a variation of Joye-Libert's scheme. Several other aggregator-oblivious encryption schemes based on a variety of complexity assumptions are presented in Section 5. This clearly demonstrates the generic aspect of our framework.

AGGREGATOR-OBLIVIOUS ENCRYPTION

We review the definition of aggregator-oblivious (secret-key) encryption and then proceed with the corresponding security notion. We refer the reader to [START_REF] Shi | Privacy-Preserving Aggregation of Time-Series Data[END_REF] for further introductory background.

Definition 2.1. An aggregator-oblivious encryption scheme is a tuple of three algorithms, (Setup, Enc, AggrDec), defined as:

Setup(1 λ ). On input a security parameter λ, a trusted dealer generates the system parameters param, the aggregator's private key sk 0 , and the private key sk i for each user i (1 ≤ i ≤ n). Enc(param, sk i , τ, x i,τ ). At time period τ , user i encrypts a value x i,τ using her private encryption key sk i to get c i,τ = Enc(param, sk i , τ, x i,τ ). AggrDec(param, sk 0 , τ, c 1,τ , . . . , c n,τ ). At time period τ , the aggregator using sk 0 obtains

X τ = n i=1 x i,τ mod M ,
as the evaluation of X τ = AggrDec(param, sk 0 , τ, c 1,τ , . . . , c n,τ ). M is some fixed integer contained in the system parameters param.

This definition slightly generalizes the definition introduced in [START_REF] Shi | Privacy-Preserving Aggregation of Time-Series Data[END_REF]]. We make explicit the fact the sum is computed modulo some integer M . To compute sums over the integers, it is sufficient to choose M greater than the maximal possible sum, as done in the constructions of [START_REF] Shi | Privacy-Preserving Aggregation of Time-Series Data[END_REF]. Furthermore, we note that some constructions assume AggrDec only works on a small subset of {0, . . . , M -1}.

A New Framework for Privacy-Preserving Aggregation 10:5

Aggregator obliviousness

Basically, the security notion of aggregator obliviousness (AO) requires that the aggregator cannot learn, for each time period, anything more than the aggregate value X τ from the encrypted values of n (honest) users. If there are corrupted users (i.e., users sharing their private information with the aggregator), the notion only requires that the aggregator gets no extra information about the values of the honest users beyond their aggregate value. Further, it is assumed that each user encrypts only one value per time period.

More formally, AO is defined by the following game between a challenger and an attacker.

Setup. The challenger runs the Setup algorithm and gives param to the attacker. Queries. In a first phase, the attacker can submit queries that are answered by the challenger. The attacker can make two types of queries:

(1) Encryption queries: The attacker submits tuples (i, τ, x i,τ ) for a pair (i, τ ) and gets back the encryption of x i,τ under key sk i for time period τ ; (2) Compromise queries: The attacker submits i and receives the private key sk i of user i; if i = 0, the attacker receives the private key of the aggregator. Challenge. In a second phase, the attacker chooses a time period τ . Let U ⊆ {1, . . . , n} be the whole set of users for which, at the end of the game, no encryption queries have been made on time period τ and no compromise queries have been made. The attacker chooses a subset S ⊆ U and two different series of triples

(i, τ , x (0)
i,τ ) i∈S and (i, τ , x

i,τ ) i∈S , that are given to the challenger. Further, if the aggregator capability sk 0 is compromised at the end of the game and S = U , it is required that

i∈S x (0) i,τ mod M = i∈S x (1) i,τ mod M .
(1)

Guess. The challenger chooses uniformly at random a bit b ∈ {0, 1} and returns the encryption of x (b)

i,τ i∈S to the attacker. More queries. The attacker can make more encryption and compromise queries. Note that since S ⊆ U , the attacker cannot submit an encryption query (i, τ , •) with i ∈ S or a compromise query i with i ∈ S . Outcome. At the end of the game, the attacker outputs a bit b and wins the game if and only if b = b.

Definition 2.2. An encryption scheme is said to meet the AO security notion if no probabilistic polynomial-time attacker can guess correctly, in the above game, the bit b with a probability non-negligibly better (in the security parameter) than 1/2. Formally, an encryption scheme is AO-secure if the advantage of any probabilistic polynomialtime attacker A defined as

Adv AO (A) := 2 Pr[b = b] -1/2
is negligible; the probability is taken over the random coins of the game according to the distribution induced by Setup and over the random coins of the attacker.

Existing schemes

So far, there are two known constructions of AO encryption schemes. They both meet the AO security notion, in the random oracle model. The first one is due to [START_REF] Shi | Privacy-Preserving Aggregation of Time-Series Data[END_REF] and works in DDH groups. The second construction, due to [START_REF] Joye | A Scalable Scheme for Privacy-Preserving Aggregation of Time-Series Data[END_REF], relies on the composite residuosity assumption [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF]]. These two schemes are reviewed in Appendix A.

A NEW DDH-BASED SCHEME

As aforementioned, the security proof offered in [START_REF] Shi | Privacy-Preserving Aggregation of Time-Series Data[END_REF]] incurs an O(T n 3 ) degradation factor. The scheme in [START_REF] Joye | A Scalable Scheme for Privacy-Preserving Aggregation of Time-Series Data[END_REF] avoids this degradation factor; namely, the multiplicative gap between the adversary's maximal advantage and the probability to break the underlying complexity assumption is only proportional to the number q enc of encryption queries made by the adversary for distinct time periods other than τ (so that, q enc < T ). In this section, we introduce an aggregator-oblivious encryption scheme enjoying a security reduction as tight as in [START_REF] Joye | A Scalable Scheme for Privacy-Preserving Aggregation of Time-Series Data[END_REF] but based on the DDH assumption. The main advantage is that the resulting ciphertexts are much shorter.

Basic scheme

We base the security of our basic scheme on the standard DDH assumption.

Definition 3.1. Let G be a group of prime order p. The Decision Diffie-Hellman (DDH) problem in G is to distinguish among the following two distributions:

D 0 = (g, g a , g b , g ab ) | g R ← G, a, b R ← Z p and D 1 = (g, g a , g b , g c ) | g R ← G, a, b, c R ← Z p .
The DDH assumption states that the advantage of a polynomial-time distinguisher A, defined as

Adv DDH (A) = Pr[A(g, u, v, w) = 1 | (g, u, v, w) R ← D 0 ] - Pr[A(g, u, v, w) = 1 | (g, u, v, w) R ← D 1 ] ,
is negligible.

We are now ready to present the scheme. It is given by the following tuple of algorithms.

Setup(1 λ ). Let G be a group of prime order M = p for which the DDH assumption holds, and let g ∈ G be a random generator. Let also H 1 : Z → G and H 2 : Z → G be two hash functions. Finally, for 2n random elements s 1 , . . . , s n , t 1 , . . . , t n R ← Z p , define s 0 = -n i=1 s i mod p and t 0 = -n i=1 t i mod p. The system parameters are param = {p, G, g, H 1 , H 2 } and the secret key of user i is

sk i = (s i , t i ), with 0 ≤ i ≤ n. Enc(param, sk i , τ, x i,τ ). At time period τ , for a private input x i,τ ∈ Z p , user i produces c i,τ = g xi,τ H 1 (τ ) si H 2 (τ ) ti . AggrDec(param, sk 0 , τ, c 1,τ , . . . , c n,τ ). The aggregator obtains the sum X τ = n i=1 x i,τ for time period τ by first computing V τ := H 1 (τ ) s0 H 2 (τ ) t0 n i=1 c i,τ = g Xτ and next the discrete logarithm of V τ w.r.t. basis g.
As for the Shi et al. construction, since g has order p, the sum X τ is computed modulo M = p. Further, in the AggrDec algorithm, the aggregator has to obtain the value of X τ from V τ = g Xτ in G. The most appropriate method for computing discrete logarithms is Pollard's λ algorithm (or variants thereof) and requires that the range of X τ be relatively small.

A New Framework for Privacy-Preserving Aggregation 10:7

Security

The next theorem proves that the basic scheme meets the AO security notion in the random oracle model, based on the DDH assumption. THEOREM 3.2. The scheme provides AO security under the DDH assumption in the random oracle model. Specifically, for any probabilistic polynomial-time adversary A, there exists a DDH distinguisher B DDH with comparable running time1 and such that

Adv AO (A) ≤ 2e (q enc + 1) • (Adv DDH (B DDH ) + 1/p) ,
where q enc is the number of encryption queries made by the adversary for distinct time periods other than τ , and e is the base for the natural logarithm.

PROOF. The theorem is a corollary of Theorem 4.3, which ensures the security of our abstract scheme (cf. Section 4.4).

Performance

The new scheme combines the advantages of [START_REF] Joye | A Scalable Scheme for Privacy-Preserving Aggregation of Time-Series Data[END_REF] (which offers tighter security in the random oracle model) and of [START_REF] Shi | Privacy-Preserving Aggregation of Time-Series Data[END_REF]] (which has more compact ciphertexts when implemented using elliptic-curve groups). As already shown in Table I (Section 1), our basic scheme represents the aggregator-oblivious encryption with the shortest ciphertexts. The key sizes are derived from the ECRYPT 2 recommendations [ECRYPT II 2012] -where Shi et al.'s scheme and our basic scheme are implemented in elliptic-curve groups and Joye-Libert's scheme in Z * N 2 with N an RSA modulus. Concretely, for a security gap of 2 γ , key sizes are chosen such that the underlying problem (DDH for the Shi et al.'s scheme and our scheme, or DCR for the Joye-Libert scheme) cannot be solved in time 2 γ+λ (with constant probability, e.g., 1/2). According to ECRYPT 2 recommendations, for DDH-based scheme, the order of the group used has to have 2(γ + λ) bits, while for DCR-based scheme, the modulus has to have s -1 (γ + λ) bits, where s is the function defined in [ECRYPT II 2012, Section 6.2.1]. As the latter function is sublinear, higher security levels yield better results for our basic scheme compared to [START_REF] Joye | A Scalable Scheme for Privacy-Preserving Aggregation of Time-Series Data[END_REF].

As exemplified in Table II, our new scheme also features better encryption times. Table II presents the running times for a security level of 80 bits and was constructed from a synthetically generated dataset by taking n = 2 20 ≈ 10 6 users and T = 2 20 time periods. This approximately allows computing an aggregation every 15 minutes for 30 years over a city like Paris (there are about one million households in Paris). Moreover, to have the fairest possible comparison, the worst case for our reduction is considered: q enc = T -1 ≈ 2 20 . Higher security levels yield better results for our basic scheme compared to [START_REF] Joye | A Scalable Scheme for Privacy-Preserving Aggregation of Time-Series Data[END_REF] as attacks against factorization and DCR are subexponential in the key size while attacks against DDH are exponential in the key size.

GENERALIZATION USING KEY-HOMOMORPHIC SMOOTH PROJECTIVE HASH FUNCTIONS

In this section, we use the framework of key-homomorphic smooth projective hashing to generalize our DDH construction presented in Section 3.

Table II. Running times (with margin of error at 95% confidence, computed with 100 samples) of our basic scheme and the existing schemes (for T = n = 2 20 , 80-bit security, using parameters in

Key-homomorphic smooth projective hash functions

4.1.1. Subset-membership problem. We start with the important notion of subsetmembership problems, as introduced in [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF]. Consider an NPlanguage L ⊂ X , defined by a polynomial-time witness relation R:

L = y ∈ X | ∃w such that R(y, w) = 1 .
We suppose that L, X , L = X \ L are efficiently (uniformly) samplable, and even that sampling a word y ∈ L along with an associated witness w for this word can also be done efficiently. We also assume that |L|/|X | is negligible: in other words, a random element of X is in L with overwhelming probability.

Basically, the language L induces a hard subset-membership problem if random elements of L cannot be distinguished from random elements of X . More formally, this notion can be defined via the following game between a challenger and an attacker. The challenger chooses at random a bit b. The attacker can issue up to q m (a parameter of the game) queries to the challenger. On each query, the challenger returns a uniformly random element in Defining the subset-membership hardness via the above game allows us to generically obtain tighter security bounds. In instantiations based on specific assumptions (e.g., DDH), the random self-reducibility of underlying problems (e.g., [START_REF] Abadi | On Hiding Information from an Oracle[END_REF][START_REF] Stadler | Publicly Verifiable Secret Sharing[END_REF][START_REF] Naor | Number-theoretic Constructions of Efficient Pseudo-random Functions[END_REF]) allows avoiding any dependency on q m in the reduction.

4.1.2. Smooth projective hash functions. Smooth projective hash functions (SPHFs) were introduced by [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF] as a tool to construct chosen-ciphertext secure encryption schemes. We present below a variant tailored to fulfill our needs. A recent account on the different flavors of SPHFs can be found in [START_REF] Benhamouda | New Techniques for SPHFs and Efficient One-Round PAKE Protocols[END_REF]].

Definition 4.2. Using the previous notations, a smooth projective hash function (SPHF) is specified by a tuple of algorithms, (HashKG, ProjKG, Hash, ProjHash), of which the first one is probabilistic and the other algorithms are deterministic, defined as:

HashKG(1 λ ). On input a security parameter λ, algorithm HashKG generates a hashing key hk identified as an element of K, where K denotes the key space. ProjKG(hk). Given a hashing key hk, this algorithm derives a projection key hp. Hash(hk, y). Given a hashing key hk and a word y ∈ X , algorithm Hash outputs the hash value h of y. ProjHash(hp, y, w). Given a projection key hp, a word y ∈ L and a corresponding witness w (such that R(y, w) = 1), algorithm ProjHash outputs the hash value h of y.

Further, letting Π denote the range of Hash and ProjHash and assuming that (Π, •) is an Abelian group (written multiplicatively with 1 Π as neutral element), an SPHF must satisfy the properties of correctness and special smoothness:

Correctness. This property means that Hash and ProjHash hash to the same value for any word y in the language L. More precisely, for every hashing key hk R ← HashKG(1 λ ), for all y ∈ L and associated witness w (such that R(y, w) = 1), we have Hash(hk, y) = ProjHash(hp, y, w) provided hp = ProjKG(hk). Special smoothness. Let Π ⊆ Π be a subset of Π. Intuitively, the special smoothness says that the hash value of any y ∈ L = X \ L looks random "over Π ", even knowing hp. Formally, an SPHF is said to be (ε s , Π )-smooth, if for all y ∈ L, the following two distributions are ε s -statistically indistinguishable:

D 0 = (hp, h) | hk R ← K, hp ← ProjKG(hk), h ← Hash(hk, y)
and

D 1 = (hp, h • h ) | hk R ← K, hp ← ProjKG(hk), h ← Hash(hk, y), h R ← Π .
There are a couple of differences compared to the definition given in [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF]. Special smoothness replaces the original smoothness property. The latter basically corresponds to the definition of special smoothness when Π = Π. The special smoothness is also required to hold for any word y ∈ L, and not just on average as in the original definition. Furthermore, only HashKG and Hash are required to be polynomialtime algorithms; ProjKG or ProjHash are not required to be efficient and they may run in exponential time.

An additional property which will be used in the security proofs is called key uniformity. Key uniformity. An SPHF is ε hk -key-uniform when an honestly generated hashing key is ε hk -statistically indistinguishable 2 from a random element in K.

4.1.3. Key-homomorphic SPHF. An SPHF is said key-homomorphic if in addition

(1) (K, +) is an Abelian group (written additively with 0 K as neutral element);

(2) Π is a subgroup of Π;

(3) for any two hashing keys hk 1 , hk 2 ∈ K and for every word y ∈ X Hash(hk 1 + hk 2 , y) = Hash(hk 1 , y) • Hash(hk 2 , y) .

2 Recall that two distributions D 0 and D 1 on some finite set S are ε-statistically indistinguishable or ε-close

if 1 2 x∈S | Pr X R ←D 0 [X = x] -Pr X R ←D 1 [X = x]| ≤ ε .
10:10 F. Benhamouda, M. Joye, and B. Libert

Our abstract scheme

We can now present our generic aggregator-oblivious encryption scheme, based on keyuniform, key-homomorphic SPHF with the special smoothness property. Let f be an injective group homomorphism, f : Z M → Π . We assume that this homomorphism is efficiently and publicly invertible over the domain of possible sums X τ (which may be smaller than {0, . . . , M -1}, as is the case for our DDH-based scheme).

Setup(1 λ ). Let L ⊂ X be a hard subset-membership language. Let also H : Z → X be a hash function (viewed as a random oracle in the security analysis). Finally, let hk 1 R ← HashKG(1 λ ), . . . , hk n R ← HashKG(1 λ ) be n random hashing key. Define the aggregator's secret key as hk 0 = -n i=1 hk i . The system parameters are param = {L, H} and the secret key of user i is sk i = hk i , with 0 ≤ i ≤ n. Enc(param, sk i , τ, x i,τ ). At time period τ , for a private input x i,τ ∈ Z M , user i produces

c i,τ = f (x i,τ ) • Hash(hk i , H(τ )) ∈ Π .
AggrDec(param, sk 0 , τ, c 1,τ , . . . , c n,τ ). The aggregator obtains the sum X τ (mod M ) for time period τ by computing X τ := f -1 Hash(hk 0 , H(τ )) • n i=1 c i,τ . The correctness of the aggregation step follows from the homomorphic properties:

Hash(hk 0 , H(τ )) • n i=1 c i,τ = n i=0 Hash(hk i , H(τ )) • n i=1 f (x i,τ ) = Hash( n i=0 hk i , H(τ )) • f ( n i=1 x i,τ ) = Hash(0 K , H(τ )) • f ( n i=1 x i,τ ) = 1 Π • f ( n i=1 x i,τ ) = f ( n i=1 x i,τ ) , and therefore X τ = n i=1 x i,τ (mod M ) since f is injective.

Security

We prove security of the abstract scheme in the random oracle model, based on the hardness of the subset-membership problem.

THEOREM 4.3. The scheme provides AO security under the hard subset-membership assumption of L in the random oracle model. Namely, for any probabilistic polynomialtime adversary A, if the SPHF is (ε s , Π )-smooth and ε hk -key-uniform, there exists a distinguisher B memb for the subset-membership problem of L with comparable running time and such that

Adv AO (A) ≤ 2e (q enc + 1) • Adv memb T (B memb ) + n ε hk + |L| |X | + n(n + 1) ε s ,
where n is the number of users, q enc is the number of encryption queries made by the adversary for distinct time periods other than τ , and e is the base for the natural logarithm.

We recall that we suppose |L|/|X | is negligible.

PROOF. The proof proceeds with a sequence of several games. It begins with Game 0, which is the real game, and ends with Game 6, where even a computationally unbounded adversary has no advantage. For each j ∈ {0, . . . , 6}, we denote by S j the event that the challenger B outputs 1 in Game j. 3 We also define Adv j = 2•| Pr[S j ]-1/2|.

A New Framework for Privacy-Preserving Aggregation 10:11

In the following, we assume w.l.o.g. that the adversary A has always already queried the random oracle H on input τ before any encryption query for the time period τ . We assume that the adversary does not query the random oracle H more than once for a given τ .

Game 0. This is the real game. Namely, the challenger performs the setup of the system by generating hk 1 , . . . , hk n using HashKG and defining hk 0 = -n i=1 hk i . Queries to the random oracle H are answered by returning uniformly random group elements in X . Encryption queries (i, τ, x i,τ ) for time period τ are answered by returning the ciphertext c i,τ = f (x i,τ ) • h i,τ with h i,τ = Hash(hk i , H(τ )). Whenever the adversary decides to corrupt some player i ∈ {0, . . . , n}, the challenger reveals hk i . In the challenge phase, the adversary chooses a target time period τ , an uncorrupted subset S ⊆ U , and two distinct series (i, τ , x

(0) i,τ ) i∈S , (i, τ , x (1)
i,τ ) i∈S that must sum up to the same value if S = U and the aggregator's private key sk 0 is exposed at some point of the game (see Section 2.1). At this stage, the challenger flips a fair binary coin b R ← {0, 1} and the adversary A receives

c i,τ = f (x (b) i,τ ) • h i,τ i∈S with h i,τ = Hash(hk i , H(τ )) .
We assume that the adversary queries H(τ ) before the challenge phase. Otherwise, B can simply make the query for itself. In the second phase, after a second series of queries, A outputs a bit b ∈ {0, 1}. We let the challenger B output 1 if b = b and 0 otherwise. The adversary's advantage in Game 0 is thus Adv

0 = 2 • | Pr[S 0 ] -1/2| = Adv AO (A).
Game 1. This game is identical to Game 0 with the following difference. For each random oracle query H(τ ), the challenger B flips a biased coin δ τ ∈ {0, 1} that takes the value 1 with probability 1/(q enc + 1) and the value 0 with probability q enc /(q enc + 1).

At the end of the game, B considers the event E that one of the following conditions holds:

-For the target time period τ , the coin δ τ flipped for the hash query H(τ ) was δ τ = 0. -There exists a time period τ = τ such that an encryption query (i, τ, .) was made for some user i ∈ U but for which δ τ = 1. If event E occurs (which B can detect at the end of the game), B halts and outputs a random bit. Otherwise, it outputs 1 if and only if b = b. An analysis similar to that in [START_REF] Coron | On the Exact Security of Full Domain Hash[END_REF]] shows that

Pr[¬E] = 1 q enc + 1 • q enc q enc + 1 qenc = 1 q enc + 1 1 - 1 q enc + 1 qenc ≥ 1 e (q enc + 1)
,

where e is the base for the natural logarithm. The transition from Game 0 to Game 1 is thus a transition based on a failure event of large probability [START_REF] Dent | A Note On Game-Hopping Proofs[END_REF]] and we therefore have

Adv 1 = Adv 0 • Pr[¬E] ≥ Adv 0 /(e(q enc + 1)).
Game 2. In this game, we modify the distribution of random oracle outputs. Specifically, the treatment of each hash query τ depends on the random coin δ τ ∈ {0, 1}.

-If δ τ = 0, the challenger B samples a random word y τ ∈ L together with a witness w τ , and defines H(τ ) = y τ ; this modification does not change anything. But it helps for the other games, as it enables the challenger to change the output of the adversary. It is straightforward to see that Game 2 and Game 1 are computationally indistinguishable if the hard subset-membership assumption holds. Namely, there exists a distinguisher B memb for the subset-membership problem of L with comparable running time and such that

| Pr[S 2 ] -Pr[S 1 ]| ≤ Adv memb T (B memb ) . Therefore Adv 1 ≤ Adv 2 + 2 • Adv memb T (B memb ).
Game 3. In this game, after the challenge query, if H(τ ) = y τ ∈ L, then B halts and outputs a random bit. We recall that, in the previous game, y τ was drawn uniformly at random from X (or B would already have stopped because of event E). Therefore

| Pr[S 3 ] -Pr[S 2 ]| ≤ |L|/|X | and Adv 2 ≤ Adv 3 + 2|L|/|X |.
Game 4. In this game, B generates hk i as hk i R ← K, for each i ∈ {1, . . . , n}, instead of using HashKG (note that B is not polynomially bounded in this game nor in the subsequent games). Therefore | Pr[S 4 ] -Pr[S 3 ]| ≤ n ε hk and Adv 3 ≤ Adv 4 + 2n ε hk .

Game 5. At the beginning of the game, the challenger picks a random index i ∈ {0, . . . , n} and at the end of the game, B considers event E that one of the following conditions holds:

-i = max S and i∈S x (0) i,τ = i∈S x (1) i,τ ; or
-i = max(U \ S ) and i∈S x (0) i,τ = i∈S x (1) i,τ , where U = U when the aggregator is corrupted, U ∪ {0} otherwise. Notice that when i∈S x (0) i,τ = i∈S x (1)
i,τ , the set U \ S cannot be empty, so that the previous definition makes sense. If event E occurs (which B can detect at the end of the game), B halts and outputs a random bit. Otherwise, it outputs 1 if and only if b = b. As for the transition from Game 0 to Game 1, the transition from Game 4 to Game 5 is a transition based on a failure event of large probability. We therefore have Adv 5 = Adv 4 • Pr[¬E ] = Adv 4 /(n + 1). Game 6. In this game, B picks hk i independently and uniformly at random in K, for i ∈ {0, . . . , n} \ {i }, and computes hk i = -i∈{0,...,n}\{i } hk i at the beginning of the game. For any time period τ , B computes h i ,τ as i∈{0,...,n}\{i } (h i,τ ) -1 . Furthermore, for any i ∈ U \ {i } and any time period τ = τ , B now computes h i,τ as ProjHash(hp i , y τ , w τ ) (with w τ a witness for y τ ∈ L), instead of Hash(hk i , y τ ). Game 6 is perfectly indistinguishable from Game 5 (thanks to the fact that hk 0 , . . . , hk n are, in both games, all chosen uniformly at random under the only condition that n i=0 hk i = 0, and thanks to key-homomorphism and correctness of the SPHF) and Adv 6 = Adv 5 .

Game 7. In this game, for all i ∈ U \ {i }, we set h i,τ = Hash(hk i , H(τ ))

• h i with h i R ← Π .
In other words, we have:

-if i∈S x (0) i,τ = i∈S x (1) i,τ , then h i,τ = Hash(hk i , H(τ )) • h i with h i R ← Π , for i ∈ S ⊆ U \ {i }; in this case, clearly, h i completely masks f (x (b) i,τ );
A New Framework for Privacy-Preserving Aggregation 10:13 -otherwise, then h i,τ = Hash(hk i , H(τ )) • h i with h i R ← Π for i ∈ S \ {i } ⊆ U \ {i }; and we have that, for any sequence (h i ) i∈S , there exists a unique sequence

(h i ) i∈S (with i∈S h i = i∈S h i = 1) that satisfies h i • f (x (0) i,τ ) = h i • f (x (1) i,τ ).
It is therefore clear that Pr[S 7 ] = 1/2, so that A has no advantage (Adv 7 = 0). In addition, Games 6 and 7 are statistically indistinguishable thanks to the special smoothness of the SPHF: | Pr[S 7 ] -Pr[S 6 ]| ≤ n ε s and so Adv 6 ≤ Adv 7 + 2n ε s .

Putting all together, we get

Adv AO (A) ≤ 2e (q enc + 1) • Adv memb (B) + n ε hk + |L| |X | + n(n + 1) ε s , which concludes the proof.

A concrete instantiation

An example of hard subset-membership language is the DDH language. We then have:

X = G × G , L = y = (y 1 , y 2 ) ∈ X | ∃w ∈ Z p such that R( y, w) = 1 with R( y, w) = 1 ⇐⇒ y 1 = g 1 w and y 2 = g 2 w ,
where g 1 and g 2 are two generators of a group G of prime order p. The hard subsetmembership assumption for this language is the DDH assumption.

For the DDH language, Cramer and Shoup construct an SPHF as follows. The key space is K = Z p × Z p and the hash range is Π = G. The hashing key is a random tuple hk = (s, t) ∈ K and the projection key is hp = g 1 s g 2 t . We then have:

Hash : K × X → Π, hk, (y 1 , y 2 ) → Hash hk, (y 1 , y 2 ) = y 1 s y 2 t
and, if w is a witness for (y 1 , y 2 ), i.e., y 1 = g 1 w and y 2 = g 2 w ,

ProjHash : G × X × Z p → Π, hp, (y 1 , y 2 ), w → ProjHash hp, (y 1 , y 2 ), w = hp w .

This SPHF is (0, Π)-smooth (see [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF]). It is readily seen that this SPHF is key-homomorphic and 0-key-uniform. If we set f : Z p → Π, x → f (x) = g x (where g is a generator of G), which clearly is an injective group homomorphism, we get exactly our DDH-based scheme of Section 3. Observe also that plugging ε hk = ε s = 0, |X | = p 2 , and |L| = p in Theorem 4.3 yields the statement of Theorem 3.2.

FURTHER INSTANTIATIONS

k-linear assumption and generalizations

In [2013], Escala et al. generalize the k-LIN assumptions [START_REF] Boneh | Short Group Signatures[END_REF][START_REF] Hofheinz | Secure Hybrid Encryption from Weakened Key Encapsulation[END_REF][START_REF] Shacham | A Cramer-Shoup Encryption Scheme from the Linear Assumption and from Progressively Weaker Linear Variants[END_REF]] in an assumption called MDDH. They also show how to construct an SPHF from any MDDH assumption. Their construction can be used directly in our framework, with f (x) = g x (which is invertible for x in small ranges), since their SPHFs are clearly key-homomorphic and 0-key-uniform. This yields in particular an aggregator oblivious encryption scheme from the k-LIN assumption.

When k = 1, since 1-LIN = DDH, we get exactly the new scheme presented in Section 3. A larger value of k implies a weaker assumption: indeed, the k-LIN assumption is implied by the (k -1)-LIN assumption for any k > 1, as shown in [START_REF] Hofheinz | Secure Hybrid Encryption from Weakened Key Encapsulation[END_REF][START_REF] Shacham | A Cramer-Shoup Encryption Scheme from the Linear Assumption and from Progressively Weaker Linear Variants[END_REF]. The disadvantage of a larger k is an increase of the private-key size, which has to be multiplied by (k + 1)/2. However, other parameter sizes given in Table I remain unchanged. In particular, increasing k does not affect the ciphertext size, which is unusual for encryption schemes based on the k-LIN assumption.

Subgroup Decision (SD) assumption

Yet another instantiation can be derived from the subgroup decision (SD) assumption (for cyclic groups of composite order, without pairing) as introduced by [START_REF] Boneh | Evaluating 2-DNF Formulas on Ciphertexts[END_REF].

Let N = pq be an RSA modulus with p and q two large primes. Let G = g be a cyclic group of order N , G p = g p be the subgroup of order p, and G q = g q be the subgroup of order q. Define X = G, L = G p , K = Z N , Π = G, and Π = G q . A witness w for y ∈ L is a discrete logarithm of y in base g p , y = g p w . Then set:

-for any y ∈ X , Hash(hk, y) = y r , and for any y ∈ L, ProjHash(hp, y, w) = hp w with w a witness for y such that y = g p w , for hk = r R ← K and hp = g p hk ; f (x) = g q x for x ∈ Z q .

The so-obtained SPHF is (0, Π )-smooth, 0-key-uniform, and key-homomorphic.

DCR assumption

Paillier's decision composite residuosity (DCR) assumption [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF]] can also be used to instantiate a slight variant of general framework. The resulting aggregator-oblivious encryption scheme shares many similarities with the Joye-Libert's construction in [START_REF] Joye | A Scalable Scheme for Privacy-Preserving Aggregation of Time-Series Data[END_REF] but it is not strictly the same scheme. We rely on a variant of the hash proof system proposed by [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF], with inefficient ProjKG and ProjHash. Let N = pq be an RSA modulus where p and q are two distinct primes. Define

X = (Z N 2 ) * , L = {y = z N | z ∈ X } ⊂ X , K = Z N φ(N ) , Π = X , Π = 1 + N ⊂ Π ,
and set -For any y ∈ X , Hash(hk, y) = y r , and for any y ∈ L, ProjHash(hp, y, ⊥) = y hp , where the hashing key is chosen as hk = r R ← {-2 κ N 2 , . . . , 2 κ N 2 } (with κ depending on the expected security -see below) and hp = r mod φ(N ) -since φ(N ) is unknown (otherwise the language is not hard subset membership), note that hp cannot be efficiently computed;

-f (x) = (1 + N ) x ∈ Π for x ∈ Z N .
If we set K = Z N φ(N ) and identify hashing keys hk ∈ {-2 κ N 2 , . . . , 2 κ N 2 } as elements of K, the resulting SPHF is clearly key-homomorphic. Furthermore, r mod N φ(N ) is 1/2 κ+1 -statistically close from the uniform distribution over K. Since if r R ← K would lead to a (0, Π )-smooth SPHF, the actual resulting SPHF is (1/2 κ+1 , Π )-smooth. As shown in Appendix B, the corresponding scheme provably meets the notion of aggregator obliviousness. We have the following theorem: THEOREM 5.1. The scheme provides AO security under the DCR assumption in the random oracle model. Specifically, for any probabilistic polynomial-time adversary A, there exists a DCR distinguisher B DCR with comparable running time and such that

Adv AO (A) ≤ 2e (q enc + 1) • Adv DCR (B) + n(n + 1) 2 κ+1 + 1 φ(N ) ,
where n is the number of users, q enc is the number of encryption queries made by the adversary for distinct time periods other than τ , and e is the base for the natural logarithm.

following probability distributions (for j = 0, . . . , m):

D j = (hk 0 , hp 1 , hk 1 , . . . , hp m , hk m , hk m +1 , . . . , hk n-1 ) | hk 1 , . . . , hk n R ← {-2 κ N 2 , . . . , 2 κ N 2 }, hk 0 ← - n i=1 hk i , hk 1 R ← K, . . . , hk j R ← K, hk j+1 = hk j+1 mod N φ(N ), . . . , hk m = hk m mod N φ(N ) such that hp 1 = hk 1 mod φ(N ) = hk 1 mod φ(N ), . . . , hp m = hk m mod φ(N ) = hk m mod φ(N ) .
When all these variables are drawn from distibution D 0 , we get Game 5, while when they are drawn from distribution D m , we get Game 6.

To do that, we use the following lemma:

LEMMA B.1. Let M, N , N be three integers, with M ≥ N N and N coprime with N . Let X, Y be two random uniform random variables in {-M, . . . , M }, and X be a uniform random variable in {0, . . . , N -1}. If we suppose that X, Y, X are mutually independent, then the statistical distance between the distribution of (X mod N , X mod N , X + Y ) and of (X , X mod N , X + Y ) is at most N (N +1) 2(2M +1) .

PROOF OF LEMMA B.1. This statistical distance is

1 2 x ∈{0,...,N -1} x ∈{0,...,N -1} z∈{-2M,...,2M } Pr[X mod N = x , X mod N = x , X + Y = z] - Pr[X = x , X mod N = x , X + Y = z] .
We have X , X, Y are mutually independent, so

Pr[X = x , X mod N = x , X + Y = z] = x∈{-M,...,M } such that x mod N =x Pr[X = x ] • Pr[X mod N = x, X + Y = z] = x∈{-M,...,M } such that x mod N =x 1 N • Pr[X mod N = x , Y = z -x] = n x N (2M + 1) 2
where n x is the number of values x ∈ {-M, . . . , M } such that x mod N = x and z -x ∈ {-M, . . . , M }. There are 2M + 1 -|z| values x such that z -x ∈ {-M, . . . , M }, namely -M, . . . , M + z if z ≤ 0, and -M + z, . . . , M if z ≥ 0. Among these values either (2M + 1 -|z|)/N or (2M + 1 -|z|)/N + 1 of them are such that x mod N = x . Therefore, we have:

(2M + 1 -|z|) N -1 ≤ n x ≤ (2M + 1 -|z|) N + 1.
A New Framework for Privacy-Preserving Aggregation 10:19

Moreover, we have

Pr[X mod N = x , X mod N = x , X + Y = z] = x∈{-M,...,M } such that x mod N =x and x mod N =x Pr[X mod N = x , X mod N = x , X + Y = z] = x∈{-M,...,M } such that x mod N =x and x mod N =x Pr[X mod N = x , X mod N = x , Y = z -x] = n x ,x (2M + 1) 2
where n x ,x is the number of values x ∈ {-M, . . . , M } such that x mod N = x and x mod N = x and z -x ∈ {-M, . . . , M }. There are 2M + 1 -|z| values x such that z -x ∈ {-M, . . . , M }, namely -M, . . . , M + z if z ≤ 0, and -M + z, . . . , M if z ≥ 0. Among these values either (2M + 1 -|z|)/(N N ) or (2M + 1 -|z|)/(N N ) + 1 of them are such that x mod N = x and x mod N = x , as N and N are coprime, and thanks to the CRT. Therefore, we have:

(2M + 1 -|z|) N N -1 ≤ n x ,x ≤ (2M + 1 -|z|) N N + 1 .
Thus, the statistical distance satisfies 1 2

x ,x ,z

n x N (2M + 1) 2 - n x ,x (2M + 1) 2 = 1 2 x ,x ,z 1 (2M + 1) 2 n x N -n x ≤ 1 2
x ,x ,z 1 (2M + 1) 2 1 + 1 N ≤ N (N + 1) 2(2M + 1) .

This concludes the proof of the lemma.

We use the lemma with M = 2 κ N 2 , N = N , and N = φ(N ). For any integers x ∈ {0, . . . , N -1} and x ∈ {0, . . . , N -1}, let us denote by x = CRT(x , x ) the unique integer x ∈ {0, . . . , N N -1} such that x mod N = x and x mod N = x . Then, in D j-1 , we remark that hk j , hp j , hk j , hk n , and hk 0 can alternatively be defined as: We remark that if sk i1 or sk i2 is valid, B would behave exactly as an all powerful (non polynomially bounded) adversary A which would do the same as B, except it does not perform any rewinding (and so never corrupts sk i1 and sk i2 ), and instead computes sk i1 and sk i2 simply by trying all possible values. This is true thanks to the check with sk 0 which ensures that if c i1,2 is an encryption of 0 (respectively, 1), then c i2,2 is an encryption of 1 (respectively, 0), and so knowing only one of sk i1 and sk i2 is sufficient. In addition, if any sk i for some i / ∈ {i 1 , i 2 } (obtained after the last rewinding for B) is not valid, both A and B abort. Therefore, A and B behave identically, except if all secret keys sk i (for i / ∈ {i 1 , i 2 }) are valid (after the last rewinding for B) but B cannot find a valid key sk i1 or a valid key sk i2 among all keys it got from all the rewindings. We call 'bad case' the case where the previous bad event happens, and let ε bad the probability of this event.

hk j = X
The advantage of A (to break the aggregator obliviousness) is exactly Adv A = 2ε A -1, since when A plays against the real challenger for the aggregator obliviousness, A never aborts, and the bit b computed by A is always equal to b, the bit chosen in the game, hence b = b with probability ε A . In the bad case, B outputs b = b with probability 1/2 instead of ε A for A, while outside the bad case, B and A output b = b with the same probability. Therefore, when playing with B, the reduction solves the original hard problem with probability at least:

ε R -ε bad • |ε A -1/2| = ε R -ε bad • Adv A /2
which in term of advantage (if the reduction solves a decisional problem) is

2 ε R -ε bad ε A -1 2 -1 = (2ε R -1) -ε bad |2ε A -1| = Adv R -ε bad • Adv A .
This has to be negligible, otherwise the hard problem would not be hard. Therefore, ε R or Adv R cannot be larger than ε bad • Adv A /2 or ε bad • Adv A (minus some negligible factor in the security parameter). We just need to prove that ε bad ≥ 2/(n(n -1)), to show our impossibility result.

For that purpose, for any integers j 1 and j 2 , let E j1,j2 denote the event that, when the secret keys sk i for i ∈ {1, . . . , n} \ {j 1 , j 2 } are corrupted, the secret keys given by the reduction are all valid. We clearly have:

ε bad ≤ Pr   E i1,i2 ∧ {i3,i4} ={i1,i2} ¬E i3,i4   ,
since if E i3,i4 is true for some {i 3 , i 4 } = {i 1 , i 2 } (i 3 = i 4 ), then i 1 / ∈ {i 3 , i 4 } or i 2 / ∈ {i 3 , i 4 }, and we get a valid secret key sk i1 or sk i2 . If we fix everything except the choice of i 1 and i 2 , each event E i3,i4 is either satisfied (it has probability 1) or not satisfied (it has probability 0). If two distinct event E i5,i6 and E i 5 ,i 6 are satisfied, the event {i3,i4} ={i1,i2} ¬E i3,i4 never happens and ε bad = 0. If no event is satisfied, the event E i1,i2 never happens and ε bad = 0. Finally, if only one event E i5,i6 is satisfied, E i1,i2 ∧ ( {i3,i4} ={i1,i2} ¬E i3,i4 ) happens only when {i 1 , i 2 } = {i 5 , i 6 }, which happens with probability 2/(n(n -1)). Therefore, ε bad ≤ 2/(n(n -1)).

  X if b = 0, and a uniformly random element in L if b = 1. At the end of the game, the attacker outputs a bit b and wins the game if and only if b = b. Definition 4.1. A subset-membership problem is hard if, in the previous game, the advantage, which is defined as Adv memb qm (A) := 2 Pr[b = b] -1/2 , is negligible for any probabilistic polynomial-time attacker A.

-

  If δ τ = 1, B samples a word y τ ∈ X and defines H(τ ) = y τ .

R

  ← {-M, . . . , M } (not actually used in the distribution directly)hp j = X mod N hk j = hk j mod N N = CRT(X mod N , X mod N ) hk n = Y R ← {-M, . . . , M } hk 0 = -i∈{1,...,n-1}\{j} hk i -(X + Y ) ,sk i1 and if Enc(param, sk i1 , 2, 0) = c i1,2 , B sets b = 0; if B got a valid secret key sk i2 and Enc(param, sk i2 , 2, 1) = c i2,1 , B sets b = 0; otherwise, B sets b = 1. And B outputs b = b with probability ε A and b = 1 -b otherwise.

Table I ,

 I SHA-512 for hashing, 24-bit x i,τ , and Xτ in a pre-determined 24-bit range, on an Intel TM Core i5 750 with MIRACL TM library https://github.com/CertiVox/MIRACL, Jun 20, 2013) Computation of H(τ ) or H 1 (τ ) and H 2 (τ ); b Computation of c i,τ , excluding computation of H(τ )/H 1 (τ )/H 2 (τ ); c Computation of Vτ from (c i,τ ), excluding computation of H(τ )/H 1 (τ )/H 2 (τ ); d Computation of Xτ from Vτ (we used a variant of the Pollard's kangaroo (or λ) method described in[START_REF] Montenegro | How long does it take to catch a wild kangaroo?[END_REF]).

			Time (ms)
	Scheme	Hashing a	Encryption b	First phase of decryption c	Second phase of decryption d
	[Shi et al. 2011]	0.23 (±0.01)	5.5 (±0.1)	11.3 (±0.0)	192 (±20)
	[Joye and Libert 2013]	0.01 (±0.00)	58.3 (±0.5)	45.5 (±0.0)	0.0 (±0.0)
	Our basic scheme	0.23 (±0.01)	2.6 (±0.1)	6.9 (±0.0)	126 (±13)

a

ACM Transactions on Information and System Security, Vol. 18, No. 3, Article 10, Publication date: February 2016.

By "comparable running time", we mean that B DDH 's running time exceeds that of A by a small additive term (rather than a multiplicative factor) which only depends on the security parameter and the number of queries, but not on A's running time. More precisely, B DDH 's running time roughly amounts to the running time of A plus O(q H + qenc) group exponentiations, where q H is the number of queries to the random oracle.ACM Transactions on Information and System Security, Vol. 18, No. 3, Article 10, Publication date: February

In the proof, the output b ∈ {0, 1} of the adversary A is not directly the output of the game, but is first given to the challenger which then outputs a bit. For Game 0, which corresponds to the AO security notion, ACM Transactions on Information and System Security, Vol. 18, No. 3, Article 10, Publication date: February 2016.

This work was supported in part by "Programme Avenir Lyon Saint-Etienne de l'Université de Lyon" in the framework of the French program "Investissements d'Avenir" (ANR-11-IDEX-0007) and the CFM Foundation. Part of this work was done while the third author was in Technicolor (France).

A. AO ENCRYPTION SCHEMES

For completeness, we review in this appendix the two known constructions for aggregator-oblivious encryption [START_REF] Shi | Privacy-Preserving Aggregation of Time-Series Data[END_REF][START_REF] Joye | A Scalable Scheme for Privacy-Preserving Aggregation of Time-Series Data[END_REF].

A.1. Shi et al.'s scheme

Setup(1 λ ). Let G be a group of prime order p for which the DDH assumption holds, and let a random generator g ∈ G. Let also H : Z → G be a hash function viewed as a random oracle. Finally, let n random elements in Z p , s 1 , . . . , s n , and define s 0 = -n i=1 s i mod p. The system parameters are param = {G, g, H} and the secret key of user i, 0 ≤ i ≤ n, is sk i = s i . Enc(param, sk i , τ, x i,τ ). At time period τ , for a private input x i,τ ∈ Z p , user i produces

AggrDec(param, sk 0 , τ, c 1,τ , . . . , c n,τ ). The aggregator obtains the sum X τ for time period τ by first computing V τ := H(τ ) s0 n i=1 c i,τ = g Xτ and next the discrete logarithm of V τ w.r.t. basis g.

[Notice that since g has order p, the so-obtained value for X τ is defined modulo M = p.]

A.2. Joye-Libert's scheme

Setup(1 λ ). Let M = N = pq be an RSA modulus of length , i.e., a product of two random equal-size primes p, q. Note that the size condition on p and q implies that gcd(φ(N ), N ) = 1. Let also H : Z → Z * N 2 be a hash function viewed as a random oracle. Finally let s 1 , . . . , s n be n randomly chosen elements in ±{0, 1} 2 , and define s 0 = -n i=1 s i .

10:17

The system parameters are param = {N, H} and the secret key of user i, 0 ≤ i ≤ n, is sk i = s i . Enc(param, sk i , τ, x i,τ ). At time period τ , for a private input x i,τ ∈ Z N , user i produces

AggrDec(param, sk 0 , τ, c 1,τ , . . . , c n,τ ). The aggregator obtains the sum X τ for time period τ by first computing V t := H(τ ) s0 n i=1 c i,τ mod N 2 and next X τ as X τ = Vτ -1 N .

[Notice that since (1 + N ) has order N and (1 + x i,τ N ) ≡ (1 + N ) xi,τ (mod N 2 ), the so-obtained value for X τ is defined modulo M = N .]

B. DEFERRED PROOF OF OUR DCR INSTANTIATION

The proof of our DCR instantiation in Section 5.3 (Theorem 5.1) is similar to the proof of Theorem 4.3 but not exactly the same, since the scheme is not key-uniform (as hashing keys have multiple representations), and hk 0 is the opposite of the sum of the hk i over the integers and not in the group

Again, we do a proof by games. We use the same first four games: Game 0 to Game 3. Then, as the SPHF is not key-uniform, we just skip Game 4 and go directly to Game 5 (except now, in this game, we suppose that hk R ← {-2 κ N 2 , . . . , 2 κ N 2 } and that hk 0 = n i=1 hk i over the integers). The problem, is that, when i = 0, it is no more true that Game 6 is indistinguishable from Game 5: B cannot pick hk i independently and uniformly at random in K (or even in {-2 κ N 2 , . . . , 2 κ N 2 }), for i ∈ {0, . . . , n} \ {i } and cannot compute hk i as -i∈{0,...,n}\{i } hk i , because hk 0 is not uniform in K nor in {-2 κ N 2 , . . . , 2 κ N 2 }, as it is the sum of the hk i over the integers.

We remark however, that if i = 0, the adversary nevers sees hk 0 , and if in Game 6, B picks hk i independently and uniformly at random in {-2 κ N 2 , . . . , 2 κ N 2 }), for i ∈ {0, . . . , n} \ {i } and computes hk i = hk 0 as -i∈{0,...,n}\{i } hk i over the integers, then the proof still works and Adv 5 ≤ Adv 6 + 2nε s ≤ n/2 κ .

We now focus on the difficult case i = 0. We use the following Game 6: B picks hk 1 , . . . , hk n uniformly at random in {-2 κ N 2 , . . . , 2 κ N 2 } and set hk 0 = -i∈{1,...,n} hk i over the integers (as in Game 5). However, as in the original Game 6 and contrary to Game 5, B computes h i ,τ as i∈{0,...,n}\{i } h -1 i,τ (which is perfectly indistinguishable). Furthermore, for any i ∈ S \ {i }, B computes h i,τ as Hash(hk i , y τ ), with hk i a random hashing key in K corresponding to the same projection key hp i as hk i , or in other words:

but hk i mod N and hk i mod N are independent (and uniformly random). We remark that h i,τ = Hash(hk i , y τ ) = y hk i τ could also be computed as (in the case of the SPHF that we consider):

Therefore, Game 6 (in this proof) is actually similar to Game 7 in the original proof, and A has no advantage in this game: Adv 6 = 0.

To conclude the proof, we just need to prove that Game 6 is statistically indistinguishable from Game 5. We suppose w.l.o.g. that S \ {i } = {1, . . . , m }, where m = m < n if i / ∈ S and m = m -1 < n otherwise. We also suppose that i = n. We first remark that for any i ∈ S \ {i } and for any time period τ = τ , H i,τ can be computed from hp i = hk i mod φ(N ) and hk i is only used to compute hk 0 . Define the 10:20 F. Benhamouda, M. Joye, and B. Libert while in D j , these random variables can alternatively be defined as:

. . , M } (not actually used in the distribution directly)

Back to the theorem, thanks to Lemma B.1, we can conclude D j-1 and D j are (N + 1)N /(2(2M + 1))-close, and the statistical distance between D 0 and D n is at most:

Therefore, Adv 5 ≤ Adv 6 + n/2 κ .

C. IMPOSSIBILITY RESULT OF TIGHTNESS FOR A PREVIOUS SCHEME

We now show that any blackbox non-rewinding reduction from the aggregator obliviousness of Shi et al.'s scheme in [2011] to a non-interactive problem loses a factor of at least n 2 . This bound cannot be improved in the Shi et al.'s scheme. This impossibility result is shown by outlining a meta-reduction (that is, a reduction against the reduction) as in [START_REF] Coron | Optimal Security Proofs for PSS and Other Signature Schemes[END_REF]]. The idea is to show that any reduction losing a factor better than (about) n 2 can be converted into an adversary for the original hard problem, by constructing an adversary B which acts as an adversary for the reduction but which can also rewind the reduction.

The basic idea is that, in the scheme of Shi et al., sk i is completely defined (from the information theory viewpoint) when a ciphertext c i,1 for 0 (for example) is given; and sk 0 is defined by (c i,1 ) i∈{1,...,n} .

More precisely, suppose that the reduction can solve the original hard problem with probability ε R , when playing with any adversary breaking the aggregator obliviousness with advantage 2ε A -1. We construct an adversary B (which has the right to rewind the reduction) as follows: B will first ask for the aggregator secret key sk 0 and for ciphertexts c i,1 of 0 for time period 1 (and for each user i). It can check that any secret key sk i given by the reduction is valid or not (for each user i), with respect to c i,1 (by checking that Enc(param, sk i , 1, 0) = c i,τ ) and that sk 0 is valid (by checking that AggrDec(param, sk 0 , 1, c 1,1 , . . . , c n,1 ) = 0). Then it will choose two random users i 1 = i 2 . For all pairs of distinct users {i 3 , i 4 } = {i 1 , i 2 }, it then asks all the secret keys sk i (in an arbitrary order) except i 3 and i 4 , store them, and then rewind the adversary just after the corruption of sk 0 -B therefore rewinds the reduction (n -1)(n -2)/2 times (one for each pair {i 3 , i 4 } = {i 1 , i 2 }). After that, B will have stored (n -1)(n -2)/2 keys sk i1 and (n -1)(n -2)/2 keys sk i2 . If any of them are invalid, B aborts and returns b = 0 with probability 1/2, and b = 1 otherwise.

Otherwise, B then asks all the secret keys sk i except for i 1 and i 2 . If none of them are valid, B aborts and returns b = 0 with probability 1/2, and b = 1 otherwise. Otherwise, it just submits the challenge: S = {i 1 , i 2 }, τ = 2, (x (1) i2,2 . And B will check that these ciphertexts are coherent with sk 0 , by computing c i,2 = Enc(param, sk i , 2, 0) for all i / ∈ {i 1 , i 2 }, and checking that AggrDec(param, sk 0 , 2, c 1,2 , . . . , c n,2 ) = 1. Finally, if B got a valid secret key


Alain Audouard

Jean-Yves Fortin

David Vignolles

Vladimir N Laukhin

Nataliya D Kushch

Eduard B Yagubskii

la diffusion de documents scientifiques de niveau

Keywords: Organic superconductors, high magnetic fields, quantum oscillations, Fermi surface

recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

New insights on frequency combinations and 'forbidden frequencies' in de Haas-van Alphen spectrum of κ-(ET)

2 Cu(SCN) 2

I. INTRODUCTION

The family of organic charge transfer salts κ-(ET) 2 X, where ET stands for the bis(ethylenedithio)tetrathiafulvalene molecule and X is a monovalent cation, arouses interest for many years. Indeed, its members can be classified in a very rich phase diagram including ground states ranging from Mott insulator to superconductor [1,2]. κ-(ET) 2 Cu(SCN) 2 , which has been synthesized as early as 1988 [3], is on the metallic side of this phase diagram and is still one of the most studied organic superconductor. Illustrating this long-standing interest, the existence of a Fulde-Ferrell-Larkin-Ovchinnikov inhomogeneous superconducting state in this salt, considered more than 20 years ago for low dimensional conductors [4,5], have received first experimental hints in the early 2000s [6] and have been recently confirmed [7].

Remarkably, the Fermi surface of κ-(ET) 2 Cu(SCN) 2 [8][9][10] (see Fig. 1) is the first experimental realization of the model Fermi surface proposed by Pippard in the early sixties to compute the effect of magnetic breakdown (MB) in multiband metals [11]. Both Shubnikovde Haas (SdH) [12][START_REF] Müller | The Physics and Chemistry of Organic Superconductors[END_REF][START_REF] Sasaki | [END_REF][15][16][17][18][19] and de Haas-van Alphen (dHvA) [20][21][22][23][24] oscillations have been widely

studied in this compound. Provided the magnetic field strength is high enough to overcome the MB gap between the α orbit and the quasi one-dimensional sheets, linear combinations of the frequencies linked to the α and MB-induced β orbits are observed in the oscillatory spectrum (for a review see e.g. [START_REF] Uji | The Physics of Organic Superconductors and Conductors[END_REF]), as expected in the framework of the coupled orbits network model of Falicov-Stachowiak [27]. Within this model, the frequency F η of any Fourier component can be expressed as F η = n α F α + n β F β where n α(β) is an integer and F α(β) is the frequency linked to the α(β) orbit. With the exception of quantum interference (QI), which only holds for magnetoresistance, and for which the effective mass is the difference between the partial effective mass of each QI path [28], the effective mass m η is given by

m η = n α m α + n β m β .
However, limiting ourselves to dHvA data, the field and temperature dependence of few of the observed Fourier components does not behave consistently with this model. For example, the effective masses linked to 2α and 2β, determined in the framework of the Lifshitz-Kosevich model [START_REF] Shoenberg | Magnetic Oscillations in Metals[END_REF], are strongly different from 2m α and 2m β , respectively [22]. In addition, puzzling data are reported regarding the component β + α which corresponds to a MB orbit. Indeed, even though according to [21] m β+α is equal to m β +m α within the error bars, in agreement with the Falicov-Stachowiak model, this relation cannot account for the data of [22,23] for which m β+α is definitely smaller than the sum m β + m α (see [START_REF] Audouard | [END_REF] for a discussion of this feature). In addition to all this, the most striking discrepancy between the Falicov-Stachowiak model and the dHvA data (for which QI is not relevant since dHvA is only sensitive to the density of states) is the presence of the Fourier components βα and 2(βα), known as 'forbidden frequencies' which cannot correspond to closed orbits (for a review, see [START_REF] Uji | The Physics of Organic Superconductors and Conductors[END_REF]31]).

These features have been addressed in the case of θ-phase salts belonging to the family θ-(ET) 4 MBr 4 (C 6 H 4 Cl 2 ) for M = Co, Zn [START_REF] Audouard | [END_REF]32,33] which share with κ-(ET) 2 Cu(SCN) 2 the same Fermi surface topology. Briefly, the strong two-dimensionality of these compounds is responsible for a significant oscillation of the chemical potential in magnetic field which requires a calculation of the free energy (canonical ensemble) up to the second-order in damping factors. In few cases, the first order term of the oscillatory magnetization, which corresponds to the usual Lifshitz-Kosevich formula [START_REF] Shoenberg | Magnetic Oscillations in Metals[END_REF], may have a smaller contribution to the amplitude of the Fourier components linked to MB orbits than the second order term. Moreover, the second order term solely accounts for the 'forbidden frequencies'. A very good quantitative agreement between these calculations and the reported dHvA data is observed. Nevertheless, as pointed out in [START_REF] Audouard | [END_REF], data analysis relevant to other salts, with different physical parameters, such as effective masses, MB field, etc., are required.

Therefore, the aim of this paper is to report on dHvA data of κ-(ET) 2 Cu(SCN) 2 at high magnetic field. It is confirmed that the usual Lifshitz-Kosevich formalism cannot account for few of the Fourier component amplitudes such as 2α and, obviously, βα. In contrast, it is demonstrated that the above mentioned second order development holds for all the observed Fourier components.

II. EXPERIMENTAL

The studied crystal, with approximate dimensions 0.1 × 0.1 × 0.04 mm 3 , was synthesized by electrocrystallization technique. Magnetic torque measurements were performed in pulsed magnetic fields of up to 55 T with pulse decay duration of 0.36 s, in the temperature range from 1.7 K to 4.2 K. The angle between the magnetic field direction and the normal to the conducting plane was θ = 20 • . Fig. 1(a) displays magnetic torque data at 1.7 K. As expected, a strong hysteresis is observed in the superconducting state at low field due to flow of magnetic flux either into or out of the crystal as the field either increases or decreases [34]. In contrast, data for up and down fields are indiscernible from each other in the range where oscillations are observed. This result indicates that any temperature change due to eventual eddy currents is negligible. In addition, torque interaction effect might have been considered since, due to magnetic torque, θ angle is liable to change during the field sweep for small cantilever stiffness and (or) high θ value [35]. In the present case, θ changes are always smaller than 0.1 • , leading to negligibly small amplitude and frequency changes of at most 0.2 % at the highest fields explored. In the following, only data recorded during the decreasing part of the field is therefore considered. Analysis of the oscillatory part of the magnetic torque is based on discrete Fourier transforms of the data, after substraction of a smoothly varying background, calculated with a Blackman window.

III. RESULTS AND DISCUSSION

The high field range of the oscillatory part of the torque data is displayed in Fig. 1(a). As expected, corresponding Fourier analysis reveals several components, of which the frequencies are linear combinations of F α and F β . Owing to the tilt angle θ= 20 • , these frequencies are F α (θ = 0) = 0.600(1) kT and F β (θ = 0) = 3.861 (7) kT. These values are in good agreement with the data of the literature [12][START_REF] Müller | The Physics and Chemistry of Organic Superconductors[END_REF][START_REF] Sasaki | [END_REF][15][16][17][18][19][20][21][22][23][24] in which values in the range F α (θ = 0) = 0.596(2)-0.670(4) kT and F β (θ = 0) = 3.8-3.923 (9) kT are reported. The corresponding α orbit area amounts to 16 % of the first Brillouin zone area, in agreement with both previous experimental data and band structure calculations [8][9][10].

According to the calculations reported in Refs. [START_REF] Audouard | [END_REF]32,33], the amplitude of the basic α and β Fourier components, up to second order in damping factors, is accounted for by:

A α = - F α πm α R α,1 - F α πm β 1 2 R α,1 R α,2 + 1 6 R α,2 R α,3 + 2R β,1 R β+α,1 + 1 2 R β,2 R 2β-α,1 (1)
and

A β = - F β πm β R β,1 - F β πm β 1 2 R β,1 R β,2 + 1 6 R β,2 R β,3 + 2R α,1 R β+α,1 + 2R β,1 R 2β,1 , (2)
respectively. Damping factors can be expressed as R η,p (B, T ) =

R T η,p (B, T )R D η,p (B)R M B η,p (B)R s η,p
, where η stands either for α or β and p is the har- monic number. For a two-dimensional Fermi surface, the thermal, Dingle, MB and spin damping factors are expressed as R T η,p = pu η sinh -1 (pu η ), R D η,p = exp(-pu 0 m η T Dη /B cos θ), R M B η,p = (ip 0 ) n t η (q 0 ) n r η and R s η,p = cos(πg * η m η /2 cos θ), respectively [START_REF] Shoenberg | Magnetic Oscillations in Metals[END_REF]. The parameter (u η ) and the constant (u 0 ) are expressed as u η = u 0 m η T /B cos θ and u 0 = 2π 2 k B m e (e ) -1 = 14.694 T/K. T Dη is the Dingle temperature defined by T D = (2πk B τ ) -1 , where τ -1 is the scattering rate. m η and g η are the effective mass (in m e units) and effective Landé factor, respectively. The MB damping factor involves the number of tunnelings (n t η ) and reflections (n r η ) encountered by a quasiparticle traveling the orbit. The corresponding probabilities, p 0 and q 0 =(1 -p 2 0 ) 1/2 , respectively, are given by the Chambers formula which involve the magnetic breakdown field B 0 : p 2 0 = e -B 0 /B cos θ [START_REF] Chambers | Magnetic breakdown in real metals[END_REF]. The first order term of these equations just corresponds to the Lifshitz-Kosevich formula.

Besides, provided that the spin damping factors R s α(β) are not too small (i.e. m η g η / cos θ) is not close to an odd integer), the second order term is negligible [START_REF] Audouard | [END_REF]. This point, which can be checked a posteriori, allows us to perform the data analysis relevant to α and β in the framework of Lifshitz-Kosevich formula. Nevertheless, even though the spin damping factors act as constant prefactors in this case, 5 parameters are still involved, namely m α , m β , T Dα , T Dβ and B 0 . For this reason, it is assumed in the following that the Dingle temperature is the same for the α and β orbits (T Dα =T Dβ =T D ). Finally, it must be kept in mind that the magnetic torque amplitudes A τ η are related to the dHvA amplitude by A τ η = τ 0 BA η where τ 0 is a prefactor depending on the crystal mass, cantilever stiffness and tilt angle θ.

Dingle plots relevant to the α and β orbits are displayed in Fig. 2. A good agreement between the data and the calculations is obtained with m α = 3.07(4), m β = 6.03 (11), T D = 0.87(6) K and B 0 = 16(8) T. The effective mass values are within the range of the data reported in the literature in which m α and m β ranging from 3 to 3.6 and 5.6 to 7.1, respectively, can be found. In line with statement of Ref. [37], m β /m α = 2 within the error bars.

It can be noticed that the MB field B 0 is obtained with a large uncertainty. This feature, can be explained considering that, in addition to an increase of the Dingle plot slope relevant to the β orbit, the main discernible effect of MB is to induce a curvature in the field dependence of the α amplitude. However, this curvature remains small in the explored field range which yields a large uncertainty. This uncertainty is reflected in the strong scattering of the previously reported experimental data which yield B 0 values (themselves with large uncertainties) in the range from 15 T to 45 T [17,18,21,22,24,25].

Data relevant to frequency combinations are reported in Fig. 3. Let us consider first the component 2α, the amplitude of which is given by

A 2α = - F α 2πm α R α,2 + F α πm β R 2 α,1 - 2 3 R α,1 R α,3 -R β,2 R β+α,2 . (3)
The first order term of Eq. 3, involving R α,2 , corresponds to the Lifshitz formula. The second order term is dominated by the factor involving R 2 α,1 . Putting aside the spin damping factors, R 2 α,1 is strictly equal to R α,2 as the ratio B/T goes to zero. In the explored high field range, R 2 α,1 takes even larger values than R α,2 . As a consequence, both the first and second order terms contribute to the amplitude. Hence, the two involved spin damping factors, R s α,2 and R s α,1 , must be taken into account. Solid lines in Fig. 3(a) are best fits of Eq. 3. They are obtained with the same effective masses, Dingle temperature and magnetic breakdown field as for the data relevant to α and β (see Fig. 2) and with g α = 1.73 (5). This latter value is slightly larger than deduced from the angle dependence of the α oscillations (g α = 1.63(8) [21]). Nevertheless, it can be remarked that the product g α m α = 5.6(2), governing the spin damping factor is close to the value, g α m α = 5.2 (5), obtained in Ref. [21]. Strikingly, it can be observed that the second order term has a dominant contribution to the amplitude of the component 2α.

Similar considerations hold for 2β. Indeed, its amplitude is accounted for by

A 2β = - F β 2πm β [R β,2 + 2R 2β,1 ] + F β πm β R 2 β,1 - 2 3 R β,1 R β,3 - 1 4 R β,2 R β,4 -R α,2 R β+α,2 (4)
+ 2R α,1 R 2β-α,1 -R β,2 R 2β,2 -R β,4 R 2β,1 ].
The Lifshitz-Kosevich contribution arises from both the magnetic breakdown orbit 2β involving 4 tunneling and 2 reflections and the second harmonics of β governed by R 2β,1

and R β,2 , respectively (see [START_REF] Audouard | [END_REF] for a discussion of this point). The factors R 2 β,1 , and to a less extent R α,1 R 2β-α,1 , appearing in Eq. 4 play a role similar to R 2 α,1 in Eq. 3, the other second order factors being negligible. Solid lines in Fig. 3(b) are best fits of Eq. 4. They are obtained with the same set of parameters as in Fig. 2 and g β = 1.52 (12) which is just the value given in Ref. [24]. Similarly to 2α, the second order term dominates the amplitude of 2β.

The amplitude of the component 2β -α, which corresponds to a classical magnetic breakdown orbit involving 4 tunneling and 2 reflections, is given by

A 2β-α = - F 2β-α πm 2β-α R 2β-α,1 - F 2β-α πm β 1 2 R α,1 R β,2 + 1 3 R α,3 R β+α,2 . (5)
The second order term is dominated by the product R α,1 R β,2 which is much lower than the damping factor R 2β-α,1 entering the Lifshitz-Kosevich formula, provided the spin damping factor R s 2β-α is not too small. For this reason, the Lifshitz-Kosevich formula holds for this orbit as it is the case for the above considered α and β orbits and accounts for the data of Fig. 3(c).

Finally, the 'forbidden orbit' βα is accounted for by

A β-α = - F β-α πm β [R α,1 R β,1 + R α,2 R β+α,1 + R β,2 R β+α,1 + R β,1 R 2β-α,1 ] . (6)
Since this component does not correspond to a classical orbit, only a second order term, dominated by the product R α,1 R β,1 , enters the amplitude. Solid line in Fig. 3(d) are best fits to Eq. 6. They are obtained with the same set of parameters as in Fig. 2, as well. A very good agreement is observed.

IV. SUMMARY AND CONCLUSION

De Haas-van Alphen oscillations of the quasi-two dimensional organic metal κ-(ET) 2 Cu(SCN) 2 have been studied at high magnetic field. The Fermi surface of this emblematic organic metal is a prime example of a linear chain of orbits coupled by magnetic breakdown. Accordingly, the oscillation spectrum is composed of linear combinations of the frequencies linked to the α and magnetic breakdown-induced β orbits. The field and temperature dependence of the observed Fourier components is consistently analyzed in the framework of analytical calculations based on a second order development of the free energy taking into account the oscillations of the chemical potential, i.e. beyond the first order Lifshitz-Kosevich formula, and with the same set of parameters [m α = 3.07(4), m β = 6.03 (11), T D = 0.87(6) K, B 0 = 16(8) T, g α = 1.73(5) and g β = 1.52 (12)] for all the considered components. A very good quantitative agreement with the experimental data is observed. Even though the data relevant to the classical orbits α, β and 2β-α follow the Lifshitz-Kosevich formula due to negligible second order terms, these second order terms strongly enters the field-and temperature-dependent amplitude of the components 2α, 2β

and alone are responsible for the 'forbidden frequency' β-α.

FIG. 1 :

 1 FIG. 1: (a) Field-dependent magnetic torque at T = 1.7 K. Black and blue lines stand for increasing and decreasing field sweeps, respectively. (b) Field-dependent oscillatory torque for decreasing field sweeps at various temperatures and (c) corresponding Fourier analysis in the field range 20-55 T. The angle between the magnetic field direction and the normal to the conducting plane is θ = 20 • . Marks are calculated with F α (θ = 0) = 0.600 kT and F β (θ = 0) = 3.861 kT. The insert displays a sketch of the Fermi surface in which the α and β orbits are indicated.

FIG. 3 :

 3 FIG. 3: Dingle plots of (a) 2α, (b) 2β, (c) 2β -α and (d) βα Fourier components. Mass plots are reported in the inserts. Symbols are experimental Fourier amplitudes and solid lines are best fits of Eqs. 3, 4, 5 and 6, respectively, to the data, obtained with the same parameters as in Fig. 2 and with g * α = 1.73 and g * β = 1.52. Uncertainty on these parameters is given in the text. Thin solid and dashed lines are the contribution of the first (i.e. Lifshitz-Kosevich) and second order terms, respectively, of the above mentioned equations.

Acknowledgments

The support of the European Magnetic Field Laboratory (EMFL) is acknowledged. The work was partially supported by the RFBR grant 14-03-00119-a and Program N2 of the Presidium of Russian Academy of Science.