Notorieties Based On Transitive Trust

0
0
1722 days ago, 645 views
PowerPoint PPT Presentation
Notorieties In light of Transitive Trust. Slides by Josh Albrecht. Review. Transitive Trust Illustrations Issue Foundation and Definition Sample Calculations Sybil Assaults More Definitions Two Hypotheses on Outlandish possibility of Protection Against Sybil Assaults [Friedman et al, 2007]

Presentation Transcript

Slide 1

Notorieties Based On Transitive Trust Slides by Josh Albrecht

Slide 2

Overview Transitive Trust Examples Problem Background and Definition Example Algorithms Sybil Attacks More Definitions Two Theorems on Impossibility of Defense Against Sybil Attacks [Friedman et al, 2007] Solution—Two More Theorems Practical Implications Related Theorems [Altman & Tennenholtz, 2007]

Slide 3

Transitive Trust-Based Reputations Problem: Want to choose the amount to trust some element within the sight of subjective criticism Solution: Use transitive trust—an element's notoriety decides the amount we confide in a bit of input from that substance. ie, if A trusts B, and B puts stock in C, then A trusts C more than obscure hub D Basically, we begin with an arrangement of trusted hubs, and extend the thought of trust recursively from that point

Slide 4

Real Life Examples

Slide 5

Transitive Trust-Based Reputations 0.1 0.35 0.4 0.9 0.5 0.02 0.05 0.45 0.25 0.02

Slide 6

Example Trust Mechanisms Pathrank Max Flow PageRank

Slide 7

Definitions Trust Graph: Set of players (vertices): Set of edges: Trust values: Reputation work: Reputation of is symmetric iff drives with stage of the hub names

Slide 8

Example Trust Mechanisms Pathrank Max Flow PageRank

Slide 9

PathRank Example 0.1 0.35 0.4 0.9 0.5 0.02 0.05 0.45 0.25 0.02

Slide 10

Max Flow Example 0.1 0.35 0.4 0.9 0.5 0.02 0.05 0.45 0.25 0.02

Slide 11

PageRank Initial calculation behind Google's positioning of pages Each page has a PageRank score Outgoing connections give 1/PageRank score to their objectives Simplified Algorithm: [Wikipedia, 2008] Simulate surfer that begins at an arbitrary page and arbitrarily clicks joins, with a 15% possibility of setting off to a totally irregular page. Coming about rankings are around equivalent to the possibility that such a surfer will be on that page at any given time

Slide 12

PageRank Example 0.33 0.25 1 0.25 0.5 1 0.5

Slide 13

Problems With Transitive Trust We will accept the system and all information is known Players have no impetus to give trust values There might be solid motivator to give erroneous trust values Ideally we need a notoriety framework that is rank-strategyproof: v can't enhance his rank requesting by key decisions of t qualities. … sadly, any nontrivial, monotonic, symmetric notoriety framework can't be rank-strategyproof. This is anything but difficult to see. Whenever another hub that you have connected with is higher positioned than you, simply drop your active edge to them to cut them down

Slide 14

Sybil Attacks A solitary specialist makes numerous other fake players (sybils) with the objective of enhancing the operator's notoriety The malevolent specialist can make any structure of connections and trust amongst sybils and himself Incoming trust connections can be diverted from the first vindictive specialist to any of the sybils in a way that jam the general measure of approaching trust

Slide 15

Sybil Attack Example

Slide 16

More Definitions: Sybil Strategy Given diagram and client v we say that and subset is a sybil system for v in G if and falling into a solitary hub v in yields G . Accordingly a sybil technique is meant , and we allude to as the sybils of v.

Slide 17

G V

Slide 18

V

Slide 19

V

Slide 20

More Definitions: Value-Sybilproof A notoriety work F is esteem sybilproof if for all charts, there is no sybil methodology of hub v that can make v have a higher notoriety esteem than in the first diagram.

Slide 21

More Definitions: Rank-Sybilproof A notoriety work F is rank-sybilproof if for all diagrams, there is no sybil technique that can make hub v outrank a hub w if v did not outrank w in the first chart.

Slide 22

Theorem 27.5 Theorem : There is no nontrivial symmetric rank-sybilproof notoriety work. Casual Proof : Given a chart with rank( v ) > rank( w ), let the sybils of v be a copy of the whole diagram Then by symmetry, there is some hub u in the sybil set to such an extent that rank( u ) = rank( w ) Thus, F is not rank-sybilproof. QED

Slide 23

Theorem 27.5 v Original Graph ( G ) w New Graph ( G 1 ) v u w

Slide 24

Theorem 27.5 Theorem : There is no nontrivial symmetric rank-sybilproof notoriety work. Confirmation : Given and notoriety fn F Let Consider where By symmetry Thus, F is not rank-sybilproof. QED

Slide 25

Last Definition: K-Rank-Sybilproof Reputation work F is K-rank-sybilproof iff it is rank-sybilproof for all sybil methodologies with

Slide 26

Theorem 27.7 Theorem : There is no symmetric nontrivial K-rank-sybilproof for K > 0 Informal Proof : Consider the setup from the past confirmation There is some hub w that outranks v in the first diagram and is equivalent to u in the last chart Consider the procedure of gradually developing the copy diagram eventually, including a solitary hub will bring about the rank( u ) >= rank( w ) Then including that solitary hub is an effective sybil methodology for u in that specific chart Thus F is not rank-1 sybilproof on all diagrams

Slide 27

Theorem 27.7 Original Graph ( G ) w New Graph ( G 1 ) w

Slide 28

Theorem 27.7 Original Graph ( G ) w New Graph ( G 1 ) w

Slide 29

Theorem 27.7 Original Graph ( G ) w New Graph ( G 1 ) v w

Slide 30

Implications All symmetric notoriety capacities are helpless against this assault Ex: PageRank, SEO, and spam sites Solution? Utilize hilter kilter approaches (seed set, true arrangement) Next hypotheses demonstrate sybilproofness for max stream and most limited way notoriety capacities

Slide 31

Theorem 27.8 Theorem : The maximum stream based positioning component is esteem sybilproof Proof : Max Flow = Min Cut All sybils of v must be on an indistinguishable side of the cut from v, in this way not on an indistinguishable side from the source s Thus, no sybil can have a higher incentive than the min cut, which is equivalent to , QED

Slide 32

Max Flow Example

Slide 33

Theorem 27.9 Theorem : The Pathrank notoriety system is esteem and rank-sybilproof Proof : Sybils can't diminish the length of the briefest way, hence it is esteem sybilproof For rank-sybilproofness, take note of that a hub v can just influence another hub w 's positioning if v is on the most limited way to w . Yet, in the event that that is valid, then . QED

Slide 34

Practical Implications SybilGuard [Yu et. al., 2006] Some specialists at Intel have done an observational investigation of safeguard against Sybil assaults They utilize way separate (uneven measure) to get around these symmetry issues SEO The web works at all in light of the fact that there is an arrangement of destinations that we know have great notorieties, so PageRank worked (at any rate previously) Also, making sybils in this area (page notoriety) is costly and troublesome P2P Some scientists have taken a gander at how these standards apply in the P2P setting, where clients need to know which different hubs will give them substantial duplicates of the record, and have great execution

Slide 35

Other Properties of Reputation Ranking Mechanisms Weak Positive Response: adding an edge from u to v won't diminish the rank of v Strong Positive Response: if w and v have parallel positions, adding an edge from u to v will expand the rank of v

Slide 36

Other Properties of Reputation Ranking Mechanisms Minimal Fairness: when there are no edges, all players have a similar rank Weak Monotonicity: if the arrangement of vertices with edges going to v is a superset of the arrangement of edges with vertices going to u , then v does not have a lower rank than u Strong Monotonicity: if the arrangement of vertices with edges going to v is a strict superset of the arrangement of edges with vertices going to u , then v has a higher rank than u

Slide 37

Other Properties of Reputation Ranking Mechanisms Old chart New diagram Weak Union Condition: If v is positioned <= u in G , then v is positioned <= u in another diagram comprising of G and some other self-assertive diagram H . Solid Union Condition: If v is positioned <= u in G , then v is positioned <= u in another chart comprising of G and some other subjective diagram H regardless of the possibility that edges are permitted amongst G and H in the new chart.

Slide 38

Approval Voting Ranking Definition : v is positioned <= u iff the quantity of approaching edges of v is <= the number approaching edges of u . Certainty : The Approval Voting positioning mechanims fulfills insignificant reasonableness, solid monotonicity, solid positive reaction, the solid union condition, and unbounded non-technicality.

Slide 39

Incentive Compatibility Incentive Compatible: F is motivator perfect if the normal utility from its positioning is not influenced by controlling its active edges. Emphatically Incentive Compatible: F is motivating force good for all nondecreasing utility capacities. Pitifully Incentive Compatible: F is motivator good for every utility capacity of the frame a*k+b, where an and b are genuine numbers and k is the rank.

Slide 40

Incentive Compatibility Without Minimum Fairness Proposition : There exists a positioning framework F1 that fulfills solid motivator similarity, solid positive reaction, boundless non-technicality, and the solid union condition.

Slide 41

Incentive Compatibility With Minimum Fairness Theorem : There exist pitifully motivator good, interminably nontrivial, negligibly reasonable positioning frameworks F2, F3, F4, that fulfill feeble monotonicity; frail positive reaction; and the powerless union condition individually. However there is no pitifully impetus good, nontrivial, negligibly reasonable positioning system that fulfills any two of those three properties. Hypothesis : There is no feebly motivating force perfect, nontrivial, negligibly reasonable positioning framework t

SPONSORS