On a family of preimage-resistant functions

Bérczes, Attila; Folláth, János; Pethő, Attila

doi:10.2478/v10127-010-0028-3

Abstract

In the present paper we define a new hash function, based on inhomogeneous polynomials. First we define a large family of polynomials over finite fields and we prove that the members of this family are nearly permutational polynomials. Then we define a subfamily of the above family, such that the elements in the subfamily are easy to evaluate. We prove that (working in a large enough finite field) finding a preimage by chance of such a function is computationally infeasible, and we mention that methods for solving the equation corresponding to the preimage problem for such polynomials are also out of reach.

References

[1] AJTAI,M.-DWORK, C.: A public-key cryptosystem with worst-case/average-case equivalence, in: Proc. of the 29th Annual ACM Symposium on Theory of Computing- -STOC ’97, El Paso, TX, 1997, ACM Press, New York, NY, 1999, pp. 284-293.10.1145/258533.258604
Search in Google Scholar
[2] AGNEW, G. B.-MULLIN, R. C.-ONYSZCHUK, I. M.-VANSTONE, S. A.: An im- plementation for a fast public-key cryptosystem, J. Cryptology 3 (1991), 63-79.10.1007/BF00196789
Search in Google Scholar
[3] AGNEW, G. B.-MULLIN, R. C.-VANSTONE, S. A.: An implementation of elliptic curve cryptosystems over F2155, IEEE J. Selected Areas in Comm. 11 (1993), 804-813.10.1109/49.223883
Search in Google Scholar
[4] AUMASSON, J.-P.: Cryptanalysis of a hash function based on norm form equations, Cryptologia 33 (2009), 1-4.10.1080/01611190802306793
Search in Google Scholar
[5] BERNSTEIN, D. J.-LANGE, T.: Type-II optimal polynomial bases, http://eprint.iacr.org/2010/069. 10.1007/978-3-642-13797-6_4
Search in Google Scholar
[6] BERLEKAMP, E. R.: Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713-715.10.1090/S0025-5718-1970-0276200-X
Search in Google Scholar
[7] B´ ERCZES, A.-K¨O DM¨ON, J.-PETH˝O, A.: A one-way function based on norm form equations, Period. Math. Hungar. 49 (2004), 1-13.10.1023/B:MAHU.0000040535.45427.38
Search in Google Scholar
[8] B´ERCZES, A.-J´AR´ASI, I.: An application of index forms in cryptography, Period. Math. Hungar. 58 (2008), 35-45.10.1007/s10998-009-9035-8
Search in Google Scholar
[9] BUCHMANN, J.-PAULUS, S.: A one way function based on ideal arithmetic in number fields, in: Advances in Cryptology-CRYPTO ’97, Proc. of the 17th Annual International Cryptology Conference, Santa Barbara, CA, USA, 1997 (B. S. Kaliski, jr., ed.), Lect. Notes in Comput. Sci., Vol. 1294, Springer, Berlin, 1997, pp. 385-394.
Search in Google Scholar
[10] CAFURE, A.-MATERA, G.: Improved explicit estimates on the number of solutions of equations over a finite field, Finite Fields Appl. 12 (2006), 155-185.10.1016/j.ffa.2005.03.003
Search in Google Scholar
[11] CANTOR, D. G.-ZASSENHAUS, H.: A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), 587-592.10.1090/S0025-5718-1981-0606517-5
Search in Google Scholar
[12] CHAO, L. R.-LIN, Y. C.: Associative one-way function and its significances to crypto- graphics, Internat. J. Inform. Management. Sci. 5 (1994), 53-59.
Search in Google Scholar
[13] CONTINI, S.-LENSTRA, A. K.-STEINFELD, R.: VSH, an efficient and provable collision-resistant hash function, in: Advances in Cryptology-EUROCRYPT ’06, Proc. of the 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, 2006 (S. Vaudenay, ed.), Lecture Notes in Comput. Sci., Vol. 4004, Springer, Berlin, 2006, pp. 165-182,10.1007/11761679_11
Search in Google Scholar
[14] GOLDREICH, O.-LEVIN, L.-NISAN, N.: On constructing 1-1 one-way functions, ECCC, TR-95-029, 6/25/95, 1995.
Search in Google Scholar
[15] HASAN, M. A.-WANG, M. Z.-BHARGAVA, V. K.: A modified Massey-Omura parallel multiplier for a class of finite fields, IEEE Trans. Computers, Vol. 42, Washington, DC, 1993, pp. 1278-1280.10.1109/12.257715
Search in Google Scholar
[16] HEMASPAANDRA, L. A.-ROTHE, J.: Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory, J. Comput. System Sci. 58 (1999), 648-659.10.1006/jcss.1998.1613
Search in Google Scholar
[17] KALTOFEN, E.-KOIRAN, P.: On the complexity of factoring bivariate supersparse (lacunary) polynomials, in: Proc. of the 2005 International Symposium on Symbolic and Algebraic Computation-ISSAC ’05, Beijing, China, 2005 (M. Kauers, ed.), ACM Press, New York, NY, 2005, pp. 208-215.10.1145/1073884.1073914
Search in Google Scholar
[18] LANG, S.-WEIL, A.: The number of points of varieties in finite fields, Amer. J. Math. 76 (1954), 819-827.10.2307/2372655
Search in Google Scholar
[19] LIDL, R.-NIEDERREITER, H.: Finite Fields (2nd ed.), Encyclopedia Math. Appl., Vol. 20, Cambridge University Press, Cambridge, 1997.
Search in Google Scholar
[20] MASSEY, J. L.-OMURA, J. K.: Computational Method and Apparatus for Finite Field Arithmetic. US Patent No. 4,587,627, 1986.
Search in Google Scholar
[21] MENEZES, A. J.-VAN OORSCHOT, P. C.-VANSTONE, S.: Handbook of Applied Cryptography. CRC Press, 1997.
Search in Google Scholar
[22] MERKLE, R.C.: A fast software one-way hash function, J. Cryptology 3 (1990), 43-58.10.1007/BF00203968
Search in Google Scholar
[23] PAPADIMITRIOU, C. H.: Computational Complexity. Addison-Wesley Publ. Comp., Reading, MA, 1994.
Search in Google Scholar
[24] REYHANI-MASOLEH, A.-HASAN, M. A.: Fast normal basis multiplication using general purpose processors, IEEE Trans. Computers, Vol. 52, Washington, DC, 2003, pp. 1379-1390.10.1109/TC.2003.1244936
Search in Google Scholar
[25] ROGAWAY, P.-SHRIMPTON, T.: Cryptographic hash-function basics: definitions, im- plications, and separations for preimage resistance, second-preimage resistance, and col- lision resistance, in: Fast Software Encryption-FSE ’04, 11th International Workshop, Delhi, India, 2004 (B. Roy et al., eds.), Lecture Notes in Comput. Sci., Vol. 3017, Springer, Berlin, 2004, pp. 371-388.
Search in Google Scholar
[26] SCHINZEL, A.: On reducible trinomials, Dissertationes Math. (Rozprawy Mat.) 329 (1993); errata, Acta Arith. 73 (1995), 399-400.
Search in Google Scholar
[27] SCHINZEL, A.: On reducible trinomials. II, Publ. Math. Debrecen 56 (2000), 575-608.10.5486/PMD.2000.2307
Search in Google Scholar
[28] SCHINZEL, A.: On reducible trinomials. III, Period. Math. Hungar. 43 (2001), 43-69.10.1023/A:1015277414179
Search in Google Scholar
[29] SCHMIDT, W. M.: A lower bound for the number of solutions of equations over finite fields, J. Number Theory 6 (1974), 448-480.10.1016/0022-314X(74)90043-2
Search in Google Scholar
[30] SCHNEIER, B.: Applied Cryptography. John Wiley & Sons, New York, NY, 1996.
Search in Google Scholar
[31] SHPARLINSKI, I.: Number Theoretic Methods in Cryptography. Complexity Lower Bounds, in: Progr. Comput. Sci. Appl. Logic, Vol. 17, Birkh¨auser Verlag, Basel, 1999.
Search in Google Scholar
[32] SUN, Q.: A kind of trap-door one-way function over algebraic integers, J. Sichuan Univ., Nat. Sci. Ed. 1986 (1986), 22-27.
Search in Google Scholar
[33] SUNAR, B.-KOC, C. K.: An efficient optimal normal basis type II multiplier, IEEE Trans. Computers, Vol. 50, Washington, DC, 2001, pp. 83-88.10.1109/12.902754
Search in Google Scholar

On a family of preimage-resistant functions

Abstract

Paradigm

My account