Säker beräkning av flera parter - Secure multi-party computation

Säker beräkning av flera parter (även känd som säker beräkning , flerpartsberäkning (MPC) eller sekretessbevarande beräkning ) är ett delfält av kryptografi med målet att skapa metoder för parter att gemensamt beräkna en funktion över sina ingångar samtidigt som de behålls ingångar privata. Till skillnad från traditionella kryptografiska uppgifter, där kryptografi säkerställer säkerhet och integritet för kommunikation eller lagring och motståndaren är utanför deltagarnas system (en avlyssnare på avsändaren och mottagaren), skyddar kryptografin i denna modell deltagarnas integritet från varandra.

Grunden för säker flerpartsberäkning började i slutet av 1970-talet med arbetet med mental poker, kryptografiskt arbete som simulerar spel- / beräkningsuppgifter över avstånd utan att kräva en pålitlig tredje part. Observera att kryptografi traditionellt handlade om att dölja innehåll, medan den här nya typen av beräkning och protokoll handlar om att dölja partiell information om data medan man beräknar med data från många källor och korrekt producerar utdata.

Historia

Protokoll för specialändamål för specifika uppgifter startade i slutet av 1970-talet. Senare introducerades säker beräkning formellt som säker tvåpartsberäkning (2PC) 1982 (för det så kallade miljonärsproblemet , ett specifikt problem som är ett booleskt predikat) och i allmänhet (för alla möjliga beräkningar) 1986 av Andrew Yao . Området kallas också Secure Function Evaluation (SFE). Tvåpartifallet följdes av en generalisering till flerpartiet av Goldreich, Micali och Wigderson. Beräkningen är baserad på hemlig delning av alla ingångar och bevis på noll kunskap för ett potentiellt skadligt fall, där majoriteten av ärliga spelare i det skadliga motståndarfallet försäkrar att dåligt beteende upptäcks och beräkningen fortsätter med att den oärliga personen elimineras eller hans ingång avslöjad. Detta arbete föreslog det mycket grundläggande allmänna schemat som följs av i princip alla framtida flerpartsprotokoll för säker databehandling. Detta arbete introducerade ett tillvägagångssätt, känt som GMW-paradigm, för att sammanställa ett beräkningsprotokoll med flera parter som är säkert mot halvärliga motståndare till ett protokoll som är säkert mot skadliga motståndare. Detta arbete följdes av det första robusta säkra protokollet som tolererar felaktigt beteende nådigt utan att avslöja någons produktion via ett verk som uppfann för detta ändamål den ofta använda `` andel av aktier-idén '' och ett protokoll som gör det möjligt för en av parterna att dölja sin input ovillkorligt . GMW-paradigmet ansågs vara ineffektivt i flera år på grund av enorma omkostnader som det leder till basprotokollet. Det visas dock att det är möjligt att uppnå effektiva protokoll, och det gör denna forskningslinje ännu mer intressant ur ett praktiskt perspektiv. Ovanstående resultat finns i en modell där motståndaren är begränsad till polynomiska tidsberäkningar, och den observerar all kommunikation, och därför kallas modellen för 'beräkningsmodell'. Vidare visade sig protokollet om glömsk överföring vara komplett för dessa uppgifter. Ovanstående resultat visade att det är möjligt under ovanstående variationer att uppnå säker beräkning när majoriteten av användarna är ärliga.

Nästa fråga att lösa var fallet med säkra kommunikationskanaler där punkt-till-punkt-kommunikationen inte är tillgänglig för motståndaren; i det här fallet visades det att lösningar kan uppnås med upp till 1/3 av parterna som uppför sig och skadar och lösningarna använder inga kryptografiska verktyg (eftersom säker kommunikation är tillgänglig). Genom att lägga till en sändningskanal kan systemet tolerera upp till 1/2 dåligt uppförande minoritet, medan anslutningsbegränsningar på kommunikationsgrafen undersöktes i boken Perfectly Secure Message Transmission.

Genom åren blev begreppet flerpartsprotokoll för allmänt ändamål ett bördigt område för att undersöka grundläggande och allmänna protokollfrågor om egenskaper, såsom universell komponeringsbarhet eller mobil motståndare som vid proaktiv hemlig delning .

Sedan slutet av 2000-talet, och säkert sedan 2010 och framåt, har domänen för allmänna ändamålsprotokoll flyttats för att hantera effektivitetsförbättringar av protokollen med praktiska tillämpningar i åtanke. Alltmer effektiva protokoll för MPC har föreslagits och MPC kan nu betraktas som en praktisk lösning på olika verkliga problem (särskilt sådana som endast kräver linjär delning av hemligheterna och främst lokal verksamhet på aktierna med inte mycket interaktion mellan parterna. ), såsom distribuerad omröstning, privat budgivning och auktioner, delning av signatur- eller dekrypteringsfunktioner och hämtning av privat information . Den första storskaliga och praktiska tillämpningen av beräkning av flera parter (visat på ett verkligt auktionsproblem) ägde rum i Danmark i januari 2008. Uppenbarligen behövs både teoretiska föreställningar och utredningar och tillämpade konstruktioner (t.ex. villkor för att flytta MPC till en del av det dagliga arbetet förespråkades och presenterades i).

Definition och översikt

I en MPC, ett givet antal deltagare, s ₁ , s ₂ , ..., p _-N , har var och privata data , respektive D ₁ , d ₂ , ..., d _N . Deltagarna vill beräkna värdet av en offentlig funktion på den privata informationen: F (d ₁ , d ₂ , ..., d _N ) medan de håller sina egna ingångar hemliga.

Antag till exempel att vi har tre parter Alice, Bob och Charlie, med respektive ingångar x, y och z som anger deras löner. De vill ta reda på den högsta av de tre lönerna utan att avslöja för varandra hur mycket var och en av dem tjänar. Matematiskt betyder detta att de beräknar:

F (x, y, z) = max (x, y, z)

Om det fanns någon pålitlig extern part (säg, de hade en gemensam vän Tony som de visste kunde hålla hemligt), kunde de berätta var sin lön till Tony, han kunde beräkna det maximala och berätta det antalet för dem alla. Målet med MPC är att utforma ett protokoll, där Alice, Bob och Charlie, genom att bara utbyta meddelanden med varandra, fortfarande kan lära sig $F (x, y, z)$ utan att avslöja vem som gör vad och utan att behöva förlita sig på Tony. De borde inte lära sig mer genom att engagera sig i deras protokoll än de skulle lära sig genom att interagera med en oförstörbar, helt pålitlig Tony.

I synnerhet är allt som parterna kan lära sig vad de kan lära sig av produktionen och deras egna input. Så i exemplet ovan, om utdata är $z$ , lär Charlie att hans $z$ är det maximala värdet, medan Alice och Bob lär sig (om $x$ , $y$ och $z$ är olika), att deras inmatning inte är lika med maximalt, och att det maximala hållet är lika med $z$ . Basscenariot kan lätt generaliseras till där parterna har flera in- och utgångar, och funktionen matar ut olika värden till olika parter.

Informellt sett är de mest grundläggande egenskaperna som ett beräkningsprotokoll för flera parter syftar till att säkerställa:

Ingångsintegritet: Ingen information om parternas privata data kan dras från de meddelanden som skickas under genomförandet av protokollet. Den enda informationen som kan dras om de privata uppgifterna är vad som kan dras från att bara se funktionens resultat.
Korrekthet: Varje korrekt delmängd av kontroversiella motparter som är villiga att dela information eller avvika från instruktionerna under protokollets genomförande bör inte kunna tvinga ärliga parter att ge ett felaktigt resultat. Detta riktighetsmål finns i två smaker: antingen är de ärliga parterna garanterade att beräkna rätt utdata (ett "robust" protokoll) eller så avbryts de om de hittar ett fel (ett MPC-protokoll "med avbrott").

Det finns ett brett utbud av praktiska applikationer, som varierar från enkla uppgifter som myntkastning till mer komplexa som elektroniska auktioner (t.ex. beräkna marknadspriset), elektronisk röstning eller sekretessbevarande datautvinning. Ett klassiskt exempel är miljonärsproblemet: två miljonärer vill veta vem som är rikare, på ett sådant sätt att ingen av dem lär sig andras nettovärde. En lösning på denna situation är i huvudsak att säkert utvärdera jämförelsefunktionen.

Säkerhetsdefinitioner

Ett beräkningsprotokoll med flera parter måste vara säkert för att vara effektivt. I modern kryptografi är säkerheten för ett protokoll relaterad till ett säkerhetsskydd. Säkerhetsbeviset är ett matematiskt bevis där säkerheten för ett protokoll reduceras till säkerheten för dess underliggande primitiver. Ändå är det inte alltid möjligt att formalisera krypteringsprotokollets säkerhetsverifiering baserat på partikännedomen och protokollets korrekthet. För MPC-protokoll är den miljö där protokollet fungerar associerad med den verkliga världen / Ideal World Paradigm. Parterna kan inte sägas lära sig ingenting, eftersom de behöver lära sig resultatet av operationen, och utgången beror på ingångarna. Dessutom garanteras inte utgångens korrekthet, eftersom utgångens riktighet beror på parternas ingångar, och ingångarna måste antas vara skadade.

The Real World / Ideal World Paradigm anger två världar: (i) I idealvärldsmodellen finns det en oförstörbar pålitlig part som varje protokolldeltagare skickar sin input till. Denna betrodda part beräknar funktionen på egen hand och skickar tillbaka lämplig utdata till varje part. (ii) Däremot finns det i verklighetsmodellen ingen pålitlig part och allt parterna kan göra är att utbyta meddelanden med varandra. Ett protokoll sägs vara säkert om man inte kan lära sig mer om varje parts privata insatser i den verkliga världen än man kan lära sig i den ideala världen. I den ideala världen utbyts inga meddelanden mellan parterna, så verkliga utbytta meddelanden kan inte avslöja någon hemlig information.

Real World / Ideal World Paradigm ger en enkel abstraktion av komplexiteten hos MPC för att möjliggöra konstruktion av en applikation under förevändning att MPC-protokollet i sin kärna faktiskt är ett perfekt utförande. Om applikationen är säker i idealfallet är den också säker när ett riktigt protokoll körs istället.

Säkerhetskraven på ett MPC-protokoll är stränga. Ändå demonstrerades 1987 att vilken funktion som helst kan beräknas säkert, med säkerhet för skadliga motståndare och andra tidigare verk som nämnts tidigare. Trots dessa publikationer var MPC inte utformat för att vara tillräckligt effektivt för att användas i praktiken vid den tiden. Villkorslöst eller informationsteoretiskt säkert MPC är nära besläktat och bygger på problemet med hemlig delning och mer specifikt verifierbar hemlig delning (VSS), som många säkra MPC-protokoll använder mot aktiva motståndare.

Till skillnad från traditionella kryptografiska applikationer, som kryptering eller signatur, måste man anta att motståndaren i ett MPC-protokoll är en av de spelare som är engagerade i systemet (eller kontrollerar interna parter). Den eller de skadade partierna kan samarbeta för att bryta mot protokollets säkerhet. Låt vara antalet parter i protokollet och antalet parter som kan vara kontroversiella. Protokollen och lösningarna för fallet (dvs. när man antar en ärlig majoritet) skiljer sig från dem där inget sådant antagande görs. I det senare fallet ingår det viktiga fallet med tvåpartsberäkning där en av deltagarna kan bli skadad och det allmänna fallet där ett obegränsat antal deltagare är korrupta och samarbetar för att attackera de ärliga deltagarna. ${\ displaystyle n}$ ${\ displaystyle t}$ ${\ displaystyle t <n / 2}$

Motståndare inför olika protokoll kan kategoriseras efter hur villiga de är att avvika från protokollet. Det finns i huvudsak två typer av motståndare, som alla ger upphov till olika former av säkerhet (och var och en passar in i olika verkliga scenarier):

Halvärlig (passiv) säkerhet: I det här fallet antas det att korrupta parter bara samarbetar för att samla in information ur protokollet, men avviker inte från protokollspecifikationen. Detta är en naiv motståndarmodell som ger svag säkerhet i verkliga situationer. Protokoll som uppnår denna säkerhetsnivå förhindrar dock oavsiktligt läckage av information mellan (annars samarbetspartier) och är därför användbara om detta är det enda problemet. Dessutom är protokoll i den semi-ärliga modellen ganska effektiva och är ofta ett viktigt första steg för att uppnå högre säkerhetsnivåer.
Skadlig (aktiv) säkerhet: I det här fallet kan motståndaren godtyckligt avvika från protokollkörningen i sitt försök att fuska. Protokoll som uppnår säkerhet i denna modell ger en mycket hög säkerhetsgaranti. När det gäller majoriteten av de felaktiga partierna: Det enda som en motståndare kan göra i fall av oärlig majoritet är att få de ärliga parterna att "avbryta" efter att ha upptäckt fusk. Om de ärliga parterna uppnår produktion, garanteras de att det är korrekt. Deras integritet bevaras alltid.

Säkerhet mot aktiva motståndare leder vanligtvis till en minskning av effektiviteten som leder till dold säkerhet, en avslappnad form av aktiv säkerhet. Dold säkerhet säkerhet fångar mer realistiska situationer där aktiva motståndare är villiga att fuska men bara om de inte fångas. Till exempel kan deras rykte skadas och förhindra framtida samarbete med andra ärliga parter. Således ger protokoll som är hemligt säkra mekanismer för att säkerställa att om några av parterna inte följer instruktionerna kommer det att märkas med stor sannolikhet, säg 75% eller 90%. På ett sätt är dolda motståndare aktiva som tvingas agera passivt på grund av externa icke-kryptografiska (t.ex. affärs) bekymmer. Denna mekanism sätter en bro mellan båda modellerna i hopp om att hitta protokoll som är effektiva och säkra nog i praktiken.

Liksom många kryptografiska protokoll kan säkerheten för ett MPC-protokoll förlita sig på olika antaganden:

Det kan vara beräkningsmässigt (dvs baserat på något matematiskt problem, som factoring) eller villkorslöst, nämligen att förlita sig på fysisk otillgänglighet av meddelanden på kanaler (vanligtvis med viss sannolikhet för fel som kan göras godtyckligt liten).
Modellen kan anta att deltagarna använder ett synkroniserat nätverk , där ett meddelande som skickas vid ett "kryss" alltid kommer fram till nästa "kryss", eller att det finns en säker och pålitlig sändningskanal, eller att det finns en säker kommunikationskanal mellan varje par av deltagare där en motståndare inte kan läsa, ändra eller generera meddelanden i kanalen etc.

Uppsättningen ärliga parter som kan utföra en beräkningsuppgift är relaterad till begreppet åtkomststruktur . Motståndsstrukturer kan vara statiska, där motståndaren väljer sina offer innan flerpartsberäkningen påbörjas, eller dynamisk, där den väljer sina offer under genomförandet av flerpartsberäkningen som gör försvaret svårare. En motståndsstruktur kan definieras som en tröskelstruktur eller som en mer komplex struktur. I en tröskelstruktur kan motståndaren förstöra eller läsa minnet hos ett antal deltagare upp till någon tröskel. Under tiden kan det i en komplex struktur påverka vissa fördefinierade delmängder av deltagare och modellera olika möjliga samverkan.

Protokoll

Det finns stora skillnader mellan de föreslagna protokollen för tvåpartsberäkning (2PC) och beräkning av flera parter (MPC). Ofta måste också specialprotokoll av betydelse utformas för ett specialprotokoll som avviker från de generiska (rösträtt, auktioner, betalningar etc.)

Tvåpartsberäkning

Tvåpartsinställningen är särskilt intressant, inte bara ur ett applikationsperspektiv utan också för att speciella tekniker kan användas i tvåpartsinställningen som inte gäller i flerpartsfallet. I själva verket presenterades säker beräkning av flera parter (i själva verket det begränsade fallet med utvärdering av säker funktion, där endast en enda funktion utvärderas) i tvåpartsinställningen. Det ursprungliga arbetet citeras ofta som ett av Yaos två artiklar; även om tidningarna faktiskt inte innehåller det som nu kallas Yaos protokoll med förvrängd krets .

Yaos grundprotokoll är säkert mot halvärliga motståndare och är extremt effektivt när det gäller antalet omgångar, vilket är konstant och oberoende av målfunktionen som utvärderas. Funktionen ses som en boolesk krets, med ingångar i binär med fast längd. En boolesk krets är en samling grindar som är anslutna till tre olika typer av ledningar: kretsingångsledningar, kretsutgångsledningar och mellanledningar. Varje grind tar emot två ingångsledningar och den har en enda utgångsledning som kan vara fläktad (dvs. skickas till flera grindar på nästa nivå). Enkel utvärdering av kretsen görs genom att utvärdera varje grind i tur och ordning; förutsatt att grindarna har beställts topologiskt. Porten representeras som en sanningstabell så att för varje möjligt bitpar (de som kommer från ingångsledarnas port) tilldelar tabellen en unik utgångsbit; vilket är värdet på portens utgångstråd. Resultaten av utvärderingen är bitarna som erhållits i krets-utgångsledningarna.

Yao förklarade hur man klumpar i en krets (döljer dess struktur) så att två parter, avsändare och mottagare, kan lära sig utgången från kretsen och inget annat. På hög nivå förbereder avsändaren den förvrängda kretsen och skickar den till mottagaren, som omedvetet utvärderar kretsen och lär sig kodningarna som motsvarar både hans och avsändarens utgång. Han skickar sedan tillbaka avsändarens kodningar, så att avsändaren kan beräkna sin del av utdata. Avsändaren skickar kartläggningen från mottagarnas utgångskodningar till bitar till mottagaren, så att mottagaren kan få sin utgång.

Mer detaljerat beräknas den förvrängda kretsen enligt följande. Huvudingrediensen är ett dubbeltangent symmetriskt krypteringsschema. Med tanke på en kretsgrind kodas varje möjligt värde för dess ingångsledningar (antingen 0 eller 1) med ett slumpmässigt tal (etikett). Värdena som härrör från utvärderingen av grinden vid vart och ett av de fyra möjliga paret av ingångsbitar ersätts också med slumpmässiga etiketter. Portens förvrängda sanningstabell består av krypteringar av varje utdatamärkning med dess ingångsetiketter som nycklar. Positionen för dessa fyra krypteringar i sanningstabellen är slumpmässig så ingen information om grinden läcks ut.

För att korrekt utvärdera varje förvrängd grind har krypteringsschemat följande två egenskaper. För det första är krypteringsfunktionens intervall under två olika nycklar oskiljaktiga (med överväldigande sannolikhet). Den andra egenskapen säger att det kan kontrolleras effektivt om en viss ciphertext har krypterats under en viss nyckel. Med dessa två egenskaper kan mottagaren, efter att ha erhållit etiketterna för alla kretsingångsledningar, utvärdera varje grind genom att först ta reda på vilken av de fyra krypteringstexterna som har krypterats med hans etikettnycklar och sedan dekryptera för att erhålla etiketten för utgångstråden. . Detta görs omedvetet eftersom all mottagare lär sig under utvärderingen är kodning av bitarna.

Sändarens (dvs. kretsskapare) ingångsbitar kan bara skickas som kodningar till utvärderaren; medan mottagarens (dvs. kretsutvärderare) kodningar motsvarande hans ingångsbitar erhålls via ett 1-ut-av-2 Oblivious Transfer (OT) -protokoll. Ett 1-ut-av-2 OT-protokoll gör det möjligt för avsändaren, som har två värden C1 och C2, att skicka det som begärs av mottagaren (ba-värde i {1,2}) på ett sådant sätt att avsändaren gör vet inte vilket värde som har överförts, och mottagaren lär sig bara det ifrågasatta värdet.

Om man överväger skadliga motståndare måste ytterligare mekanismer för att säkerställa båda parters korrekta beteende tillhandahållas. Genom konstruktion är det enkelt att visa säkerhet för avsändaren om OT-protokollet redan är säkert mot skadlig motståndare, eftersom allt mottagaren kan göra är att utvärdera en förvrängd krets som inte skulle nå kretsutgångsledningarna om han avviker från instruktionerna . Situationen är mycket annorlunda på avsändarens sida. Till exempel kan han skicka en felaktig förvrängd krets som beräknar en funktion som avslöjar mottagarens ingång. Detta skulle innebära att sekretess inte längre gäller, men eftersom kretsen är förvrängd skulle mottagaren inte kunna upptäcka detta. Det är dock möjligt att effektivt använda Zero-Knowledge-bevis för att göra detta protokoll säkert mot skadliga motståndare med en liten kostnad jämfört med det semi-ärliga protokollet.

Flerpartsprotokoll

De flesta MPC-protokoll, i motsats till 2PC-protokoll och särskilt under ovillkorlig inställning av privata kanaler, använder hemlig delning. I de hemliga delningsbaserade metoderna spelar inte parterna särskilda roller (som i Yao, av skapare och utvärderare). Istället delas data som är kopplade till varje tråd mellan parterna och ett protokoll används sedan för att utvärdera varje grind. Funktionen definieras nu som en "krets" över ett ändligt fält, i motsats till de binära kretsarna som används för Yao. En sådan krets kallas i litteraturen en aritmetisk krets och den består av "grindar" för tillägg och multiplikation där värden som används definieras över ett ändligt fält.

Hemlig delning gör det möjligt för en att distribuera en hemlighet bland ett antal parter genom att distribuera aktier till varje part. Två typer av hemliga delningsscheman används ofta; Shamirs hemliga delning och additiv hemlig delning. I båda fallen är delarna slumpmässiga element i ett ändligt fält som ökar hemligheten i fältet; intuitivt uppnås säkerhet eftersom varje icke-kvalificerad uppsättning aktier ser slumpmässigt ut.

Hemliga delningsscheman kan tolerera en motståndare som kontrollerar upp till t partier av n totala partier, där t varierar beroende på schemat, motståndaren kan vara passiv eller aktiv, och olika antaganden görs om motståndarens kraft. Shamirs hemliga delningsschema är säkert mot en passiv motståndare när och en aktiv motståndare när de uppnår informationsteoretisk säkerhet, vilket innebär att även om motståndaren har obegränsad beräkningskraft kan de inte lära sig någon information om hemligheten bakom en andel. BGW-protokollet, som definierar hur man beräknar tillägg och multiplikation på hemliga aktier, används ofta för att beräkna funktioner med Shamirs hemliga aktier. Additiva hemliga delningsscheman kan tolerera att motståndaren kontrollerar alla utom en part, det vill säga samtidigt som de bibehåller säkerheten mot en passiv och aktiv motståndare med obegränsad beräkningskraft. Vissa protokoll kräver en installationsfas, som bara kan vara säker mot en beräkningsmässigt begränsad motståndare. ${\ displaystyle t <{\ frac {n} {2}}}$ ${\ displaystyle t <{\ frac {n} {3}}}$ ${\ displaystyle t <n}$

Ett antal system har implementerat olika former av MPC med hemliga delningsscheman. Den mest populära är SPDZ, som implementerar MPC med additiva hemliga aktier och är säker mot aktiva motståndare.

Andra protokoll

Under 2014 har en "modell av rättvisa i säker beräkning där en kontradiktorisk part som avbryter mottagande av produktionen tvingas betala en ömsesidigt fördefinierad penningavgift" beskrivits för Bitcoin- nätverket eller för rättvis lotteri.

Praktiska MPC-system

Många framsteg har gjorts med 2PC- och MPC-system de senaste åren.

Yao-baserade protokoll

En av huvudfrågorna när man arbetar med Yao-baserade protokoll är att funktionen som ska utvärderas säkert (vilket kan vara ett godtyckligt program) måste representeras som en krets, vanligtvis bestående av XOR- och AND-grindar. Eftersom de flesta verkliga program innehåller slingor och komplexa datastrukturer är detta en mycket icke-trivial uppgift. Fairplay-systemet var det första verktyget för att hantera detta problem. Fairplay består av två huvudkomponenter. Den första av dessa är en kompilator som gör det möjligt för användare att skriva program på ett enkelt språk på hög nivå och mata ut dessa program i en boolsk kretsrepresentation. Den andra komponenten kan sedan klumpa ihop kretsen och utföra ett protokoll för att säkert utvärdera den förvrängda kretsen. Förutom beräkning av två parter baserat på Yaos protokoll kan Fairplay också utföra protokoll med flera partier. Detta görs med hjälp av BMR-protokollet, som utvidgar Yaos passivt säkra protokoll till det aktiva fallet.

Under åren efter införandet av Fairplay har många förbättringar av Yaos grundprotokoll skapats, i form av både effektivitetsförbättringar och tekniker för aktiv säkerhet. Dessa inkluderar tekniker som gratis XOR-metoden, som möjliggör mycket enklare utvärdering av XOR-grindar och förvrängd radreduktion, vilket minskar storleken på förvrängda bord med två ingångar med 25%.

Det tillvägagångssätt som hittills verkar vara det mest givande när det gäller att uppnå aktiv säkerhet kommer från en kombination av grumlingstekniken och "klipp ut och välj" -paradigmet. Denna kombination verkar göra effektivare konstruktioner. För att undvika de ovannämnda problemen med avseende på oärligt beteende skickas många garblings av samma krets från konstruktören till utvärderaren. Sedan öppnas ungefär hälften av dem (beroende på det specifika protokollet) för att kontrollera konsistens, och i så fall är en stor majoritet av de oöppnade korrekta med hög sannolikhet. Produktionen är majoritetsröstningen av alla utvärderingar. Observera att här behövs majoritetsutdata. Om det är oenighet om utgångarna vet mottagaren att avsändaren fuskar, men han kan inte klaga eftersom det annars skulle läcka information om hans ingång.

Detta tillvägagångssätt för aktiv säkerhet initierades av Lindell och Pinkas. Denna teknik implementerades av Pinkas et al. 2009 gav detta den första aktivt säkra tvåpartsutvärderingen av Advanced Encryption Standard (AES) krets, betraktad som en mycket komplex (bestående av cirka 30 000 AND- och XOR-grindar), icke-trivial funktion (även med vissa potentiella applikationer) , tar cirka 20 minuter att beräkna och kräver 160 kretsar för att få en fusk sannolikhet. ${\ displaystyle 2 ^ {- 40}}$

Eftersom många kretsar utvärderas måste parterna (inklusive mottagaren) förbinda sig till sina ingångar för att säkerställa att samma värden används i alla iterationer. Experimenten från Pinkas et al. rapporterade visar att flaskhalsen i protokollet ligger i konsistenskontrollerna. De var tvungna att skicka över 6553 600 åtaganden till olika värden för att utvärdera AES-kretsen. I de senaste resultaten förbättrades effektiviteten för aktivt säkra Yao-baserade implementeringar ytterligare, vilket endast krävde 40 kretsar och mycket mindre åtaganden för att uppnå fusk sannolikhet. Förbättringarna kommer från nya metoder för att utföra klipp-och-välja på de sända kretsarna. ${\ displaystyle 2 ^ {- 40}}$

På senare tid har det fokuserats på mycket parallella implementeringar baserade på förvrängda kretsar, utformade för att köras på processorer med många kärnor. Kreuter et al. beskriva en implementering som körs på 512 kärnor i en kraftfull klusterdator. Med hjälp av dessa resurser kunde de utvärdera 4095-bitars redigeringsavståndsfunktionen , vars krets består av nästan 6 miljarder grindar. För att åstadkomma detta utvecklade de en anpassad, bättre optimerad kretskompilator än Fairplay och flera nya optimeringar såsom pipelining, där överföring av den förvrängda kretsen över nätverket börjar medan resten av kretsen fortfarande genereras. Tiden för att beräkna AES reducerades till 1,4 sekunder per block i det aktiva fallet med hjälp av en 512-nodsklustermaskin och 115 sekunder med en nod. Shelat och Shen förbättrar detta, med hjälp av råvaruhårdvara, till 0,52 sekunder per block. Samma papper rapporterar om en genomströmning på 21 block per sekund, men med en latens på 48 sekunder per block.

Under tiden har en annan grupp forskare undersökt användning av GPU: er av konsumentkvalitet för att uppnå liknande nivåer av parallellitet. De använder OT-tillägg och några andra nya tekniker för att utforma sitt GPU-specifika protokoll. Detta tillvägagångssätt verkar uppnå jämförbar effektivitet med implementeringen av klusterberäkning med ett liknande antal kärnor. Författarna rapporterar dock bara om en implementering av AES-kretsen, som har cirka 50 000 grindar. Å andra sidan är den hårdvara som krävs här mycket mer tillgänglig, eftersom liknande enheter redan finns i många människors stationära datorer eller spelkonsoler. Författarna får en tidpunkt på 2,7 sekunder per AES-block på ett vanligt skrivbord med en standard GPU. Om de tillåter säkerhet att minska till något som liknar hemlig säkerhet, får de en körtid på 0,30 sekunder per AES-block. I det passiva säkerhetsfallet finns rapporter om bearbetning av kretsar med 250 miljoner grindar och med en hastighet av 75 miljoner grindar per sekund.

Se även

Referenser

externa länkar

En enkel beskrivning av miljonärproblemet
Helger Lipmaas länkar om multiparty-beräkning
Nick Szabo, "The God Protocols" på Wayback Machine (arkiverad 30 december 2006)
EMP-toolkit - Effektivt beräkningsverktyg för flera parter. Inkluderar implementering av grundläggande MPC-primitiv samt protokoll med halvärlig säkerhet och skadlig säkerhet.
Säker distribuerad CSP (DisCSP) -lösare - en webbapplikation med en applet-tolk för att designa och köra din egen fullfjädrade säkra multiparty-beräkning (baserat på SMC-deklarationsspråket). Använder säker aritmetisk kretsutvärdering och mix-nät.
VMCrypt Ett Java-bibliotek för skalbar säker beräkning. Av Lior Malka.
Fairplay-projektet - Innehåller ett mjukvarupaket för säker tvåpartsberäkning, där funktionen definieras med hjälp av ett högnivåfunktionsbeskrivningsspråk och utvärderas med Yaos protokoll för säker utvärdering av booleska kretsar.
SIMAP-projektet ; Secure Information Management and Processing (SIMAP) är ett projekt sponsrat av Danmarks nationella forskningsbyrå som syftar till att implementera Secure Multiparty Computation.
Secure Multiparty Computation Language - projekt för utveckling av ett "domänspecifikt programmeringsspråk för säker multiparty-beräkning" och tillhörande kryptografisk körtid.
VIFF: Virtual Ideal Functionality Framework - Framework för asynkrona flerpartsberäkningar (kod tillgänglig under LGPL ). Erbjuder aritmetik med hemliga delade värden inklusive säker jämförelse.
MPyC : Secure Multiparty Computation in Python (and Jupyter notebooks ) - Öppen källkodspaket för MPC med en anpassad typ av Python coroutines, som stöder avancerade applikationer som ID3-beslutsträd, linjär programmering, CNN / MLP-neurala nätverk, AES, enkelriktad hashkedjor och många fler. Lanserades i maj 2018.
SCALE-MAMBA MPC: Secure Computation Algorithms from LEuven - Framework for diverse MPC protocols, including the SPDZ family (code available under the BSD ). Erbjuder aritmetik med hemliga delade värden inklusive säker jämförelse och stöd för fixpunkt och flytpunkt.
Sharemind: analysera konfidentiella data utan att äventyra sekretess - En distribuerad virtuell maskin med möjlighet att köra sekretessbevarande operationer. Har ett integritetsbevarande programmeringsspråk för verktyg för datautvinning. Inkluderar utvecklarverktyg.
MPCLib: Multi-Party Computation Library - Ett bibliotek skrivet i C # och C ++ som implementerar flera byggstenar som krävs för att implementera säkra beräkningsprotokoll för flera parter. MPCLib har en diskret händelsessimuleringsmotor som kan användas för att simulera MPC-protokoll i virtuella nätverk.
Virtuella parter i SMC Ett protokoll för virtuella parter i SMC (Secure Multi Party-beräkning)
MPC Java-baserad implementering En Java-baserad implementering av MPC-protokollet baserat på Michael.B, Shafi.G och Avi.W: s sats ("Fullständighetsteoremer för icke-kryptografisk feltolerant distribuerad beräkning") med Welch-Berlekamp felkorrigeringskod algoritm till BCH-koder. Stöder flera spelare och identifiering av "fuskare" med bysantinskt protokoll. Av Erez Alon, Doron Friedland & Yael Smith.
SEPIA Ett java-bibliotek för SMC med hemlig delning. Grundläggande operationer är optimerade för ett stort antal parallella anrop (kod tillgänglig under LGPL ).
Introduktion till SMC på GitHub
Myst Project - JavaCard-applet som implementerar Secure Multiparty Key Generation, Signing and Decryption.
Grundläggande bibliografi Secure Multiparty Computation

Languages

In other projects