UDC 681.3.06:006.354
1 National Technical University of Ukraine
“Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv, IOHK, Hong Kong
 lusi.kovalchuk@gmail.com
|
2 V.N. Karazin Kharkiv National University, Kharkiv National University of Radio Electronics, IOHK, Hong Kong
roliynykov@gmail.com
|
3 V.N. Karazin Kharkiv National University, Kharkiv Ukraine, IOHK, Hong Kong
m.rodinko@gmail.com
|
|
SECURITY OF POSEIDON HASH FUNCTION AGAINST NON-BINARY
DIFFERENTIAL AND LINEAR ATTACKS
Abstract. In this work we build the 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 analysed 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 also showed how many full rounds is sufficient to guarantee security of such hash function against non-binary linear and differential attacks and calculated the number of constraints per bit that is achieved in the proposed realizations demonstrating a considerable gain was demonstrated, as compared to the Pedersen hash function.
Keywords: SNARK, constraints, Poseidon hash function, non-binary linear and differential cryptanalysis.
FULL TEXT
REFERENCES
- Ben-Sasson E., Bentov I., Horesh Y., Riabzev M. Scalable, transparent, and post-quantum secure computational integrity. IACR Cryptology ePrint Archive. 2018. URL: https://eprint.iacr.org/2018/046.pdf.
- Groth J. On the size of pairing-based non-interactive arguments. Proc. Advances in Cryptology — EUROCRYPT 2016. (8–12 May 2016, Vienna, Austria). Vienna, 2016. LNCS. Vol. 9666, P. 305–326. https://doi.org/10.1007/978-3-662-49896-5_11.
- Parno B., Howell J., Gentry C., Raykova M. Pinocchio: nearly practical verifiable computation. Proc. IEEE Symposium on Security and Privacy. (19–22 May 2013, Berkeley, CA, USA). Berkeley, 2013. P. 238–252. https://doi.org/10.1109/SP.2013.47.
- Hopwood D., Bowe S., Hornby T., Wilcox N. Zcash protocol specification: Version 2020.1.15 [Overwinter+Sapling+Blossom+Heartwood+Canopy]. Tech. rep., Electric Coin Company. 2020. URL: https://github.com/zcash/zips/blob/master/protocol/protocol.pdf.
- Grassi L., Kales D., Khovratovich D., Roy A., Rechberger C., Schofnegger M. Starkad and Poseidon: New hash functions for zero knowledge proof systems, IACR Cryptology ePrint Archive. 2019. URL: https://eprint.iacr.org/2019/458.pdf.
- Bertoni G., Joan D., Michal P., Gilles V.A. Cryptographic sponge functions. 2011: 93 p. URL: https://keccak.team/files/CSF-0.1.pdf.
- Grassi L., Lftenegger R., Rechberger C., Rotaru D., Schofnegger M. On a generalization of substitution-permutation networks: the HADES design strategy. IACR Cryptology ePrint Archive. 2019. URL: https://eprint.iacr.org/2019/1107.pdf.
- Abdelraheem M.A., gren M., Beelen P., and Leander G. On the distribution of linear biases: Three instructive examples. Proc. Advances in Cryptology — CRYPTO 2012. (19–23 August 2012, Santa Barbara, CA, USA). Santa Barbara, 2012. LNCS. Vol. 7417. P. 50–67. https://doi.org/ 10.1007/978-3-642-32009-5_4.
- Baigneres T., Stern J., Vaudenay S. Linear cryptanalysis of non binary ciphers. Proc. 14th International Workshop, SAC 2007. (16-17 August 2007, Ottawa, Canada). Ottawa, 2007. LNCS. Vol. 4876. P. 184–211. https://doi.org/10.1007/978-3-540-77360-3_13.
- Miyaji A., Nakabayashi M., Takano Sh. New explicit conditions of elliptic curve traces for FR-reduction. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. 2001. Vol. E84-A, N 5. P. 1234–1243. URL: http://citeseerx.ist.psu.edu/viewdoc/ download?doi=10.1.1.20.8113&rep=rep1&type=pdf.
- Constructing optimal pairing-friendly curves. Coinlist [online]. URL: https://coinlist.co/build/ coda/pages/theory.
- Bertoni G., Daemen J., Peeters M., Assche G.V. On the indifferentiability of the sponge construction. Proc. Advances in Cryptology — EUROCRYPT 2008. (13-17 April 2008, Istanbul, Turkey) Istanbul, 2008. LNCS. Vol. 4965. P. 181–197. https://doi.org/10.1007/978-3-540-78967-3_11.
- Lai X., Massey J.L., Murphy S. Markov ciphers and differential cryptanalysis. Proc. Advances in Cryptology — EUROCRYPT’91. (8–11 April 1991, Brighton, UK). Brighton, 1991. Vol. 547. P. 17–38. https://doi.org/10.1007/3-540-46416-6_2.
- Youssef A.M., Mister S., Tavares S.E.: On the design of linear transformations for substitution permutation encryption networks. Workshop on Selected Areas of Cryptography (SAC’96): Workshop Record. 1997. P. 40–48. URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.1208&rep=rep1&type=pdf.
- Vaudenay S. On the security of CS-cipher. Proc. 6th International Workshop, FSE’99. (24–26 March 1999, Rome, Italy). Rome, 1999. P. 260–274. https://doi.org/10.1007/3-540-48519-8_19.
- Nyberg K. Differentially uniform mappings for cryptography. Proc. Advances in Cryptology — EUROCRYPT ’93. (23–27 May 1993, Lofthus, Norway). Lofthus, 1993. LNCS. Vol. 765. P. 55–64 (1994). https://doi.org/10.1007/3-540-48285-7_6.
- Lidl R., Niederreiter H. Introduction to finite fields and their applications. UK: Cambridge University Press, 1994. https://doi.org/10.1017/CBO9781139172769.
- Kovalchuk L.V. Upper-bound estimation of the average probabilities of integer-valued differentials in the composition of key adder, substitution block, and shift operator. Cybernetics and Systems Analysis. 2010. Vol. 46, N 6. P. 936–944. https://doi.org/10.1007/s10559-010-9274-2.
- Kovalchuk L.V., Bezditnyi V.T. Upper bounds for the average probabilities of difference characteristics of block ciphers with alternation of Markov transformations and generalized Markov transformations. Cybernetics and Systems Analysis. 2014. Vol. 50, Iss. 3. P. 386–393. https://doi.org/10.1007/s10559-014-9627-3.
- Alekseychuk A.N., Kovalchuk L.V., Shevtsov A.S., Yakovliev S.V. Cryptographic properties of a new national encryption standard of Ukraine. Cybernetics and Systems Analysis. 2016. Vol. 52, Iss. 3. P. 351–366. https://doi.org/10.1007/s10559-016-9835-0.
