Kovalchuk L., Oliynykov R., Rodinko M.
Security of Poseidon hash function against non-binary differential and linear attacks

In the paper, we construct security estimations of Poseidon hash function against non-binary linear and differential attacks. We adduce the general parameters for the Poseidon hash function that allow using this hash function in recurrent SNARK-proofs based on MNT-4 and MNT-6 triplets. We also analyse how to choose S-boxes for such function for this choice to be optimal from the point of view of the number of constraints and security. We show how many full rounds are sufficient to guarantee security of such hash function against non-binary linear and differential attacks. We also calculate the number of constraints per bit achieved in the proposed realizations and demonstrate a considerable gain as compared to the Pedersen hash function. © 2021, Springer Science+Business Media, LLC, part of Springer Nature.

Keywords: constraints, non-binary linear and differential cryptanalysis, Poseidon hash function, SNARK, Computer science, Cybernetics, Differential attacks, Non-binary, S-boxes, Security estimation, Hash functions

Побудовано оцінки стійкості геш-функції Poseidon до небінарних лінійних і різницевих атак. Визначено загальні параметри для геш-функції Poseidon, які забезпечують можливість її використання у рекурентних SNARK-доведеннях, що базуються на триплетах MNT-4 і MNT-6. Проаналізовано, як потрібно обирати S-блоки для цієї геш-функції, щоб цей вибір був оптимальним з погляду як стійкості, так і кількості констрейнтів. Показано, яка кількість раундів є достатньою, щоб гарантувати стійкість такої геш-функції до небінарних лінійних і різницевих атак, та обчислено кількість констрейнтів на біт інформації для запропонованих реалізацій цієї функції з демонстрацією суттєвого виграшу у порівнянні з геш-функцією Педерсена.

PDF

Cite:
Kovalchuk, Oliynykov, Rodinko. (2021). Security of Poseidon hash function against non-binary differential and linear attacks. Cybernetics and Systems Analysis, 57 (2), 115–127. doi: https://doi.org/10.1007/s10559-021-00352-y http://jnas.nbuv.gov.ua/article/UJRN-0001221027