Feistel Network, som består av en upprepad tillämpning av Feistel Transform, ger en mycket bekväm och populär metod för att utforma "kryptografiskt starka" permutationer från motsvarande "kryptografiskt starka" funktioner. Fram till nu, alla användningar av Feistel Network, inklusive den berömda Luby-Rackoff resultat, förlitar sig kritiskt på a) (pseudo)randomness av runda funktioner, och b) hemlighetsmakeriet (åtminstone några av) de mellanliggande runda värden som visas under Feistel beräkning. Dessutom var ett litet konstant antal Feistelrundor vanligtvis tillräckliga för att garantera säkerheten enligt antagandena a och b. I detta arbete överväger vi flera naturliga scenarier där åtminstone en av ovanstående antaganden inte håller, och visar att ett konstant, eller till och med logaritmiskt antal rundor är bevisligen otillräckliga för att hantera sådana tillämpningar, vilket innebär att en ny analysmetod behövs. På en positiv sida utvecklar vi en ny kombinatorisk förståelse av Feistelnätverk, vilket gör dem tillämpliga på situationer där de runda funktionerna bara är oförutsägbara snarare än (pseudo)random och / eller när de mellanliggande runda värden kan läcka till motståndaren (antingen genom en attack eller eftersom ansökan kräver det). I grund och botten visar våra resultat att i varje sådant scenario är ett superlogaritmiskt antal Feistelrundor nödvändiga och tillräckliga för att garantera säkerheten. Detta förklarar delvis varför praktiska blockchiffer använder betydligt mer än 3-6 omgångar som förutses av de tidigare teoretiska resultaten, och ger också den första teoretiska motiveringen till användningen av Feistel Networks som inte uppfyller antaganden a) eller b) ovan. I synnerhet visar vi att superlogaritmiskt antal Feistel rundor är nödvändigt och tillräckligt för att ge • en stark oförutsägbar permutation (UP) från någon oförutsägbar funktion (UF). • en stark pseudorandom permutation (PRP) från någon pseudorandom funktion (PRF), som förblir säker även om alla runda värden offentliggörs. • en stark kontrollerbar oförutsägbar permutation (VUP) - en ny idé som vi introducerar här - från någon kontrollerbar oförutsägbar funktion (VUF). • en stark kontrollerbar slumpmässig permutation (VRP) - ett nytt begrepp som vi introducerar här - från någon kontrollerbar slumpmässig funktion (VRF, även känd som unik signatur schema). Av oberoende intresse, vår teknik ger en ny domän förlängningsmetod för meddelanden autentisering koder och andra relaterade primitiver, lösa frågan som studerades av An och Bellare i CRYPTO 1999.
Efterföljande arbete av Dodis och Puniya REF studerade andra egenskaper (såsom oförutsägbarhet och verifiablity) av Luby-Rackoff konstruktion när de mellanliggande värdena är kända för angriparen.
Feistel networks made public, and applications
{'venue': 'Advances in Cryptology – EUROCRYPT ’07. LNCS', 'journal': None, 'mag_field_of_study': ['Computer Science']}