Vi studerar verifieringen av set-operationer i modellen för autentiserade datastrukturer, nämligen problemet med kryptografisk kontroll av korrektheten hos outsourcade set-operationer som utförs av en opålitlig server över en dynamisk samling av uppsättningar som ägs (och uppdateras) av en betrodd källa. Vi presenterar ett nytt autentiserat datastruktursystem som gör det möjligt för alla enheter att offentligt kontrollera korrektheten i primitiva uppsättningar operationer som skärningspunkt, union, delmängd och set skillnad. Baserat på en ny utbyggnad av säkerhetsegenskaperna hos bilinear-kartackumulatorer samt på ett primitivt så kallat ackumulationsträd, är vår autentiserade datastruktur den första som uppnår optimal verifiering och bevismässig komplexitet (dvs. endast proportionell mot storleken på frågeparametrarna och svaret), samt optimal uppdateringskomplexitet (dvs. konstant), och utan att bära något extra asymptotiskt utrymme overhead. Frågor (dvs. konstruktion av bevis) är också effektiva, vilket tillför en logaritmisk overhead till den komplexitet som krävs för att beräkna det faktiska svaret. Befintliga system medför däremot höga kommunikations- och kontrollkostnader eller höga lagringskostnader eftersom de återberäknar frågan över autentiska uppgifter eller förkompilerar svar på alla möjliga frågor. Tillämpningar av intresse inkluderar effektiv verifiering av sökordssökning och databasfrågor. Vi baserar säkerheten i våra konstruktioner på det bilinjära q-starka Diffie-Hellman antagandet.
De använder den autentiserade datastrukturen i REF för att kontrollera att de fastställda transaktionerna är korrekta.
N.: Optimal verification of operations on dynamic sets
{'venue': 'CRYPTO 2011. LNCS', 'journal': None, 'mag_field_of_study': ['Computer Science']}