On a family of preimage-resistant functions. (English) Zbl 1287.94052
Summary: 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 permutation 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.
MSC:
| 94A60 | Cryptography |
| 11T06 | Polynomials over finite fields |
| 68P25 | Data encryption (aspects in computer science) |
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. · Zbl 0962.68055 |
| [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. · Zbl 0725.94002 · doi:10.1007/BF00196789 |
| [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. |
| [4] | AUMASSON, J.-P.: Cryptanalysis of a hash function based on norm form equations, Cryptologia 33 (2009), 1-4. · Zbl 1165.94315 · doi:10.1080/01611190802306793 |
| [5] | BERNSTEIN, D. J.-LANGE, T.: Type-II optimal polynomial bases, · Zbl 1230.12001 · doi:10.1007/978-3-642-13797-6_4 |
| [6] | BERLEKAMP, E. R.: Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713-715. · Zbl 0247.12014 · doi:10.2307/2004849 |
| [7] | BÉRCZES, A.-KÖ DMÖN, J.-PETH\Acute\Acute O, A.: A one-way function based on norm form equations, Period. Math. Hungar. 49 (2004), 1-13. · Zbl 1061.94046 · doi:10.1023/B:MAHU.0000040535.45427.38 |
| [8] | BÉRCZES, A.-JÁRÁSI, I.: An application of index forms in cryptography, Period. Math. Hungar. 58 (2008), 35-45. · Zbl 1199.94060 · doi:10.1007/s10998-009-9035-8 |
| [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 , Lect. Notes in Comput. Sci., Vol. 1294, Springer, Berlin, 1997, pp. 385-394. · Zbl 0888.94011 |
| [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. · Zbl 1163.11329 · doi:10.1016/j.ffa.2005.03.003 |
| [11] | CANTOR, D. G.-ZASSENHAUS, H.: A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), 587-592. · Zbl 0493.12024 · doi:10.2307/2007663 |
| [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. · Zbl 0824.68038 |
| [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 , Lecture Notes in Comput. Sci., Vol. 4004, Springer, Berlin, 2006, pp. 165-182, · Zbl 1140.94331 · doi:10.1007/11761679_11 |
| [14] | GOLDREICH, O.-LEVIN, L.-NISAN, N.: On constructing 1-1 one-way functions, ECCC, TR-95-029, 6/25/95, 1995. · Zbl 1343.94056 |
| [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. · Zbl 1231.68037 · doi:10.1109/12.257715 |
| [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. · Zbl 0939.68036 · doi:10.1006/jcss.1998.1613 |
| [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 , ACM Press, New York, NY, 2005, pp. 208-215. · Zbl 1356.11092 · doi:10.1145/1073884.1073914 |
| [18] | LANG, S.-WEIL, A.: The number of points of varieties in finite fields, Amer. J. Math. 76 (1954), 819-827. · Zbl 0058.27202 · doi:10.2307/2372655 |
| [19] | LIDL, R.-NIEDERREITER, H.: Finite Fields , Encyclopedia Math. Appl., Vol. 20, Cambridge University Press, Cambridge, 1997. |
| [20] | MASSEY, J. L.-OMURA, J. K.: Computational Method and Apparatus for Finite Field Arithmetic. US Patent No. 4,587,627, 1986. |
| [21] | MENEZES, A. J.-VAN OORSCHOT, P. C.-VANSTONE, S.: Handbook of Applied Cryptography. CRC Press, 1997. |
| [22] | MERKLE, R.C.: A fast software one-way hash function, J. Cryptology 3 (1990), 43-58. · Zbl 0705.68022 · doi:10.1007/BF00203968 |
| [23] | PAPADIMITRIOU, C. H.: Computational Complexity. Addison-Wesley Publ. Comp., Reading, MA, 1994. · Zbl 0833.68049 |
| [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. · Zbl 1067.94558 |
| [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 , Lecture Notes in Comput. Sci., Vol. 3017, Springer, Berlin, 2004, pp. 371-388. · Zbl 1079.68560 · doi:10.1007/b98177 |
| [26] | SCHINZEL, A.: On reducible trinomials, Dissertationes Math. (Rozprawy Mat.) 329 (1993); errata, Acta Arith. 73 (1995), 399-400. · Zbl 0839.12001 |
| [27] | SCHINZEL, A.: On reducible trinomials. II, Publ. Math. Debrecen 56 (2000), 575-608. · Zbl 0960.12001 |
| [28] | SCHINZEL, A.: On reducible trinomials. III, Period. Math. Hungar. 43 (2001), 43-69. · Zbl 1026.12003 · doi:10.1023/A:1015277414179 |
| [29] | SCHMIDT, W. M.: A lower bound for the number of solutions of equations over finite fields, J. Number Theory 6 (1974), 448-480. · Zbl 0298.12010 · doi:10.1016/0022-314X(74)90043-2 |
| [30] | SCHNEIER, B.: Applied Cryptography. John Wiley & Sons, New York, NY, 1996. · Zbl 0883.94001 |
| [31] | SHPARLINSKI, I.: Number Theoretic Methods in Cryptography. Complexity Lower Bounds, in: Progr. Comput. Sci. Appl. Logic, Vol. 17, Birkhäuser Verlag, Basel, 1999. · Zbl 0912.11057 |
| [32] | SUN, Q.: A kind of trap-door one-way function over algebraic integers, J. Sichuan Univ., Nat. Sci. Ed. 1986 (1986), 22-27. · Zbl 0598.94007 |
| [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. · Zbl 1231.68042 · doi:10.1109/12.902754 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
