How do you find the inverse degree of a hash function?

Question

I am trying to learn cryptanalysis on the Keccak hash function. One of the papers on zero sum distinguishers talks about Keccak having inverse degree of 3.

I am unable to figure this out: how do you get an inverse degree of 3? For example one of the permutations Chi in Keccak does the multiplication in GF(2). So I would guess that means the image transformation for Keccak has degree 2, but am unable to figure out how they derive degree 3 for preimage or inverse or going backwards.

If someone can point me to a resource, that would be of great help, since I am unable to find one.

score 5 · Accepted Answer · answered Jun 26 '13 at 07:29

5

Trying to express the inverse of the non-linear Chi fonction of Keccak as a multivariate polynomial of the bits of the state will yield a degree 3 polynomial.

How to derive such inverse is explained in section 6.6.2 of Joan Daemen PhD thesis as stated page 15 of http://keccak.noekeon.org/Keccak-reference-3.0.pdf

answered Jun 26 '13 at 07:29

Alexandre Yamajako

1,074
6
6

Thanks Alexandre, for pointing that out. I should read the documents more carefully. And apologies for late reply. – Soham Jun 29 '13 at 14:08

How do you find the inverse degree of a hash function?

1 Answers1