Sean Sirur
email: sean.sirur@stx.ox.ac.uk

Tim Muller
email: tim.muller@nottingham.ac.uk

The Reputation Lag Attack

Keywords: Reputation Lag, Reputation, Trust System, Attack, Malicious Peer

Reputation systems and distributed networks are increasingly common. Examples are electronic marketplaces, IoT and ad-hoc networks. The propagation of information through such networks may suffer delays due to, e.g., network connectivity, slow reporting and ratingupdate delays. It is known that these delays enable an attack called the reputation lag attack. There is evidence of impact of reputation lag attacks on existing trust system proposals. There has not been in-depth formal analysis of the reputation lag attack. Here, we present a formal model capturing the core properties of the attack: firstly, the reputation of an actor failing to reflect their behaviour due to lag and, secondly, a malicious actor exploiting this for their personal gain. This model is then used to prove three key properties of the system and the attacker: if there is no decay of reputation, then the worst-case attacker behaviour is to cooperate initially, then wait, then behave badly; increasing communication between users was found to always be of benefit to the users; performing a specified number of negative interactions given any instance of the system is an NP-hard problem.

Introduction

Ratings can be found as a basis for trust in various networks including ecommerce and social media. Typically, actors will rate their interactions with one another. These individual ratings are propagated through the system, and considered by others when judging who is trustworthy. Timely and effective propagation is necessary for actors to accurately judge each other. Non-ideal networks introduce lag due to network connectivity, people providing ratings late, or other reasons. An attacker can exploit this lag by engaging actors who, due to lag, have not received news of the attacker's prior negative behaviour and still consider them trustworthy. Broadly, we define a reputation lag attack as any instance where an attacker exploits a lag in the propagation of their negative reputation to allow them to perform negative actions they otherwise couldn't have.

No substantial research or well-reported instances of the reputation lag attack exist (not much work has followed up [START_REF] Kerr | Modeling trust using transactional[END_REF], which introduced the notion). We do not know the scale, prevalence and effect on vulnerable networks remains unknown. Nonetheless, existing research [START_REF] Kerr | Smart cheaters do prosper[END_REF] shows that the attack is viable on proposed trust systems. Attacks on trust systems often combine different types, and, e.g., fake ratings, Sybil accounts or camouflaging tactics are more obvious, so combined attacks may have been classified as these.

There is general theoretical model of reputation lag attacks. A formal model provides insight into the attacks, even without data. This paper takes a first step towards defining a general formal model of reputation lag attacks. The model successfully captures the core mechanism of the reputation lag attack: some user(s) must trust an attacker who they would not have trusted had no lag been present in the system. Three primary insights were gained from the model. Firstly, if users judge all actions equally regardless of when they occurred, there exists an ordering to the attacker's actions which is always superior to any other ordering: the attacker first behaves positively; waits for that reputation to spread through the system; and then attempts to behave negatively as much as possible before being rejected by the users. This drastically reduces the search space of possible optimal sequences of actions for the attacker. Secondly, increasing the rate of communication between users relative to the attacker is always detrimental to the attacker in the average case. Finally, how to successfully performing a specified number of negative actions for a given instance of the system is an NP-hard decidability problem for the attacker.

Related Work

Distributed systems can use ratings or recommendations between actors as a basis for trust, where an actor's reputation is defined through these ratings [START_REF] Yahalom | Trust relationships in secure systems-a distributed authentication perspective[END_REF]. In such systems, reputation is imperative to actors' decision-making processes, for example in marketplace environments [START_REF] Jolivet | Reputation and prices on the e-market: Evidence from a major french platform[END_REF][START_REF] Przepiorka | Buyers pay for and sellers invest in a good reputation: More evidence from ebay[END_REF]. The delay present in the propagation of these ratings was first identified as a vulnerability by Kerr and Cohen [START_REF] Kerr | Modeling trust using transactional[END_REF] as the "reputation lag attack". The vulnerability is not present in previous surveys on reputation systems [START_REF] Hoffman | A survey of attack and defense techniques for reputation systems[END_REF][START_REF] Marti | Taxonomy of trust: Categorizing p2p reputation systems[END_REF]. Hoffman, Zage and Nita-Rotaru [START_REF] Hoffman | A survey of attack and defense techniques for reputation systems[END_REF] is an example of how the attack often went unrecognised. The authors decompose reputation systems into their constituent parts and discuss the vulnerabilities present in each. They are prudent in making rating propagation explicit within the dissemination stage. However, no notion of lag is considered here so the authors miss a likely environment for exploitation (focusing primarily on transmission integrity).

Even once discovered, the reputation lag attack remained largely unnoticed by the trust community, appearing in some subsequent surveys (e.g. [START_REF] Jøsang | Challenges for robust trust and reputation systems[END_REF][START_REF] Muller | On robustness of trust systems[END_REF]) but not others (e.g. [START_REF] Koutrouli | Taxonomy of attacks and defense mechanisms in p2p reputation systems -lessons for reputation system designers[END_REF]). The first analysis is performed by Kerr and Cohen [START_REF] Kerr | Smart cheaters do prosper[END_REF], when investigating the success of dishonest sellers against various proposed trust systems in a simulated marketplace. They conclude that the reputation lag attack, though somewhat successful, was largely less so than other attacks, acquiring less profit and beating fewer trust systems. This finding comes with two major caveats, however: Firstly, the authors' intuitive but informal definition of reputation lag attacks assumes the attacker must at some point behave honestly. We find that no such restriction is necessary when defining the attack. The second caveat is the implementation of the lag. Every sale suffers from a constant lag before the buyer learns whether they have been cheated. There is no lag in the propagation of this information, however. This makes it difficult to separate how reputation lag effects buyers' decision given that every sale is subject to the same reputation lag effect. An implication of the above two caveats is that according to their analysis the "re-entry attack" was more successful. We argue that, due to limitations in analysis, the attack was functionally identical to the "reputation lag attack", except the attacker never needed to behave honestly (with even the author's noting this). An issue is that, beyond the initial intuition, it is not always clear what a reputation lag attack entails. We feel the issues faced in existing research motivate an abstract formal model to avoid conflating the idiosyncrasies of an attack's implementation with its analysis.

The reputation lag attack is not restricted to traditional reputation systems with many distributed networks being vulnerable to it. Commonly, strong security guarantees exist through the use of trusted authorities or shared secrets. In some networks, however, it is necessary to establish trust between nodes on a more ad-hoc basis [START_REF] Pirzada | Establishing trust in pure ad-hoc networks[END_REF]. Any delay in the communication of trust establishing information (and perhaps other "hopping" protocols) would be vulnerable to reputation lag attacks. For example, while research on reputation lag attacks in these contexts are not widespread, many instances of such networks encounter malicious peers and it is possible that the mechanisms against these attackers (e.g. distributed warning systems) are vulnerable to reputation lag attacks. Examples include peer-to-peer networks used for file-sharing (Gnutella, BitTorrent) [START_REF] Lee | Analysis on malicious peer's behavior of the p2p trust resource chain model[END_REF][START_REF] Zeinalipour-Yazti | Exploiting the security weaknesses of the gnutella protocol[END_REF]; ad-hoc networks (mesh networks, vehicle-to-vehicle communication) [2,14]; hardware networks (BGP/routing, IoT) [START_REF] Liu | Identifying malicious nodes in multihop iot networks using diversity and unsupervised learning[END_REF]; and overlay networks (Tor, I2P) [START_REF] Egger | Practical attacks against the i2p network[END_REF].

Preliminaries

In this section, some mathematical tools are defined for use later in the paper.

Sequences of events are an important notion through the paper as they are used to describe the sequential behaviour in time of the model presented herein. First, we define sequences recursively: Definition 1 (Sequence). A sequence σ ∈ Σ over an alphabet C is recursively defined:

σ := ∅ σ :: c ∈ C.
We may write σ :: σ as a shorthand, where σ :: ∅ = σ and σ :: (σ :: c) = (σ :: σ ) :: c. It is useful to reason about the length of a sequence, |σ|, by letting |∅| = 0 and |σ :: c| = |σ| + 1. This provides a mechanism for both differentiating the number of elements in sequences and assigning positions to elements of the sequence. To refer to elements or subsequences of a sequence by their position, we introduce indexing as follows:

σ t = σ t t < |σ| ∧ σ = σ :: c c t = |σ| ∧ σ = σ :: c (1)
σ x∼y = σ x∼y-1 :: σ y x < y σ x x = y (2)
It is useful to discuss the number of occurrences of a particular subset of elements in a sequence as well as the order in which that particular subset occurs irrespective of the other elements e.g. when analysing the behaviour of that particular subset alone. This is done by extracting the subsequence of a particular element from within a sequence. The function : 2 C × Σ → Σ returns the subsequence of σ consisting only of the members c ∈ C of the set of elements C ⊆ C:

C σ =      (C σ ) :: c if σ = σ :: c where c ∈ C (C σ ) if σ = σ :: c where c ∈ C ∅ if σ = ∅ (3)
It is useful to be able to compare two sequences, where one sequence is essentially the same as another sequence, except it has certain additional actions sprinkled in. Intuitively σ ≺ C σ means that we can transform σ into σ, by removing certain elements c ∈ C from σ . So, for c, c ∈ C ⊆ C s.t. c = c , we define

≺ C : 2 C × Σ → Σ: σ ≺ C σ =      T rue if |C σ| < |C σ | ∧ ((C\C) σ) = ((C\C) σ ) F alse otherwise (4)
Probability theory plays a significant part in the paper as the system is defined on continuous-time stochastic processes. If X is a (continuous) random variable, then X(ω) represents the outcome of X, p(X = x) represents the probability density at x, Pr(X < x) represents the probability that the outcome of X is below x; so Pr(X <

x) = x -∞ p(X = x)dx.
The relevant stochastic processes can be modelled using continuous-time Markov chains [START_REF] Norris | Continuous-time Markov chains I[END_REF]. Intuitively, a CTMC is a series of random variables indexed with a time t, representing the state at time t. More recent states are not influenced by older states, as the process must be memoryless [START_REF] Norris | Continuous-time Markov chains I[END_REF].

Definition 2. A continuous-time Markov chain [START_REF] Norris | Continuous-time Markov chains I[END_REF] is a continuous series of random variables (S) t for t ∈ R, such that for x > y > z, Pr(S x =s|S y =t) = Pr(S x =s|S y =t, S z =u).

Model

Our aim is to model the reputation lag attack. Honest users may communicate information to each other, but when and how often depends on external factors, such as internet connectivity, configuration settings or preference. We assume that honest users do not communicate strategically, and thus model them as stochastic processes. The attacker behaves strategically and tries to act in a way to maximise how often he can cheat others, relative to cooperating with others. However, the attacker is still bound to physical limitations, and cannot act at infinite speeds. The first step is to construct a model that defines how often certain users tend to communicate, as well as how often the attacker may be able to act. We refer to this model as the abstract model. The concrete model (Section 4.3) is an instantiation of the abstract model, and tells us the exact communication between users.

Abstract Model

The abstract model does not tell us what is being communicated, or what actions have occurred. In order to be able to reason about the concrete communications and actions (and thus the attacker's strategy), we need to instantiate the attacker's actions appropriately. The concrete model is defined in Section 4.3 to facilitate this. The final step will be to define and reason about the behaviour of the attacker. The abstract model defines when two users communicate but not what they communicate. Attacker behaviour is not explicit in the abstract model, only when the attacker has an opportunity to act. We introduce the notion of abstract traces, which specify how and when users and the attacker communicate, but not what they communicate. Users may communicate at different rates. The attacker's independent communication rate describes the rate at which they receive the opportunity to act.

Definition 3. An abstract system ψ ∈ Ψ consists of a tuple ψ = (U, R, r A ): a set of users U = {i ∈ {1, ..., n} | n ∈ N >0 };
an n × n matrix R describing the communication rates between users, with r ij ∈ R ≥0 and r ii = 0; and the rate r A ∈ R ≥0 with which the attacker acts.

An abstract trace is a sequence of abstract interactions between users and the attacker. It describes in what order interactions occurred for some particular instance of the stochastic system described in subsection 5. It is comprised of either the empty trace; an interaction between two users; an abstract attacker action; or the concatenation of two other traces. The trace semantics takes the form of sets of messages assigned to users, representing which messages those users have received:

Definition 4 (Abstract Trace). An abstract trace σ ∈ Σ is a sequence over the alphabet C = {c ij | i, j ∈ U} ∪ {c A }.
As a shorthand, we may write r c to mean

r ij or r A if c = c ij or c = c A , respectively.
The abstract model defines a stochastic system (or probabilistic run) describing who interacts when. In this system, the actors communicate at intervals. The time between each communication is independent of the time between the preceding communications. Formally, every action in the abstract alphabet can be modelled as a series of random variables representing the time between occurrences of that action. Definition 5. A probabilistic run of the abstract system ψ consists of collection of series of random variables satisfying the Markov property. For each c ∈ C, the probability density functions of the corresponding series (m ≥ 0) of random variables are:

p(τ m c =t) = r c e -rct
We let λ k c be a random variable representing the time in which the k th c-action occurred: λ k c (ω) = 0≤i≤k τ i c (ω). The probabilistic run can be viewed as a distribution over possible traces. In particular, we can say that the probabilistic run defines a (continuous-time) Markov chain, where the state consists of the current trace. First, we define the Definition 6. The abstract system execution is a continuous series of random variables (S) t for t ≥ 0, such that S 0 (ω) = ∅, and for every t, there exists t < t such that either S t (ω) = S t (ω) or S t (ω) = S t (ω) :: c. The latter case occurs if and only if t ≤ λ k c (ω) ≤ t.

The random variable S 10 would give you the distribution of all abstract traces of the abstract system running for 10 time units. Intuitively, the state only changes at times where the probabilistic run determines an action occurs. The definition implicitly assumes that no two actions happen at exactly the same time (and the probability of this occurring is indeed 0). First we prove a lemma showing that the occurrence of an interaction within a particular time range is independent from any events occurring before that time range.

Lemma 1. Pr(t < λ k+1 c < t | λ k+1 c > t) = Pr(τ k+1 c ≤ t -t) Proof. Pr(t < λ k+1 c < t | λ k+1 c > t) = Pr(t < λ k c + τ k+1 c < t | λ k c + τ k+1 c > t) = Pr(t-λ k c < τ k+1 c < t -λ k c | τ k+1 c > t-λ k c ) = Pr((t-λ k c <τ k+1 c <t -λ k c )∧(τ k+1 c >t-λ k c )) Pr(τ k+1 c >t-λ k c ) = t -λ k c t-λ k c rce -rc tc dtc ∞ t-λ k c rce -rc tc dtc = e -rc (t-λ k c ) -e -rc (t -λ k c ) e -rc (t-λ k c ) = 1 -e -rc(t -t) = Pr(τ k+1 c ≤ t -t)
The abstract system execution is a continuous-time Markov chain:

Proposition 1. The abstract system execution satisfies, for x > y > z, that

Pr(S x =σ x |S y =σ y ) = Pr(S x =σ x |S y =σ y , S z =σ z )
Proof. Recall that user communications are exponentially distributed. The definition of an abstract system execution trivially implies that σ 1∼x = σ 1∼y :: σ , for some σ . If

σ 1∼x = σ 1∼y , then Pr(S x =σ x |S y =σ y ) = Pr(∀ c,m λ m c ∈ [y, x]) = Pr(S x =σ x |S y =σ y , S z =σ z ). If σ x = σ y :: c, then Pr(S x =σ x |S y =σ y ) = Pr(∀ c =c,m λ m c ∈ [y, x] ∧ ∃ 1 m λ m c ∈ [y, x]) = Pr(S x =σ x |S y =σ y , S z =σ z )
, again, by the memorylessness of the exponential distribution. If σ isn't ∅ or in C, then we can take x > y > y and recursively apply the argument.

In the abstract trace, the probability distribution for the "next" interaction to occur is independent of all previous occurrences. Specifically, the probability is dependent only on the relative interaction rates. Proposition 2. For all times t and t s.t. t > t and for all abstract alphabets C, Pr(S t = σ :: c|S t = σ) increases with r c relative to r c ∈ R.

Proof. W.l.o.g. for each set of occurrences of some interaction c we define a single natural number k c such that

∀ c∈C ∃ 1 kc λ kc c ≤ t < λ kc+1 c
. Again, w.l.o.g. we define t = min{λ kc+1 c | c ∈ C}. By applying lemma 1, we note that the probability that some interaction c occurs within an interval

[t, t ] is Pr(λ k+1 c ∈ [t, t ] | λ k+1 c > t) = Pr(τ k+1 c ≤ t -t)
which is a result of the memorylessness of the exponential distribution.

From this we may conclude that for two interactions c and c with distributions τ c = r c e -rctc and τ c = r c e -r c t c respectively:

Pr(t < λ kc+1 c < λ k c +1 c | λ kc+1 c , λ k c +1 c > t) = Pr(τ kc+1 c < τ k c +1 c ) = ∞ 0 r c e -r c t c t c 0 r c e -rctc dt c dt c = ∞ 0 r c e -r c t c (1 -e -rct c )dt c = rc /(rc+r c
). This monotonically increase with r c and decreases with r c . Thus, Pr(S t = σ ::

c | S t = σ) = Pr(λ kc+1 c = min{λ k c +1 c | c ∈ C}) = c ∈C,c =c Pr(t < λ kc+1 c < λ k c +1 c | λ kc+1 c , λ k c +1 c > t) = c ∈C,c =c rc /(rc+r c
) which monotonically increase with r c and decreases with each r c . The last step follows from the fact that each interaction is independently distributed. Thus the theorem holds.

Reputation

Before defining the concrete model, it is important that we capture the notion of reputation. We do this through the judgement function δ. We define a judgement function as any function that defines a metric over ratings (messages) that establishes the reputation of the attacker. Users will not accept interactions with a disreputable attacker. Despite this generalised definition of δ, there are some properties which we consider key to the definition of a rational judgement function:

1. Only information known by a user can be made when judging an incoming interaction on behalf of that user. 2. Positive actions must be rewarded and negative actions punished. 3. The judgement function must accept interactions from an attacker with no known prior behaviour to ensure they can enter the system.

There are many additional properties a judgement function could satisfy. Furthermore, it would be simple to extend the model to allow different users to utilise different judgement functions thus representing the various tolerances different users may have to the attacker's behaviour. However, for the purposes of an initial analysis, the simple δ defined for all users in this paper considers only the number of and ⊥ interactions known to user i as arguments. This means, for instance, it is independent of the order in which messages were received and the time at which interactions occurred. Definition 7. The function δ : N 0 × N 0 → R is an arbitrary function with the following properties:

δ(m , n) > δ(m, n) when m > m (5)
δ(m, n ) < δ(m, n) when n > n (6)
δ(0, 0) ≥ 0 (7)

The Concrete Model

In the concrete model, the attacker instantiates their abstract actions with concrete actions consisting of an action applied to a user. Actions can have a positive impact or a negative impact, increasing or decreasing the actor's reputation respectively. Positive actions are denoted and negative ones ⊥. When the attacker interacts with a user through one of the above actions, a message, held by that user, is generated. This message contains information regarding what action the attacker performed. It is then propagated through the graph of users, who then use this information to judge the trustworthiness of the attacker. This captures the notion of reputation. A user receiving messages from different users reporting e.g. a positive action, must be able to distinguish which particular action is being reported. We assume users can distinguish different actions and model this using a unique index for each action. Every abstract trace σ has a set of corresponding concrete traces. A concrete trace σ is an abstract trace σ that has had every abstract attacker action c A substituted with a concrete attacker action. Concrete actions consist of interacting positively or negatively with a user i (c i or c ⊥ i ) or skipping a turn (c ).

Definition 9 (Concrete Trace

). An concrete trace σ is a sequence over the alphabet

C = {c ij |i, ∈ U} ∪ {c θ i |θ ∈ Θ, i ∈ U} ∪ {c }.
The family of functions defining the set messages known by users in the concrete system is defined: Definition 10. The function µ O⊆Θ i>0 : Σ → 2 M returns the set of messages held by user i concerning actions of a type in T given that the trace σ occurred:

µ O i (σ) =          µ O i (σ ) ∪ µ O j (σ ) σ = σ :: c ji (θ, i, |σ|) ∪ µ O i (σ ) (σ = σ :: c θ i ) ∧ (θ ∈ O) µ O i (σ ) σ = σ :: c, for other c ∅ σ = ∅ (8)
We introduce the shorthand:

µ O (σ) = U i=1 µ O i (σ) (9)
δ i (σ) = δ(|µ i (σ)|, |µ ⊥ i (σ)|) (10)
δ(σ) = δ(|µ (σ)|, |µ ⊥ (σ)|) (11)
5 Reputation Lag attack

Above we have defined the environment in which the reputation lag attack can occur. Now, we define the attacker model and the attack itself.

The Attacker Model

In this model, the attacker A is captured as a function which outputs a trace of concrete attacker actions which, when substituted into an abstract trace, instantiates a set of abstract attacker action. The attacker function can instantiate each abstract action with one of three actions c i , c ⊥ i or c . The attacker aims to maximise their profit.

Informally, profit is (rationally) defined as any function which monotonically increases with the attacker's negative interactions and decreases with their positive interactions i.e. the profit depends on the number of negative interactions the attacker has committed relative to the number of positive interactions they have invested into the system. As such, an "optimal attacker" is defined as an attacker which, for all abstract traces σ, can commit the maximum number of negative interactions when restricted to a particular number of positive interactions and/or given an abstract trace of finite length i.e. maximise their profit given finite resources and/or finite time.

Definition 11. The attacker's profit function : Σ → R is subject to the following constraints:

(σ) < (σ ) when µ (σ) > µ (σ ) if µ ⊥ (σ) = µ ⊥ (σ ) ( 12
) (σ) > (σ ) when µ ⊥ (σ) > µ ⊥ (σ ) if µ (σ) = µ (σ ) (13)
In this model, different types of attacker can be delineated by how much information they have of the system when making decisions i.e. what subset of the system is considered by the attacker A(s ⊆ ψ). For example, it is important to consider how much of the abstract trace σ and attacker is aware of when making decisions. Note, for the purposes of a security analysis, assuming an apparently overestimated attacker is useful for testing the constraints of the system and providing strong guarantees of the system's resilience against attack. We will consider this when choosing A:

1. Attacker Model 1 in which the attacker is omniscient to the past and future i.e. the attacker can view the full abstract trace σ at will. This attacker's power is somewhat unrealistic as it grants the attacker the ability to see the future when making decisions but, as stated, for the purposes of a security analysis this is not unreasonable. For instance, an eavesdropping attacker that monitors a system long enough to notice a pattern in the system behaviour could be captured somewhat realistically by this model. Thus, this is the model considered in this paper. 2. Attacker Model 2 in which the attacker is an eavesdropper to the entire system but is only aware of the past when making decisions i.e. for each abstract attacker action σ x = c A , the attacker can view σ 1∼x-1 . 3. Attacker Model 3 in which the attacker is blinded to every interaction in σ which is not an attacker action i.e. the attacker only sees c A σ.

Similarly, the attacker's knowledge of other aspects of the system such as the user rates R or the judgement function δ can also be allowed or restricted to different extents. However, given the fact that the attacker is solely concerned with instantiating an abstract trace such that their profit is maximised, for the most powerful attacker it is sufficient to only consider the abstract trace σ and the and judgement function δ.

Using this information the attacker generates a trace of concrete attacker actions σ such that | σ| = |c A σ|. This attack trace is then substituted into the full abstract trace to make a concrete trace σ: Definition 12 (Attack Trace). An attack trace σ ∈ Σ is a sequence over the alphabet Ċ = {c θ i |θ ∈ Θ, i ∈ U} ∪ {c }.

Definition 13. Attack traces are constructed by the attacker function A : Σ × (N 0 × N 0 → R) → Σ defined thus:

A(σ, δ) =      ∅ σ :: c θ i where (i > 0) ∧ (θ ∈ Θ) σ :: c (14)
We give no explicit definition of the function itself and instead explore its properties in section 6. The attack trace σ is then substituted into the abstract trace σ to construct the concrete trace σ. This is performed by an instantiation function. To model the fact that users will not accept interactions with a disreputable attack, the instantiation function will substitute any rejected attacker actions with a c action. User i judges the attacker at each attacker action c θ∈Θ i via δ with only the information known to them:

Definition 14. The instantiation function Γ : Σ × Σ → Σ is defined: Γ δ (σ, σ) =          ∅ if σ = σ = ∅ c ij :: Γ δ (σ , σ, ) if σ = c ij :: σ c :: Γ δ (σ , σ ) if (σ = c A :: σ ) ∧ ( σ = c :: σ ) ∧ (δ i (σ ) ≥ 0) c :: Γ δ (σ , σ ) if (σ = c A :: σ ) ∧ ( σ = c :: σ ) ∧ (δ i (σ ) < 0) (15)
If none of the attacker's actions are denied by a user, we deem that attack trace complete for σ. Otherwise, we deem it incomplete for σ.

The Reputation Lag Attack

Here the reputation lag itself is defined in terms of the model presented thus far. Informally, a reputation lag attack occurs when the attacker is allowed to perform a (presumably malicious) interaction with a user who would have rejected the interaction had they had perfect information of the attacker's prior actions. By construction, any example of imperfect user knowledge within this model stems directly from a failure of the system to propagate the messages in a timely manner. While this definition is very high-level, it successfully captures every instance which could be considered a reputation lag attack.

If an attacker interaction with user i is accepted by that user using only the information (messages) known to them but is rejected when using all the information present in the system, then a reputation lag attack has occurred.

First, we define an omniscient instantation function in which users judge the attacker with all the information available in the system: Definition 15. The omniscient instantiation function Γ * : Σ × Σ → Σ is defined:

Γ * δ (σ, σ) =          ∅ if σ = σ = ∅ c ij :: Γ * δ (σ , σ) if σ = c ij :: σ c :: Γ * δ (σ , σ ) if (σ = c A :: σ ) ∧ ( σ = c :: σ ) ∧ (δ(σ ) ≥ 0) c :: Γ * δ (σ , σ ) if (σ = c A :: σ ) ∧ ( σ = c :: σ ) ∧ (δ(σ ) < 0) ( 16
)
Here we define the reputation lag attack indicator. If the attacker has an increased profit when instantiated normally compared to when instantiated by the omniscient function (i.e. if the attacker has successfully exploited the lag for their own gain), a reputation lag attack has occurred.

Definition 16. The reputation lag attack indicator is defined:

RLA δ (σ, σ) = 1 (Γ δ (σ, σ)) > (Γ * δ (σ, σ)) 0 (Γ δ (σ, σ)) = (Γ * δ (σ, σ)) (17)

Results

The primary motivation for the above formalism is to provide insight into the reputation lag attack. Here we elicit the three following key properties of the attack: the definition of δ defined herein is shown to be vulnerable to a superior ordering of attacker actions; increasing the rate of user communication is shown to never be detrimental to the users and could be detrimental to the attacker in the average case; the decidability problem of whether the attacker can perform a specified number of negative actions is shown to be have an NP-hard computational complexity.

Attack Ordering

The order in which the attacker executes their actions has an impact on their success. In a structured attack trace, the attacker goes through three phases: a phase, a phase and a ⊥ phase. In a given phase, the attacker only executes actions of that type. We show that structured attack traces, under the particular δ defined in the above model, are always superior to unstructured strategies. Intuitively, this results from the fact that positive actions occurring earlier in the trace gives them more chance to be propagated whilst negative occurring later in the trace have less time to be propagated. Definition 17. Define the reflexive partial order < A on attacker actions, s.t. c i < A c < A c ⊥ j , for all i, j. We define the partial order < A on traces as σ :: c :: c :: σ < A σ :: c :: c :: σ iff c < A c . Proposition 3. For every σ, there is a minimal element σ < A σ, and this minimal element has the property that it is a structured attack trace.

Proof. If σ is structured, then there is no σ = σ1 :: c :: c :: σ2 where c < A c, so σ is a minimal element. Vice versa, any minimal element may not be of the shape σ = σ1 :: c :: c :: σ2 either, so it must structured.

Theorem 1. For all abstract traces σ; attack traces σ and σ < A σ (where σ is complete for σ); users i; and locations x ≤ |σ|:

δ i (Γ δ (σ, σ )) ≥ δ i (Γ δ (σ, σ))
Proof. Consider two adjacent attacker actions σa and σa+1 . We denote their corresponding positions in the abstract (or concrete) traces as σ y and σ z respectively. Two cases follow from this: σa < A σa+1 and σa+1 < A σa .

Case 1 ( σa < A σa+1 ): This implies σ σ. In this, it follows trivially that

δ i (Γ δ (σ, σ )) ≥ δ i (Γ δ (σ, σ))
Case 2 ( σa+1 < A σa ): We construct σ by swapping the two elements in question: σ = σ1∼a-1 :: σa+1 :: σa :: σa+2∼| σ| . This implies that σ 1∼x-1 = σ 1∼x-1 and σ y+1∼|σ| = σ y+1∼|σ | . We consider the case where σa+1 = σ a = c i . We notice two things: firstly, user i is still aware of the c i action at the time of σ z and so has lost no information in comparison to σ.

Secondly, we notice that the earlier introduction of c i creates the opportunity for it to be propagated between σ y and σ z and thus possibly even further. Essentially, more users u = i may be aware of the c i in σ than in σ from point y onward: for all users u and locations

x ≥ y, µ u (Γ δ (σ, σ) 1∼x ) ⊆ µ u (Γ δ (σ, σ ) 1∼x ) =⇒ |µ u (Γ δ (σ, σ ) 1∼x )| ≥ |µ u (Γ δ (σ, σ ) 1∼x )|.
A symmetrical argument in the case that σa = σ a+1 = c ⊥ i leads us to conclude that the each user is aware of less or equal negative actions after the swap: for all users u and locations

x ≥ |σ|, |µ ⊥ u (Γ δ (σ, σ ) 1∼x )| ≤ |µ ⊥ u (Γ δ (σ, σ) 1∼x )|.
We also see from both arguments that the case in which one of the swapped attacker actions are c , that particular action has no effect on the knowledge of the users i.e. the inequality holds trivially. By the definition of < A , it is not possible for two actions to be swapped where both actions are of the same type (e.g. where both are positive).

The increased awareness of positive interactions and the decreased awareness of negative ones coupled with the monotonicity of δ implies that, for all users i and locations

x ≤ |σ|, (|µ u (Γ δ (σ, σ ) 1∼x )| ≥ |µ u (Γ δ (σ, σ) 1∼x )|)∧(|µ u (Γ δ (σ, σ ) 1∼x )| ≤ |µ u (Γ δ (σ, σ) 1∼x )|) =⇒ δ i (Γ δ (σ, σ ) 1∼x ) ≥ δ i (Γ δ (σ, σ) 1∼x ).
By transitivity of < A , the proof for pairs holds for all traces. Proposition 3 shows that the optimal ordering is structured.

Thus, for all complete attack traces, structured traces are superior. We restrict our theorem to complete attack traces as incomplete traces contain counterexamples and any optimal attack trace will be complete. Structuring may not affect profit but it reduces the search space of attack traces as the optimal strategy must be structured. However, structuring is dependent on the judgement function. A judgement function in which reputation decays with time would be sensitive to abrupt changes in behaviour such as in a structured attack trace, thus making time-dependent judgement a simple but effective mitigation.

Effect of Communication Rates on the Attacker Strategy

Considering a structured attack trace σ with optimal dealing (i.e. the users are aware of every in the system when the attacker is in their ⊥ phase), we show that increasing the communication rates is detrimental to the attacker. For the purposes of this analysis we focus on effectively cheating users, hence the assumption that we are in a state where the knowledge of the deals has spread to all users, and the attacker is in the ⊥ stage of their structured attack.

We formulate our theorem as follows:

Theorem 2. Let ψ, ψ be a pair of abstract systems differing only in their respective matrices R, R , such that ∃ i,j (r ij < r ij ) ∧ (∀ p =i,q =j r pq = r pq ).

For any time t > 0; any attack trace σ < A σ; any concrete trace σ = σ :: σ :: σ ⊥ s.t. ∀ i∈U c ⊥ i (σ :: σ ) = ∅ and ∀ i∈U µ i (σ :: σ ) = µ (σ :: σ ); and any pair of system executions S t and S t corresponding to abstract systems ψ and ψ then:

Pr(RLA δ (S t (ω), σ) = 1) < Pr(RLA δ (S t (ω), σ) = 1)
Proof. For notational convenience, we define

C U = {c ij | r ij = r ij } and C U = {c ij | r ij > r ij }
We prove that if σ ≺ C U σ , then the attacker's reputation during their misbehaving phase (i.e. during σ ⊥ ) can only decrease in σ compared to their reputation in σ. If σ = σ 1 :: σ 2 and σ = σ 1 :: c ij :: σ 2 for some c ij ∈ C U , then for every user h, either µ h (σ ) = µ h (σ) or µ h (σ ) = µ h (σ) ∪ µ j (σ 1 ). The latter means that the messages j told i after σ 1 have reached h, the former means that they have not, implying µ h (σ) ⊆ µ h (σ ). For any two traces with σ ≺ {cij } σ we can iteratively apply this argument for the additional messages. Due to the well-disseminated good messages ∀ i∈U µ i (σ :: σ ) = µ (σ :: σ ) and the fact that no new good interactions occur in σ ⊥ , it is not possible for the users to learn any good messages during σ ⊥ . This, combined with the monotonicity of δ, implies that the users may only know additional negative messages during the attacker's ⊥ phase. Thus the reputation can only decrease along with the possibility of a reputation lag attack occurring. For notational convenience (and brevity), if we define w.l.o.g. {k 1 , . . . , k n } as the set of indices of the attacker's ⊥ actions in trace σ and {k 1 , . . . , k n } as the corresponding indices in σ :

∀ i∈U ∀ x∈[1,n] (µ i (σ 1∼kx ) = µ i (σ 1∼k x )) ∧ (µ ⊥ i (σ 1∼kx ) ⊆ µ ⊥ i (σ 1∼k x )) =⇒ δ i (σ 1∼k x ) ≤ δ i (σ 1∼kx ) =⇒ RLA δ (σ , σ) ≤ RLA δ (σ, σ)
. Thus, σ is more robust to the reputation lag attack than σ. This is our first finding. Now we show that ψ has a higher probability of outputting traces with more communication (and which are thus more likely to be robust) than ψ. By definition, the probability of n occurrences of c pq before some time t is described by a homogeneous Poisson process [START_REF] Kingman | Poisson Processes[END_REF]: Pr(N (t

) pq = n) = (rpqt) n
n! e -rpqt . When t is the time of the last event in an abstract trace, this shows us that the expected number of occurrences of c pq within a trace increases with the rate r pq independently of any other rate or interaction c ij = c pq .

Similarly to lemma 1, it can also be shown that the probability of n occurrences of c pq happening between times t 1 and t 2 is dependent only on the time range [t 1 , t 2 ] and independent of the events preceding t 1 . Thus, ∀ t2>t1 Pr(N (t 1 < t < t 2 ) pq = n | t > t 1 )) = Pr(N (t 2 -t 1 ) pq = n). From this we see that the expected number of c pq occurrences within a given time range increases with only its own rate r pq independently of events prior to that time range or any other rate. For example, the number of c pq occurrences between two other actions σ 1 , σ 2 = c pq is dependent only on r pq and the time between the actions.

From the above two findings alongside the premise, we may infer that the system execution S t is as likely to output a particular number and ordering of C U interactions as S t but is more likely to output C U interactions between any two C U interactions. Hence, the traces output by S t are more communicative and, by our first finding in this proof, more likely to be robust than those of S t : (

Pr(|C U S t (ω)|>|C U St(ω)|) Pr(|C U S t (ω)|<|C U St(ω)|) > 1) ∧ ( Pr(|C U S t (ω)|>|C U St(ω)|) Pr(|C U S t (ω)|<|C U St(ω)|) = 1) =⇒ Pr(Stω≺ C U S t ω) Pr(S t ω≺ C U Stω) > 1 =⇒ Pr(RLA δ (S t (ω), σ) = 1) < Pr(RLA δ (S t (ω), σ) = 1
). Thus the theorem holds.

NP-Hardness

While strategies may exist to improve the attacker's profit in different scenarios, it is important to consider the feasibility of the optimal attacker. A polynomial optimal strategy for a given judgement function would be the ideal goal for any attacker. However, we show below that, for any judgement function, the computation complexity of constructing a strategy which can perform a specified number of negative interactions is NP-hard. Theorem 3. For any judgement function δ, the decidability problem of whether it is possible to perform m cheats without performing deals is NP hard.

Proof. We provide a reduction to the 3-SAT problem, which is NP-complete [START_REF] Garey | Continuous-time Markov chains I[END_REF]. In this proof outline, we provide the reduction itself, but omit the full proof that it is indeed a reduction. The full proof is a tedious exercise in bookkeeping, whereas the reduction provides insight in why it is NP-hard.

Let X = x 1 . . . x k be the set of variables in the 3-sat problem. Let ij be the j th literal in the i th clause. Assume there are n clauses.

For each variable take a user for its positive and negative atom, take a user for each literal in the formula, and we add an additional pair of users for every variable:

U = {u xi , u ¬xi |x i ∈ X} ∪ {v ij | ij } ∪ {v xi , v ¬xi |x i ∈ X}.
A pseudo clause is formed by each pair of users in the last set -they represent the clause x ∨ ¬x. There are a total of n + k (pseudo) clauses. The set

U ≥h = {v ij |i ≥ h, ij } ∪ {v xi , v ¬xi |i + n ≥ h, x i ∈ X}.
As a short-hand, we say a set of users performs a kill-communication, if they communicate their messages to all other users (O(n 2 )).

Consider an abstract trace σ with the following shape:

-The trace starts with k attacker actions.

-Then, for h ∈ [1, . . . k + n] do:

• Users U ≥h perform a kill-communication.

• The users u x , u y , u z , corresponding to the inverse of literals h1 , h2 , h3 send a single communication to the respective literals. • The attacker gets 1 action.

• All users u x and u ¬ x communicate to h1 , h2 , h3 .

-After performing these k + n steps, the attacker gets k more actions.

The decidability question for k variables and n clauses is whether the attacker can perform n+3k actions. The size of the trace σ is O(n 3 ), which is polynomial.

Conclusion

The formalism captured the two core properties of the attack: firstly, users inaccurately judging the reputation of the attacker due to incomplete knowledge caused by reputation lag and, secondly, a malicious actor exploiting this for their personal gain. The primary aim of the paper was to gain insight regarding the attacker's strategies to help with both mitigation and detection of the attack. There were three key outcomes: Theorem 1 shows how to re-order the attacker's actions, to increase the power of the attack: the attacker behaves positively; waits for this reputation to spread to as many users as possible; then begins behaving as negatively as possible before the users reject them. The fact that our judgement function, which models reputation, does not have a decay factor is a crucial ingredient for this theorem. Trust/reputation with decay factors may be somewhat more resistant against these attacks. Theorem 2 showed that, when dealing with an optimally dealing attacker, increasing user communication rates cannot be detrimental to users and may be detrimental to the attacker. Intuitively, this follows directly from the definition of the reputation lag attack which relies on poor user communication. However, as also evidenced by Theorem 3, the issue of determining the effectiveness of attacks is difficult, so it is important to have a proof of our intuitions. Finally, Theorem 3 showed that performing a specified number of negative interactions given any instance of the system σ is an NP-hard problem, implying the optimal attacker is computationally unfeasible.

Our definitions were chosen to be sufficiently abstract to cover a variety of systems and are readily extendable to more than one particular reputation system. The class of systems we consider are those systems where users communicate certain information about how other users have acted in the past, where good behaviour offsets bad behaviour, and too much bad behaviour leads to refusing to interact. We argue that many systems that consist of a distributed set of entities communicating knowledge about one another could be defined through the presented model with some modification.

Here we discuss further study. There is much to learn about the system and its effect on the attacker e.g. the effects of different judgement functions or how profit functions affect them. Investigating the combination of the reputation lag attack with other attacks may be of use for learning in which environments the attack is likely to be. Identifying real-world examples of the attack would also offer insight into the effectiveness of the model. Further investigation into the attacker's strategy is a vital next step as understanding identifying likely attack patterns is imperative not only to mitigating but also to detecting reputation lag attacks in the wild.

This paper provided a formal model of the reputation lag attack. The formalism captured the core properties of reputation lag attacks. The formalism allowed us to prove three interesting properties of the reputation lag attack: deals before cheats, communication benefits users but not the attacker, and finding optimal attacks is NP-hard. However, the analysis presented here is still in early stages. We hope to apply some of our techniques in practice, as well as continue to strengthen the formalism. The attacker's strategies and their relationship with the system as a whole warrants further study.

Fig. 1 .

 1 Fig. 1. A graph of users U = {1, 2, 3} and the independent attacker A with rate rA.

Definition 8 .

 8 The concrete system ψ ∈ Ψ is composed of a tuple ψ = (U, R, r A , M, Θ, δ, A, , Γ ): set of users U = {1, . . . , n}; an n × n matrix R describing the communication rates between users, with r ij ∈ R ≥0 and r ii = 0; the rate r A ∈ R ≥0 with which the attacker acts; a set of concrete messages M = {(θ, i, x) | θ ∈ Θ, i ∈ U, x ∈ N}; two possible results Θ = { , ⊥}; a judgement function δ; an attacker function A; an attacker profit function ; and an instantiation function Γ .


Hongyuan Chen

Zhenfu Cao
email: zfcao@sei.ecnu.edu.cn

Xiaolei Dong
email: dongxiaolei@sei.ecnu.edu.cn

Jiachen Shen
email: jcshen@sei.ecnu.edu.cn

SDKSE-KGA: A Secure Dynamic Keyword Searchable Encryption Scheme Against Keyword Guessing Attacks

Keywords: Searchable encryption, Dynamic, Keyword Guessing Attack, Trapdoor-IND-CKA, Index-IND-CKA

A number of searchable encryption schemes have been widely proposed to solve the search problem in ciphertext domain. However, most existing searchable encryption schemes are vulnerable to keyword guessing attacks. During keyword guessing attacks, with the help of the cloud, an adversary will learn what keyword a given trapdoor is searching for, which leads to the disclosure of users' privacy information. To address this issue, we propose SDKSE-KGA: a secure dynamic keyword searchable encryption scheme which resists keyword guessing attacks. SDKSE-KGA has constant-size indexes and trapdoors and supports functionalities such as dynamic updating of keywords and files. Formal proofs show that it is Trapdoor-IND-CKA and Index-IND-CKA secure in the standard model.

Introduction

Searchable encryption is an effective way to solve the search problem in ciphertext domain. It not only protects users' privacy but also completes search task. During the process of searchable encryption, users need encrypt data before uploading it. Then, they use trapdoors of keywords to execute search task. So the cloud cannot get exact information about data and keywords.

Song et al. firstly proposed a searchable encryption scheme for mail system in [START_REF] Song | Practical techniques for searches on encrypted data[END_REF]. Then, the concept of searchable encryption (SE) came into people's attention and aroused a series of researches [START_REF] Boneh | Public Key Encryption with Keyword Search[C]. theory and application of cryptographic techniques[END_REF][START_REF] Waters | Building an Encrypted and Searchable Audit Log[END_REF][START_REF] Curtmola | Searchable symmetric encryption: improved definitions and efficient constructions[END_REF][START_REF] Wang | Threshold Privacy Preserving Keyword Searches[END_REF][START_REF] Dong | Searchable Keyword-Based Encryption[END_REF]. According to the encryption methods, divide SE into searchable encryption scheme (SSE) and public-key encryption with keyword search (PEKS). SSE has the advantages of high efficiency and practicability. So people tend to research the functionality of SSE. [START_REF] Moataz | Privacy-Preserving Multiple Keyword Search on Outsourced Data in the Clouds[END_REF][START_REF] Yang | Multi-user Multi-Keyword Rank Search over Encrypted Data in Arbitrary Language[END_REF] realized the function of multi-keyword search. [START_REF] Fu | Toward Efficient Multi-Keyword Fuzzy Search Over Encrypted Outsourced Data With Accuracy Improvement[END_REF][START_REF] Wang | Privacy-preserving multi-keyword fuzzy search over encrypted data in the cloud[END_REF] realized the function of fuzzy search. [START_REF] Zhang | Secure Ranked Multi-keyword Search for Multiple Data Owners in Cloud Computing[END_REF] realized the ranking function of search results. PEKS has the advantage of strong security. So people tend to improve search expressions and security. [START_REF] Ameri | A Key-Policy Attribute-Based Temporary Keyword Search scheme for Secure Cloud Storage[END_REF][START_REF] Liang | Attribute based proxy re-encryption with delegating capabilities[END_REF] implement access control for users search privileges. [START_REF] Cui | AKSER: Attribute-based Keyword Search with Efficient Revocation in Cloud Computing[END_REF] has the traceability for malicious users. [START_REF] Hur | Attribute-Based Access Control with Efficient Revocation in Data Outsourcing Systems[END_REF] implements the revocation of malicious users privileges. [START_REF] Cui | Attribute-Based Encryption with Expressive and Authorized Keyword Search[C[END_REF] implements the verification of search results.

Consider one dynamic mail system: For user Alice, she has many friends and business partners in real life. So her inbox may received all kinds of mails everyday. The inbox will store these mails into cloud servers. Considering the cloud is not fully trusted, all information should be encrypted. When Alice checks mails, she will filter mails generally and search for parts of them. The search keywords are determined by Alice herself, and she is likely to change keywords according to the actual life. This application scenario requires our searchable encryption scheme to support dynamic keywords.

Kamara et al. firstly proposed a dynamic searchable symmetric encryption scheme in [START_REF] Kamara | Dynamic searchable symmetric encryption[END_REF]. They gave the definition of dynamic CKA2 security and constructed algorithm by reverse indexes. But this scheme has the disadvantage of information leakage. They offered an improved scheme in [START_REF] Kamara | Parallel and Dynamic Searchable Symmetric Encryption[C[END_REF]. It uses red black tree as index tree to protect information. But this advantage is at the cost of reducing search efficiency. Hahn et al. presented a new scheme in [START_REF] Hahn | Searchable Encryption with Secure and Efficient Updates[END_REF]. It leaks nothing except the access pattern and requires the scenario to have huge data and a few keywords. Xia et al proposed a multi-keyword ranked search scheme in [START_REF] Xia | A Secure and Dynamic Multi-Keyword Ranked Search Scheme over Encrypted Cloud Data[END_REF], which supports dynamic environment, too. It uses balanced binary tree as index tree and sorts search results for users. But it lacks trapdoor indistinguishable security. Later, they presented a new scheme in [START_REF] Miers | IO-DSSE: Scaling Dynamic Searchable Encryption to Millions of Indexes By Improving Locality[END_REF]. For mail systems, it has significant reduction in IO cost. But the size of index is large. It will make pressure on communication overhead.

Meanwhile, Byun et al. first introduced the concept of keyword guessing attack in [START_REF] Byun | Off-line keyword guessing attacks on recent keyword search schemes over encrypted data[C]. very large data bases[END_REF]. In keyword guessing attacks, adverseries take advantage of the fact that the keywords that one user are likely to use commonly are very limited. So they make guesses of the keyword corresponding to a trapdoor. With the help of the cloud, they are able to verify whether the guess is correct and shortly they will know which keyword this trapdoor is searching for. It is a crucial attack and violates the goal of searchable encryption.

The concept of offline keyword guessing attacks was proposed in [START_REF] Byun | Off-line keyword guessing attacks on recent keyword search schemes over encrypted data[C]. very large data bases[END_REF]. Then Yau et al. presented the concept of online keyword guessing attacks in [START_REF] Yau | Keyword guessing attacks on secure searchable public key encryption schemes with a designated tester[END_REF]. Tang et al. proposed a public-key encryption supporting registered keyword search in [START_REF] Tang | Public-key encryption with registered keyword search[C]. european public key infrastructure workshop[END_REF]. But it requires the sender and the receiver to negotiate registered keywords before the system was established. Compare with it, our scheme relaxes the restrictions on communication between senders and receivers. Chen et al. proposed a searchable encryption under dual systems in [START_REF] Chen | Dual-Server Public-Key Encryption With Keyword Search for Secure Cloud Storage[END_REF]. There are multiple interactions between front server and back server. It prevents independent servers from getting complete information to withstand attacks. Compare with it, the cloud server in our scheme has less computational and communication pressure.

For the above mail system, we construct a dynamic searchable encryption scheme which resists keyword guessing attacks. Our contribution is summarized as follows:

1. Our SDKSE -KGA supports dynamic management of both keywords and files. In the mail system, senders may send messages anytime and receivers may delete messages too. The receiver may add or delete keywords by the binary tree. Compared with other papers, the cost of updating keywords and files is negligible. In addition, the update operation is completely executed by the receiver, so there is no risk of leaking private data. 2. Our SDKSE -KGA has Index-IND-CKA(Index Indistinguishable against Chosen Keyword Attack) security and Trapdoor-IND-CKA(Trapdoor Indistinguishable against Chosen Keyword Attack) security. We will demonstrate security under the standard model. Moreover, the indexes and trapdoors are of constant size which helps to reduce transmission overhead significantly. 3. Our SDKSE-KGA resists keyword guessing attacks. Therefore, our scheme has higher security level compared with other searchable encryption scenarios. In this scheme, the search task is assigned to the cloud server and the receiver, The cloud server performs fuzzy search while the receiver accurate search, The cloud server is not able to obtain specific information of keywords, so it cannot launch the keyword guessing attacks.

The rest of our paper is organized as follows. In Section 2, we will introduce the system model and security model, and describe some symbols used in our construction. In Section 3, we will introduce the keyword tree and fuzzy mapping function in detail. Section 4 depicts SDKSE -KGA scheme in detail. Section 5 and Section 6 will show security analysis and performance analysis of SDKSE -KGA. In the last section we will summarize this paper.

Definitions

System Model

There are three roles in our application scenario: mail senders, mail receivers and the cloud server. The sender is responsible for adding keywords to these files, encrypting files and generating exact indexes and fuzzy indexes for keywords, and uploading them to the cloud server. The receiver is responsible for managing all the keywords by constructing a binary tree, and generating fuzzy and exact trapdoors. After receiving a fuzzy trapdoor, the cloud server conducts fuzzy search upon fuzzy indexes and sends fuzzy results to the receiver. Then the receiver performs exact search on the fuzzy results based on the exact trapdoors to obtain final results. Considering third-party cloud servers cannot be fully trusted, we hope the cloud server get as little information as possible. Moreover, with the help of the cloud, KGA will learn what keyword a given trapdoor is searching for, which leads to the disclosure of users privacy information. In our model, the cloud server is only allowed to perform fuzzy search. Even if it has access to all the fuzzy indexes of keywords and some of legal fuzzy trapdoors, it is still unable to get the exact information of the search. Moreover, this model not only protects the security of keywords, but also resists keyword guessing attacks. Query Phase 2. Repeat Query Phase 1.The adversary A continue to issue keywords except the target keywords w * 0 and w * 1 . Guess. The adversary gives β as the guess of β, if β = β, then the adversary wins. The advantage of A in this game is defined as follows:

Adv A = |P r[β = β ] -1 2 |
Definition 1. We say that SDKSE-KGA is Index-Indistinguishable security if Adv A is negligible for any polynomial time attacker A. The advantage of B in this game is defined as follows:

Adv B = |P r[β = β ] -1 2 |
Definition 2. We say that SDKSE-KGA is Trapdoor-Indistinguishable security if Adv B is negligible for any polynomial time attacker B. The advantage of C in this game is defined as follows:

Adv C = |P r[β = β ] -1 2 | Definition 3.
We say that SDKSE-KGA is Adaptive KGA security if Adv C is negligible for any polynomial time attacker C.

Notations

This part we will illustrate some symbols used in this scheme. To manage all the keywords, we build a binary tree denoted by T , use L to indicate the height of T . And the height L is related to N which means the number of keywords. The fuzzy keyword mapped by the keyword w is expressed as w f . [I 1 , .. -IndexDelete(w) : Notify related files to update keyword list and delete existing index of w.

3 Preliminaries

Keyword Tree

The receiver is responsible for constructing the binary tree T . The tree T has two tasks: managing keywords dynamically and running fuzzy mapping function.

Construct tree T based on the number of keywords N , height L = log 2 N + 2.

Each leaf node may bind to one keyword. We call one leaf node that have not yet bound keyword as available node. The number of available nodes is denoted by avlS. In order to ensure the growth of the tree, we require avlS ≥ minS, where minS = 2 It is very easy to delete one keyword. We just need to set the state of the leaf node bound to this keyword to 0, and if this key is used again later, just change the state of the leaf node to 1. Adding keyword can be divided in two situations: If avlS > minS, select an appropriate available leaf node and bind it to the keyword. Then set its state value to 2. If avlS = minS, then generate child nodes of all available leaf nodes to double the number of available leaf nodes. The growth process is shown in Now we design fuzzy mapping function to map each keyword to a fuzzy keyword. The position of the fuzzy keyword in the tree will be used to generate the pair of fuzzy index and fuzzy trapdoor. The cloud server searches upon the fuzzy index-trapdoor pair while the receiver searches upon the exact indextrapdoor pair. Now we introduce the fuzzy mapping function. For one leaf node in the binary tree, trace it up to n levels where n is a parameter defined by users, the obtained node is the corresponding fuzzy node of it. If two leaf nodes have the same ancestor node after tracing the same layers, then these nodes share a fuzzy node.

Bilinear Map

In our scheme, we apply bilinear map to F uzzySearch and ExactSearch algorithm. The specific principle is as follows:

There is a composite group G with order n = p 1 p 2 p 3 p 4 where p 1 , p 2 , p 3 and p 4 are distinct primes. Assume one of the generators of G is G, then the generators of G p1 , G p2 , G p3 and G p4 are G 1 , G 2 , G 3 and G 4 respectively. And

G 1 = G p2p3p4 , G 2 = G p1p3p4 , G 3 = G p1p2p4 , G 4 = G p1p2p3
. We infer that for distinct i and j, ∀R i ∈ G pi , R j ∈ G pj , e(R i , R j ) = 1 holds.

Complexity Assumptions

The security of our scheme is based on six complexity assumptions [START_REF] Seo | Fully Secure Anonymous Hierarchical Identity-Based Encryption with Constant Size Ciphertexts[END_REF]. The hardness of these assumptions relies on the theorems proposed by [START_REF] Katz | Predicate encryption supporting disjunctions, polynomial equations, and inner products[C]. theory and application of cryptographic techniques[END_REF].

In Assumption 1, given a group generator G, input security parameter λ, then generate primes p 1 , p 2 , p 3 , p 4 , two groups G, G T , and the bilinear map e. Set the integer n = p 1 p 2 p 3 p 4 . Select random element x from G p1 , similarly select The following assumptions are very similar to Assumption1, so we only introduce their differences. In Assumption 2,

G 3 from G p3 and G 4 from G p4 . Set D = {G, n, x, G 3 , G 4 }. T 0 ∈ G p1p2p4 , T 1 ∈ G p1p4
D = {G, n, x, G 1 G 2 , G 3 , H 2 H 3 , G 4 }, T 0 ∈ G p1p2p3 ,T 1 ∈ G p1p3 . And G 1 R ← G p1 , G 2 , H 2 R ← G p2 , G 3 , H 3 R ← G p3 , G 4 R ← G p4 . In Assumption 3, D = {G, n, G 1 , H 2 H 3 , G 3 , G 4 }, T 0 = H 2 H 3 ,T 1 ∈ G p1p3 . And G 1 R ← G p1 , H 2 R ← G p2 , G 3 , H 3 , H 3 R ← G p3 , G 4 R ← G p4 . In Assumption 4, D = {G, n, G 1 , H 2 H 4 , G 3 , G 4 }, T 0 ∈ G p2p4 ,T 1 ∈ G p4 . And G 1 R ← G p1 , H 2 R ← G p2 , G 3 R ← G p3 , G 4 , H 4 R ← G p4 . In Assumption 5, D = {G, n, x, G 1 G 2 , G 3 , H 1 H 2 , I 2 I 3 , G 4 }, T 0 = e(G 1 , H 1 ),T 1 ∈ G T . And x, G 1 , H 1 R ← G p1 , G 2 , H 2 , I 2 R ← G p2 , G 3 , I 3 R ← G p3 , G 4 R ← G p4 . In Assumption 6, D = {G, n, G 1 G 4 , H 1 H 2 , I 2 , I 3 , I 4 , J 1 J 2 J 4 }, T 0 ∈ J 1 J 2 J 4 ,T 1 ∈ G p1p2p4 . And G 1 , H 1 , J 1 R ← G p1 , H 2 , I 2 , J 2 , J 2 R ← G p2 , I 3 R ← G p3 , G 4 , I 4 , J 4 , J 4 R ← G p4 .
For Assumption 1 ∼ 6, we have the following definition: Definition 4 : For any polynomial time, if Adv -N G,B (λ) is a negligible function of λ, then we think the group generator G satisfies Assumption N , N ∈ {1, 2, 3, 4, 5, 6}.

Construction

In this section we will introduce SDKSE-KGA in detail.

Setup(λ, N ) : First, the receiver builds the keyword tree T to manage initial keywords. For keyword w, encode it as [I 1 , . . . , I h ] according to its position in the binary tree. Note h = L -1. Next, runs group generator G and obtains (p 1 , p 2 , p 3 , p 4 , G, G T , e). Then, selects random elements x, y, u 1 , ...,

u h , ω ← G p1 , G 3 ← G p3 , G 4 ← G p4 , R 4 , R 4,g , R 4,h , R 4,u1 , ..., R 4,u h ← G p4 . G 3 is
the generator of G p3 and G 4 is the generator of G p4 respectively. So a random element of G p4 can be chosen by raising G 4 to random exponents from

Z n . At last, set n = p 1 p 2 p 3 p 4 , X = xR 4,g , Y = yR 4,h , U 1 = u 1 R 4,u1 , ..., U h = u h R 4,u h , E = e(g, ω). The public parameters params = [G, n, X, Y, U 1 , . . . , U h , R 3 , R 4 , E].
The master private key M SK = [x, y, u 1 , . . . , u h , ω]. The receiver publishes the params and retains the M SK for generate trapdoors later.

Encrypt(params, w) : w represents the keyword to be encrypted, parse it to [I 1 , ..., I h ]. The sender selects random integer s ← Z n and random elements R 4 , R 4 ← G p4 . Picks random message M . Next, set

CT 0 = M E s , CT 1 = (H h i=1 U Ii i ) s R 4 , CT 2 = G s R 4 . Set CT ← [CT 0 , CT 1 , CT 2 ] ∈ G T × G 3 . Define ExactIndex = [M, CT ].
Then, according to the fuzzy mapping function, the keyword w is mapped to w f , parse it to [I 1 , ..., I h f ]. The sender selects random integer

s f ← Z n and random elements R f,4 , R f,4 ← G p4 . Picks random message M f . Next, set CT f,0 = M f E s f , CT f,1 = (H h f i=1 U Ii i ) s f R f,4 , CT f,2 = G s f R f,4 . Set CT f ← [CT f,0 , CT f,1 , CT f,2 ] ∈ G T × G 3 . Define F uzzyIndex = [M f , CT f ].
TDGen(M SK, w) : w is the keyword to be retrieved. Parse w to [I 1 , ..., I h ]. The receiver selects random integers r 1 , r 2 ← Z n and random elements

R 1 3 , R 3 2 , R 3 3 , R 4 3 , R 3 5 , R 6 3 ← G 4 p3 .
To obtain the exact trapdoor ET d of the keyword w.

Set T d 1 = x r1 R 1 3 , T d 2 = ω(y h i=1 u Ii i ) r1 R 3 2 , T d 3 = u r1 h R 3 3 , T d 4 = x r2 R 4 3 , T d 5 = ω(y h i=1 u Ii i ) r2 R 3 5 , T d 6 = u r2 h R 6 3 . Set ET d = [T d 1 , T d 2 , T d 3 , T d 4 , T d 5 , T d 6 ].
Map the keyword w to w f , parse it to [I 1 , ..., I h f ]. The receiver selects random integers r f,1 , r f,2 ← Z n and random elements

R 1 f,3 , R f,3 2 , R 3 f,3 , R 4 f,3 , R f,3 5 , R 6 f,3 ← G 4 p3 .
To obtain the fuzzy trapdoor F T d of the keyword w.

Set T d f,1 = x r f,1 R 1 f,3 , T d f,2 = ω(y h f i=1 u Ii i ) r f,1 R f,3 2 , T d f,3 = u r f,1 h f R 3 f,3 , T d f,4 = x r f,2 R 4 f,3 , T d f,5 = ω(y h f i=1 u Ii i ) r f,2 R f,3 5 , T d f,6 = u r f,2 h f R 6 f,3 . Set F T d = [T d f,1 , T d f,2 , T d f,3 , T d f,4 , T d f,5 , T d f,6 ]. FuzzySearch(F uzzyIndex, F T d) : Parse F T d to [T d f,1 , T d f,2 , T d f,3 , T d f,4 , T d f,5 ,T d f,6 ]. F uzzyIndex = [M f , CT f ], parse CT f to [CT f,0 , CT f,1 , CT f,2 ]. Compute M f = CT f,0 • e(T d f,1 ,CT f,1 ) e(T d f,2 ,CT f,2 ) . If M f = M f ,
add all files containing exact keywords which mapping to w f into the fuzzy result F uzzyCipher. Then F uzzyCipher will be sent to the receiver.

ExactSearch(ExactIndex, ET d) : Parse ET d to [T d 1 , T d 2 , T d 3 , T d 4 , T d 5 , T d 6 ]. ExactIndex = [M, CT ], parse CT to [CT 0 , CT 1 , CT 2 ]. Compute M = CT 0 • e(T d1,CT1) e(T d2,CT2) .
If M = M , then output the file set C which contains the keyword w. KWInsert(w) : Select an appropriate leaf node to bind the new keyword w in the binary tree.

IndexInsert(w) : Generate the index based on the location in the tree and add it into index list.

KWDelete(w) : Disable the keyword w in the binary tree. IndexDelete(w) : Delete the index of w from the index list.

Security Proof

In this section, we will prove the security of SDKSE -KGA. Each keyword owns an exact trapdoor-index pair and a fuzzy trapdoor-index pair. The sender generates fuzzy indexes and exact indexes and sends them to the cloud. The receiver generates fuzzy trapdoors and exact trapdoors and sends fuzzy trapdoors to the cloud. Notice that in both F uzzySearch and ExactSearch algorithms, only if the location strings corresponding to the trapdoor and the index are identical, the match operation will succeed. Since the fuzzy trapdoors and fuzzy indexes are generated upon the position, which one-to-one mapped into the location string of the fuzzy node, the match operation will only succeed when the fuzzy trapdoor and fuzzy index are generated upon the same fuzzy node. On the other hand, fuzzy nodes and exact nodes are different from each other, so the match operation upon a fuzzy trapdoor and an exact index will always generates ⊥. Therefore, even the cloud gets exact indexes, the privacy of users will not be destroyed. Now we will prove our SDKSE -KGA is Index -IN D -CKA and T rapdoor -IN D -CKA secure.

Theorem 1. Our SDKSE -KGA scheme is Index -IN D -CKA secure if a group generator G holds assumptions in [START_REF] Seo | Fully Secure Anonymous Hierarchical Identity-Based Encryption with Constant Size Ciphertexts[END_REF].

Proof. We will give the definitions of semi-functional indexes and semi-functional trapdoors for ExactIndex and ET d , and show a series of games. Semi-functional indexes are composed by CT 0 ,CT 1 ,CT 2 .

CT 0 = CT 0 , CT 1 = CT 1 x rzc 2 , CT 2 = CT 2 x r 2 .
where CT 0 , CT 1 and CT 2 are components of CT generated in Encrypt algorithm. And x 2 ∈ G p2 , r, z c R ← Z N . Semi-functional trapdoors are as follows:

T d 1 = T d 1 x γ 2 , T d 2 = T d 2 x γz1 2 , T d 3 = T d 3 x γz2 2 , T d 4 = T d 4 x γ 2 , T d 5 = T d 5 x γ z 1 2 , T d 6 = T d 6 x γ z 2 2
, where T d ← Z N . In addition, we need to construct a series of games. Game Real : Game 1. Game Restricted : It is similar to Game Real except that the adversary cannot query keywords which are prefixes of the challenge keyword modulus p 2 . Game k :0 ≤ k ≤ q, and q is the number of queries made by the adversary. The difference between Game k and Game Restricted are query results. The challenge index is semi-functional index in two games and the first k results of trapdoor are semi-functional trapdoors in Game k . Game Mhiding : It selects random elements from G and constructs CT 0 of the challenge index. Game Random : The second component and the third component of challenge indexes are independent random elements in G p1p2p4 in this game.

In Game Random , the adversary knows nothing about keyword from the challenge index. So we need prove Game Real and Game Random are distinguishable. First step, the adversary selects keywords w 0 and w 1 , w 0 = w 1 mod n and w 0 ≡ w 1 mod p 2 . The simulator ∫ factor n by computing gcd(w 0 -w 1 , N ). But the assumption 1,2,3 will prove that n cannot be decomposed. As a result, Game Real and Game Restricted are distinguishable. Second step, we will prove Game Restricted and Game k are distinguishable. According to assumption 1, construct a new game. In this game, if T = T 0 , the index generated by challenger is semi-functional index. In this case, the game is equal to Game 0 eventually. If T = T 1 , the index generated by challenger is normal index and the game is equal to Game Restricted . T 0 and T 1 have the same distribution in statics, so Game Restricted and Game k are distinguishable. Third step, we will prove the series games Game k (0 ≤ k ≤ q) are distinguishable. Use the same way to construct a new game according to assumption 5. The trapdoors sent by challenger are semi-functional trapdoors. If T = T 0 , the game is equal to Game q . If T = T 1 , the game is equal to Game M hiding . So Game q and Game M hiding are indistinguishable. Continue to deduce, we will get the conclusion that Game M hiding and Game Random are indistinguishable by constructing the new game according to assumption 6. Finally, Game Real and Game Random are distinguishable. The proof is completed.

= x r1 R 1 3 , T d 2 = ω(y h i=1 u Ii i ) r1 R 2 3 , T d 3 = u r1 h R 3 3 , T d 4 = x r2 R 4 3 , T d 5 = ω(y h i=1 u Ii i ) r2 R 5 3 , T d 6 = u r2 h R 6 3 .
x, y, w, u 1 , . . . , u h belong to public parameters, R i . m 0 and m 1 are the elements in G p1 . In statistics, the distributions of m r 0 and m r 1 are exactly the same where r is a random element in Z n . So the adversary is not able to guess the value of β by m 0 , m 1 . In other words, the adversary should not be able to distinguish the trapdoors of w * 0 and w * 1 . The proof is completed.

Theorem 3. Our SDKSE -KGA scheme is Adaptive KGA secure.

Proof. Case 1: If two challenge keywords will map to different fuzzy keywords, they will generate different fuzzy trapdoors. So the KGA security game is exactly the same as Trapdoor-IND security game. In this case, the advantage of adversary winning the game is negligible. Case 2: If two challenge keywords will map to the same fuzzy keywords, they will generate the same fuzzy trapdoors. The challenge keywords w * 0 and w * 1 have the same distribution in statistics. The adversary cannot determine β based on the fuzzy trapdoor. In other words, he cannot distinguish between w * 0 and w * 1 . In both cases, the advantage of the adversary winning the game is negligible.

Performance

This section mainly gives the performance analysis of SDKSE-KGA. The Setup algorithm requires h + 2 multiplications and one pairing, it takes 2(h + 3) multiplications and 6 modular exponentiations to generate one exact trapdoor where h denotes the height of keyword tree in the scheme. It takes h + 2 multiplications and 3 modular exponentiations to generate one index. For Search algorithm, it requires 2 pairings and 2 multiplications. The computational overhead of KW Insert and KW Delete are negligible. Our SDKSE -KGA scheme supports keyword and file updating at the same time. To add a document, [START_REF] Xia | A Secure and Dynamic Multi-Keyword Ranked Search Scheme over Encrypted Cloud Data[END_REF] and [START_REF] Kamara | Dynamic searchable symmetric encryption[END_REF] need to iterate through keyword arrays and [START_REF] Kamara | Parallel and Dynamic Searchable Symmetric Encryption[C[END_REF] needs to traverse a KRB tree. So the updating cost is very high. In addition, the index and trapdoors of our scheme are of constant size which reduces transmission overhead significantly. Table 1 shows the efficiency comparison between [START_REF] Xia | A Secure and Dynamic Multi-Keyword Ranked Search Scheme over Encrypted Cloud Data[END_REF], [START_REF] Kamara | Dynamic searchable symmetric encryption[END_REF], [START_REF] Kamara | Parallel and Dynamic Searchable Symmetric Encryption[C[END_REF] Compared with other searchable encryption schemes which resist keyword guessing attacks, In terms of communication overhead, the size of index and trapdoor in SDKSE-KGA scheme is not affected by the number of files. Table 2 shows our advantages between this scheme and others. In this table, G represents a member of the group, P airing means a bilinear pair operation, Exp means

Conclusion

In this paper, we proposed a secure dynamic searchable encryption scheme SDKSE -KGA which resists keyword guessing attacks for mail systems. The complexity of the index and the trapdoor of SDKSE -KGA are both constant size. Therefore, SDKSE -KGA is capable of supporting dynamic management of mails and keywords and resisting keyword guessing attacks. In addition, it is both Index -IN D -CKA and T rapdoor -IN D -CKA secure.

Acknowledgement

by "the Fundamental Research Funds for the Central Universities". Zhenfu Cao and Jiachen Shen are the corresponding authors.

  Fig 1 shows the system model.

Fig. 1 :

 1 Fig. 1: System model

Game 2 :

 2 (T rapdoor -IN D -CKA security) Setup. The challenger runs Setup algorithm to obtain the public parameters and the master secret key. He retains the master secret key and gives the public parameters to the adversary B. Query phase 1. The adversary B adaptively selects keyword w to issue. The challenger generates ET d for w and sends it to B. Challenge. The adversary B selects target keywords w * 0 and w * 1 . Both of two target keywords has not queried before. Then, the challenger flips a coin β ∈ {0, 1}, generates the ET d for w * β and sends it to B. Query Phase 2. Repeat Query Phase 1. The adversary continue to issue keywords except the target keywords w * 0 and w * 1 . Guess. The adversary gives β as the guess of β, if β = β, then the adversary wins.

Game 3 :

 3 (Adaptive KGA security) Setup. The challenger runs this algorithm to obtain the public parameters and the master secret key. Then he retains the master secret key and gives the public parameters to the adversary C. Query phase 1. The adversary C queries the fuzzy trapdoor and fuzzy index of any keyword. Challenge. The adversary selects the keyword w * 0 and w * 1 as challenge keywords, and neither keyword has been quried before. Then the challenger randomly selects the keyword w * β (β ∈ {0, 1}), generates ciphertext F T d w * β for it, and sends the trapdoor to C. Query Phase 2. Repeat Query Phase 1. The adversary C continue to query the fuzzy trapdoor and fuzzy index of keywords except the target keywords w * 0 and w * 1 . Guess. The adversary gives β as the guess of β, if β = β, then the adversary wins.

  ., I h ] represents the location of keyword in the tree. The exact index and fuzzy index of keywords are respectively represented by ExactIndex and F uzzyIndex. The exact trapdoor and fuzzy trapdoor of keywords are respectively represented by ET d and F T d. Definition 3.(SDKSE -KGA) A securely dynamic keyword searchable encryption scheme which resists keyword guessing attacks is a tuple of nine polynomialtime algorithms SDKSE = (Setup, Encrypt, T DGen, F uzzySearch, ExactSearch, KW Insert, IndexInsert, KW Delete, IndexDelete) such that -Setup(λ, N ) → (params, M SK) : In this algorithm, input the security parameter λ and the number of keywords N , generate keyword tree T , output public parameters of the scheme params and master secret key M SK. -Encrypt(params, w) → (F uzzyIndex, ExactIndex) : In this algorithm, input params and keyword w. Generate fuzzy index F uzzyIndex and exact index ExactIndex for w. -T DGen(M SK, w) → (F T d, ET d) : In this algorithm, generate fuzzy trapdoor F T d and exact trapdoor ET d for keyword w by M SK. -F uzzySearch(F uzzyIndex, F T d) → (F uzzyCipher or ⊥) : In this algorithm, input fuzzy index F uzzyIndex and fuzzy trapdoor F T d to match. If the match operation is successful, add these files associated with F uzzyIndex to the fuzzy ciphertext set F uzzyCipher. If the operation is failed, output ⊥. -ExactSearch(ExactIndex, ET d) → (C or ⊥) : In this algorithm, input exact index ExactIndex and exact trapdoor ET d for operation. If the operation is successful, output file set which contain keyword w. If the operation is failed, output ⊥. -KW Insert(w) : Insert new keyword w to the tree T . -IndexInsert(w) : Notify related files to update keyword list and generate encrypted keyword C for new keyword w. -KW Delete(w) : Disable node bound to keyword w from tree T .

Fig 2 .

 2 Now avlS > minS, so we continue to add keywords.

Fig. 2 :

 2 Fig. 2: Grow Tree

  and β ∈ {0, 1}. Give (D, T β ) to the adversary B, the adversary B outputs a guess β , if β = β, then he succeeds. Define Adv1 G,B (λ) to denote the advantage of B, Adv1 G,B (λ) = |P r[β = β] -1 2 |.

Theorem 2 .

 2 Our SDKSE -KGA scheme is T rapdoor -IN D -CKA secure. Proof. In Game 2, the adversary selects target keywords w 0 and w 1 , then receives ET d w * β from the challenger. As we all known, ET d w = [T d 1 , T d 2 , T d 3 , T d 4 , T d 5 , T d 6 ] where T d 1

1 3 ∼ R 6 3

 6 are random elements selected from G 4 p3 . So the adversary only infer the value of β from T d 2 or T d 5 . According to the property of bilinear pairing, R 2 3 in T d 2 can be removed by elements of G pi ,i ∈ [1, 2, 4]. The location strings [I 1 , . . . , I h ] of w 0 and w 1 are known to the adversary, he is able to compute m 0 = y h i=1 u

Fig. 3 :

 3 Fig. 3: Index Size

  and SDKSE-KGA and Fig 3 shows the comparison of the index sizes of different schemes.

  L-2 . Each leaf node has three states: disable, occupied, available. They are represented by [0, 1, 2] respectively. Disable state means this leaf node is bound to one disable keyword. Occupied state means this leaf node is bound to one keyword. Available state means this leaf node has not been bound.

  1 , T d 2 , T d 3 , T d 4 , T d 5 , T d 6 are components of ET d generated in T DGen algorithm, x 2 ∈ G p2 , and γ, γ , z 1 , z 1 , z 2 , z 2

	R

Table 1 :

 1 Comparisons with dynamic searchable schemes

	Compare Items	[20] [17] [18] SDKSE -KGA
	Dynamic file
	Dynamic Keyword ×	×	×
	Trapdoor-IND		×	×
	Index Size	O(n 2 ) O(n) O(n)	O(1)
	Trapdoor Size O(n 2 ) O(1) O(1)	O(1)
	Insert File	O(n) O(n) O(n)	O(1)
	Insert Keyword N/A N/A N/A	O(n)

power operation while M ul means multiplication operation. n is the number of all files.

Table 2 :

 2 Comparisons with schemes resisting KGA

	Schemes	Index Size Search Overhead KGA Dynamic
	[27]	2 |G|	P airing	×
	[28]	3 |G|	(7Exp + 3M ul) n	×
	[29]	2 |G|	P airing	×
	SDKSE-KGA	3 |G|	2P airing

This work was supported in part by the National Natural Science Foundation of China (Grant No.61632012, 61672239, 61602180. and U1509219), in part by Natural Science Foundation of Shanghai (Grant No. 16ZR1409200), and in part