Ověřitelné výpočty - Verifiable computing

Ověřitelné výpočty (nebo ověřený výpočet nebo ověřené výpočty) umožňuje a počítač na vyložit the výpočet některé funkce, jiné možná nedůvěryhodné klienty, při zachování ověřitelných výsledků. Ostatní klienti vyhodnotí funkci a vrátí výsledek s důkazem, že výpočet funkce byla provedena správně. Zavedení tohoto pojmu přišlo v důsledku stále častějšího jevu „outsourcing "výpočet nedůvěryhodným uživatelům v projektech jako SETI @ home a také na rostoucí touhu slabých klientů outsourcovat výpočetní úkoly výkonnější výpočetní službou jako v cloud computing. Koncept se datuje do práce od Babai et al.,[1] a byl studován pod různými pojmy, včetně „kontroly výpočtů“ (Babai et al.), „delegování výpočtů“,[2] "ověřený výpočet",[3] a ověřitelné výpočty. Termín ověřitelné výpočty sám byl formován Rosario Gennaro, Craig Gentry a Bryan Parno,[4] a odráží Micaliho „certifikovaný výpočet“.[3]

Motivace a přehled

Rostoucí touha outsourcovat výpočetní úlohy z relativně slabého výpočetního zařízení (klienta) na výkonnější výpočetní služby (pracovník) a problém nepoctivých pracovníků, kteří upravují software svého klienta tak, aby poskytovali věrohodné výsledky bez provedení skutečné práce[5] motivovalo formalizaci pojmu ověřitelné výpočty.[4]

Ověřitelné výpočty se netýkají pouze získání výsledku outsourcované funkce na vstup klienta a důkaz jeho správnosti, ale také s tím, že klient je schopen ověřit důkaz s výrazně menším výpočetním úsilím, než je výpočet funkce od nuly.

Značná pozornost byla věnována ověřování výpočtu funkcí prováděných nedůvěryhodnými pracovníky včetně použití zabezpečit koprocesory,[6][7] Důvěryhodné moduly platformy (TPM),[8] interaktivní důkazy,[9][10] pravděpodobnostně ověřitelné důkazy,[11][12] efektivní argumenty,[13][14] a Micaliho CS důkazy.[15] Tato ověření jsou buď interaktivní, která vyžadují, aby klient interagoval s pracovníkem, aby ověřil důkaz správnosti,[13][14] nebo jsou neinteraktivní protokoly, které lze prokázat v náhodný věštec Modelka.[15]

Ověření replikací

Největší ověřený výpočet (SETI @ home ) používá ověření replikací.

The SETI @ home ověření Proces zahrnuje jeden klientský stroj a mnoho pracovních strojů. Klientský stroj odesílá identické pracovní jednotky do více počítačů (alespoň 2).

Když se v rozumném čase nevrátí dostatek výsledků - kvůli náhodnému vypnutí strojů, poruchám komunikace atd. - nebo výsledky nesouhlasí - kvůli chybám ve výpočtu, podvádění zadáváním falešných dat, aniž by práci skutečně vykonávali atd. —Tak klientský stroj odešle více identických pracovních jednotek na jiné pracovní stroje. Jakmile souhlasí minimální kvorum (často 2) výsledků, klient předpokládá, že tyto výsledky (a další identické výsledky pro tuto pracovní jednotku) jsou správné. Klient uděluje kredit na všechny stroje, které vrátily správné výsledky.

Ověřitelný výpočet

Gennaro a kol.[4] definoval pojem ověřitelné výpočetní schéma jako a protokol mezi dvěma polynomiálními časovými stranami ke spolupráci na výpočtu funkce F: {0,1}n → {0,1}m. Toto schéma se skládá ze tří hlavních fází:

  1. Předběžné zpracování. Tuto fázi klient provede jednou za účelem výpočtu některých pomocných informací spojených s F. Část těchto informací je veřejná, aby byla sdílena s pracovníkem, zatímco ostatní jsou soukromé a uchovávány s klientem.
  2. Příprava vstupu. V této fázi klient vypočítá některé pomocné informace o vstupu funkce. Část těchto informací je veřejná, zatímco ostatní jsou soukromé a uchovávají se u klienta. Veřejné informace se odesílají pracovníkovi, aby vypočítal F na vstupních datech.
  3. Výpočet a ověření výstupu. V této fázi pracovník používá veřejné informace spojené s funkcí F a vstupem, které se počítají v předchozích dvou fázích, k výpočtu kódovaný výstup funkce F na zadaném vstupu. Tento výsledek je poté vrácen klientovi, aby ověřil jeho správnost výpočtem skutečné hodnoty výstupu dekódování výsledek vrácený pracovníkem pomocí soukromých informací vypočítaných v předchozích fázích.

Definovaný pojem ověřitelného výpočetního schématu minimalizuje interakce mezi klientem a pracovníkem do přesně dvou zpráv, kdy jedna zpráva odeslána z každé strany druhé straně během různých fází protokolu.[4]

Příklad schématu založeného na plně homomorfním šifrování

Gennaro a kol.[4] definoval ověřitelné výpočetní schéma pro jakoukoli funkci F použitím Zkažený obvod Yaa[16][17] v kombinaci s a plně homomorfní šifrovací systém.

Toto ověřitelné výpočetní schéma VC je definována takto:[4]

VC = (KeyGen, ProbGen, Compute, Verify) se skládá ze čtyř následujících algoritmů:

  1. KeyGen (F, λ) → (PK, SK): Náhodně algoritmus generování klíčů generuje dva klíče, veřejný a soukromý, na základě bezpečnostní parametr λ. The veřejný klíč kóduje cílovou funkci F a je odeslána pracovníkovi k výpočtu F. Na druhou stranu tajný klíč je klientem soukromý.
  2. ProbGenSK (x) → (σx, τx): Algoritmus generování problému kóduje vstup funkce x do dvou hodnot, veřejné a soukromé, pomocí tajného klíče SK. Veřejná hodnota σx je dána pracovníkovi, se kterým vypočítá F (x), zatímco tajná hodnota τx je klientem soukromá.
  3. Vypočítat (PK, σx) → σy: Pracovník vypočítá zakódovanou hodnotu σy výstupu funkce y = F (x) pomocí veřejného klíče klienta PK a zakódovaného vstupu σx.
  4. OvěřitSK(τx, σy) → y ∪ ⊥: Ověřovací algoritmus převádí kódovaný výstup pracovníka σy na skutečný výstup funkce F pomocí tajného klíče SK i tajného „dekódování“ τx. Na výstupu y = F (x), pokud σy představuje platný výstup F na x, nebo výstupy ⊥ jinak.

Protokol ověřitelného výpočetního schématu definovaný Gennaro et al.[4] funguje takto:

Funkce F by měla být reprezentována jako a Booleovský obvod na kterém generace klíčů byl by použit algoritmus. Algoritmus generování klíčů spouští zkomolený postup Yao v tomto booleovském obvodu a vypočítává veřejné a tajné klíče. Veřejný klíč (PK) se skládá ze všech šifrovací texty které představují poškozený obvod a tajný klíč (SK) se skládá ze všech náhodných štítků drátu. Vygenerovaný tajný klíč se poté použije v algoritmu generování problému. Tento algoritmus nejprve generuje novou dvojici veřejných a tajných klíčů pro homomorfní šifrovací schéma, a poté použije tyto klíče s homomorfním schématem k zašifrování správných vstupních vodičů, představovaných jako tajný klíč poškozeného obvodu. Vyrobené ciphertexty představují veřejné kódování vstupu (σx), který je dán pracovníkovi, zatímco tajný klíč (τx) je klientem soukromý. Poté pracovník použije výpočtové kroky protokolu Yao na šifrovací texty generované algoritmem generování problému. To se provádí pomocí rekurzivně dešifrování hradlových šifrovacích textů až do dosažení konečných hodnot výstupního drátu (σy). Homomorfní vlastnosti šifrovacího schématu umožňují pracovníkovi získat šifrování správného výstupního drátu. Nakonec pracovník vrátí šifrovací výstupy klientovi, který je dešifruje, aby vypočítal skutečný výstup y = F (x) nebo ⊥.

Definice ověřitelného výpočetního schématu uvádí, že schéma by mělo být správné a bezpečné. Správnost schématu je dosaženo, pokud algoritmus generování problémů produkuje hodnoty, které umožňují poctivému pracovníkovi vypočítat kódované výstupní hodnoty, které budou úspěšně ověřeny a odpovídají vyhodnocení F na těchto vstupech. Na druhou stranu je ověřitelné výpočetní schéma zajistit pokud pracovník se zlými úmysly nemůže přesvědčit ověřovací algoritmus, aby přijal nesprávný výstup pro danou funkci F a zadal x.

Praktické ověřitelné výpočty

Ačkoli se ukázalo, že ověřitelné výpočty jsou teoreticky možné (při plném využití homomorfní šifrování nebo prostřednictvím pravděpodobnostně ověřitelné důkazy ), většina známých konstrukcí je v praxi velmi nákladná. V poslední době se někteří vědci zabývají provedením ověřitelného výpočtu. Jedním z takových snah je práce UT Austin výzkumníci.[18] Autoři začínají systémem argumentů založeným na pravděpodobnostně ověřitelné důkazy a snížit jeho náklady o faktor 1020. Svou techniku ​​implementovali také v Pepř Systém. Autoři poznamenávají, že „Náš závěr zatím je, že jako nástroj pro vytváření bezpečných systémů nejsou PCP a systémy argumentů ztracenou příčinou.“

Byla prozkoumána celková oblast, která nyní zahrnuje řadu implementací od různých skupin.[19]

Reference

  1. ^ Babai, László; Fortnow, Lance; Levin, Leonid A .; Szegedy, Mario (01.01.1991). Kontrola výpočtů v polylogaritmickém čase. Sborník z dvacátého třetího ročníku ACM symposia o teorii práce s počítačem. STOC '91. New York, NY, USA: ACM. 21–32. CiteSeerX  10.1.1.42.5832. doi:10.1145/103418.103428. ISBN  978-0897913973.
  2. ^ Goldwasser, Shafi; Kalai, Yael Tauman; Rothblum, Guy N. (01.01.2008). Delegování výpočtu: Interaktivní důkazy pro mudly. Proceedings of the Fortiethhe Annual ACM Symposium on Theory of Computing. STOC '08. New York, NY, USA: ACM. str. 113–122. doi:10.1145/1374376.1374396. ISBN  9781605580470.
  3. ^ A b Micali, S. (2000-01-01). "Výpočtově spolehlivé důkazy". SIAM Journal on Computing. 30 (4): 1253–1298. CiteSeerX  10.1.1.207.8277. doi:10.1137 / S0097539795284959. ISSN  0097-5397.
  4. ^ A b C d E F G Gennaro, Rosario; Gentry, Craig; Parno, Bryan (31. srpna 2010). Neinteraktivní ověřitelné výpočty: Outsourcing výpočtu pro nedůvěryhodné pracovníky. CRYPTO 2010. doi:10.1007/978-3-642-14623-7_25.
  5. ^ Molnar, D. (2000). "Problém SETI @ Home". ACM Crossroads. 7 (1).
  6. ^ Smith, S .; Weingart, S. (1999). "Budování vysoce výkonného programovatelného zabezpečeného koprocesoru". Počítačové sítě. 31 (8): 831–960. CiteSeerX  10.1.1.22.8659. doi:10.1016 / S1389-1286 (98) 00019-X.
  7. ^ Yee, B. (1994). Používání zabezpečených koprocesorů (Disertační práce). Univerzita Carnegie Mellon.
  8. ^ Trusted Computing Group (červenec 2007). Hlavní specifikace modulu důvěryhodné platformy. 1.2, revize 103.
  9. ^ L. Babai (1985). „Teorie obchodní skupiny pro náhodnost.“ v Proceedings of the ACM Symposium on Theory of Computing (STOC), New York, NY, USA, str. 421–429
  10. ^ S. Goldwasser, S. Micali a C. Rackoff (1989). „Znalostní složitost interaktivních zkušebních systémů.“ SIAM Journal on Computing, 18(1), s. 186–208
  11. ^ S. Arora a S. Safra (1998). „Pravděpodobně ověřitelné důkazy: nová charakteristika NP.“ Deník ACM, 45501-555
  12. ^ O. Goldreich (1998). Moderní kryptografie, pravděpodobnostní důkazy a pseudonáhodnost. Řada Algoritmy a kombinatorika, 17Springer
  13. ^ A b J. Kilian (1992). „Poznámka k účinným důkazům a argumentům s nulovými znalostmi (rozšířený abstrakt).“ v Proceedings of the ACM Symposium on Theory of Computing (STOC)
  14. ^ A b J. Kilian (1995). "Vylepšené efektivní argumenty (předběžná verze)." v Řízení o krypto, Londýn, Velká Británie, str. 311–324. Springer-Verlag
  15. ^ A b S. Micali (1994). „CS proofs (extended abstract).“ v Proceedings of the IEEE Symposium on Foundations of Computer Science, str. 436-453.
  16. ^ A. Yao (1982). "Protokoly pro bezpečné výpočty." v Proceedings of the IEEE Symposium on Foundations of Computer Science, str. 160-164
  17. ^ A. Yao (1986). „Jak generovat a vyměňovat tajemství.“ v Proceedings of the IEEE Symposium on Foundations of Computer Science, str. 162-167
  18. ^ Setty, Srinath; McPherson, Richard; Blumberg, Andrew J .; Walfish, Michael (únor 2012). Provedení praktických systémů argumentů pro outsourcované výpočty (někdy). Sympozium o zabezpečení sítí a distribuovaných systémů (NDSS) 2012.
  19. ^ Walfish, Michael; Blumberg, Andrew J. (01.01.2015). „Ověření výpočtů bez jejich opětovného provedení“. Commun. ACM. 58 (2): 74–84. doi:10.1145/2641562. ISSN  0001-0782.