Den offentliga rapporteringsbördan för insamling av information uppskattas till i genomsnitt 1 timme per svar, inklusive tid för översyn av instruktioner, genomsökning av befintliga datakällor, insamling och bevarande av de uppgifter som behövs samt slutförande och översyn av insamlingen av information. Skicka kommentarer om denna kostnadsberäkning eller någon annan aspekt av denna informationsinsamling, inklusive förslag för att minska denna börda, till Washingtons huvudkontor, Direktoratet för informationsverksamhet och rapporter, 1215 Jefferson Davis Highway, Suite 1204, Arlington VA 22202-4302. Respondenterna bör vara medvetna om att utan hinder av någon annan lagbestämmelse får ingen person bli föremål för en påföljd för underlåtenhet att följa en insamling av information om den inte uppvisar ett för närvarande giltigt kontrollnummer för OMB. Nyckelord: Enkelriktade hashkedjor, effektiva konstruktioner, sändningsautentisering. Enkelriktade kedjor är en viktig kryptografisk primitiv i många säkerhetsapplikationer. Lamport föreslog först att använda enkelriktade kedjor för engångsautentisering av lösenord [19]. Därefter föreslog forskarna enkelriktade kedjor som en grundläggande byggsten för digitala kontanter, för att förlänga livstiden för digitala certifikat, för att bygga engångssignaturer, för paketautentisering, etc. Eftersom enkelriktade kedjor är mycket effektiva att verifiera, blev de nyligen allt populärare för att utforma säkerhetsprotokoll för resursbegränsade mobila enheter och sensornätverk, eftersom deras lågdrivna processorer kan beräkna en enkelriktad funktion inom millisekunder, men skulle kräva tiotals sekunder eller upp till minuter för att generera eller verifiera en traditionell digital signatur [6]. Senaste sensornätverk säkerhetsprotokoll således i stor utsträckning använda enkelriktade kedjor för att designa protokoll som skala ner till resurs-konstruerade sensorer [20, 28]. Nyligen föreslog forskarna också en mängd förbättringar av enkelriktade hashkedjor för att göra lagring och åtkomst effektivare [9, 17, 32], eller för att göra installation och verifiering effektivare [16, 20]. I detta dokument presenterar vi två nya konstruktioner för enkelriktade hashkedjor, som avsevärt förbättrar effektiviteten i enkelriktade kedjor. Vår första konstruktion, Sandwich-kedjan, ger en mindre bandbredd overhead för enkelriktade kedjevärden, och möjliggör effektiv verifiering av enkelriktade kedjevärden om det pålitliga enkelriktade kedjevärdet är långt borta. Vår andra konstruktion, Comb Skipchain, har en ny nedre gräns för enkelriktade kedjor när det gäller lagring och traversal overhead. I själva verket tidigare, forskare [9] citera en lägre gräns av log 2 (n) för produkten av per-värde Traversal overhead och minne krav för endimensionella kedjor. Vi visar att man kan uppnå en lägre gräns genom att överväga flerdimensionella kedjor. I synnerhet kräver vår tvådimensionella konstruktion O(log(n) minne och O(1) Traversal overhead, vilket förbättrar på endimensionell gräns. Dessutom är installationskostnaden för enkelriktad kedja däremot endast O(n/ log(n)). Andra fördelar för båda konstruktionerna inkluderar ett snabbare verifieringssteg än de traditionella hashkedjorna ger; en kontrollör kan "ta igen" effektivt, efter att ha missat ett antal tidigare släppta hashvärden (för Sandwich-kedjan); och motstånd mot DoS attacker på autentiseringsvärden. Dessutom beskriver vi fraktala traversala system för våra föreslagna strukturer, vilket sänker de traversala kostnaderna för vår struktur till samma som för den enklare "traditionella" hashkedjan. Vår nya konstruktion är ortogonal till de flesta tidigare föreslagna tekniker, och kan användas tillsammans med tekniker för effektiv installation eller verifiering av enkelriktade kedjor.
I synnerhet Hu et al. REF tillhandahåller två olika konstruktioner av envägs hashkedjor, Sandwich-kedjan och Comb Skipchain, vilket möjliggör snabbare verifiering.
Efficient Constructions for One-way Hash Chains