Bezpečné výpočty více stran - Secure multi-party computation

Bezpečné výpočty více stran (také známý jako bezpečný výpočet, výpočet více stran (MPC)nebo výpočet zachování soukromí) je podpole z kryptografie s cílem vytvořit metody pro strany, které budou společně počítat funkci nad jejich vstupy, přičemž tyto vstupy budou soukromé. Na rozdíl od tradičních kryptografických úkolů, kde kryptografie zajišťuje bezpečnost a integritu komunikace nebo úložiště a protivník je mimo systém účastníků (odposlech na odesílatele a příjemce), kryptografie v tomto modelu chrání účastníky Soukromí od sebe navzájem.

Základ pro bezpečný výpočet více stran začal koncem sedmdesátých let prací na mentálním pokeru, kryptografické práci, která simuluje hraní her / výpočetní úkoly na velké vzdálenosti, aniž by vyžadovala důvěryhodnou třetí stranu. Všimněte si, že kryptografie byla tradičně o skrytí obsahu, zatímco tento nový typ výpočtu a protokolu je o skrytí dílčích informací o datech při výpočtu s daty z mnoha zdrojů a správném vytváření výstupů.

Dějiny

Konce speciálních protokolů pro konkrétní úkoly začaly koncem sedmdesátých let.^[1] Později byl bezpečný výpočet formálně zaveden jako bezpečný výpočet pro dvě strany (2PC) v roce 1982 (pro tzv Problém milionářů, specifický problém, kterým je booleovský predikát) a obecně (pro jakýkoli proveditelný výpočet) v roce 1986 Andrew Yao.^[2][3] Tato oblast se také označuje jako Secure Function Evaluation (SFE). Po případu dvou stran následovalo zobecnění na multi-party od Goldreicha, Micaliho a Wigdersona. Výpočet je založen na tajném sdílení všech vstupů a důkazech nulových znalostí pro potenciálně nebezpečný případ, kdy většina poctivých hráčů v případě škodlivého protivníka zajišťuje, že je zjištěno špatné chování a výpočet pokračuje s vyloučením nepoctivé osoby nebo vstup odhalen. Tato práce navrhla velmi základní obecné schéma, kterým by se měly řídit v podstatě všechny budoucí protokoly více stran pro zabezpečené výpočty.^[4] Na tuto práci navázal první robustní zabezpečený protokol, který laskavě toleruje vadné chování, aniž by odhalil něčí výstup prostřednictvím díla, které pro tento účel vynalezlo často používaný nápad „sdílení akcií“^[5] a protokol, který umožňuje jedné ze stran bezpodmínečně skrýt svůj vstup.^[6] Výše uvedené výsledky jsou v modelu, kde je protivník omezen na polynomiální výpočty času a pozoruje veškerou komunikaci, a proto se model nazývá „výpočetní model“. Dále protokol z lhostejný přenos bylo prokázáno, že je pro tyto úkoly kompletní.^[7] Výše uvedené výsledky prokázaly, že ve výše uvedených variantách je možné dosáhnout bezpečného výpočtu, když je většina uživatelů upřímná.

Další otázkou, kterou je třeba vyřešit, byl případ zabezpečených komunikačních kanálů, kde protivník nemá přístup z bodu do bodu; v tomto případě se ukázalo, že řešení lze dosáhnout až u 1/3 stran, které se chovají špatně a škodlivě, a řešení nepoužívají žádné kryptografické nástroje (protože je k dispozici zabezpečená komunikace).^[8][9] Přidání vysílacího kanálu umožňuje systému tolerovat až 1/2 nevhodné menšiny,^[10] zatímco omezení připojení na komunikačním grafu byla zkoumána v knize Perfectly Secure Message Transmission.^[11]

V průběhu let se pojem univerzálních vícestranových protokolů stal úrodnou oblastí pro zkoumání základních a obecných vlastností problémů protokolu, jako například univerzální skladatelnost nebo mobilní protivník jako v proaktivní sdílení tajemství.^[12]

Od konce dvacátých let 20. století a určitě od roku 2010 a dále se doména protokolů pro všeobecné účely přesunula, aby se zabývala zlepšováním účinnosti protokolů s ohledem na praktické aplikace. Byly navrženy stále účinnější protokoly pro MPC a MPC lze nyní považovat za praktické řešení různých problémů v reálném životě (zejména těch, které vyžadují pouze lineární sdílení tajemství a hlavně lokální operace s akciemi bez přílišných interakcí mezi stranami ), jako je distribuované hlasování, soukromé dražení a aukce, sdílení funkcí podpisu nebo dešifrování a vyhledávání soukromých informací.^[13] První rozsáhlá a praktická aplikace výpočtu s více účastníky (prokázaná na skutečném aukčním problému) se uskutečnila v Dánsku v lednu 2008.^[14] Je zřejmé, že jsou zapotřebí jak teoretické pojmy, tak šetření a aplikované konstrukce (např. Podmínky pro přesun MPC do části každodenního podnikání byly obhajovány a prezentovány v^[15]).

Definice a přehled

V MPC je daný počet účastníků, str₁, str₂, ..., s_N, každý má soukromá data, respektive d₁, d₂, ..., d_N. Účastníci chtějí vypočítat hodnotu veřejné funkce na těchto soukromých datech: F (d₁, d₂, ..., d_N) při zachování vlastních vstupů v tajnosti.

Předpokládejme například, že máme tři strany Alice, Bob a Charlie, s příslušnými vstupy x, yaz označujícími jejich platy. Chtějí zjistit nejvyšší ze tří platů, aniž by si navzájem odhalili, kolik každý z nich vydělává. Matematicky to pro ně znamená výpočet:

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

Pokud by existovala nějaká důvěryhodná vnější strana (řekněme, měli společného přítele Tonyho, o kterém věděli, že by mohl držet tajemství), mohli by každý říct Tonymu svůj plat, mohl vypočítat maximum a říct toto číslo všem. Cílem MPC je navrhnout protokol, kde se Alice, Bob a Charlie mohou stále učit výměnou zpráv jen mezi sebou F (x, y, z) aniž by prozradil, kdo co vyrábí, a aniž by se musel spoléhat na Tonyho. Neměli by se naučit víc tím, že se zapojí do svého protokolu, než by se naučili interakcí s neporušitelným, naprosto důvěryhodným Tonym.

Zejména se strany mohou naučit jen to, co se mohou naučit z výstupu a vlastního vstupu. Takže ve výše uvedeném příkladu, pokud je výstup z, pak se Charlie naučí, že jeho z je maximální hodnota, zatímco Alice a Bob se učí (pokud jsou x, y a z odlišné), že jejich vstup se nerovná maximu a že maximální držená se rovná z. Základní scénář lze snadno zobecnit tak, že strany mají několik vstupů a výstupů a funkce poskytuje různým stranám různé hodnoty.

Neformálně řečeno, nejzákladnější vlastnosti, které chce zajistit výpočetní protokol více stran, jsou:

• Soukromí vstupu: Ze zpráv odeslaných během provádění protokolu nelze odvodit žádné informace o soukromých údajích uchovávaných stranami. Jedinou informací, kterou lze odvodit o soukromých datech, je cokoli, co lze odvodit ze samotného zobrazení funkce.
• Správnost: Jakákoli správná podmnožina sporných stran, které jsou ochotné sdílet informace nebo se odchýlit od pokynů během provádění protokolu, by neměla být schopna přinutit čestné strany, aby vydaly nesprávný výsledek. Tento cíl správnosti má dvě příchutě: buď poctivé strany zaručeně vypočítají správný výstup („robustní“ protokol), nebo se přeruší, pokud naleznou chybu (protokol MPC „s přerušení“).

Existuje široká škála praktických aplikací, které se liší od jednoduchých úkolů, jako je házení mincí, po složitější, jako jsou elektronické aukce (např. Výpočet ceny za zúčtování trhu), elektronické hlasování nebo těžba dat chránících soukromí. Klasickým příkladem je problém milionářů: dva milionáři chtějí vědět, kdo je bohatší, a to takovým způsobem, aby se ani jeden z nich nedozvěděl čistou hodnotu toho druhého. Řešením této situace je v podstatě bezpečné vyhodnocení srovnávací funkce.

Definice zabezpečení

Aby byl výpočetní protokol více účastníků účinný, musí být zabezpečený. V moderní kryptografii souvisí zabezpečení protokolu s bezpečnostním důkazem. Důkaz zabezpečení je matematický důkaz, kdy je bezpečnost protokolu snížena na bezpečnost jeho základních primitiv. Přesto není vždy možné formalizovat kryptografický protokol bezpečnostní ověření založené na znalostech strany a správnosti protokolu. U protokolů MPC je prostředí, ve kterém protokol funguje, spojeno s paradigmatem Real World / Ideal World.^[16] O účastnících nelze říci, že se nic nenaučí, protože se potřebují naučit výstup operace a výstup závisí na vstupech. Správnost výstupu navíc není zaručena, protože správnost výstupu závisí na vstupech stran a je třeba předpokládat, že vstupy jsou poškozené.

Paradigma Real World / Ideal World uvádí dva světy: (i) V modelu ideálního světa existuje neporušitelná důvěryhodná strana, které každý účastník protokolu zasílá své vstupy. Tato důvěryhodná strana vypočítá funkci sama a odešle zpět příslušný výstup každé straně. ii) Naproti tomu v modelu reálného světa neexistuje žádná důvěryhodná strana a strany si mohou pouze vyměňovat zprávy. Protokol je považován za bezpečný, pokud se člověk nemůže dozvědět více o soukromých vstupech každé strany v reálném světě, než by se mohl naučit v ideálním světě. V ideálním světě si strany nevyměňují žádné zprávy, takže vyměněné zprávy v reálném světě nemohou odhalit žádné tajné informace.

Paradigma Real World / Ideal World poskytuje jednoduchou abstrakci složitosti MPC, která umožňuje konstrukci aplikace pod záminkou, že protokol MPC v jeho jádru je ve skutečnosti ideálním provedením. Pokud je aplikace v ideálním případě zabezpečená, pak je také zabezpečená, když je místo toho spuštěn skutečný protokol.

Bezpečnostní požadavky na protokol MPC jsou přísné. V roce 1987 se nicméně ukázalo, že lze bezpečně vypočítat jakoukoli funkci se zabezpečením pro škodlivé protivníky^[4] a další počáteční práce zmíněné výše. Navzdory těmto publikacím nebyl MPC navržen tak, aby byl dostatečně efektivní, aby mohl být v té době používán v praxi. Bezpodmínečně nebo informační teoreticky zabezpečený MPC úzce souvisí a staví na problému tajné sdílení a konkrétněji ověřitelné sdílení tajemství (VSS), který mnoho zabezpečených protokolů MPC používá proti aktivním protivníkům.

Na rozdíl od tradičních kryptografických aplikací, jako je šifrování nebo podpis, je třeba předpokládat, že protivník v protokolu MPC je jedním z hráčů zapojených do systému (nebo ovládajících interní strany). Tato poškozená strana nebo strany se mohou domluvit za účelem porušení bezpečnosti protokolu. Nechat ${ displaystyle n}$ být počet stran v protokolu a ${ displaystyle t}$ počet stran, které mohou být sporné. Protokoly a řešení pro případ ${ displaystyle t$ (tj. když se předpokládá čestná většina) se liší od těch, u nichž takový předpoklad neexistuje. Tento druhý případ zahrnuje důležitý případ výpočtu dvou stran, kdy může dojít k poškození jednoho z účastníků, a obecný případ, kdy je poškozen neomezený počet účastníků a domlouvá se, že zaútočí na čestné účastníky.

Protivníky, kterým čelí různé protokoly, lze kategorizovat podle toho, jak ochotně se odchylují od protokolu. V zásadě existují dva typy protivníků, z nichž každý vede k různým formám zabezpečení (a každý zapadá do jiného scénáře reálného světa):

• Poločestné (pasivní) zabezpečení: V tomto případě se předpokládá, že poškozené strany pouze spolupracují na shromažďování informací mimo protokol, ale neodchylují se od specifikace protokolu. Jedná se o naivní model protivníka, který přináší slabé zabezpečení v reálných situacích. Protokoly, které dosahují této úrovně zabezpečení, však zabraňují neúmyslnému úniku informací mezi (jinak spolupracujícími) stranami, a jsou tedy užitečné, pokud je to jediný problém. Protokoly v částečně upřímném modelu jsou navíc docela efektivní a jsou často důležitým prvním krokem k dosažení vyšší úrovně zabezpečení.
• Škodlivé (aktivní) zabezpečení: V tomto případě se může protivník při pokusu o podvádění libovolně odchýlit od provedení protokolu. Protokoly, které v tomto modelu zajišťují zabezpečení, poskytují velmi vysokou záruku zabezpečení. V případě většiny zneužití stran: Jedinou věcí, kterou může protivník udělat v případě nečestné většiny, je přimět poctivé strany k „potratu“ po zjištění podvádění. Pokud poctivé strany skutečně získají výstup, je zaručeno, že jsou správné. Jejich soukromí je vždy zachováno.

Zabezpečení proti aktivním protivníkům obvykle vede ke snížení účinnosti, které vede ke skrytému zabezpečení,^[17] uvolněná forma aktivní bezpečnosti. Skryté zabezpečení zachycuje realističtější situace, kdy jsou aktivní protivníci ochotni podvádět, ale pouze pokud nejsou chyceni. Mohlo by to například poškodit jejich pověst, což by zabránilo budoucí spolupráci s jinými poctivými stranami. Skrytě zabezpečené protokoly tedy poskytují mechanismy, které zajistí, že pokud některá ze stran nedodrží pokyny, bude si toho všimnout s vysokou pravděpodobností, řekněme 75% nebo 90%. Skrytí protivníci jsou svým způsobem aktivní, kteří jsou nuceni pasivně jednat kvůli externím ne kryptografickým (např. Obchodním) zájmům. Tento mechanismus nastavuje most mezi oběma modely v naději, že najde protokoly, které jsou v praxi dostatečně účinné a bezpečné.

Jako mnozí kryptografické protokoly, zabezpečení protokolu MPC se může spolehnout na různé předpoklady:

• Může to být výpočetní (tj. Založené na nějakém matematickém problému, jako je factoring) nebo bezpodmínečné, a to spoléhat se na fyzickou nedostupnost zpráv na kanálech (obvykle s určitou pravděpodobností chyby, kterou lze libovolně snížit).
• Model může předpokládat, že účastníci používají a synchronizovaná síť, kde zpráva zaslaná „zaškrtnutím“ vždy dorazí na další „zaškrtnutí“, nebo že existuje bezpečný a spolehlivý vysílací kanál, nebo že existuje bezpečný komunikační kanál mezi každou dvojicí účastníků, kde protivník nemůže číst, upravovat nebo generovat zprávy v kanálu atd.

Sada poctivých stran, které mohou vykonat výpočetní úkol, souvisí s konceptem přístupová struktura. Nepříznivé struktury může být statický, kdy si protivník vybere své oběti před zahájením výpočtu několika stranami, nebo dynamický, kde si vybere své oběti v průběhu provádění výpočtu několika stranami, což ztěžuje obranu. Protivnou strukturu lze definovat jako prahovou strukturu nebo jako složitější strukturu. Ve struktuře prahových hodnot může protivník poškodit nebo přečíst paměť řady účastníků až do určité prahové hodnoty. Mezitím může ve složité struktuře ovlivnit určité předdefinované podmnožiny účastníků a modelovat různé možné koluze.

Protokoly

Mezi protokoly navrhovanými pro výpočet dvou stran (2PC) a výpočet více stran (MPC) existují velké rozdíly. Také pro důležité speciální protokoly musí být často navržen specializovaný protokol, který se liší od obecných protokolů (hlasování, aukce, platby atd.)

Výpočet dvou stran

Nastavení dvou stran je obzvláště zajímavé, a to nejen z pohledu aplikací, ale také proto, že v prostředí dvou stran lze použít speciální techniky, které se v případě více stran nepoužijí. Ve skutečnosti byl zabezpečený výpočet více účastníků (ve skutečnosti omezený případ vyhodnocení zabezpečené funkce, kde je hodnocena pouze jedna funkce) poprvé představen v nastavení dvou účastníků. Původní dílo je často citováno jako pocházející z jednoho ze dvou článků Yao;^[18] ačkoli články ve skutečnosti neobsahují to, co je nyní známé jako Yaoův zkomolený obvodový protokol.

Základní protokol Yao je zabezpečen proti částečně čestným protivníkům a je extrémně efektivní z hlediska počtu kol, který je konstantní a nezávislý na hodnocené cílové funkci. Funkce je považována za booleovský obvod se vstupy v binárním formátu pevné délky. Booleovský obvod je sbírka bran spojených se třemi různými typy vodičů: vodiče vstupního obvodu, vodiče výstupního obvodu a mezilehlé vodiče. Každá brána přijímá dva vstupní vodiče a má jeden výstupní vodič, který může být rozvětvený (tj. Může být veden do více bran na další úrovni). Jednoduché vyhodnocení obvodu se provádí vyhodnocením každé brány postupně; za předpokladu, že brány byly topologicky uspořádány. Brána je reprezentována jako pravdivostní tabulka tak, že každé možné dvojici bitů (těch, které vycházejí z brány vstupních vodičů) tabulka přiřadí jedinečný výstupní bit; což je hodnota výstupního drátu brány. Výsledkem vyhodnocení jsou bity získané ve vodičích výstupu obvodu.

Yao vysvětlil, jak zkomolit obvod (skrýt jeho strukturu), aby se dvě strany, odesílatel a příjemce, mohly naučit výstup obvodu a nic jiného. Na vysoké úrovni odesílatel připraví zkomolený obvod a odešle jej přijímači, který zapomněle vyhodnotí obvod a učí se kódování odpovídající jeho i odesílatelovu výstupu. Poté pouze odešle zpět kódování odesílatele a umožní odesílateli vypočítat jeho část výstupu. Odesílatel odesílá mapování z výstupních kódování přijímačů na bity do přijímače, což umožňuje přijímači získat jejich výstup.

Podrobněji je zkomolený obvod vypočítán následujícím způsobem. Hlavní ingrediencí je schéma dvojitého symetrického šifrování. Vzhledem k bráně obvodu je každá možná hodnota jeho vstupních vodičů (buď 0 nebo 1) kódována náhodným číslem (štítkem). Hodnoty vyplývající z vyhodnocení brány u každé ze čtyř možných dvojic vstupních bitů jsou také nahrazeny náhodnými štítky. Zkomolená pravdivostní tabulka brány se skládá ze šifrování každého výstupního štítku pomocí jeho vstupních štítků jako klíčů. Pozice těchto čtyř šifrování v tabulce pravdivosti je náhodná, takže nedochází k úniku informací na bráně.

Pro správné vyhodnocení každé zkomolené brány má schéma šifrování následující dvě vlastnosti. Nejprve jsou rozsahy funkce šifrování pod libovolnými dvěma odlišnými klíči disjunktní (s naprostou pravděpodobností). Druhá vlastnost říká, že lze efektivně zkontrolovat, zda byl daný šifrovací text zašifrován pod daným klíčem. S těmito dvěma vlastnostmi může přijímač po získání štítků pro všechny vodiče vstupu do obvodu vyhodnotit každou bránu tak, že nejprve zjistí, který ze čtyř šifrovacích textů byl zašifrován pomocí jeho štítkových klíčů, a poté dešifruje, aby získal štítek výstupního vodiče . To se děje bez povšimnutí, protože všechny přijímače, které se během vyhodnocení naučí, jsou kódování bitů.

Vstupní bity odesílatele (tj. Tvůrce obvodů) lze pouze poslat jako kódování hodnotiteli; vzhledem k tomu, že kódování přijímače (tj. vyhodnocovače obvodu) odpovídající jeho vstupním bitům jsou získávána pomocí 1-z-2 Oblivious Transfer (OT) protokol. Protokol OT 1 ze 2 umožňuje odesílateli, který má dvě hodnoty C1 a C2, odeslat tu, kterou požaduje příjemce (hodnota ba v {1,2}), a to tak, že odesílatel nevím, jaká hodnota byla přenesena, a přijímač se naučí pouze požadovanou hodnotu.

Pokud uvažujete o škodlivých protivnících, je třeba poskytnout další mechanismy k zajištění správného chování obou stran. Konstrukcí lze snadno ukázat zabezpečení odesílatele, protože přijímač může pouze vyhodnotit poškozený obvod, který by nedosáhl výstupních vodičů obvodu, pokud by se odchýlil od pokynů. Na straně odesílatele je situace velmi odlišná. Například může poslat nesprávný zkomolený obvod, který počítá funkci odhalující vstup přijímače. To by znamenalo, že soukromí již neplatí, ale protože je obvod zkomolený, přijímač by to nebyl schopen detekovat.

Protokoly více stran

Většina protokolů MPC, na rozdíl od protokolů 2PC, zejména při bezpodmínečném nastavení soukromých kanálů, využívá sdílení tajných informací. V metodách založených na tajném sdílení nehrají strany zvláštní role (jako v Yao, tvůrce a hodnotitele). Místo toho jsou data spojená s každým kabelem sdílena mezi stranami a protokol je poté použit k vyhodnocení každé brány. Funkce je nyní definována jako „obvod“ přes konečné pole, na rozdíl od binárních obvodů použitých pro Yao. Takový obvod se v literatuře nazývá aritmetický obvod a skládá se z „bran“ sčítání a násobení, kde jsou hodnoty operované definovány přes konečné pole.

Tajné sdílení umožňuje jednomu distribuovat tajemství mezi několik stran distribucí sdílených položek každé straně. Běžně se používají dva typy schémat sdílení tajemství; Shamirovo tajné sdílení a aditivní sdílení tajemství. V obou případech jsou sdílené položky náhodné prvky konečného pole, které doplňují tajemství v poli; intuitivně je zabezpečení dosaženo, protože jakákoli nekvalifikovaná sada akcií vypadá náhodně distribuovaná.

Schémata sdílení tajemství mohou tolerovat protivníka ovládajícího až t strany mimo n celkem stran, kde t liší se podle schématu, protivník může být pasivní nebo aktivní a na moc protivníka se staví různé předpoklady. Schéma sdílení Shamirova tajemství je bezpečné proti pasivnímu protivníkovi, když ${ displaystyle t <{ frac {n} {2}}}$ a aktivní protivník, když ${ displaystyle t <{ frac {n} {3}}}$ při dosažení informační teoretické bezpečnosti, což znamená, že i když má protivník neomezenou výpočetní sílu, nemůže se dozvědět žádné informace o tajemství, které je základem sdílené položky. Protokol BGW,^[19] který definuje, jak vypočítat sčítání a násobení na tajných sdílených složkách, se často používá k výpočtu funkcí s tajnými sdílenými položkami Shamir. Schémata sdílení aditivních tajemství mohou tolerovat protivníka ovládajícího všechny kromě jedné strany ${ displaystyle t$, při zachování bezpečnosti proti pasivnímu a aktivnímu protivníkovi s neomezenou výpočetní silou. Některé protokoly vyžadují fázi nastavení, která může být zabezpečena pouze proti výpočetně ohraničenému protivníkovi.

Řada systémů implementovala různé formy MPC se schématy tajného sdílení. Nejoblíbenější je SPDZ,^[20] který implementuje MPC s aditivními tajnými sdílenými položkami a je zabezpečen proti aktivním protivníkům.

Další protokoly

V roce 2014 byl popsán „model spravedlnosti v bezpečném výpočtu, při kterém je sporná strana, která přeruší přijímání výstupu, nucena zaplatit vzájemně předem stanovenou peněžní pokutu“ pro Bitcoin síť nebo pro spravedlivou loterii.^[21]

Praktické systémy MPC

V posledních letech došlo v systémech 2PC a MPC k mnoha pokrokům.

Protokoly založené na Yao

Jedním z hlavních problémů při práci s protokoly založenými na Yao je, že funkce, která má být bezpečně vyhodnocena (což může být libovolný program), musí být reprezentována jako obvod, obvykle sestávající z bran XOR a AND. Jelikož většina programů v reálném světě obsahuje smyčky a složité datové struktury, jedná se o velmi netriviální úkol. Systém Fairplay^[22] byl prvním nástrojem navrženým k řešení tohoto problému. Fairplay se skládá ze dvou hlavních komponent. Prvním z nich je kompilátor umožňující uživatelům psát programy v jednoduchém jazyce vysoké úrovně a výstup těchto programů v logické reprezentaci obvodu. Druhá složka pak může obvod zkomolit a provést protokol pro bezpečné vyhodnocení poškozeného obvodu. Kromě výpočtů dvou stran založených na protokolu Yao může Fairplay provádět i protokoly více stran. To se provádí pomocí protokolu BMR,^[22] což rozšiřuje pasivně zabezpečený protokol Yao na aktivní případ.

V letech následujících po zavedení Fairplay bylo vytvořeno mnoho vylepšení základního protokolu Yao, a to v podobě vylepšení efektivity i technik pro aktivní zabezpečení. Patří mezi ně techniky, jako je bezplatná metoda XOR, která umožňuje mnohem jednodušší vyhodnocení bran XOR, a zmenšení zkomolených řádků, čímž se zmenší velikost zkomolených stolů se dvěma vstupy o 25%.^[23]

Přístup, který se zatím jeví jako nejplodnější pro získání aktivní bezpečnosti, vychází z kombinace kloktání a paradigmatu „cut-and-choose“. Zdá se, že tato kombinace vykresluje efektivnější konstrukce. Aby se předešlo výše uvedeným problémům s ohledem na nečestné chování, je z konstruktoru k hodnotiteli odesláno mnoho útržků stejného obvodu. Poté se zhruba polovina z nich (v závislosti na konkrétním protokolu) otevře, aby se zkontrolovala konzistence, a pokud ano, naprostá většina neotevřených je s vysokou pravděpodobností správná. Výstupem je většinový hlas všech hodnocení. Zde je potřeba většinový výstup. Pokud dojde k neshodě na výstupech, přijímač ví, že odesílatel podvádí, ale nemůže si stěžovat, protože jinak by došlo k úniku informací o jeho vstupu.

Tento přístup k aktivní bezpečnosti zahájili Lindell a Pinkas.^[24] Tuto techniku ​​implementovali Pinkas et al. v roce 2009,^[23] To poskytlo první aktivně zabezpečené dvouúrovňové hodnocení obvodu Advanced Encryption Standard (AES), považovaného za vysoce komplexní (skládající se z přibližně 30 000 bran AND a XOR), netriviální funkce (také u některých potenciálních aplikací), 20 minut na výpočet a získání 160 obvodů k získání a ${ displaystyle 2 ^ {- 40}}$ pravděpodobnost podvádění.

Protože se vyhodnocuje mnoho obvodů, musí se strany (včetně přijímače) zavázat ke svým vstupům, aby zajistily, že ve všech iteracích budou použity stejné hodnoty. Pokusy Pinkas et al. hlášeno^[23] ukazují, že úzké místo protokolu spočívá v kontrolách konzistence. Aby mohli vyhodnotit obvod AES, museli poslat přes síť asi 6553 600 závazků na různé hodnoty. V posledních výsledcích^[25] efektivita aktivně zabezpečených implementací založených na Yao byla ještě dále vylepšena, k získání bylo zapotřebí pouze 40 obvodů a mnohem méně závazků ${ displaystyle 2 ^ {- 40}}$ pravděpodobnost podvádění. Vylepšení vycházejí z nových metodik pro provádění cut-and-choose na přenášených obvodech.

V poslední době se zaměřuje na vysoce paralelní implementace založené na poškozených obvodech, které jsou určeny pro provoz CPU s mnoha jádry. Kreuter a kol.^[26] popsat implementaci běžící na 512 jádrech výkonného clusterového počítače. Pomocí těchto prostředků mohli vyhodnotit 4095 bitů upravit vzdálenost funkce, jejíž obvod zahrnuje téměř 6 miliard bran. Aby toho dosáhli, vyvinuli vlastní, lépe optimalizovaný kompilátor obvodů než Fairplay a několik nových optimalizací, jako je pipelining, kdy začíná přenos zkomoleného obvodu v síti, zatímco zbytek obvodu se stále generuje. Čas pro výpočet AES byl snížen na 1,4 sekundy na blok v aktivním případě, za použití klastrového stroje s 512 uzly, a 115 sekund s použitím jednoho uzlu. Shelat a Shen^[27] vylepšit to pomocí komoditního hardwaru na 0,52 sekundy na blok. Stejný papír hlásí propustnost 21 bloků za sekundu, ale s latencí 48 sekund za blok.

Mezitím další skupina vědců zkoumala použití spotřebitelské kvality GPU dosáhnout podobných úrovní paralelismu.^[28] K návrhu svého protokolu specifického pro GPU využívají OT rozšíření a některé další nové techniky. Zdá se, že tento přístup dosahuje srovnatelné efektivity s implementací klastrových počítačů při použití podobného počtu jader. Autoři však referují pouze o implementaci obvodu AES, který má kolem 50 000 bran. Na druhou stranu zde požadovaný hardware je mnohem přístupnější, protože podobná zařízení již lze najít ve stolních počítačích nebo herních konzolách mnoha lidí. Autoři získají časování 2,7 sekundy na blok AES na standardní ploše se standardním GPU. Pokud dovolí snížení zabezpečení na něco podobného skrytému zabezpečení, získají dobu běhu 0,30 sekundy na blok AES. V případě pasivního zabezpečení existují zprávy o zpracování obvodů s 250 miliony bran a rychlostí 75 milionů bran za sekundu.^[29]

Viz také

• Digitální měna
• Homomorfní šifrování
• Mentální poker
• Vícestranný spravedlivý směnný protokol
• Nezapomenutelný převod
• Výpočtová geometrie chránící soukromí
• Problém Yaoových milionářů

Reference

externí odkazy

• A simple description of the Millionaire Problem
• Helger Lipmaa's links about multiparty computation
• Nick Szabo, "The God Protocols" na Wayback Machine (archived December 30, 2006)
• EMP-toolkit — Efficient Multi-Party computation Toolkit. Includes implementation of basic MPC primitives as well as protocols with semi-honest security and malicious security.
• Secure distributed CSP (DisCSP) solvers — a web-application with an applet-interpreter to design and run your own full-fledged secure multiparty computation (based on the SMC declarative language). Uses secure arithmetic circuit evaluation and mix-nets.
• VMCrypt A Java library for scalable secure computation. By Lior Malka.
• The Fairplay Project — Includes a software package for secure two-party computation, where the function is defined using a high-level function description language, and evaluated using Yao's protocol for secure evaluation of boolean circuits.
• The SIMAP project; Secure Information Management and Processing (SIMAP) is a project sponsored by the Danish National Research Agency aimed implementing Secure Multiparty Computation.
• Secure Multiparty Computation Language - project for development of a 'domain specific programming language for secure multiparty computation' and associated cryptographic runtime.
• VIFF: Virtual Ideal Functionality Framework — Framework for asynchronous multi-party computations (code available under the LGPL ). Offers arithmetic with secret shared values including secure comparison.
• MPyC: Secure Multiparty Computation in Krajta (a Notebooky Jupyter ) — Open-source package for MPC using a customized type of Python coroutines, supporting advanced applications such as ID3 decision trees, linear programming, CNN/MLP neural networks, AES, one-way hash chains, and many more. Launched in May 2018.
• SCALE-MAMBA MPC: Secure Computation Algorithms from LEuven — Framework for various MPC protocols, including the SPDZ family (code available under the BSD ). Offers arithmetic with secret shared values including secure comparison and support for fixed point and floating point arithmetic.
• Sharemind: analyze confidential data without compromising privacy — A distributed virtual machine with the capability to run privacy-preserving operations. Has a privacy-preserving programming language for data mining tools. Includes developer tools.
• MPCLib: Multi-Party Computation Library — A library written in C# and C++ that implements several building blocks required for implementing secure multi-party computation protocols. MPCLib has a discrete-event simulation engine that can be used for simulating MPC protocols in virtual networks.
• Virtual Parties in SMC A protocol for Virtual Parties in SMC (Secure Multi Party computation)
• MPC Java-based implementation A Java-based implementation of the MPC protocol based on Michael.B, Shafi.G and Avi.W's theorem ("Completeness theorems for non-cryptographic fault-tolerant distributed computation") with Welch-Berlekamp error correcting code algorithm to BCH codes. Supports multiple players and identification of "cheaters" with Byzantine protocol. By Erez Alon, Doron Friedland & Yael Smith.
• SÉPIE A java library for SMC using secret sharing. Basic operations are optimized for large numbers of parallel invocations (code available under the LGPL ).
• Introduction to SMC na GitHubu
• Myst Project - JavaCard Applet implementing Secure Multiparty Key Generation, Signing and Decryption.
• Essential bibliography Secure Multiparty Computation