DOC PREVIEW
UT CS 395T - Private Graph Algorithms in the Semi-Honest Model

This preview shows page 1-2-3-25-26-27 out of 27 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Private Graph Algorithms in the Semi-Honest ModelTwo Party Graph AlgorithmsUnnecessary InformationThe Semi-Honest ModelGeneral Secure Two Party ComputationTwo-Input Graph Algorithms?Graph SynthesisGraph SynthesisGraph IsomorphismComparison of Graph StatisticsSynthesized GraphsAPSD(gmin(G1,G2))Run APSD on G1 and G2Initialize G0’Find shortest blue edge lengthsPrivately find global shortest lengthFind edges of length blueminPrivately find all edges of length blueminUpdate S edges in G0’Run APSD on G0’Repeat!……… until all edges are redThe solution is correct!Other ResultsFinal ThoughtPrivate Graph Algorithms in the Semi-Honest ModelJustin BrickellNovember 24, 2004Two Party Graph Algorithms• Parties P1and P2own graphs G1and G2 • f is a two-input graph algorithm• Compute f(G1,G2) without revealing “unnecessary information”Unnecessary Information• Intuitively, the protocol should function as if a trusted third party computed the output• We use simulation to prove that a protocol is privateThe Semi-Honest Model•A malicious adversary can alter his input• A semi-honest adversary – adheres to protocol– tries to learn extra information from the message transcriptGeneral Secure Two Party Computation• Any polynomial sized functionality can be made private (in the semi-honest model)– Yao’s Method• What are our goals?– Yao’s Method is inefficient– Efficient, private protocols to compute particular graph functionalities– Take advantage of information “leaked” by the resultTwo-Input Graph Algorithms?• Graph Isomorphism• Comparison of graph statistics– f(G1) > f(G2) ?– max flow,diameter,average degree• Synthesized Graphs– f(G1• G2)Graph Synthesis• G1and G2are weighted complete graphs on the same vertex and edge set– G1= (V,E,w1); G2= (V,E,w2)•gmax(G1,G2) = (V,E,wmax)–wmax(e) = max(w1(e),w2(e))• gmin(G1,G2) = (V,E,wmin)–wmin(e) = min(w1(e),w2(e))Graph Synthesis1 234∞1 234∞867854G1gmax(G1,G2)52771 23421 2342667654gmin(G1,G2)G25 25 5Graph Isomorphism• Unlikely to find a private protocol– No known poly-time algorithmComparison of Graph Statistics1. Compute statistic on own graph– Semi-honest participants can’t lie2. Use a private comparison protocol– Yao’s Millionaire Protocol– Yao’s method (circuit protocol)Synthesized Graphs• This is the interesting case• All Pairs Shortest Distance and Single Source Shortest Distance both “leak”significant useful information– Solved: APSD(gmin),SSSD(gmin)– Solved with leaks: APSD(gmax),SSSD(gmax)APSD(gmin(G1,G2))• Basic Idea: Add edges to the solution graph in order of smallest to largest• Private, because we can recover the order from the final solution graphRun APSD on G1and G21 23471 234∞854854G1G1’22671 23421 2342667667G2’G25 55 5Initialize G0’1 234726854G1’1 23421 234∞667∞∞∞5∞5∞G2’G0’Find shortest blue edge lengths1 234726854G1’1 23421 234∞667∞∞∞5∞5∞G2’G0’min1 = 2 min2 = 2min0 = ∞Privately find globalshortest length1 23471 234251 234∞854667∞∞∞2∞56∞G1’G2’G0’min1 = 2 min2 = 2min0 = ∞bluemin = min(min0,min1,min2) =2Find edges of length bluemin1 234726854G1’1 23421 234∞667∞∞∞5∞5∞G2’G0’S1={e23} S2={e12}S0= {}bluemin = min(min0,min1,min2) =2Privately find all edges oflength bluemin1 23471 234251 234∞854667∞∞∞2∞56∞G1’G2’G0’S1={e23} S2={e12}S0= {}S = S1∪ S2∪ S3= {e12,e23}Update S edges in G0’1 234726854G1’1 23421 2342667∞∞∞5 25∞G2’G0’S1={e23} S2={e12}S0= {}S = S1∪ S2∪ S3= {e12,e23}Run APSD on G0’1 234726854G1’1 23421 23426674∞∞5 25∞G2’G0’Repeat!1 234726854G1’1 23421 23426674∞∞5 25∞G2’G0’bluemin = min(min0,min1,min2) =4S = S1∪ S2∪ S3= {e13,e24}…1 234726854G1’1 23421 23426674465 25 6G2’G0’bluemin = min(min0,min1,min2) =5S = S1∪ S2∪ S3= {e34}…1 234726854G1’1 23421 23426674465 25 5G2’G0’bluemin = min(min0,min1,min2) =6S = S1∪ S2∪ S3= {e14}… until all edges are red1 234726854G1’1 23421 23426674465 25 5G2’G0’The solution is correct!1 23421 23426544462255gmin(G1,G2)G0’Other Results• A similar protocol for SSSD(gmin)– This isn’t free!• Protocol for special case of APSD(gmax) and SSSD(gmax)– Input graphs obey triangle inequality• “Leaky” protocol for APSD(gmax) and SSSD(gmax) in the general caseFinal Thought• Other graph algorithms don’t leak enough information•


View Full Document

UT CS 395T - Private Graph Algorithms in the Semi-Honest Model

Documents in this Course
TERRA

TERRA

23 pages

OpenCL

OpenCL

15 pages

Byzantine

Byzantine

32 pages

Load more
Download Private Graph Algorithms in the Semi-Honest Model
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Private Graph Algorithms in the Semi-Honest Model and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Private Graph Algorithms in the Semi-Honest Model 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?