Vi presenterar programvaruarkitekturen och implementeringen av en effektiv datastruktur för dynamisk underhåll av en autentiserad ordbok. De byggstenar i datastrukturen är skip listor och envägs pendlande hash funktioner. Vi presenterar också resultaten av ett preliminärt experiment om datastrukturens prestanda. Tillämpningar av vårt arbete inkluderar certijicate återkallande i offentlig nyckelinfrastruktur och publicering av datainsamlingar på Internet. Vi presenterar programvaruarkitekturen och implementeringen av en effektiv och praktisk datastruktur för dynamisk underhåll av en distribuerad samling av element på ett autentiserat sätt. Tillämpningar av vårt arbete inkluderar certifikatindragning i offentlig nyckelinfrastruktur och autentiserad publicering av datainsamlingar på Internet. Problemet vi tar itu med berör tre parter: en pålitlig källa, en opålitlig katalog och en användare. Källan definierar en ändlig uppsättning S av element som utvecklas med tiden genom införanden och raderingar av element. Katalogen underhåller en kopia av uppsättningen S. Den får tidsstämplade uppdateringar från källan tillsammans med information om uppdateringsautentisering, såsom undertecknade uttalanden om uppdateringen och de aktuella elementen i uppsättningen. Användaren utför medlemsfrågor på uppsättningen S av typen "är element e i uppsättning S?" men istället för att kontakta källan direkt, frågar den katalogen. Katalogen ger användaren ett jalno-svar på frågan tillsammans med svarsautentiseringsinformation, som ger ett bevis på svaret som sammanställts genom att kombinera påståenden som undertecknats av källan. Användaren kontrollerar sedan beviset genom att förlita sig enbart på sitt förtroende för källan och tillgången till offentlig information om källan som gör det möjligt att kontrollera källans signatur. Den datastruktur som används av katalogen för att upprätthålla uppsättningen S, tillsammans med protokollet för frågor och uppdateringar kallas en autentiserad ordbok [ 18, 291. Figur 1 visar en schematisk vy över en autentiserad ordbok. Utformningen av ett autentiserat lexikon bör inriktas på följande mål: låga beräkningskostnader: de beräkningar som utförs internt av varje enhet (källa, katalog och användare) bör vara enkla och snabba. Det minnesutrymme som används av de datastrukturer som stöder beräkningen bör också vara så litet som möjligt.
Goodrich, Tamassia och Schwerin REF presenterar programvaruarkitekturen och genomförandet av en autentiserad ordbok baserad på ovanstående metod.
Implementation of an authenticated dictionary with skip lists and commutative hashing
{'venue': "Proceedings DARPA Information Survivability Conference and Exposition II. DISCEX'01", 'journal': "Proceedings DARPA Information Survivability Conference and Exposition II. DISCEX'01", 'mag_field_of_study': ['Computer Science']}