Abstrakt. Micali, Rabin och Kilian [9] införde nyligen nollkunskapsuppsättningar och databaser, i vilka en provtagare upprättar en databas genom att publicera ett åtagande, och sedan ger bevis om särskilda värden. Även om en elegant och användbar primitiv, noll-kunskap databaser inte erbjuder något bra sätt att utföra uppdateringar. Vi undersöker frågan om att uppdatera databaser med nollkunskap. Vi definierar och diskuterar transparenta uppdateringar, som (1) tillåter innehavare av bevis som fortfarande är giltiga att uppdatera sina bevis, men (2) annars upprätthålla sekretess om uppdateringen. Vi ger strikta definitioner för öppet uppdaterade noll-kunskapsdatabaser, och ger en praktisk konstruktion baserad på Chase et al [2] konstruktion, förutsatt att kontrollerbara slumpmässiga funktioner finns och att merkuriella åtaganden finns, i den slumpmässiga orakle modellen. Vi undersöker också tanken på updatable-åtaganden, ett försök att göra enkla åtaganden öppet updatable. Vi definierar denna nya primitiva konstruktion och ger en enkel säker konstruktion. Nyckelord: noll-kunskapsdatabaser, noll-kunskapsuppsättningar, öppet uppdaterade noll-kunskapsdatabaser, noll-kunskap, protokoll, åtaganden, uppdaterade åtaganden Nyligen introducerades noll-kunskapsdatabaser av Micali, Rabin och Kilian [9]. En nollkunskap databas är en ändlig partiell funktion D kartläggning binära strängar till binära strängar (dvs, en uppsättning par strängar (x, y) sådan att inga två par har lika första poster men olika andra poster). 1 Databasägaren väljer D och "publicerar" databasen noll-kunskap i form av ett åtagande som fäster ner databasen men läcker ingenting, inte ens dess storlek. När databasen är upptagen, den inställda ägaren fungerar som en bevisare: på en fråga x, bevisaren ger ett bevis på att antingen x ligger utanför D eller D(x) = y, men fortfarande inte avslöja någon ytterligare information om D. Åtaganden och bevis i en noll-kunskap databas är icke-interaktiva och görs i den gemensamma slumpmässiga strängmodellen. Zero-kunskap visas genom att uppvisa en polynom-tid simulator som producerar en full transkript distribution (dvs. engagemang och bevis för alla frågesträngar) identisk med den verkliga visaren, vet endast "D(x) = y" eller "x är inte i D" för varje fråga och i sista möjliga ögonblick. Även om det är begreppsmässigt enklare att hantera beräkning noll-kunskap (och i själva verket beräkning noll-kunskap databaser tillhandahölls i tidigare versioner av deras papper [5,?]), Micali-Rabin-Kilian lösningen är mer önskvärd eftersom det är perfekt noll-kunskap. Dessutom är det mycket effektivare eftersom det inte omfattar komplexa allmänna syften icke-interaktiva nollkunskapsbevis. Zero-kunskap databaser är en kraftfull primitiv, men de har en stor nackdel i att de är statiska. Detta verkar vara en oönskad egenskap i de flesta tillämpningar. Till exempel, om databasen var en lista över personer som är under utredning för brottslig verksamhet, uppdateringar skulle vara en kritisk del av systemet. Naively, det enda sättet att uppdatera en noll-kunskap databas skulle vara att binda sig till sin nya version från grunden. Detta är dock inte önskvärt på två viktiga sätt. -För det första, körtiden för en sådan uppdatering beror på storleken på D, som kan vara enorm, även om den nyaste versionen kan skilja sig endast på ett enda par (x, y). 1 Micali, Rabin och Kilian kallar dessa enkla databaser "elementära" databaser. Alla databaser i detta dokument är av denna enkla typ. -För det andra kan det vara så att de som har sett bevis på medlemskap eller icke-medlemskap i den ursprungliga uppsättningen kan ha rätt till, eller kan begära igen, samma bevis i den nya uppsättningen (till exempel, om bevis ges på grund av prenumeration på vissa tjänster). Om så är fallet måste ägaren åter utfärda gamla bevis, vilket kan bli en enorm extra kostnad. Den andra av dessa punkter väcker en fråga som är av intresse: när en sådan databas uppdateras, bör även bevisen uppdateras, eller bör den nya uppsättningen vara privat även mot dem med gamla bevis? 2 Beroende på det program där noll-kunskapsuppsättningen används, kan antingen en vara den önskvärda typen av uppdatering. Vi skiljer dessa två typer av uppdateringar genom att ge dem olika namn: -opaque uppdateringar gör det uppdaterade åtagandet oskiljaktiga från ett nytt åtagande (därav att databasen blir "opaque" till användarna efter uppdateringen); -transparenta uppdateringar gör det möjligt för användarna att avgöra om deras bevis fortfarande är giltiga, och tillhandahålla en mekanism för att uppdatera bevis (därav, "transparent" till bevishållare). Vi fokuserar på problemet med transparenta uppdateringar av två skäl: för det första anser vi att det är mer önskvärt av de två, eftersom idén om en prenumerationstjänst av något slag naturligt verkar passa idén om en databas med noll kunskap, och för det andra finns det en ineffektiv men lämplig metod för ogenomskinligt uppdaterade nollkunskapsuppsättningar, nämligen att rekonstruera det uppdaterade åtagandet från grunden, medan det inte finns någon metod för öppet uppdaterade nollkunskapsuppsättningar. I detta dokument definierar vi begreppet öppet uppdaterade noll-kunskapsdatabaser, och visar hur man bygger effektiva transparent updatable noll-kunskapsdatabaser både baserat på Micali-Rabin-Kilian konstruktion och på den mer allmänna konstruktionen av Chase et al [2], under det ytterligare antagandet att kontrollerbara slumpmässiga funktioner finns i den slumpmässiga oraklet modellen. Vi definierar också idén om ett updatable åtagande och ger en beräkningsmässig gömma, helt bindande säker updatable åtagandesystem. I bilaga B diskuterar vi problemet med ogenomskinligt updatable noll-kunskapsdatabaser. Zero-kunskapsuppsättningar infördes i Micalis, Rabins och Kilians arbete [9]. Viktiga prekursorer till noll kunskapsuppsättningar framträdde i tidigare uppsatser av dessa författare [5,?]. Chase, Healy, Lysyanskaya, Malkin och Reyzin [2] beskriver begreppet merkurära åtaganden, det vill säga åtaganden som kan vara "hårda" eller "mjuka", en abstraktion av den typ av åtaganden som används i Micali-Rabin-Kilian konstruktion, och visar att alla mercurial åtagandesystem kan användas för att bygga noll-kunskap databaser. Nyligen utfört arbete av Ostrovsky, Rackoff och Smith [11] utökar avsevärt funktionaliteten i databaser med noll-kunskap genom att tillåta mer komplexa frågor (t.ex., "gör databasens stöd skär ett givet strängintervall?"). De utformar först en datastruktur som, utan några sekretessproblem, effektivt hanterar komplexa frågor, och sedan utökar den med nollkunskapsbevis för att ge integritet, bygga noll-kunskap uppsättningar enligt allmänna antaganden. I avsnitt 2 ger vi notation som ska användas i resten av pappret. I avsnitt 3 definierar vi de säkerhetsegenskaper som behövs för updatable noll-kunskapsdatabaser. I avsnitt 4 sammanfattar vi olika primitiva och tidigare arbeten och introducerar begreppet uppdatering av åtaganden. I avsnitt 5, vi ger en konstruktion för transparent updatable noll-kunskap databaser. I avsnitt 6 diskuterar vi effektiviteten i vår konstruktion. Vi avslutar och diskuterar öppna problem i avsnitt 7. 2 Det är möjligt att inte heller kommer att hålla, men det verkar naturligt att vi bör vilja ha en av dessa.
Liskov REF förstärkte den ursprungliga konstruktionen av Micali et al. För att vara updatable.
Updatable Zero-Knowledge Databases
{'venue': 'ASIACRYPT', 'journal': None, 'mag_field_of_study': ['Computer Science']}