text:
Provably Manipulation-Resistant Reputation Systems

We consider a community of users who must make periodic decisions about whether to interact with one another. We propose a protocol which allows honest users to reliably interact with each other, while limiting the damage done by each malicious or incompetent user. The worst-case cost per user is sublinear in the average number of interactions per user and is independent of the number of users. Our guarantee holds simultaneously for every group of honest users. For example, multiple groups of users with incompatible tastes or preferences can coexist. As a motivating example, we consider a game where players have periodic opportunities to do one another favors but minimal ability to determine when a favor was done. In this setting, our protocol achieves nearly optimal collective welfare while remaining resistant to exploitation. Our results also apply to a collaborative filtering setting where users must make periodic decisions about whether to interact with resources such as movies or restaurants. In this setting, we guarantee that any set of honest users achieves a payoff nearly as good as if they had identified the optimal set of items in advance and then chosen to interact only with resources from that set.

Introduction
Trust and reciprocity distinguish repeated interactions within a small village from isolated interactions in a massive online community. In a small group we are willing to trust each other and expect that "what goes around comes around," but online we are more guarded: we rely on trusted mediators, expect others to do the bare minimum they have promised, and rarely leave ourselves vulnerable to exploitation. Can the advantages of trust within a small group be realized at a global scale, in an environment where repeat interactions are rare and manipulation will be rampant if it is profitable?
We help address this question by showing that a subset of individuals who intend to trust and help each other can reap the benefits even in the presence of a large majority of exploitative manipulators. This result continues to hold when feedback is extremely noisy, individuals engage in only a handful of interactions, and the manipulators coordinate adversarially. Our per-user performance guarantees are completely independent of the size of the community.
We use online learning over positive semidefinite matrices to iteratively adjust a symmetric measure of trust. This symmetric measure is coupled with a non-trivial system for tracking reciprocal obligations. The result is a protocol which guarantees that the honest users perform nearly as well as if they had simply excluded all dishonest users.

Motivating example
Consider a set of N users with periodic opportunities to do one another favors. In each round, two users Alice and Bob are chosen at random; Alice may choose to a pay a cost of 1, and if she does then Bob receives an expected benefit of 1 + ε.
If the users were maximizing collective welfare then they would always take these opportunities. After kN rounds the average user's payoff would be εk. But such an altruistic community is open to exploitation by defectors, who receive favors but don't reliably pay them back. Is there an altruistic strategy which can achieve high collective welfare but isn't vulnerable to such exploitation?
We assume that a favor confers an expected benefit of 1 + ε, but that the actual benefit is either 0 or ρ. In this case three distinct outcomes are indistinguishable to most users: • Alice does Bob a favor, but by chance the benefit is 0.
• Alice claims to have done a favor for Bob, though in fact she did not.
• Bob claims not to have received a favor, though in fact he did.
Suppose some set of αN "honest" users is willing to follow whatever protocol we specify. If they knew each other's identities in advance, then after kN rounds these users could achieve an average benefit of αεk by always doing favors for each other and never doing unreciprocated favors for outsiders. We show how to obtain a result nearly this good without knowing the identities of the honest users in advance. Namely, we show that there is a protocol which allows the average honest user a payoff of αεk − O ρk 2/3 α after kN rounds, regardless of how the dishonest users behave or how many of them there are.

The model
Consider a set of N users and a sequence of rounds, t = 0, 1, . . .. In each round, a pair of users x t 0 , x t 1 ∈ [N ] is chosen by nature, along with a pair of payoffs p t 0 , p t 1 ∈ [−ρ, ρ]. All users learn the values x t 0 , x t 1 . The users x t i choose whether to interact, picking s t i ∈ {0, 1}. If either user picks 0 then they don't interact and both receive a payoff of 0. If both users pick 1 then they do interact and x i receives a payoff p t i . Each user learns the payoff they receive but not what payoff their partner received.
For the analysis, we fix a set H ⊂ [N ] of "honest" users who will follow whatever protocol we prescribe and whose welfare we will seek to maximize. Our guarantees will simultaneously hold for any set H whose members follow our protocol. We will assume that the users have access to unlimited cheap talk (in the form of broadcasts), verifiable identities, and a shared random beacon. 1 The payoff of a user p ≤T (x) is the sum of their payoffs in rounds they participated in: Let p ≤T (H) be the total payoff of the honest users after T rounds, i.e.
We define the benchmark OPT ≤T (H) to be the counterfactual payoff of the honest users if they had always interacted with each other and only with each other: In some of our results we include the possibility of transfers. If transfers are available, player x t i chooses a payment τ t i ≥ 0 to make to their partner at the end of round t. Player x t 0 then receives an additional payoff of τ t 1 − τ t 0 and player x t 1 receives an additional payoff of τ t 0 − τ t 1 . These additional payoffs are included in the sum defining p ≤T (x).
Our framework only considers interactions between users, but by introducing users who always agree to interact and always receive a payoff of 0 we can easily model static resources such as movies, news articles, or merchants who don't care whom they interact with. Some of our results concern the collaborative filtering setting, in which each interaction involves one resource and one user. For notational convenience, we will assume that the resource is always x t 1 and the user is always x t 0 . In this setting the set H contains both honest users and some set of resources. To obtain the best bounds we will usually imagine that H contains the "optimal" set of items according to the users in H, i.e. all items which yield a positive payoff on average.
We have described the interactions as being proposed "by nature" but these interactions can also be proposed by the users. Our protocol can be used as a black box within a larger system designed to maximize OPT ≤T (H). 2

The results
Our main result is the following: Theorem 1. There is a randomized polynomial time protocol which yields expected performance for every set H of honest users, assuming that one of the following conditions is satisfied: 1. Transfers are available.
2. In every round p t 1 = 0. (The collaborative filtering setting.) 3. In every round with x t 0 , x t 1 ∈ H the payoffs are symmetric ex ante: , and all information available before round t.
Note that the favor setting described in Section 1.1 satisfies this ex ante symmetry condition, provided that Alice has an opportunity to do Bob a favor with the same probability that Bob has an opportunity to do Alice a favor. 3 If we hold fixed the ratio k = T /N , then the regret is O ρN k 2/3 . So the introduction of each dishonest user increases the total regret by O ρk 2/3 over the first k interactions. 4 If we also hold fixed the ratio α = |H| /N = α, then the per-user regret bound is independent of N . In massive communities, this requires two interacting users to make informed decisions even if they are connected only by a long and tenuous chain of mutual acquaintances.
We also prove the following lower bound on the achievable regret: Theorem 8. For every protocol and every T , there exists a set of payoffs and a set H such that in expectation, even assuming that p t 0 = p t 1 in every interaction.
That is, over the first k interactions it is necessary for the honest users to collectively pay a cost of Ω ρk 1/2 per dishonest user just to get enough information to statistically identify them.
There is a tension between choosing a smaller set H-for which the optimum payoff may be higherand choosing a larger set H in order to amortize the loss O ρ 3 √ N T 2 over a larger set. For collaborative filtering in particular, recommendations optimized for a smaller group of users will be strictly better. This tension is only in the analysis, however, since the guarantee applies simultaneously for every group H. As T grows and the term O ρ 3 √ N T 2 becomes less important, the best 3 Some condition of this form is clearly necessary. For example, suppose that Alice has an opportunity to do Bob a favor in every round. If Alice does not take these opportunities, then we have failed to maximize collective welfare. But if Alice does take these opportunities, then we have failed to maximize Alice's welfare. Since we need to satisfy the theorem for both H = {Alice} and H = {Alice, Bob}, either way we are in trouble. 4 The addition of an honest user also increases the regret by O ρk 2/3 , but typically decreases the average regret per honest user. If an α fraction of users are honest, then the average regret per honest user is O ρk 2/3 α . analysis might obtain for smaller and smaller groups H, and to compete the algorithm must make more and more finely-tuned recommendations.
We note that our model differs from many other approaches to reputation systems or collaborative recommendation; our protocol merely filters proposed interactions, rather than recommending optimal interactions. It is up to the users of the system to propose interactions, and also to estimate the opportunity cost of mediocre interactions (we assume that any interaction with a positive payoff was good, so 0 needs to represent the "indifferent" outcome; watching a good movie should have a negative payoff, if I would otherwise watch a great movie).
In some settings this seems like an acceptable model. For example, I might browse an online marketplace, find an item that looks like a good deal, and then use the merchant's reputation to decide whether to purchase it. Or I might see a movie which looks interesting and use reviews to decide whether to watch it.
In other settings this is a very inappropriate model. For example, I might have the choice between hundreds of merchants offering the same item. In this case I just want to be recommended the best one. Our results would need to be strengthened to be applicable in such settings.
See Section 11 for a more extensive discussion of modeling issues, limitations, and directions for further work. Our protocol makes a qualitatively novel guarantee, but there is ample room for improvement. For example, our algorithm is not distributed, the protocol is not incentive-compatible for honest users, and we only consider sequential interactions.

The protocol
Our main algorithmic contribution is an online learning algorithm which could be used by a central planner to decide which pairs of users should interact. The primary difficulty is that the set H is not known in advance and so we need to simultaneously lower bound the total payoff of every set H. This is an unusual guarantee, and requires a novel technical approach. This algorithm is outlined in Section 4.1 and formally analyzed in Section 6.
This algorithm can then be used directly to achieve our guarantees when p t 1 = 0 or when p t 0 = p t 1 . If transfers are available, we reduce to the case p t 0 = p t 1 by using transfers to equalize the two payoffs. These reductions are routine, and are analyzed in Section 7.
The most challenging condition in Theorem 1 is ex ante symmetry. To address this case we introduce a digital currency, and use transfers of this currency to equalize payoffs. The primary difficulty is ensuring that there is sufficient liquidity to facilitate transactions between honest users. We propose a robust protocol based on logarithmic utility functions. This system is outlined in Section 4.2 and formally analyzed in Section 8.

Outline of the central planner's algorithm
Consider the following single-payoff problem faced by a central planner: in each round a pair of individuals x t 0 , x t 1 ∈ [N ] is given, the planner outputs s t ∈ [0, 1] representing the probability with which x t 0 and x t 1 should interact, and then nature reveals a payoff p t for the interaction.
There are two different payoffs associated with a set H in this game, depending on whether we think of the payoff as accruing to player 0 or player 1: We can create a symmetric version, in which the payoff is shared equally between the two players, by averaging p ≤T 0 and p ≤T 1 . All of these different payoff notions are associated with the same benchmark: We exhibit an algorithm PLAN satisfying: x t 1 and the information from all previous rounds. Then for every H, T and i, PLAN achieves payoffs satisfying This protocol can be used almost directly to achieve low regret when p t 1 = 0 (by applying the lower bound on p ≤T 0 (H)) or when p t 0 = p t 1 (by applying the lower bound on p ≤T (H) = p ≤T 0 (H) + p ≤T 1 (H)).
The basic outline of our algorithm PLAN is: • The planner initializes a matrix P t ab , indexed by a, b ∈ [N ], with P 0 ab = 1.
• In step t, the planner outputs s t = P t • After step t, the planner uses an online learning algorithm to predict matrices C t+1 ab (for cut) and J t+1 ab (for join).
• The planner then updates The matrices C t+1 ab and J t+1 ab are chosen by the online learning algorithm with the goal of maximizing p t+1 s t+1 .
J t and C t are predicted by the online local learning algorithm from [4], which achieves payoffs as high as the best fixed matrices of the form for any distribution over labelings ℓ : The most counterintuitive feature of the algorithm is that the predicted matrices are used to adjust P , rather than to directly determine which users should interact. This allows the protocol to build up more complex patterns of interaction as time goes on, and is needed to minimize regret for every set H simultaneously. Other approaches we tried, such as using an online learning algorithm with a richer comparison class, were unable to achieve this guarantee.
The analysis proceeds in several steps: • The online learning guarantee implies that the matrices P t ab perform nearly as well as any sequence of the form Q t ab (J * , C * ) = (1 − J * ab − C * ab )P t−1 ab + J * ab , where J * and R * are constant matrices from the comparison class. That is, the recommendations J t and C t are nearly optimal within this class.
• The strong smoothness lemma for the online learning algorithm implies that J t ab and C t ab change slowly. Using this fact and a non-trivial analysis of our update rule we prove that P t ab − P t−1 ab is small on average. This implies that the matrices Q t perform nearly as well as the matrices R t ab (J * , C * ) = (1 − J * ab − C * ab )P t ab + J * ab . (The superscript on P has changed from t − 1 to t; this difference may appear small, but it leads to a much harder analysis and ultimately to our suboptimal dependence on T .) , then there is some pair of matrices J * , C * in the comparison class such that the matrices R t (J * , C * ) substantially outperform the matrices P t . Namely, we can take J * ab = 1 for a, b ∈ H, and C * (2) together imply that the matrices R t (J * , C * ) cannot much outperform P t for any J * , C * in the comparison class. Combined with (3), this implies that we can't have Surprisingly, the bottleneck in the quantitative analysis is actually in step (2); 5 we take a small learning rate to control the differences P t+1 ab − P t ab . This is not just a technical requirement. Because the central planner's updates are both optimal and small, we can infer that there are no big adjustments to be made. This property is what lets us ensure that the central planner is making adjustments often enough to "exhaust" all of the good ones.

Protocol for ex ante symmetric interactions
Recall the ex ante symmetry condition: where K <t is a transcript of all of the events prior to round t. In this section we describe a protocol which achieves low regret under this condition.
Our approach is to assign each user a level of wealth w(x) > 0. A high value of w(x) indicates a debt owed to a user by the rest of the community, while a low value indicates a debt owed by the user. Whenever p t 0 = p t 1 , we adjust w x t 0 and w x t 1 so that the "effective payoffs" of the two users are equal and the total wealth w x t 0 + w x t 1 is conserved. Because the effective payoffs are symmetric, we can apply the central planner's algorithm to guarantee that the total effective payoff is large. Over the long-run the budget constraints w (x) > 0 imply that the actual payoffs can't be too different from the effective payoffs.
We first considered various straightforward approaches in which payoffs were directly translated into changes in wealth, i.e. which equalized the effective payoffs The difficulty with these proposals was maintaining the invariant w(x) > 0. In order to prevent a violation, we need to prevent interactions with users who have low w(x). But this means that if insufficient liquidity is available, interactions between honest users will stop. This issue made it very difficult to analyze protocols of this type, and in most cases were able to find concrete situations in which these protocols performed poorly, 6 even in the simple favor setting described in Section 1.1.
Instead we define the effective payoff as the actual payoff plus the change in log wealth, and equalize this quantity: This automatically leads our learning protocol to place less weight on the payoffs of users who run up substantial deficits, preventing them from causing too much damage. At the same time, we never have to block an interaction between honest users due to insufficient funds; as w(x) → 0 the system places a higher and higher value on changes in w(x), which prevent it from ever setting w(x) ≤ 0. The resulting protocol seems to be self-correcting and highly robust to liquidity shortages or imbalances of payments.

Related work
In this section we discuss a number of related threads in the literature. Our novel contribution is a performance guarantee in the face of general attacks and in a general environment, rather than considering narrower threat models or making restrictive assumptions about the domain.
Collaborative filtering: There is a large literature on collaborative filtering spanning a wide range of techniques; see [19] for an overview.
Technically the most closely related results are matrix prediction algorithms that achieve low regret compared to the comparison class of matrices with small trace norm, and in particular the recent results for online matrix prediction due to Hazan, Kale, and Shalev-Shwartz [9] and the similar work by the author [4]. However, filtering systems based directly on these algorithms would be vulnerable to manipulation.
Another line of related work investigates the recovery of preference functions; for example see [1,2,7]. Some of this work uses assumptions similar to our implicit assumptions, for example the existence of large groups with concordant preferences. This line of work differs in that it aims to reconstruct the entire preference table rather than simply filtering proposed interactions. This stronger goal is unattainable in our noisy and adversarial setting.
Competitive collaborative learning: From a modeling perspective, our work is most similar to, and inspired by, the competitive collaborative learning framework of Awerbuch and Kleinberg [3].
In this setting each user must choose a resource in a series of rounds, and the aim is to ensure that the honest players perform as well as if they had all chosen the single best fixed resource in every round. Like us, they rely on machinery from online learning and convert online learning guarantees into regret bounds for the honest users.
However, this work focuses on identifying an optimal resource to use in every round, rather than considering binary decisions across varying conditions. As a result, we use quite different technical tools and are applicable in very different settings.
Transitive trust: Another literature explicitly examines chains of trust relationships, by which one user can indirectly trust another; for example see [10,15]. The techniques in this literature tend to focus on a binary notion of links as being either honest or dishonest. This assumption is appropriate in some settings (for example with respect to cryptographic credentials) but not in our target applications.
Manipulation-resistance: Another literature addresses the question of modifying recommendation systems to limit the influence of sybils, fake identities controlled by an attacker. For example, see [22,14]. The robustness guarantees achieved in this literature are similar to our own, but the results are restricted to the setting where a decision-maker can get useful feedback from the same source across many different decisions. In our setting only a handful of users have information about each decision, and so a decision-maker can only rarely get direct advice from the same source more than once. In exchange, we achieve weaker bounds on the damage done per sybil.
Economic systems for P2P networks: Many decentralized economic protocols have been proposed to reduce the scope for free-riding and enforce reciprocity, especially in the context of Peer-to-Peer (P2P) networks; for some representative examples see [5,13,20,8,17,16].
Driven by our desire to obtain end-to-end performance guarantees, we focus on robustly addressing liquidity constraints and possible payment imbalances, issues which have received little theoretical attention. These issues are particularly important because we assume that users only sometimes have the opportunity to provide valuable services, rather than assuming that such opportunities are always readily available.
Conversely, we do not confront any of the practical issues involved in tracking payments. Our protocol would need to be implemented on top of another system for managing digital payments. We also rely on our symmetric reputation system to provide appropriate incentives for honest reporting, sidestepping another prominent issue in the existing literature.
Other reputation systems: Reputation systems have been the focus of substantial research across a wide range of contexts, for example see [11,12,21]. P2P networks and online marketplaces have enjoyed the most attention.
To make a decision in these systems, a user consults feedback from peers who have made similar decisions, and trusts each source of feedback according to their past reliability. This is conceptually similar to our framework, although we use different technical tools and the resulting protocol is much more resistant to manipulation.
It may be possible to bridge the gap between our proposal and more practical reputation systems. For example, EigenTrust [12] is a reputation system which uses random walks to compute the maximum eigenvector of an interaction graph. Although it is vulnerable to manipulation, the protocol is much more efficient than ours. By changing the online learning algorithm used by the central planner in our protocol, it might be possible to replace our use of semidefinite programming by a distributed algorithm based on random walks, achieving the best of both approaches.
For us, the important properties of OLL ε are given by the following results: [4] For any sequence E t and any X 0 with entries in [0, 1], we have The algorithm in [4] maximized under some additional equality constraints, e.g. i X (a,i)(a,i) = 1. For our purposes it doesn't matter whether we include these or not, and for ease of exposition we omit them. It is easy to verify that this leaves the results of [4] unchanged; using these extra inequalities would also leave our results unchanged.
where E t 1 is the sum of the absolute values of the entries of E t . Lemma 7. [4] For any E <t and any E t we have Our statement of Theorem 9 and Lemma 7 are slightly different from the statements in [4], so we present proofs in Section 10.
We can now define the central planner's algorithm PLAN ε . This algorithm is parametrized by a learning rate ε < 1 16 ; in order to achieve the unparametrized version we decrease ε over time. Let be the sparse matrix with Z t Given Z t t<T , the following algorithm gives the central planner's recommendations in round T : • For t = 0, 1, . . . , T − 1: -Define E t to be the sparse matrix with the following non-zero entries: -Let X t+1 = OLL ε/ρ E ≤t . -Define

Analysis
For convenience, we will write p t (P ) for the payoff the planner would obtain by using the matrix P in round t, namely p t (P ) = p t P x t We write U P t , X for the matrix that would be obtained by updating P t with the matrix X t+1 = X, i.e. defined by the equations where P t are the matrices computed by PLAN ε .
Proof. We have p t P t = p t U P t−1 , X t . Moreover, where J and C are defined from X in the same way that J t and C t are defined from X t , and doesn't depend on X. We constructed the matrix E t precisely so that it would satisfy this identity.
Because X t = OLL ε/ρ E <t , by Theorem 9 we have where the last equality holds because E t 1 = 3 p t . Lemma 2. For any a, b, we have where P t are the matrices computed by PLAN ε .
Proof. Consider the "steady state" value of P given J and C, defined as This is the value to which P would converge if J and C were left unchanged for many iterations. We will show that Y t does not change very quickly, and that P t is "following" Y t and hence does not change very quickly either.
Note that each entry of J t and C t is defined to be a constant multiple of an entry of OLL ε/ρ E <t , and that the entry-wise ℓ 1 norm of E t is O p t . So by Lemma 7, we know that J t+1 ab − J t ab ≤ ε ρ p t , and similarly C t+1 ab − C t ab ≤ ε ρ p t . By definition we have C t ab ≥ 0 and J t ab ≥ ε 1/2 . Together these facts imply that By the definition of P t+1 , we have By the definition of J and C, we have J t ab + C t ab ≤ 1 4 + 1 4 + 1 4 + ε 1/2 ≤ 1. Thus P t+1 is a convex combination of P t ab and Y t ab . In particular, Intuitively this suggests that P t+1 ab − P t ab ≤ Y t+1 ab − Y t ab , from which the desired result would follow.
To see this formally, consider the total length of the path P 0 ab , P 1 ab , . . . , P t ab , Y t ab , i.e. the sum of the absolute values of the differences between consecutive points. If we change this path by adding a new point: P 0 ab , P 1 ab , . . . , P t ab , P t+1 ab , Y t ab we don't change the total length, because P t+1 is in between P t and Y t . If we then change this path by changing the last point: P 0 ab , P 1 ab , . . . , P t ab , P t+1 ab , Y t+1 ab we increase the total length by at most Y t+1 ab − Y t ab .
By induction, the total length of the path is thus Y t+1 ab − Y t ab + O (1), and this total length upper bounds P t+1 ab − P t ab .
The next step is to prove that if the honest players are not collectively performing well, then there is some recommendation the central planner could have made which would generate a substantial improvement.
The reason for the ε 1/2 loss in this theorem is our restriction that J t ≥ ε 1/2 , which lower bounds the central planner's ability to stop honest and dishonest users from interacting and was needed to prevent rapid changes in P t .

Lemma 3. For any set
where P t are the matrices produced by PLAN ε .
Proof. Observe that PLAN ε is perfectly symmetrical under an exchange of x t 0 and x t 1 : the only difference is that the matrices P t are transposed, and the indices of X (a,i)(b,j) are modified by exchanging +1 and −1. So it suffices to prove the theorem for i = 0.
Define the vector v H via v (a,0) = 1 for a ∈ H, v (a,1) = 1 for a ∈ H, and v (a,i) = 0 otherwise. Define . This matrix is clearly PSD, and has entries in [0, 1].
So for a, b ∈ H, we have For a ∈ H, b ∈ H, we have We compute: t≤T : Rearranging, and using the fact that U P t , X H ab = P t ab for a ∈ H: as desired.
We are now ready to prove the main result of this section: Theorem 2. Suppose that p t s t ∈ [−ρ, ρ] and E p t ∈ [−ρ, ρ] conditioned on the preceding rounds. Then Proof. By Lemma 3, there exists an X H 0 with 0 ≤ X H (a,i)(b,j) ≤ 1 such that in expectation, where the second equality holds because E p t ≤ ρ. So it suffices to bound Note that PLAN ε always satisfies s t = P t We have where the third line uses the definition of p t and Theorem 1, the fourth line uses the definition of U (·, ·) and the upper bound p t ≤ ρε −1/2 , the fifth line uses the bound E p t ≤ ρ conditioned on previous rounds (and in particular conditioned on P t − P t−1 ∞ , which can be computed before round t) the sixth line uses Theorem 2, and the seventh line uses the bound E p t ≤ ρ. By setting ε = N 2/3 T 2/3 and using a standard doubling trick, we obtain a more convenient form: Theorem 3. Under the same conditions as Theorem 2, there is an algorithm PLAN for the central planner which achieves an expected payoff of Proof. Every time T = 2 k , we start a new copy of PLAN ε with ε = ε k = N 2/3 T −2/3 .
By Theorem 2, we have Summing from k = 0 to k = log (T ) , we obtain the desired bound.
7 Appendix: Algorithms for symmetric payoffs, collaborative filtering, and transfers

Symmetric payoffs
We say that a game has symmetric payoffs if, in each interaction between honest users, p t 0 = p t 1 .
The algorithm SYM followed by an honest user is: • Initialize a copy of PLAN.
• For t = 0, 1, . . .: -If you are interacting: * Consult PLAN x t 0 , x t 1 to find the probability s t with which you should interact. * Using the random beacon decide whether you should interact, and broadcast the result. If you and your partner disagree about whether you should interact, don't interact. * If you decide to interact, observe your payoff and broadcast it. Otherwise broadcast a payoff of 0.
-Report a payoff of −ρ to your instance of PLAN if anything goes wrong: 8 if the interacting parties broadcast different payoffs, if either party makes multiple broadcasts, if either party broadcasts a payoff outside of [−ρ, ρ], or if you disagree about whether an interaction should have occurred (based on your independent use of the random beacon).
-Otherwise, report a payoff of p t = p t 0 /s t = p t 1 /s t to your instance of PLAN.
We can now apply Theorem 3 Theorem 4. If p t 0 = p t 1 in any interaction between honest users, then the algorithm SYM achieves a payoff Proof. It is easy to verify by induction that all of the honest users' instances of PLAN will be perfectly synchronized, and consequently that nothing will ever go wrong in an interaction between honest users. This also allows us to talk unambiguously about "the" instance of PLAN.
Let p t be the payoff reported to the central planner in round t. Either p t = 0, p t = −ρ, or p t = p t 0 /s t and p t 0 ∈ [−ρ, ρ]. Thus p t s t ∈ [−ρ, ρ]; because p t = p t 0 /s t with probability at most s t , and otherwise p t ∈ [−ρ, ρ], we have E p t ∈ [−2ρ, 2ρ]. Thus we can apply Theorem 3 to the payoffs p t (the difference between ρ and 2ρ makes no difference in the asymptotics).
In any interaction between honest users, we have E p t = p t 0 = p t 1 . Moreover, in any interaction involving an honest user, either their expected payoff is equal to s t E p t , or else they agreed to interact and p t = −ρ. In either case, their expected payoff is at least s t E p t .
Thus we can apply Theorem 3 twice and conclude in expectation.

Collaborative filtering
Our algorithm FILTER for collaborative filtering is a nearly direct application of PLAN. Formally, it works as follows.
• Initialize a copy of PLAN.
• For t = 0, 1, . . .: -If you are x t 1 , output s t 1 = 1. -Otherwise, report a payoff of p t = p t 0 /s t to your instance of PLAN.
Theorem 5. If p t 1 = 0 in any interaction between honest users, then the algorithm FILTER achieves a payoff Proof. It is easy to check that the honest user's instantiations of PLAN remain synchronized, that In an interaction where x t 0 , x t 1 are both honest, then s t 1 = 1 and we have E p t = p t 0 .
So we have in expectation as desired.

Transfers
If the payoffs aren't symmetric, but users are allowed to make transfers, then we can reduce to the symmetric case. That is, given an instance I transfers of the general problem with transfers, with payoffs p t i , we will produce a new instance I symmetric of the symmetric problem, with payoffs q t i . We will guarantee that if the uses perform well on this synthetic instance I symmetric , then they also performed well on I transfers . Since we know that SYM performs well on I symmetric , this will yield the desired result.
Whenever an honest user x t i has to make a decision in I transfers they ask the user x t i to make the same decision in I symmetric . Whenever an honest user is given a payoff p t i in I transfers , they perform the following process in order to generate the payoff q t i in I symmetric : • Send the message p t i to x t 1−i , and receive the message p t 1−i .
• If no message is received, or multiple messages are received, or the message contains a payoff p t 1−i ∈ [−ρ, ρ], then set τ t i = 0.
• Otherwise set τ i = max It is easy to verify that in any interaction between honest users we have This allows us to apply the algorithm SYM to the instance I symmetric .
Theorem 6. There is an algorithm attaining the payoff in general if transfers are available.
Proof. We apply the reduction described in this section. In any interaction between honest users we have and in any interaction we have q t i ∈ [−ρ, ρ]. So we can apply SYM to the resulting payoffs, and we have in expectation as desired.

Appendix: Ex ante symmetry
As in Section 7.3 we reduce an instance I ex ante with ex ante symmetric payoffs to an instance I symmetric with symmetric payoffs. At the beginning of the protocol each user initializes a balance w 0 (x) = 1 for every user x. When x t i receives the payoff p t i in I ex ante they do the following to generate the payoff q t i in I symmetric : • Communicate the payoff p t i to x t 1−i , and hear the payoff p t 1−i .
• If no message is heard, or multiple messages are heard, or the message contains a payoff , where w t i = w t x t i : Here δ < 1 2 is a parameter of the reduction.
It is easy to verify that in any interaction between honest users, both users will report a payoff of This is very similar to the protocol with transfers, except that the payoff of an interaction is now a weighted average of the individual payoffs. Once again, we can apply the algorithm SYM to I symmetric . The aim the analysis will be to show that if the payoff in I symmetric is good, then so is the payoff in I ex ante , which is less straightforward than in the case with transfers.
It is easy to verify that τ t i ≤ δw t i , so that each w t (x) changes by at most a factor of (1 ± δ) in any round. Since δ < 1 2 , this guarantees that w t (x) > 0.
The mechanism used to track the quantities w t (x) is not particularly important; for simplicity, and because our algorithm is already hopelessly undistributed, we assumed that every user independently tracks the quantities w t (x) for every other user. It would be straightforward, however, to use a more efficient implementation of digital cash such as [6]. 9 In this case a dishonest player might decline to make an appropriate transfer, but this can be handled in the same way as in Section 7.3.
To analyze this protocol we rely on the potential functions We use three lemmas to relate the reported payoffs q t i to the actual payoffs p t i .
Our first lemma relates the reported payoffs q t i to the underlying payoffs p t i : Lemma 4. Under the ex ante symmetry condition, in any interaction between honest users we have Proof. Under the ex ante symmetry condition, conditioned on the values of w t 0 and w t 1 , and on the users' decision to interact, we have Then we have as desired.
Our second lemma relates the reported payoffs q t i to the change in U t (x): Proof. We have where we have used the bound Our third lemma relates the quantities U T (x) to the payoffs p ≤T (x): Proof.
x w t (x) is conserved by the algorithm, and w t (x) ≥ 0, so By Jensen's inequality, x log w T (x) ≤ |H| log N |H| . We have as desired.
Combining these three lemmas yields our desired result: There is an algorithm that obtains regret assuming that the payoffs between honest users satisfy ex ante symmetry.
Proof. We will assume that T is known in advance, and choose δ = √ N T ; this assumption can then be removed by a standard doubling trick exactly as in Theorem 3.
In any interaction between honest users we have q t 0 = q t 1 . Moreover, q t i ∈ [−ρ, ρ]. Thus we can apply SYM and Lemma 4 and obtain in expectation Then we can apply Lemma 5 and Lemma 6 and obtain in expectation where the last inequality assumes T > N . If T ≤ N the result is trivial, since in this case the maximum possible difference between p ≤T (H) and

Appendix: Lower bounds
In this section we consider the game described in Section 6. We show that for any T , there is a set H and a strategy for nature such that the planner's payoff is These results extend immediately to all of our other settings, because an algorithm for any of these settings could be trivially used by the central planner (who could simply simulate the interactions of the users and recommend that two users interact with whatever probability they interacted in the simulation).
To prove this result we consider a randomized strategy for nature such that the expected payoff of every user is 0. We then consider the best possible partition of the users into two sets Proof. Consider a strategy for nature in which each x t 0 and x t 1 is uniformly random, and each p t is a uniform ±1 random variable. It is easy to see that no matter how the central planner plays in this game, the expectation of p ≤T (H) = 0.
Given some enumeration of the users 0, 1, . . . , N − 1, we define the set H 1 as follows. We include all of the users 0, 1, . . . , N/2 in H 1 . We then inductively decide whether to include i > N/2 in H 1 by evaluating the sum We include x in H 1 if and only if P x > 0.
The sum defining each P x has in expectation at least T /(2N ) terms, because 1/N of all interactions involve user x and at least half of these interactions are with a user in |H 1 |. Each of these terms is a uniform ±1 random variable. So the probability that P x > 0 is 1 2 and the expectation of P x , given that P x > 0, is at least T /N .
It is easy to see that OPT ≤T (H 1 ) = x∈H 1 P x . Each term P x for x ≤ N/2 has expectation 0. In expectation there are Ω (N ) terms with x > N/2. Each of these terms is Ω T /N in expectation.
We define H 2 = [N ]\H 1 . We have OPT ≤T (H 2 ) = 0: for each pair x < y with x, y ∈ H 2 , the event y ∈ H 2 depends only on the sum P y , which is a sum of terms independent of any interactions occurring between x and y. Thus if there is an interaction between x and y, its expected payoff is 0. Summing over pairs of users in H 2 , we obtain E OPT (H 2 ) = 0. 10 Appendix: Strengthened analysis of online local learning Lemma 7. [4] For any E <t and any E t we have which gives the desired result.

Appendix: Open questions
We have presented a protocol for managing trust which achieves a qualitatively new-and surprisingly strong-formal guarantee. But the theoretical picture is far from complete, and the proposed protocol is far from practical. We hope that our model and algorithmic approach will inspire further work in both of these directions, and in this section we highlight some areas for improvement and elaboration.
Tighter regret bounds: Our regret bound of O ρ 3 √ T 2 N can probably be improved to O ρ √ T N , which translates into a significant performance improvement.
Perhaps more importantly, our regret bound depends on the total number of interactions. This might be improved to depend only on the number of interactions involving an honest user. The distinction is particularly important in settings where dishonest users can fabricate large numbers of interactions amongst themselves.
With plausible parameters and performance goals in the favor setting, these improvements could reduce the number of required interactions per user from tens of thousands to hundreds 10 although the practical performance of the protocol might be better than the theoretical worst case, as often happens Other performance improvements, such as distinguishing between the average and maximal payoffs or improving the hidden constant factors, would also help achieve a practical guarantee.
Distributed implementation: Although our protocol is is tractable in the sense of polynomialtime, it is not distributed. Ideally each user's computation and communication would be polylogarithmic in the size of the community.
The main challenge is distributing the computation of the central planner, and particularly the online learning algorithm at the core of our protocol. The current algorithm requires semidefinite programming, which must be replaced by fast distributed computation, such as random walks or sparse linear algebra. In addition to the algorithmic difficulties, the computation must be robust to manipulation by adversarial users; this might be achieved either by finding a computation which is inherently robust or by using cryptographic tools to ensure accurate computation.
Simultaneous interactions: Our protocol assumes that interactions occur one at a time: after one pair of users interacts, their reports immediately become available to the next pair of users. In most contexts this is not a realistic assumption.
When applied to a setting with k simultaneous interactions, our protocol achieves regret Ω (k). It is not hard to construct examples where the regret must necessarily be Ω (log k). We suspect that this lower bound is tight, and that some protocol achieves regret O ρ log k √ T N . Under realistic assumptions, it may be possible to eliminate the dependence on k altogether.
Recommending vs. filtering: Our protocol answers questions of the form "should I interact with this merchant?" rather than questions of the form "which merchant should I interact with?" In many contexts the latter question is more useful-though deciding which users' input to trust is a key difficulty for both problems. [3] provides a similar algorithm that answers "which merchant should I interact with?" but exploits the simplifying assumption that there is a single best merchant for all transactions. It is natural to try to combine these two assumptions, and to design a protocol which recommends one resource from amongst k options.
Strong signals: In our setting, most interactions provide only weak evidence about which users are honest. We might expect to be able to obtain tighter bounds when very strong signals are available. For example, a dishonest user might physically assault or threaten an honest user, resulting in a payoff of −ρ * which could never occur in an interaction between honest users. In this case, we would like to obtain a regret bound whose dependence on ρ * was O (ρ * N ), independent of T .
Incentive compatibility: Our protocol has a robust theoretical guarantee, but only assuming that there are some honest users who reliably follow the protocol. It would be better if honesty were incentivized rather than assumed.
The honest players in our protocols report their payoff after each interaction, and pay a cost which depends on their reported payoff. So an honest player could always benefit by stating a lower payoff, and has no short-term incentive to play by the rules.
It is worth noting, however, that a player who follows this selfish approach will quickly find that no one wants to interact with them. Though the optimal behavior involves lying, it involves lying just enough that other users still benefit from interacting with me. In fact, a community of users lying optimally can still lead to socially optimal outcomes.
Unfortunately, in an attempt to lie optimally an honest user may inadvertently destroy value.
In fact the Myerson-Satterthwaite theorem applies to our setting, even when there are just two users, 11 to show that this is necessarily the case: in general it is impossible to achieve our desired guarantees at a Bayesian Nash equilibrium. We feel that our result is an attractive compromise given this impossibility result.
We could still achieve actual incentive compatibility or approximate incentive compatibility in many interesting cases where fundamental obstructions don't arise; in general, we might hope to translate positive results from the two-player iterated setting to our distributed setting.
Asymmetric interactions: Our protocols all require that interactions be symmetric on average, or else make use of transfers to symmetrize them. This is a very strong condition that would be nice to weaken.
One generalization is to consider sets of interactions that are balanced, so that each user has as many opportunities to give as to receive overall, even though the pairwise interactions are asymmetrical.
A more difficult generalization is to consider interactions that are inherently imbalanced, in the sense that some users systematically have more opportunities to give than to receive. In this case it is no longer possible to simultaneously maximize collective welfare for every subgroup H. We could instead try to achieve Pareto efficiency, which is a weaker condition but still meaningful if it holds for every set H simultaneously. For example, we might try to ensure that no group H can benefit all of its members by adopting a different internal policy and/or isolating itself from the users outside of H.
Honest supermajorities: Our guarantees are non-trivial even when the set H is a very large fraction of [N ]. But in this case it may be able to obtain regret bounds that depend on N − |H| rather than on N . In cases where 90% or 99% of users are honest, this could amount to a large difference in performance.

Sybilproofness:
Our system bounds the damage done by the introduction of any dishonest user. In some settings it is easy for an attacker to create large numbers of dishonest users or sybils. Our bounds are not tight enough to discourage such an attack.
It might be possible to ensure that the introduction of a dishonest user does no damage to the honest users, or that the maximum possible damage done by dishonest users is bounded. For example, if transfers are available, each user could pay an upfront deposit to cover any possible damage they might inflict (in particular, a new user would need to pay a cost of at least ρ before every interaction with an established user, which would potentially be refunded if the interaction went well). Each honest user would need to pay a manageable cost to join the system, but the cost would be large enough that attackers can only recoup it by becoming productive members of the community. 12 11 Here is a very rough sketch of the argument. Consider our setting with transfers, where −p t 0 , p t 1 are independently distributed in [0, 1] and are the same in every round. Because H might contain only one user or might contain both, a protocol that satisfies our guarantee must be incentive compatible and must maximize collective welfare (i.e. be ex post efficient). We can use the average size of the transfer to sell an item valued at p t 0 by the seller and p t 1 by the buyer, in a way that is incentive compatible and ex post efficient. By Myerson-Satterthwaite, we can conclude that any protocol satisfying our guarantees is not a Bayesian Nash equilibrium.
In the setting of bilateral exchange, our protocol recommends that the honest users honestly state their willingness to pay for the item, allocate it optimally, and then divide the surplus evenly. Evidently this is not a Nash equilibrium, since a player can benefit by understating their surplus. This case captures the essential and unavoidable reason that our protocol is not incentive-compatible. 12 Impossibility results such as [16] do apply to this problem, but we are not aware of any that apply to our approach.
Composition and complex protocols: Worst-case performance guarantees allow our protocol to be used as a subroutine without compromising its correctness. Together with other building blocks, our result might be used to design more complex protocols in the same way that simple cryptographic primitives are used to build more complex cryptographic systems.


s2fieldsofstudy:
Computer Science
Physics

text:
Safeguarding Quantum Key Distribution through Detection Randomization

We propose and experimentally demonstrate a scheme to render the detection apparatus of a Quantum Key Distribution system immune to the main classes of hacking attacks in which the eavesdropper explores the back-door opened by the single-photon detectors. The countermeasure is based on the creation of modes that are not deterministically accessible to the eavesdropper. We experimentally show that the use of beamsplitters and extra single-photon detectors at the receiver station passively creates randomized spatial modes that erase any knowledge the eavesdropper might have gained when using bright-light faked states. Additionally, we experimentally show a detector-scrambling approach where the random selection of the detector used for each measurement - equivalent to an active spatial mode randomization - hashes out the side-channel open by the detection efficiency mismatch-based attacks. The proposed combined countermeasure represents a practical and readily implementable solution against the main classes of quantum hacking attacks aimed on the single-photon detector so far, without intervening on the inner working of the devices.

more specifically weak coherent states with moderate multiphoton probability -for QKD.
Recently a critical point was recognized: back-doors may be open in some physical devices comprising the QKD system, specially the single-photon detector (SPD). The flaws may be explored by an eavesdropper (Eve) for side-channel attacks [10][11][12][13][14][15][16][17][18][19][20][21][22][23], which can jeopardize the security of the protocol. These quantum hacking attacks are interventions caused by Eve from the outside of Bob's station by high-jacking the detection apparatus -whose response can be predicted in some degree or even manipulated. In all cases, the attacks make it possible for an eavesdropper to gain information without being noticed, i.e., achieving a critically high mutual information with Alice and Bob without exceeding the upper threshold of the quantum bit error rate (QBER).
Measurement-device-independent QKD has been recently proposed to eliminate detection [29] and/or state preparation [30] loopholes. Although making use of sophisticated schemes based on long-distance interference at a third remote station [31] and (reversely or not) entangled systems, practical implementations of the schemes have been reported [32][33][34][35]. Nevertheless, the well-established traditional BB84-like QKD systems still lack a definitive solution against quantum hacking.
We propose a practical solution that extends over a broad range of known classes of quantum hacking attacks aimed at the detection equipment. The scheme is based on fundamental randomization of input modes to the detection apparatus inside Bob's station, thus not deterministically accessible to the eavesdropper. Here we show that the use of beamsplitters and extra detectors at Bob's station renders its apparatus immune to bright-light based attacks, as the blinding-and faked-states attacks [20,21]. The eavesdropper can no longer manipulate Safeguarding Quantum Key Distribution through Detection Randomization Thiago Ferreira da Silva, Gustavo C. do Amaral, Guilherme B. Xavier, Guilherme P. Temporão, and Jean Pierre von der Weid Q the detectors without leaving a strong signature which is monitored by the counting statistics of the detectors. Correlation between detectors in equivalent spatial modes reveals the attack, without intervening on the inner workings of the devices. Additionally, we experimentally show that, as suggested in [12], a detector-scrambling strategy employed by Bob dynamically alters the detector used for measurement under the chosen basis, counteracting the attacks based on the detection efficiency mismatching, like the time-shift attack [12][13]. This proposal is readily implementable through the random application of a random rotation to invert the set of mutually unbiased detection bases. This is equivalent to an active spatial mode randomization since, after the basis choice, a random SPD will effectively be used for the detection of a particular state.
The assumptions for the proposed counter-measure are that the eavesdropper has no access on the inner working of the devices and cannot deterministically manipulate the splitting ratio of the BS. The main drawbacks of our proposed scheme against quantum hacking are the increase in the number of detectors when compared to the traditional setup for the BB84 protocol and an increase in the dark count rate. Nevertheless, the scheme provides a practical readily available real-world solution against, at least, those known classes of quantum hacking attacks.

A. The BB84 Context
In the BB84 protocol [1], Alice prepares each qubit in a single-photon state, according to a random choice between four states that form two pairs of orthogonal states in canonically conjugated bases in a bi-dimensional Hilbert space. Considering polarization states encoding, the bases may be sorted from rectilinear (⊕), composed by horizontal and vertical states of polarization (SOPs); or diagonal (⊗), composed by diagonal (+45°) and anti-diagonal (-45°) statesof-polarization (SOPs).
Bob randomly chooses the measurement basis for each incoming qubit and has a deterministic or probabilistic result according to the overlap between his own and Alice's chosen bases. Bob can choose to measure on ⊕ or ⊗ bases by turning the half-wave plate (HWP) to 0 or 22.5°, respectively.
Bob's typical detection apparatus for polarization qubits includes a HWP to change the measurement basis, a polarizing beamsplitter (PBS) and two SPDs, as seen in Fig. 1a. If Alice's and Bob's bases match, the photon is routed to a deterministic spatial mode and is delivered to the SPD corresponding to the transmitted qubit. Otherwise, it becomes a superposition of the PBSs eigenstates and the photon randomly emerges at one output spatial mode, which can then be detected with an SPD. During the basis reconciliation in the post-processing round, Alice and Bob communicate though an authenticated channel and select only the time-slots when their bases have agreed. It is worth noting that only the time slots corresponding to a measurement result are considered, as in practice neither all pulses sent by Alice contain photons -due to imperfect photon sources -nor all received pulses can be detected by Bob -due to imperfect detectors and channel and component loss.

B. The Avalanche Photodiode
The traditional single-photon detector used in QKD systems is composed of a cooled InGaAs avalanche photodiode (APD) operated in gated Geiger mode and an avalanche quenching circuit [1,[36][37][38]. When reversely polarized above the breakdown threshold -during short time windows -the device becomes single-photon sensitive, so impinging weak light may trigger a self-sustained avalanche. With the end of the gate, the overvoltage bias is reduced and the macroscopic burst current is quenched to reset the single-photon sensitivity. A discriminator circuit creates a formatted voltage pulse that indicates the occurrence of a photon count. APD-based singlephoton detectors are usually not photon number resolving, i.e., they cannot discriminate between a single-photon or multiphoton optical pulse and emit an identical formatted voltage pulse in both cases. Apart the traditional commercial devices, different gating and quenching schemes can also be used with APDs to construct enhanced devices [39,40] and even photonnumber resolution capable detectors [41].

C. Bright light-based attacks: blinding plus faked states
The Geiger mode makes the SPD sensitive to a single photon during the gate time due to the high electronic gain provided by the operational point above the breakdown voltage. However, when biased with lower voltage, the APD works in linear mode, as is usual in telecom applications. In this case, the photocurrent generated in response to optical power is approximately linear. Therefore, if the bias voltage is brought below the breakdown, the device no longer detects single-photons. This behavior can be explored by Eve to disable Bob's detectors. Of course, this strategy alone gives no information to Eve, but can be combined with other ruses, as discussed ahead.
During this blinding attack, the eavesdropper sends strong light to enforce a current flow, which can alter the threshold breakdown value [15,[24][25][26][27]. The excess voltage applied to the APD to enable Geiger mode is no longer sufficient and the detector becomes blind to single-photon detection.
Even when operating with low bias voltage (in the case of free-running operation or outside a detection window in gated mode), the SPD may trigger an avalanche if a sufficiently strong pulse is received [20][21]. Assuming an interceptionresend strategy, Eve measures each qubit sent by Alice in a random basis and prepares a faked state to send to Bob according to the result obtained. If Bob's basis choice matches Eve's, the strong pulse is routed to the corresponding detector, forcing an avalanche with unity probability, and Eve knows that their results are correlated. However, if their bases disagree, the pulse is split and half the power is delivered to each of Bob's detectors. As this half-power pulse is not sufficient to trigger an avalanche, no detection event takes place. The ruse renders all valid results obtained by Bob correlated to Eve's, who then acquires high knowledge of the key. This strategy may be used standalone (e.g. aftergate attack [17]) or combined to the blinding scheme, causing no critical quantum bit error rate (QBER) increase [20][21], as Bob's SPDs never click in the absence of a faked state. Not so-bright light-based attacks have also been reported, exploring the higher probability of a multi-photon pulse to cause an avalanche [18] or by selectively causing a deadtime on a detector [19].

D. Detection Efficiency Mismatch
Each SPD operating in gated mode has its own time-(or wavelength-) dependent efficiency curve. This means that the device is usually more efficient in one temporal position (wavelength) relative to the other in a system, due to asymmetries or to temporal mismatch (different responsivity). Eve can explore a mismatch between the two efficiency curves to launch an attack by manipulating, for example, the time of arrival of the qubits relative to the gate windows. A faked states strategy may be employed [10,17,18,20,21], which makes the detection events of Bob more probable to occur at a certain detector according to the delay imposed by Eve. Another example is the time-shift attack [12,13], in which there is no interception at all by Eve, but only a bi-stable random (but known by Eve) delay change in the qubit time-offlight. By manipulating the optical path, Eve can position the optical pulse in a region of the gate window that increases the probability of a detection occurring in one or other SPD, allowing the eavesdropper to infer (part of) the key without even increasing the QBER. The drawback of this strategy is the reduction of the net detection efficiency of Bob's apparatus that must be compensated by Eve. It is assumed, however, that Eve can replace the link by a more transparent one, or can teleport the states from Alice's output to Bob's entrance.

III. PROPOSED SCHEME
Here we propose a countermeasure scheme aiming on closing the back-door opened by the SPD regarding its susceptibility to external manipulation by bright light. The spatial modes randomization is presented below. We also report on the experimental implementation of the detectorscrambling strategy, previously suggested in [12], showing that the information of Eve can be hashed out toward zero when random rotation is applied to Bob's detection bases, avoiding the efficiency mismatch-based attacks.

A. Spatial Modes Randomization
A practical scheme using beamsplitters and additional single-photon detectors is proposed to avoid the direct control of the detectors by the eavesdropper. Figure 1b shows a sketch of Bob's apparatus employed in a BB84-based QKD system with the countermeasure implemented (in contrast, Fig. 1a depicts the traditional BB84 setup). For each received qubit, Bob chooses the measurement basis at his HWP and sends it to a PBS. Each output spatial mode of the PBS is randomly divided in two modes by each beamsplitter (BS) according to where the indices in and out represent the two input and two output modes of the BS. When the splitting ratio τ is 0.5, the photon has the same probability of emerging at one or other output mode. Each output spatial mode is delivered to a SPD. When under regular operation, whenever Bob's basis is correctly chosen, detector A or B may click for a certain state (say, horizontal SOP); or detector C or D may click if the corresponding orthogonal state is received (vertical SOP). Due to the low average number of photons per optical pulse sent by Alice (µ), and the channel attenuation, the probability of both A and B, or C and D, detectors clicking together (coincident counts) is low. This is given by Poisson distribution as (disregarding the attenuation of the transmission channel and the losses inside Bob's apparatus, for simplicity) ܲ ൌ ܲ ൌ ሾ1 െ ݁ݔሺെߤߟ߬ሻሿ ଶ , where η is the detection efficiency of the SPDs (assumed to be equal). If τ is 0.5, both detectors must exhibit similar photon counting statistics and low probability correlated events. When there is no basis agreement, however, any one of the four SPDs clicks at random, as shown in Table  1.
The proposed counter-measure aims on avoiding the control of the SPDs by the eavesdropper, what is accomplished through the randomization of the spatial modes by the two beamplitters. It is thus essential for the scheme to work that the splitting ratio of the BS cannot be manipulated by the eavesdropper. It is known, however, that the splitting ratio of these devices is intrinsically wavelength dependent [42], and also the isolator's insertion loss [43]. This means that a narrow filter must be inserted at Bob's input to protect the BSs, as a Bragg grating in reflective mode with a circulator, for example. The free spectral range of a Bragg grating is sufficiently long to provide protection over the main spectral range in which the InGaAs-based SPD has significant detection efficiency (the Bragg resonance at the doubled frequency lies in the 775 nm region, considering the operation around 1550 nm). Furthermore, narrow filtering is a key element for the case of coexistence between classical and quantum communication over the same optical fiber links [44].
Consider that Eve launches bright optical pulses (in the bright-light attack context) to deterministically enforce an avalanche on Bob's right detector(s) whenever their bases agree; or cause no avalanche if their bases are mismatched. This behavior is obtained due to power splitting at the PBS according to the SOP after basis choice, and a threshold power level can be defined related to this binary behavior. For simplicity (without lack of generality), suppose that Eve launches a H-polarized pulse with power P 0 . If Bob chooses rectilinear basis -which occurs with fifty-percent probability -full power emerges from the PBS to arm AB and the power splits to detectors A and B (see Fig. 1b) according to the BS split ratio as ܲ /ܲ ൌ ߬ and ܲ /ܲ ൌ 1 െ ߬.
If the bases mismatch, half the input power emerges from each output mode of the PBS and, after splitting on the BSs, reach each detector as ܲ /ܲ ൌ ܲ /ܲ ൌ ߬ and ܲ /ܲ ൌ ܲ /ܲ ൌ 1 െ ߬.
When under attack, neither the blinding mechanism nor the faked states can operate selectively. If τ=0.5, Eve can manage to set an attack point that is valid on both detectors, she is able to enforce coincident avalanches on both detector ever -this is the symmetric case. This is the best scene from Bob's point of view, as him can easily verify an abnormal amount of coincidences between A and B, or C and D, highly above the Poisson expectation value, what will smoke the eavesdropper out, indicating the presence of the strong pulse.
A more pessimistic case can be analyzed, when, in the matched bases case, Eve can enforce an avalanche on one detector (A) and none on the other on the same arm (B) -the asymmetric case. This can occur depending on the (fixed) asymmetry of the BSs (τ≠0.5). For example, Eve can send pulses capable of triggering an avalanche on detector A for sure and no avalanche at all on detector B; or can send a stronger pulse which fires both devices simultaneously (taking care not to exceed the threshold power when the bases disagree). Nevertheless, the counting distribution of detectors A and B on both symmetric and asymmetric cases diverges from the expectation of Bob and Eve's ruse still can be detected.
In this context, the use of four standard SPDs behind the two BSs passively creates random spatial modes that are not deterministically accessible to the eavesdropper. The blind strategy suffers from the same limitations, i.e. the blinded detector will always be the same, or both detectors will be always blinded, when the attack is performed. This works as a watchdog against the attacks and has advantages over a monitoring tap placed at the entrance of Bob's station working as an auxiliary watchdog, since it causes no reduction on the system efficiency -the tapped portion of light is not effective for QKD. Furthermore, as discussed in [15,20], there is no guarantee that a tap-based watch-dog with classical or quantum detector cannot be manipulated by Eve, or if there is clear set point to warn Bob about the hacking. The drawbacks of our countermeasure are the increase in the resources employed and a rise in the dark count rate by a factor of 2.
Asymmetry of the BS is not the critical point, but a possible asymmetry inversion caused by Eve, as discussed before. If Eve can deterministically manipulate the value of τ the security of the QKD section can be fully jeopardized. For example, suppose that Eve is able to set τ(λ 1 )=0.7 and τ(λ 2 )=0.3 and that the threshold power level is equivalent to a power loss of 0.5 relative to Bob's input. So Eve can mimics the equiprobable occurrence of events at detectors A and B by sending pulses at λ 1 (unitary probability for click at SPD A ) or at λ 2 (unitary probability for click at SPD B ) by the same amount.
Provided Eve cannot manipulate the splitting ratio of the BSs, let us focus on the case of an asymmetric BS. How well could Eve mimic the expected count ratios between the detectors, or redefining the question, how well can Eve mask the lack of counts enforced on the SPD located at the less transmissive output port of the BS?
A first approximation considers that Eve intercepts Alice's pulses and attack Bob's detectors with bright light for a fraction γ of the pulses, while employs a "regular" interceptresend strategy for the remaining fraction 1-γ of the pulses. Consider that the bright-light attack causes a binary response of the detectors. Again we concentrate in the case when Alice sends H-polarized states. Mapping the probabilities in a causality tree, as in [42], we get the results for each possibility of the independent basis choice from Eve and Bob. For the sifted events -the selected cases when Alice's and Bob's bases agree -it is found that the bright-light attack causes no error, but introduces (full) asymmetry between detection on SPD A and SPD B ; while the intercept-resend attack introduces error (up to 25%), but causes no asymmetry between de count rates of that detectors. The bright-light attack also reduces the overall detection rate by a factor 2, due to the fact that if the bases of Eve and Bob disagree (half the cases), no event occurs. In this context, the sifting error introduced by Eve is given by ܧ ൌ 1/4ሺ1 െ ߛሻ/ሺ1 െ ߛ/2ሻ, which is lower bounded at zero, if only bright-light attack is performed (γ=1); and upper bounded at 0.25, if only intercept-resend attack is employed (γ=0).
The ratio between the detection rates at SPD A and SPD B is given by This means that full bright-light attack results in total assymetry between counts on both detectors, while full intercept-resend attack causes no assymetry at all.
A second approach considers that Eve intercepts Alice's pulses and attack Bob's detectors with bright light only for a fraction γ of the pulses, while the remaining fraction 1-γ is only bypassed to Bob. This strategy belongs to the most general class of attacks [45]. The main advantage of this strategy is that Eve causes no sifting error, independent of the value of γ. On the other hand, the ratio between the detection rates follows eq. (2), exactly as in the previous case, so the ruse is preferable by Eve's point of view.
Equation (2) gives the big picture for the degree of protection provided by our proposed counter-measured against bright-light-based attacks when fixed asymmetry of the BSs is considered. The fraction of events stolen by Eve is directly related to the asymmetry caused by the attack and the protection is directly given by the ability of Bob to check the asymmetry out. For example, if Bob is able to estimate the detection rate ratio with 1% of uncertainty, he can assume that Eve may have stolen 0.7% of information.

B. Detector Scrambling
The creation of the proposed random spatial modes does not directly avoid the detection-efficiency mismatch-based attacks (but increases the complexity level required for Eve's ruse). The randomization of the detectors used for photon counting at Bob's station is, nonetheless, sufficient to close this backdoor, while no additional hardware is needed.
For each incoming qubit, Bob not only randomly chooses the detection basis, but also may randomly invert the attribution of the pairs of detectors. This means that, if Bob wants to use the rectilinear basis, the HWP may be turned to 0º or 45º (or to 22.5º or 67.5º, if the diagonal basis is chosen). The additional choice [46] has no impact on the final value of the bit shared between Alice and Bob. For example, whenever Alice sends a H-polarized qubit, the bit inferred by Bob with matched basis is deterministic, say "0", but the click can occur at either detector A' (A or B in Fig. 1), if the HWP is set to 0º; or at detector C' (C or D in Fig. 1), if the HWP is set to 45º. The same idea holds for the diagonal basis. The process is written as the randomization of Alice's SOP to the spatial modes A and C as: where θ is the physical angle of Bob's HWP. Provided that this choice is truly random, Eve cannot infer at which SPD Bob's detection has occurred, so the final spatial mode is not accessible to her. In the time-shift attack context, if Eve waits the basis reconciliation and learns that Alice and Bob agreed, there is no way to infer which version of the basis Bob has chosen and the detector used, based on the imposed delay, even if the efficiency curves are fully mismatched. The countermeasure is equivalent to an active randomization of the spatial modes and drastically reduces the mutual information between Alice-Eve and Bob-Eve. When Bob's basis matches Alice's, the logical result is deterministic, but the detector that registered the event is random.
There is some discussion [13] if a Trojan-horse attack [47] could be attempted against the scrambler (the HWP in our case). Eve could send a strong pulse and read out the polarization rotation by analyzing the measured backscattered light. As discussed before, narrow filtering and isolators are necessary at the input of Bob's apparatus to provide technological protection. Here the spatial modes randomization acts in the same way as described in Section III.A to avoid the Trojan-horse attack in a fundamental level. As the probe pulse used in the attack must be bright -to overcome the isolation from Bob's HWP back to Eve -the photon counting statistics of Bob's SPDs will behave differently as from the expected.

A. Spatial Modes Randomization
The countermeasure against quantum hacking based on randomized spatial modes was experimentally implemented, as depicted in Fig. 2, which emulates the aftergate attack [17]. During the attack, Eve intercepts the optical pulses sent by Alice and resend faked states to Bob according to her result The statistics of the intercepted photons is ob experiment by the detection of a continuouslaser diode source (LD) sent by Alice though a variable optical attenuator (VOA). Eve detects the photons with a single photon APD (labeled E) operating in gated-Geiger mode. The detector has 15% detection efficiency and opens 2.5 gates triggered by the system's master clock (MC) at 100 kHz. A 10 µs deadtime is enforced after each detection event to avoid the afterpulse effect. Whenever a detection event occurs at Eve's SPD, the voltage pulse created by the detector is compressed by a pulse formatter (PF) and drives Eve's laser diode source (LD E ). The bright-light faked states are sent by Eve to Bob's station. The optical power regulated by a VOA and are delayed to reach Bob's detectors at the attack point, at the end of the gate ( attack), as explained ahead.
Bob's station setup is similar to the concept depicted in 1b, and is fully composed by fiber-optical elements. polarization controller (PC) acts as a HWP selection. Actually, this SOP selection is shared by Eve and Bob in this setup, and their combined angles are, in fact, emulated. A PBS performs the state projection and two BS create the passive randomized spatial modes, single-photon APDs are placed (labeled A to D) are similar to Eve's, including their configuration. A based coincidence counting module is connected to the four SPDs to acquire the single and coincident The delay generator is used to trigger the four SPDs in that the strong pulse reaches them at the end of the gate, when under the aftergate attack; or inside the gate, when under regular (no-attack) operation. We note that in a real attack, Eve herself would manipulate the relative delay faked states and the SPDs.
To find the attack set point, a 1-ns wide optical pulse scanned though the detection gate of each one of the four SPDs used by Bob in the experiment. As the pulse peak power is increased, the gate end is extended, due to the residual overvoltage bias. The set point for the aftergate attack, shown passive randomization of the spatial modes The setup emulates the LD: laser diode; VOA: variable optical attenuator; MC: controller; PBS: polarizing photon APDs.
Eve intercepts the optical pulses sent by according to her result. The statistics of the intercepted photons is obtained in the -wave (CW) faint laser diode source (LD) sent by Alice though a variable optical . Eve detects the photons with a single-Geiger mode. The detector has 15% detection efficiency and opens 2.5-ns wide gates triggered by the system's master clock (MC) at 100 kHz. s deadtime is enforced after each detection event to detection event occurs at Eve's SPD, the voltage pulse created by the detector is compressed by a pulse formatter (PF) and drives Eve's laser light faked states are sent by Eve to Bob's station. The optical power of the pulses is regulated by a VOA and are delayed to reach Bob's detectors the end of the gate (hence aftergate Bob's station setup is similar to the concept depicted in Fig. tical elements. A as a HWP for the basis selection. Actually, this SOP selection is shared by Eve and Bob in this setup, and their combined angles are, in fact, PBS performs the state projection and two BS zed spatial modes, where the four (labeled A to D). The SPDs are similar to Eve's, including their configuration. An FPGAis connected to the four coincident detection events. The delay generator is used to trigger the four SPDs in a way the end of the gate, when under the aftergate attack; or inside the gate, when under note that in a real attack, delay between the ns wide optical pulse was detection gate of each one of the four in the experiment. As the pulse peak power is increased, the gate end is extended, due to the residual bias. The set point for the aftergate attack, shown in Fig. 3, is reached when a 3-dB step sufficient to allow a binary beh probability. Fig. 3. Scan of optical pulses with 3-dB different peak power though the gate of the four SPDs used in the experiment (each subfigure corresponds to one of Bob's SPDs). The set point for the aftergate attack, when a bi the device is obtained, is indicated. All detectors are of the same model, except for SPDA. The higher separation of the curves for that detector is probably due to a different internal gate waveform.
The time delay between the bright gates is then fixed as indicated in Fig. 3. The 3 equivalent to the cases when Bob's and Eve's bases match (higher power reaching the right SPDs) or not (half each detector).
In the experiment, Eve sends horizon Bob, who sets the rectilinear or diagonal with a HWP adjusted to 0° corresponding to matched and mismatched bases Eve. The single and coincident events are collected during 300 s for both cases with regular operation and under attack.

B. Detector Scrambling
The detector-scrambling countermeasure was also experimentally implemented, as depicted in Fig. 4, which emulates the time-shift attack [12]. 6 dB step in peak power is sufficient to allow a binary behavior of the counting dB different peak power though the gate of the four SPDs used in the experiment (each subfigure corresponds to one of Bob's SPDs). The set point for the aftergate attack, when a binary response of the device is obtained, is indicated. All detectors are of the same model, . The higher separation of the curves for that detector is probably due to a different internal gate waveform.
The time delay between the bright pulses and the detection gates is then fixed as indicated in Fig. 3. The 3-dB step is equivalent to the cases when Bob's and Eve's bases match (higher power reaching the right SPDs) or not (half-power to In the experiment, Eve sends horizontal or vertical SOPs to rectilinear or diagonal measurement bases or 22.5°, respectively corresponding to matched and mismatched bases relative to . The single and coincident events are collected during 300 for both cases with regular operation and under attack. scrambling countermeasure was also experimentally implemented, as depicted in Fig. 4, which Alice sends 1-ns wide faint optical pulses th optical attenuator (VOA) with horizontally oriented SOPs to Bob. Alice's laser diode source driven by the formatted pulses from the master clock Bob launches the incoming pulses in freecollimating fiber-pigtailed lens. The beam passes through a bulk HWP and a bulk PBS. The output modes of the PBS are collected with aspheric lenses and delivered to SPDs, set the previous experiment. Two SPDs were used for this proof of-principle of the detector-scrambling strategy be set to 0° or 45° − the two versions of the ⊕ elements make the adjustments easier in the experiment, but in practice a fiber-optical modulator must be employed. In QKD systems using active basis choice, which correspond to most commercial systems, the randomizing element can be the same one that Bob uses for his basis choice. The only difference is that a set of four different rotations become necessary, instead of two, which requires the use of two random number clock.
In the time-shift attack, Eve controls the time pulses between Alice and Bob. Here, we analogously emulate the time shift by acting on the relative electronic delay between the optical pulses and the detection gates, all driven/triggered by the master clock. The relative gate delay of Bob's detectors was scanned relative to and their normalized detection efficiency was both devices.

V. RESULTS
The single and coincident counts were acquired for the system described in Fig. 2  ns wide faint optical pulses through a variable horizontally-or verticallyode source (LD) is master clock (MC).
-space through a . The beam passes through a bulk HWP and a bulk PBS. The output modes of the PBS are ected with aspheric lenses and delivered to SPDs, set as in Two SPDs were used for this proofscrambling strategy. The HWP can ⊕ basis. The bulk in the experiment, but in optical modulator must be employed. In QKD systems using active basis choice, which correspond to most commercial systems, the randomizing element can be the same his basis choice. The only difference is four different rotations become necessary, instead random numbers per Eve controls the time-of-flight of the we analogously emulate shift by acting on the relative electronic delay between the optical pulses and the detection gates, all The relative gate delay the optical pulse was measured for counts were acquired for the regular operation and under how in Fig. 5a and 5b, , acquired with the HWP set to different angles. With regular operation, when the HWP is sends horizontally-oriented SOP and Bob measures in the matching rectilinear basis, so SPD A for dark counts and residual optical misalignment effects). When the HWP is set to 45°, the pulses sent with vertical SOP are measured in the matching rectilinear basis. HWP is shared by Eve and Bob in the experiment, so the set angle corresponds to the composition of their individual devices. The pulses are then routed to the other output mode of the PBS, and SPD C or SPD D click. When the wrong basis is chosen for measurement, with HWP set to 22.5 preferential branch to click and any detector may fire Note the comparative behavior of the single matched bases: when under regular operation is randomly routed to one of the two detectors of the corresponding branch after the PBS under attack, a 3-dB level appears in the detectors, as both of them simultaneously optical pulse. This ratio must be hidden by Eve, accomplished by sacrificing half the detecti interception step.
The key point of the countermeasure appears when analyzing the coincident counts when is assumed. Under normal operation, a small fraction of coincident counts is expected, between SPD between SPD C and SPD D , due to multi split in the BSs and dark counts. As seen in the HWP is set to 0°, Eve oriented SOP and Bob measures in the A or SPD B click (excepting for dark counts and residual optical misalignment effects).
, the pulses sent with vertical SOP measured in the matching rectilinear basis. Note that the HWP is shared by Eve and Bob in the experiment, so the set ngle corresponds to the composition of their individual routed to the other output mode click. When the wrong basis is chosen for measurement, with HWP set to 22.5°, there is not a and any detector may fire. Note the comparative behavior of the single counts with regular operation, each faint pulse is randomly routed to one of the two detectors of the after the PBS; on the other hand, when in the count rate of the two simultaneously fire due to the bright optical pulse. This ratio must be hidden by Eve, which can be half the detections at the The key point of the countermeasure appears when when the symmetric-BS case . Under normal operation, a small fraction of counts is expected, between SPD A and SPD B or , due to multi-photon pulses that are . As seen in Fig. 5a, this occurrence is very low. On the other hand, when under the aftergate attack, almost all detections (with matched bases) are enforces detections in both SPD A and SPD D , simultaneously. Eve's fingerprints are clear from the results of the coincident counts. events between the other pairs of SPDs are hypothesis of Section III.A is ) asymmetrical hypothesis will also leave a strong signature, as only one detector of each pair will usually click -the fixed-asymmetric-BS case.
Another fingerprint left by Eve is observed when the bases are not matched. Although these events are discarded by Alice and Bob in the sifting procedure, this is avaluable source of information to Bob regarding an external intervening, as the occurrence of uncorrelated photon counts is severely reduced when the attack is performed, as seen in Fig. 5.
The results for the time-shift attack and the detectorscrambling countermeasure, measured with the setup of Fig. 4, are shown in Fig. 6.  Figure 6 shows the case of temporal efficiency mismatching between the gates of SPD A and SPD C . The normalized counting probability at SPD A and SPD C are shown when Alice respectively sends H-(black curves) or V-polarized (red curves) weak coherent states and Bob uses the ⊕ basis for measurement. For each gate delay, the mutual information between Eve and Bob is calculated from the ratio of the curves of both detectors as [12] ܫ ா ൌ 1 െ ܪ ଶ ቀ ଵା ቁ where r is the minimum ratio of the efficiency curves at a given delay and ܪ ଶ ሺݔሻ is the Shannon entropy. The mutual information between Eve and Bob is also displayed the figure (blue lines). The results in Fig. 6a are obtained with the scan of the optical pulse through the detection gates when Bob's HWP is set to 0° (⊕ basis), resulting in higher count rates in SPD A and SPD C , respectively, for H-and V-polarized states sent by Alice. This is the conventional operation without the detectorscrambling countermeasure. Eve's information can reach unity depending on the attack point (referring to the pulse delay enforced by Eve, i.e., the position of the optical pulse in the gate delay axis). If Eve enforces a set point to exploit the detection efficiency mismatch, her information about the resulting detection increases due to the higher probability of the event having occurred in the more efficient SPD. Fig. 6b exhibits equivalent results: Bob sets the HWP to 45° (⊕ basis with flipped SPDs), causing the detectors assignment to be inverted, therefore SPD A and SPD C now detect vertical and horizontal SOPs, respectively. The mutual information of Bob and Eve stills reaches high levels when looking only at this case.
When the countermeasure is active in a QKD session, Fig.  6a and 6b randomly occur, resulting in the averaged detection probability shown in Fig. 6c. We see that the efficiency mismatching disappears, and both curves corresponding to the detection of H-and V-polarized states are fairly identical. The causes of such an asymmetry are mainly the finite optical misalignment error of the SOPs and of the HWP (around 0.5%) and the statistical dispersion of the data. The first cause can be improved by careful polarization alignment of the system, while the second cause can be reduced by improving the statistics of the collection of counting events.
The mutual information between Eve and Bob drops significantly towards zero (the ideal value). A residual amount of information (due to the asymmetry discussed before) can be seen in Fig. 6c, but we can also see an efficiency penalty that must be compensated by Eve to cover her fingerprints: since the detectors are scrambled, Bob's apparent efficiency is actually the average of the mismatched counting probabilities. If Eve chooses to delay the photons to a relative temporal position with allows for higher information leakage, but far from the efficiency peak (as in the delay -10 ns on Fig. 6c), the efficiency perceived by Bob will be considerably lower than the original expected peak values. The information an eavesdropper can extract, calculated from the normalized values, is reduced from the initial value of 97%, shown in Fig.  6a, to values below 2% with the countermeasure active, shown in Fig. 6c.

VI. CONCLUSION
Despite the fact that a full practical solution for all kinds of quantum hacking attacks aimed at all aspects of traditional QKD systems has not yet been found or proved to be possible, the recent overflow of eavesdropping schemes motivated the proposal of many practical solutions. We have shown how some back-doors at the detection end can be closed in a standard BB84 frame with the creation of randomized spatial modes, passively by a combination of beamsplitters and extra SPDs and by actively scrambling the detectors at the measurement station. This represents a practical and readily implementable solution against bright-light-and efficiencymismatching-based quantum hacking attacks aimed on the single-photon detector so far.