Vi ger en noll-kunskap argument för aritmetisk krets satisfiability med en kommunikations komplexitet som växer logaritmiskt i storleken på kretsen. Den runda komplexiteten är också logaritmisk och för en aritmetisk krets med fläkt-in 2 grindar är beräkningen av provaren och kontrollören linjär i kretsens storlek. Sundheten i vårt argument bygger enbart på väletablerade diskreta logaritm antagande i prime order grupper. Kärnan i vårt nya argumentsystem är ett effektivt nollkunskapsargument för kunskap om öppningar av två Pedersen-multiåtaganden som uppfyller ett inre produktförhållande, vilket är av oberoende intresse. Det inre produktargumentet kräver logaritmisk kommunikation, logaritmisk interaktion och linjär beräkning för både provaren och kontrollören. Vi utvecklar också ett system för att binda oss till ett polynom och senare avslöja utvärderingen vid en godtycklig punkt, på ett kontrollerbart sätt. Detta används för att bygga en optimerad version av den konstant runda kvadratrot komplexitet argument Groth (CRYPTO 2009), vilket minskar både kommunikation och rund komplexitet. Informellt involverar ett nollkunskapsargument två parter, bevisaren och kontrollören, och gör det möjligt för kontrollören att bevisa för kontrollören att ett visst påstående är sant, utan att avslöja något annat om själva uttalandet. Uttalanden är av formen u  på L, där L är ett språk i NP. Vi kallar w ett vittne för ett uttalande u om (u, w) R, där R är en polynom tid decidable binär relation i samband med L. Vi kräver noll-kunskap argument för att vara komplett, ljud och noll-kunskap. En bevisare med ett vittne kan övertyga kontrollanten om detta faktum. Ljudstyrka: En provtagare kan inte övertyga en kontrollör när u /  på L. Zero-kunskap: Interaktionen bör inte avslöja något för kontrollören förutom att u  på L. I synnerhet bör det inte avslöja provkroppens vittne w. Vårt mål är att bygga ett effektivt argumentsystem för satisfiability för en aritmetisk krets, dvs. en krets som består av addition och multiplikation grindar över ett ändligt fält Z p. Dessutom vill vi basera säkerheten i detta argument enbart på diskret logaritm antagande: detta kommer att ge både starka säkerhetsgarantier och god effektivitet eftersom det inte finns några kända attacker bättre än generiska för väl valda elliptiska kurvundergrupper. De mest effektiva argumenten för nollkunskap enbart baserat på det diskreta logaritm antagandet är Groths protokoll baserat på linjär algebra [Gro09b] och dess variant av Seo [Seo11]. Båda dessa protokoll har en kommunikations komplexitet som är proportionell mot kvadratroten av kretsens storlek. Denna kvadratrot komplexitet har sedan dess framträtt som en (kanske grundläggande) barriär för diskret logaritm-baserade argument för krets satisfiability. Vi tillhandahåller en ärlig kontrollör noll-kunskap argument för aritmetisk krets satisfiability baserat på diskret logaritm antagande som bara kräver en logaritmisk kommunikation komplexitet. Vårt argument har perfekt fullständighet och perfekt speciell ärlig kontrollör noll-kunskap. Ljudstyrka är beräkningsmässig och baseras på det diskreta logaritm antagandet. Vi behöver ett logaritmiskt antal drag, och både provaren och kontrollören har linjär beräknings komplexitet. Argumentet är därför effektivt på alla parametrar med den största förbättringen av kommunikationens komplexitet. Förbättrad kvadratrot Komplexitet Argument. Vi börjar från kretsen satisfiability argument Groth [Gro09b], som kräver 7 drag och har kvadratrot kommunikation komplexitet i det totala antalet portar. I detta argument förbinder sig provtagaren till alla ledningar med hjälp av homomorfa multiåtaganden, kontrollerar additionsportar med hjälp av homomorfa egenskaper och använder ett produktargument för att visa att multiplikationsportarna är uppfyllda. Vi förbättrar först Groth argument i en 5 drag argument med kvadratrot kommunikation komplexitet i antalet multiplikation grindar endast. Vi är här.
Stövel et al. REF konstruerar argument med logaritmisk kommunikation komplexitet och linjära beräkningskostnader baserade på det diskreta logaritm antagandet.
Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting
{'venue': 'IACR Cryptology ePrint Archive', 'journal': 'IACR Cryptology ePrint Archive', 'mag_field_of_study': ['Computer Science', 'Mathematics']}