Icke-interaktivt nollkunskapsbevis

Icke-interaktiva nollkunskapsbevis är kryptografiska primitiver, där information mellan en bevisare och en verifierare kan autentiseras av bevisaren, utan att avslöja någon av den specifika informationen utöver själva påståendets giltighet. Denna krypteringsfunktion gör direkt kommunikation mellan provaren och verifieraren onödig, vilket effektivt tar bort alla mellanhänder. Kärnan, trustless kryptografi "proofing" involverar en hashfunktionsgenerering av ett slumpmässigt tal, begränsat inom matematiska parametrar (främst för att modulera hashingsvårigheter) som bestäms av provaren och verifieraren.

Den viktigaste fördelen med icke-interaktiva nollkunskapsbevis är att de kan användas i situationer där det inte finns någon möjlighet till interaktion mellan provaren och verifieraren, till exempel i onlinetransaktioner där de två parterna inte kan kommunicera i realtid. Detta gör icke-interaktiva nollkunskapsbevis särskilt användbara i decentraliserade system som blockkedjor, där transaktioner verifieras av ett nätverk av noder och det inte finns någon central myndighet för att övervaka verifieringsprocessen.

De flesta icke-interaktiva nollkunskapsbevis är baserade på matematiska konstruktioner som elliptisk kurvkryptografi eller parningsbaserad kryptografi, vilket möjliggör skapandet av korta och lätt verifierbara bevis på sanningen i ett påstående. Till skillnad från interaktiva nollkunskapsbevis, som kräver flera omgångar av interaktion mellan provaren och verifieraren, är icke-interaktiva nollkunskapsbevis designade för att vara effektiva och kan användas för att verifiera ett stort antal påståenden samtidigt.

Historia

Blum , Feldman och Micali visade 1988 att en gemensam referenssträng som delas mellan provaren och verifieraren är tillräcklig för att uppnå beräkningsnoll-kunskap utan att kräva interaktion. Goldreich och Oren gav omöjlighetsresultat [ förtydligande behövs ] för engångsnollkunskapsprotokoll i standardmodellen . År 2003 Shafi Goldwasser och Yael Tauman Kalai en instans av ett identifieringsschema för vilket någon hashfunktion kommer att ge ett osäkert digitalt signaturschema. Dessa resultat är inte motsägelsefulla, eftersom omöjlighetsresultatet [ förtydligande behövs ] av Goldreich och Oren inte håller i den vanliga referenssträngmodellen eller den slumpmässiga orakelmodellen . Icke-interaktiva nollkunskapsbevis visar dock en separation mellan de kryptografiska uppgifter som kan uppnås i standardmodellen och de som kan uppnås i "kraftfullare" utökade modeller. [ citat behövs ]

Modellen påverkar de egenskaper som kan erhållas från ett nollkunskapsprotokoll. Pass visade att i den gemensamma referenssträngsmodellen bevarar icke-interaktiva nollkunskapsprotokoll inte alla egenskaper hos interaktiva nollkunskapsprotokoll; t.ex. bevarar de inte förnekelse. Icke-interaktiva nollkunskapsbevis kan också erhållas i den slumpmässiga orakelmodellen med hjälp av Fiat–Shamir-heuristiken .

Blockchain-applikationer

En jämförelse av de mest använda bevissystemen

2012 utvecklade Alessandro Chiesa et al zk-SNARK-protokollet, en akronym för noll-kunskap kortfattat icke-interaktivt kunskapsargument . Den första utbredda tillämpningen av zk-SNARKs var i blockkedjeprotokollet Zerocash , där nollkunskapskryptering tillhandahåller beräkningsryggraden, genom att underlätta matematiska bevis på att en part har viss information utan att avslöja vad den informationen är. Zcash använde zk-SNARKs för att underlätta fyra distinkta transaktionstyper: privat, avskärmning, avskärmning och offentlig. Detta protokoll gjorde det möjligt för användare att bestämma hur mycket data som delades med den offentliga redovisningen för varje transaktion. Ethereum zk-Rollups använder också zk-SNARKs för att öka skalbarheten.

Under 2017 släpptes Bulletproofs , som gör det möjligt att bevisa att ett engagerat värde ligger inom ett intervall med hjälp av ett logaritmiskt (i intervallets bitlängd) antal fält- och gruppelement. Bulletproofs implementerades senare i Mimblewimble-protokollet (basen för Grin and Beam, och Litecoin via förlängningsblock) och Monero kryptovaluta .

2018 introducerades zk-STARK-protokollet ( zero - knowledge Scalable Transparent Argument of Knowledge ) av Eli Ben-Sasson, Iddo Bentov, Yinon Horesh och Michael Riabzev, vilket erbjuder transparens (ingen tillförlitlig installation), kvasilinjär provningstid, och polylogaritmisk verifieringstid. Zero-Knowledge Succinct Transparent Argument of Knowledge är en typ av kryptografiskt bevissystem som gör det möjligt för en part (bevisaren) att bevisa för en annan part (verifieraren) att ett visst påstående är sant, utan att avslöja någon ytterligare information utöver påståendets sanning sig. zk-STARKs är kortfattade, vilket innebär att de tillåter skapandet av korta bevis som är lätta att verifiera, och de är transparenta, vilket innebär att vem som helst kan verifiera beviset utan att behöva någon hemlig information.

Till skillnad från den första generationen av zk-SNARKs, kräver zk-STARKs som standard inte en pålitlig installation, vilket gör dem särskilt användbara för decentraliserade applikationer som blockkedjor. Dessutom kan zk-STARKs användas för att verifiera många påståenden samtidigt, vilket gör dem skalbara och effektiva.

Under 2019 presenterades HALO rekursiva zk-SNARKs utan en pålitlig installation. Pickles zk-SNARKs, baserade på den tidigare konstruktionen, driver MINA, den lättaste blockkedjan.

En lista över nollkunskapssäkra protokoll och bibliotek finns nedan tillsammans med jämförelser baserade på transparens , universalitet , rimlig post-kvantsäkerhet och programmeringsparadigm . Ett transparent protokoll är ett som inte kräver någon pålitlig installation och använder offentlig slumpmässighet. Ett universellt protokoll är ett som inte kräver en separat betrodd uppsättning för varje krets. Slutligen är ett troligt post-kvantprotokoll ett som inte är mottagligt för kända attacker som involverar kvantalgoritmer.

Icke-interaktiva noll-kunskapssäkra system
ZKP System Utgivningsår Protokoll Transparent Universell Troligtvis Post-Quantum Secure Programmeringsparadigm
Pinocchio 2013 zk-SNARK Nej Nej Nej Procedurmässigt
Geppetto 2015 zk-SNARK Nej Nej Nej Procedurmässigt
TinyRAM 2013 zk-SNARK Nej Nej Nej Procedurmässigt
Buffé 2015 zk-SNARK Nej Nej Nej Procedurmässigt
ZoKrates 2018 zk-SNARK Nej Nej Nej Procedurmässigt
xJsnark 2018 zk-SNARK Nej Nej Nej Procedurmässigt
vRAM 2018 zk-SNARG Nej Ja Nej hopsättning
vnTinyRAM 2014 zk-SNARK Nej Ja Nej Procedurmässigt
HÄGRING 2020 zk-SNARK Nej Ja Nej Aritmetiska kretsar
Sonisk 2019 zk-SNARK Nej Ja Nej Aritmetiska kretsar
Svärdfisk 2020 zk-SNARK Nej Ja Nej Aritmetiska kretsar
PLONK 2019 zk-SNARK Nej Ja Nej Aritmetiska kretsar
Överljuds 2020 zk-SNARK Ja Ja Nej Aritmetiska kretsar
Skottsäkra 2018 Skottsäkra Ja Ja Nej Aritmetiska kretsar
Hyrax 2018 zk-SNARK Ja Ja Nej Aritmetiska kretsar
Halo 2019 zk-SNARK Ja Ja Nej Aritmetiska kretsar
Jungfrun 2020 zk-SNARK Ja Ja Ja Aritmetiska kretsar
Ligero 2017 zk-SNARK Ja Ja Ja Aritmetiska kretsar
Aurora 2019 zk-SNARK Ja Ja Ja Aritmetiska kretsar
zk-STARK 2019 zk-STARK Ja Ja Ja hopsättning
Zilch 2021 zk-STARK Ja Ja Ja Objektorienterad

Definition

Ursprungligen definierades icke-interaktiv nollkunskap endast som ett enda teoremsäkert system. I ett sådant system kräver varje bevis sin egen färska gemensamma referenssträng. En vanlig referenssträng är i allmänhet inte en slumpmässig sträng. Det kan till exempel bestå av slumpmässigt valda gruppelement som alla protokollparter använder. Även om gruppelementen är slumpmässiga, är referenssträngen inte eftersom den innehåller en viss struktur (t.ex. gruppelement) som kan skiljas från slumpmässighet. Därefter introducerade Feige, Lapidot och Shamir multi-teorem noll-kunskapsbevis som en mer mångsidig uppfattning för icke-interaktiva noll-kunskapsbevis.

Parningsbaserade icke-interaktiva prov

Parningsbaserad kryptografi har lett till flera kryptografiska framsteg. En av dessa framsteg är kraftfullare och mer effektiva icke-interaktiva nollkunskapsbevis. Den främsta idén var att dölja värdena för parningsutvärderingen i ett åtagande . Med hjälp av olika åtagandescheman användes denna idé för att bygga noll-kunskapssäkra system under undergruppens gömmer och under det beslutsmässiga linjära antagandet . Dessa bevissystem bevisar att kretsen är tillfredsställande och tillåter därför genom Cook–Levin-satsen bevis på medlemskap för varje språk i NP. Storleken på den gemensamma referenssträngen och bevisen är relativt liten; att omvandla ett uttalande till en boolesk krets medför dock avsevärda omkostnader.

Bevissystem under subgruppen hiding , beslutslinjärt antagande och externt Diffie-Hellman-antagande som gör det möjligt att direkt bevisa de parningsproduktekvationer som är vanliga i parningsbaserad kryptografi .

Under starka kunskapsantaganden är det känt hur man skapar beräkningsmässigt ljudisolerade system med sublinjär längd för NP-kompletta språk. Mer exakt består beviset i sådana bevissystem endast av ett litet antal bilinjära gruppelement.

  1. ^ Goldreich, Oded; Krawczyk, Hugo (1996). "Om sammansättningen av system för nollkunskapssäkring" . SAIM . 25 (1): 169–192. doi : 10.1137/S0097539791220688 . Hämtad 4 november 2022 .
  2. ^ a b c Gong, Yinjie; Jin, Yifei; Li, Yuchan; Liu, Ziyi; Zhu, Zhiyi (januari 2022). "Analys och jämförelse av det huvudsakliga nollkunskapssäkringsschemat" . 2022 International Conference on Big Data, Information and Computer Network (BDICN) : 366–372. doi : 10.1109/BDICN55575.2022.00074 .
  3. ^ a b Manuel Blum, Paul Feldman och Silvio Micali. Icke-interaktiv Zero-Knowledge och dess tillämpningar. Proceedings of the twentieth annual ACM symposium on Theory of computing (STOC 1988). 103–112. 1988
  4. ^ Oded Goldreich och Yair Oren. Definitioner och egenskaper för Zero-Knowledge Proof Systems. Journal of Cryptology. Vol 7(1). 1–32. 1994 (PS)
  5. ^ Shafi Goldwasser och Yael Kalai. Om (o)säkerheten i Fiat–Shamir-paradigmet. Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03). 2003
  6. ^ Rafael Pass. Om förnekelse i Common Reference String och Random Oracle Model. Framsteg inom kryptologi – CRYPTO 2003. 316–337. 2003 (PS)
  7. ^    Bitansky, Nir; Canetti, Ran; Chiesa, Alessandro; Tromer, Eran (januari 2012). "Från extraherbart kollisionsmotstånd till kortfattade icke-interaktiva kunskapsargument och tillbaka igen" . Proceedings of the 3rd Innovations in Theoretical Computer Science Conference on-ITCS '12 . ACM . s. 326–349. doi : 10.1145/2090236.2090263 . ISBN 9781450311151 . S2CID 2576177 .
  8. ^ Ben-Sasson, Eli; Chiesa, Alessandro; Garman, Christina; Green, Matthew; Miers, Ian; Tromer, Eran; Virza, Madars (18 maj 2014). "Zerocash: Decentraliserade anonyma betalningar från Bitcoin" (PDF) . IEEE . Hämtad 26 januari 2016 .
  9. ^ Ben-Sasson, Eli; Chiesa, Alessandro. "Vad är zk-SNARKs?" . z.cash . Hämtad 3 november 2022 .
  10. ^ "Zero-Knowledge sammanslagningar" . ethereum.org . Hämtad 2023-02-25 .
  11. ^ Bünz, Benedikt; Bootle, Jonathan; Boneh, Dan; Poelstra, Andrew; Wuille, Pieter; Maxwell, Greg (maj 2018). "Bulletproofs: Short Proofs for Confidential Transactions and more" . 2018 IEEE Symposium on Security and Privacy (SP) : 315–334. doi : 10.1109/SP.2018.00020 .
  12. ^    Bünz, Benedikt; Bootle, Jonathan; Boneh, Dan; Poelstra, Andrew; Wuille, Pieter; Maxwell, Greg (maj 2018). "Bulletproofs: Short Proofs for Confidential Transactions and More" (PDF) . 2018 IEEE Symposium on Security and Privacy (SP) : 315–334. doi : 10.1109/SP.2018.00020 . ISBN 978-1-5386-4353-2 . S2CID 3337741 . Hämtad 2 december 2022 .
  13. ^ Odendaal, Hansie; Sharrock, Cayle; Heerden, SW. "Bulletproofs and Mimblewimble" . Tari Labs University. Arkiverad från originalet den 29 september 2020 . Hämtad 3 december 2020 .
  14. ^ http://www.cs.technion.ac.il/RESEARCH_DAY_17/POSTERS/michael_riabzev.pdf
  15. ^ a b c Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev (6 mars 2018). "Skalbar, transparent och postkvantsäker beräkningsintegritet" (PDF) . International Association for Cryptologic Research . Hämtad 24 oktober 2021 . {{ citera webben }} : CS1 underhåll: använder författarens parameter ( länk )
  16. ^ a b Bowe, Sean; Grigg, Jack; Hopwood, Daira (2019). "Rekursiv beviskomposition utan tillförlitlig installation" . Kryptologi ePrint-arkiv .
  17. ^ "Möt Pickles SNARK: möjliggör smarta kontrakt på Coda-protokollet" . Mina-protokollet . Hämtad 2023-02-25 .
  18. ^ Bonneau, Joseph; Meckler, Izaak; Rao, V.; Evan; Shapiro (2021). "Mina: Decentraliserad kryptovaluta i skala" . www.semanticscholar.org . Hämtad 2023-02-25 .
  19. ^ a b   Mouris, Dimitris; Tsoutsos, Nektarios Georgios (2021). "Zilch: A Framework for Deploying Transparent Zero-Knowledge Proofs" . IEEE-transaktioner om informationsforensik och säkerhet . 16 : 3269-3284. doi : 10.1109/TIFS.2021.3074869 . ISSN 1556-6021 .
  20. ^ Parno, Bryan; Howell, Jon; Gentry, Craig; Raykova, Mariana (maj 2013). "Pinocchio: Nästan praktisk verifierbar beräkning" . 2013 IEEE Symposium on Security and Privacy : 238–252. doi : 10.1109/SP.2013.47 .
  21. ^ Costello, Craig; Fournet, Cédric; Howell, Jon; Kohlweiss, Markulf; Kreuter, Benjamin; Naehrig, Michael; Parno, Bryan; Zahur, Samee (maj 2015). "Geppetto: mångsidig verifierbar beräkning" . 2015 IEEE Symposium on Security and Privacy : 253–270. doi : 10.1109/SP.2015.23 .
  22. ^   Ben-Sasson, Eli; Chiesa, Alessandro; Genkin, Daniel; Tromer, Eran; Virza, Madars (2013). Canetti, Ran; Garay, Juan A. (red.). "SNARKs for C: Verifiera programexekveringen kortfattat och utan kunskap" . Framsteg inom kryptologi – CRYPTO 2013 . Berlin, Heidelberg: Springer: 90–108. doi : 10.1007/978-3-642-40084-1_6 . ISBN 978-3-642-40084-1 .
  23. ^ "Effektivt RAM-minne och kontrollflöde i verifierbar utlagd beräkning" . NDSS Symposium . doi : 10.14722/ndss.2015.23097 . Hämtad 2023-02-25 .
  24. ^   Eberhardt, Jacob; Tai, Stefan (juli 2018). "ZoKrates - Scalable Privacy-Preserving Off-Chain Computations" . 2018 IEEE International Conference on Internet of Things (iThings) och IEEE Green Computing and Communications (GreenCom) och IEEE Cyber, Physical and Social Computing (CPSCom) och IEEE Smart Data (SmartData) . Halifax, NS, Kanada: IEEE: 1084–1091. doi : 10.1109/Cybermatics_2018.2018.00199 . ISBN 978-1-5386-7975-3 .
  25. ^ Kosba, Ahmed; Papamanthou, Charalampos; Shi, Elaine (maj 2018). "xJsnark: A Framework for Efficient Verifiable Computation" . 2018 IEEE Symposium on Security and Privacy (SP) : 944–961. doi : 10.1109/SP.2018.00018 .
  26. ^ Zhang, Yupeng; Genkin, Daniel; Katz, Jonathan; Papadopoulos, Dimitrios; Papamanthou, Charalampos (maj 2018). "vRAM: Snabbare verifierbart RAM med programoberoende förbearbetning" . 2018 IEEE Symposium on Security and Privacy (SP) : 908–925. doi : 10.1109/SP.2018.00013 .
  27. ^   Ben-Sasson, Eli; Chiesa, Alessandro; Tromer, Eran; Virza, Madars (2014). "Kunsad {icke-interaktiv} noll kunskap för en von Neumann-arkitektur" : 781–796. ISBN 978-1-931971-15-7 . {{ citera journal }} : Citera journal kräver |journal= ( hjälp )
  28. ^ Kosba, Ahmed; Papadopoulos, Dimitrios; Papamanthou, Charalampos; Song, Dawn (2020). "MIRAGE: Succinct Arguments for Randomized Algorithms with Applications to Universal zk-SNARKs" . Kryptologi ePrint-arkiv .
  29. ^   Maller, Mary; Bowe, Sean; Kohlweiss, Markulf; Meiklejohn, Sarah (2019-11-06). "Sonic: Zero-Knowledge SNARKs från Linear-Size Universal and Updateable Structured Reference Strings" . Proceedings of 2019 ACM SIGSAC Conference on Computer and Communications Security . CCS '19. New York, NY, USA: Association for Computing Machinery: 2111–2128. doi : 10.1145/3319535.3339817 . ISBN 978-1-4503-6747-9 .
  30. ^   Chiesa, Alessandro; Hu, Yuncong; Maller, Mary; Mishra, Pratyush; Vesely, Noah; Ward, Nicholas (2020). Canteaut, Anne; Ishai, Yuval (red.). "Marlin: Förbearbetning av zkSNARKs med universell och uppdateringsbar SRS" . Framsteg inom kryptologi – EUROCRYPT 2020 . Cham: Springer International Publishing: 738–768. doi : 10.1007/978-3-030-45721-1_26 . ISBN 978-3-030-45721-1 .
  31. ^ Gabizon, Ariel; Williamson, Zachary J.; Ciobotaru, Oana (2019). "PLONK: Permutationer över Lagrange-baser för ekumeniska icke-interaktiva kunskapsargument" . Kryptologi ePrint-arkiv .
  32. ^   Bünz, Benedikt; Fisch, Ben; Szepieniec, Alan (2020). Canteaut, Anne; Ishai, Yuval (red.). "Transparenta SNARKs från DARK Compilers" . Framsteg inom kryptologi – EUROCRYPT 2020 . Cham: Springer International Publishing: 677–706. doi : 10.1007/978-3-030-45721-1_24 . ISBN 978-3-030-45721-1 .
  33. ^ Bünz, Benedikt; Bootle, Jonathan; Boneh, Dan; Poelstra, Andrew; Wuille, Pieter; Maxwell, Greg (maj 2018). "Bulletproofs: Short Proofs for Confidential Transactions and more" . 2018 IEEE Symposium on Security and Privacy (SP) : 315–334. doi : 10.1109/SP.2018.00020 .
  34. ^ Wahby, Riad S.; Tzialla, Ioanna; Shelat, Abhi; Thaler, Justin; Walfish, Michael (maj 2018). "Dubbeleffektiva zkSNARKs utan betrodd installation" . 2018 IEEE Symposium on Security and Privacy (SP) : 926–943. doi : 10.1109/SP.2018.00060 .
  35. ^ Zhang, Jiaheng; Xie, Tiancheng; Zhang, Yupeng; Song, Dawn (maj 2020). "Transparent polynomdelegering och dess tillämpningar för noll kunskapsbevis" . 2020 IEEE Symposium on Security and Privacy (SP) : 859–876. doi : 10.1109/SP40000.2020.00052 .
  36. ^   Ames, Scott; Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan (2017-10-30). "Ligero: Lättvikts sublinjära argument utan en betrodd uppsättning" . Proceedings of 2017 ACM SIGSAC Conference on Computer and Communications Security . CCS '17. New York, NY, USA: Association for Computing Machinery: 2087–2104. doi : 10.1145/3133956.3134104 . ISBN 978-1-4503-4946-8 .
  37. ^   Ben-Sasson, Eli; Chiesa, Alessandro; Riabzev, Michael; Spooner, Nicholas; Virza, Madars; Ward, Nicholas P. (2019). Ishai, Yuval; Rijmen, Vincent (red.). "Aurora: Transparent Succinct Arguments for R1CS" . Framsteg inom kryptologi – EUROCRYPT 2019 . Cham: Springer International Publishing: 103–128. doi : 10.1007/978-3-030-17653-2_4 . ISBN 978-3-030-17653-2 .
  38. ^   Ben-Sasson, Eli; Bentov, Iddo; Horesh, Yinon; Riabzev, Michael (2019). Boldyreva, Alexandra; Micciancio, Daniele (red.). "Skalbar nollkunskap utan tillförlitlig installation" . Framsteg inom kryptologi – CRYPTO 2019 . Cham: Springer International Publishing: 701–732. doi : 10.1007/978-3-030-26954-8_23 . ISBN 978-3-030-26954-8 .
  39. ^ Computing, Trustworthy (2021-08-30). "Transparenta nollkunskapsbevis med Zilch" . Medium . Hämtad 2023-02-25 .
  40. ^ Uriel Feige, Dror Lapidot, Adi Shamir: Flera icke-interaktiva nollkunskapsbevis under allmänna antaganden. SIAM J. Comput. 29(1): 1–28 (1999)
  41. ^ Jens Groth, Rafail Ostrovsky, Amit Sahai: Perfekt icke-interaktiv nollkunskap för NP. EUROCRYPT 2006: 339–358
  42. ^ Jens Groth, Rafail Ostrovsky, Amit Sahai: Icke-interaktiva Zaps och nya tekniker för NIZK. CRYPTO 2006: 97–111
  43. ^ Jens Groth, Amit Sahai: Effektiva icke-interaktiva bevissystem för bilinjära grupper. EUROCRYPT 2008: 415–432
  44. ^ Jens Groth. Korta parningsbaserade icke-interaktiva nollkunskapsargument. ASIACRYPT 2010: 321–340
  45. ^ Helger Lipmaa. Progressionsfria uppsättningar och sublinjära parningsbaserade icke-interaktiva nollkunskapsargument. TCC 2012: 169–189
Hämtad från " https://en.wikipedia.org/w/index.php?title=Non-interactive_zero-knowledge_proof&oldid=1143070153 "