Welcome to the resource topic for 2011/532
Title:
Hash Functions Based on Three Permutations: A Generic Security Analysis
Authors: Bart Mennink, Bart Preneel
Abstract:We consider the family of 2n-to-n-bit compression functions that are solely based on at most three permutation executions and on XOR-operators, and analyze its collision and preimage security. Despite their elegance and simplicity, these designs are not covered by the results of Rogaway and Steinberger (CRYPTO 2008). By defining a carefully chosen equivalence relation on this family of compression functions, we obtain the following results. In the setting where the three permutations pi_1, pi_2, pi_3 are selected independently and uniformly at random, there exist at most four equivalence classes that achieve optimal 2^{n/2} collision resistance. Under a certain extremal graph theory based conjecture, these classes are proven optimally collision secure. Additionally, three of these classes allow for finding preimages in 2^{n/2} queries, and only one achieves optimal 2^{2n/3} preimage resistance (with respect to the bounds of Rogaway and Steinberger, EUROCRYPT 2008). Consequently, a compression function is optimally collision and preimage secure if and only if it is equivalent to F(x_1,x_2) = x_1 xor pi_1(x_1) xor pi_2(x_2) xor pi_3(x_1 xor x_2 xor pi_1(x_1)). If the compression function makes three calls to the same random permutation, there does not exist any compression function attaining 2^{n/2} collision resistance: for any scheme, collisions can be found with 2^{2n/5} queries. This result casts some doubt over the existence of any (larger) secure permutation-based compression function built only on XOR-operators and (multiple invocations of) a single permutation.
ePrint: https://eprint.iacr.org/2011/532
Talk: https://www.youtube.com/watch?v=xzgqu0AvTwA
Slides: https://iacr.org/cryptodb/archive/2012/CRYPTO/presentation/6-1-Mennink.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .