Förekomsten av koncisa icke-interaktiva argument för NP (dvs. icke-interaktiva beräkningsbaserade bevis där kontrollörens arbete i huvudsak är oberoende av den icke-deterministiska kontrollantens komplexitet) har varit en spännande fråga under de senaste två decennierna. Andra än CS-bevis i den slumpmässiga orakelmodellen [Micali, FOCS '94], är den enda befintliga kandidatkonstruktionen baserad på ett ingående antagande som är skräddarsytt för ett specifikt protokoll [Di Crescenzo och Lipmaa, CiE '08]. Vi formulerar en allmän och relativt naturlig uppfattning om en extraherbar kollisionssäker hashfunktion (ECRH) och visar att om ECRH finns, då en modifierad version av Di Crescenzo och Lipmaas protokoll är en kortfattad icke-interaktiv argumentering för NP. Dessutom är det ändrade protokollet i själva verket ett kortfattat icke-interaktivt adaptivt kunskapsargument (Snark). Vi föreslår sedan flera kandidatkonstruktioner för ECRH och avkopplingar därav. Vi visar tillämpligheten av Snarks på olika former av delegering av beräkningar, att koncis icke-interaktiv noll kunskap argument, och att koncis två-part säker beräkning. Slutligen visar vi att Snarks i huvudsak innebär förekomsten av ECRH, vilket visar att antagandet är nödvändigt.
En lösning för att förverkliga helt homomorfa signaturer skulle vara att använda koncisa icke-interaktiva argument för kunskap (Snarks) REF.
From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again
{'venue': "ITCS '12", 'journal': None, 'mag_field_of_study': ['Computer Science']}