Abstrakt. Även om det är väl känt att alla grundläggande privat-nyckel kryptografiska primitiva kan byggas från enkelriktade funktioner, finner svaga antaganden från vilka praktiska implementeringar av sådana primitiva existerar förblir en utmanande uppgift. Mot detta mål introducerar detta dokument idén om en konstant-query svag PRF, en funktion med en hemlig nyckel som är beräkningsmässigt oskiljbar från en verkligt slumpmässig funktion när den utvärderas med ett konstant antal s kända slumpmässiga ingångar, där s kan vara så liten som två. Vi tillhandahåller itererade konstruktioner av (arbitrary-input-long) PRF från konstant-query svaga PRFs som även förbättra effektiviteten i tidigare konstruktioner baserat på det starkare antagandet av en svag PRF (där polynomiskt många utvärderingar är tillåtna). En av våra konstruktioner ger direkt en ny drift med hjälp av en konstant-query svag PRF för IND-CPA symmetrisk kryptering som är i huvudsak lika effektiv som konventionell PRF-baserad motläge kryptering. Dessutom ger våra konstruktioner effektiva driftssätt för nyckelhashfunktioner (såsom MD5 och SHA-1) för att erhålla itererade PRFs (och därmed MACs) som enbart bygger på antagandet att den underliggande komprimeringsfunktionen är en konstant-query svag PRF, vilket är det svagaste antagandet någonsin beaktas i detta sammanhang.
Maurer och Tessaro REF visade hur man konstruerar en PRF från en ännu svagare primitiv-konstant-query svag PRF.
Basing PRFs on Constant-Query Weak PRFs: Minimizing Assumptions for Efficient Symmetric Cryptography
{'venue': 'ASIACRYPT', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}