Abstrakt. Historia oberoende datastrukturer, som presenteras av Micciancio, är datastrukturer som har en stark säkerhetsfastighet: även om en inkräktare lyckas få en kopia av datastrukturen, minneslayouten av strukturen ger ingen ytterligare information om datastrukturen utöver dess innehåll. I synnerhet är historiken över de operationer som tillämpas på strukturen inte synlig i sin minneslayout. Naor och Teague föreslog en starkare uppfattning om historia oberoende där inkräktaren kan bryta sig in i systemet flera gånger utan att märkas och fortfarande få någon ytterligare information från läsa minnet layout av datastrukturen. En öppen fråga som ställdes av Naor och Teague är om dessa två begrepp är lika svåra att få tag på. I detta dokument ger vi en separation mellan de två kraven för jämförelsebaserade algoritmer. Vi visar mycket starka lägre gränser för att få den starkare uppfattningen om historia oberoende för en stor klass av datastrukturer, bland annat, högen och kö abstrakta datastrukturer. Vi tillhandahåller också kompletterande övre gränser som visar att högens abstrakta datastruktur kan göras svagt historikoberoende i jämförelsemodellen utan att ådra sig några extra (asymptotiska) kostnader för någon av dess operationer. (Ett liknande resultat är lätt för kön.) Således får vi den första åtskillnaden mellan de två uppfattningarna om historiens oberoende. Glappet vi får är exponentiellt: vissa operationer kan utföras i logaritmisk tid (eller till och med i konstant tid) med den svagare denitionen, men kräver linjär tid med den starkare denitionen.
Buchbinder m.fl. REF fick första gången en komplexitetsseparation mellan svaga och starka begrepp om historiska oberoende datastrukturer (t.ex. för både högar och köer).
Lower and Upper Bounds on Obtaining History Independence
{'venue': 'CRYPTO', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}