Annals of Computer Science and Information Systems, Volume 15

DOI: http://dx.doi.org/10.15439/2018F254

Citation: Proceedings of the 2018 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 15, pages 387–390 (2018)

Full text

Abstract. This paper describes an algorithm for creating hash function, resistant for quantum computer. The given approach is based on the problem of solving a system of polynomial equations in integers, where the number of equations is less than the number of unknown parameters. The developed algorithm is parameterized so the result of the hash function depends on several parameters, therefore, it will take considerably longer to select the solution of the task. The avalanche effect is about 50\%, collision is impossible because the task to find a solution of the described system of equations with a degree greater than 3 is algorithmically unsolvable. This hash function was developed for blockchain to ensure its integrity, but it can also be used in any application where a hash function is needed.

References

1. Shor P. W. “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM J. Com., 26:5, 1997, pp. 1484-1509.
2. Bernstein D. J., Buchmann J., Dahmen E. “Post-Quantum Cryptography”. Springer-Verlag Berlin Heidelberg, 2009.
3. M. Ajtai. “Generating Hard Instances of Lattice Problems”. In: 28th ACM Symposium on Theory of Computing, ACM, Philadelphia, USA, 1996, pp. 99–108.
4. L. Carter and M. Wegman. “Universal Classes of Hash Functions”. In: J. Computer and System Sciences, Vol. 18(2), 1979, pp. 143–154.
5. O. Goldreich, H. Krawczyk and M. Luby. “On the existence of pseudorandom generators”. In: SIAM J. on Computing, Vol. 22-6, 1993, pp. 1163–1175.
6. J. Hastad, R. Impagliazzo, L.A. Levin and M. Luby. “A Pseudorandom Generator from any One-way Function”. In: SIAM J. on Computing, Vol. 28 (4), 1999, pp. 1364–1396.
7. A. K. Lenstra, H.W. Lenstra, L. Lov´asz. “Factoring Polynomials with Rational Coefficients”. In: Mathematische Annalen, vol. 261(4), 1982, pages 515–534.
8. C. P. Schnorr. “A more efficient algorithm for a lattice basis reduction”. In: Journal of Algorithms, Vol. 9, 1988, pages 47–62.