access icon free Security analysis of KAP based on enhanced MPF

© The Institution of Engineering and Technology
Received 04/07/2019, Accepted 27/01/2020, Revised 15/01/2020, Published 31/01/2020

In the previous study, authors proved that inversion of enhanced matrix power function (MPF), introduced as conjectured one-way function, is a nondeterministic polynomial time (NP)-complete problem. Furthermore, a key agreement protocol (KAP), the security of which relies on the inversion of this function, was previously proposed. The problem is that the application of MPF can yield weak keys under the linearisation attack. In this study, the authors perform a security analysis of the proposed KAP and give recommendations to avoid weak keys. Their method relies on the conjecture that enhanced MPF is an almost one-to-one function when entries of power matrices are bound to a certain range. Their result is a security parameter definition and its secure value determination using numerical simulation. On the basis of the obtained result, they estimate memory requirements for storing public parameter and keys.

Inspec keywords: computational complexity; cryptographic protocols; matrix algebra

Other keywords: public parameter; security parameter definition; linearisation attack; NP-complete problem; enhanced matrix power function; KAP; security analysis; power matrices; conjectured one-way function; enhanced MPF; key agreement protocol; secure value determination

Subjects: Cryptography; Protocols; Data security; Algebra; Algebra

References

    1. 1)
      • 2. Kumari, S., Li, X., Wu, F., et al: ‘A user-friendly mutual authentication and key agreement scheme for wireless sensor networks using chaotic maps’, Future Gener. Comput. Syst., 2016, 63, pp. 56–75.
    2. 2)
      • 20. Wolf, C., Preneel, B.: ‘Asymmetric cryptography: hidden field equations’.
    3. 3)
      • 16. Styan, G.P.H.: ‘Hadamard products and multivariate statistical analysis’, Linear Algebr. Appl., 1973, 6, pp. 217–240.
    4. 4)
      • 7. Sakalauskas, E., Tvarijonas, P., Raulynaitis, A.: ‘Key agreement protocol (KAP) using conjugacy and discrete logarithm problems in group representation level’, Informatica, 2007, 18, (1), pp. 115–124.
    5. 5)
      • 23. Courtois, N., Klimov, A., Patarin, J., et al: ‘Efficient algorithms for solving overdefined systems of multivariate polynomial equations’. Advances in Cryptology – EUROCRYPT 2000, Berlin, Heidelberg, 2000, pp. 392–407.
    6. 6)
      • 13. Sakalauskas, E.: ‘Enhanced matrix power function for cryptographic primitive construction’, Symmetry (Basel), 2018, 10, (2), p. 43.
    7. 7)
      • 14. Sakalauskas, E., Mihalkovich, A.: ‘MPF problem over modified medial semi-group is NP-complete’, Symmetry (Basel), 2018, 10, (11), p. 571.
    8. 8)
      • 8. Jacobs, K.: ‘A survey of modern mathematical cryptology’, 2011.
    9. 9)
      • 5. Wagner, N.R., Magyarik, M.R.: ‘A public-key cryptosystem based on the word problem’. Workshop on the Theory and Application of Cryptographic Techniques, Paris, France, 1984, pp. 19–36.
    10. 10)
      • 17. Inassaridze, N., Kandelaki, T., Ladra, M.: ‘Categorical interpretations of some key agreement protocols’, J. Math. Sci., 2013, 195, (4), pp. 439–444.
    11. 11)
      • 12. Eftekhari, M.: ‘A Diffie–Hellman key exchange protocol using matrices over non-commutative rings’, Groups Complexity Cryptol., 2012, 4, (1), pp. 167–176.
    12. 12)
      • 21. Buchberger, B.: ‘Gröbner bases: an algorithmic method in polynomial ideal theory’, in Bose, N.K. (Eds.): ‘Multidimensional systems theory’ (Springer, The Netherlands, 1985), pp. 184–232.
    13. 13)
      • 11. Kalka, A.: ‘Non-associative public-key cryptography’, Algebra Comput. Sci., 2016, 677, p. 85.
    14. 14)
      • 6. McEliece, R.J.: ‘A public-key cryptosystem based on algebraic’, 1978.
    15. 15)
      • 10. Sracic, M.: ‘Quantum circuits for matrix multiplication’.
    16. 16)
      • 18. Schaefer, T.J.: ‘The complexity of satisfiability problems’. Proc. Tenth Annual ACM Symp. Theory of Computing ACM, San Diego, CA, USA, 1978, pp. 216–226.
    17. 17)
      • 15. Gray, R.M.: ‘Toeplitz and circulant matrices: a review’, Found. Trends Commun. Inf. Theory, 2006, 2, (3), pp. 155–239.
    18. 18)
      • 24. Courtois, N., Goubin, L., Meier, W., et al: ‘Solving underdefined systems of multivariate quadratic equations’. Public Key Cryptography, Berlin, Heidelberg, 2002, pp. 211–227.
    19. 19)
      • 3. Wu, F., Xu, S., Kumari, X., et al: ‘An efficient authentication and key agreement scheme for multi-gateway wireless sensor networks in IoT deployment’, J. Netw. Comput. Appl., 2017, 89, pp. 72–85.
    20. 20)
      • 1. Shor, P.W.: ‘Polynomial time algorithms for prime factorization and discrete logarithms on a quantum computer’, SIAM Rev., 1999, 41, (2), pp. 303–332.
    21. 21)
      • 22. Kipnis, A., Shamir, A.: ‘Cryptanalysis of the HFE public key cryptosystem by relinearization’. Advances in Cryptology – CRYPTO’ 99, Santa Barbara, CA, USA, 1999, pp. 19–30.
    22. 22)
      • 25. Barker, E.: ‘NIST special publication 800–57 part 1, revision 4’, 2016.
    23. 23)
      • 9. Ottaviani, V., Zanoni, A., Regoli, M.: ‘Conjugation as public key agreement protocol in mobile cryptography’. 2010 Int. Conf. Security and Cryptography (SECRYPT), Athens, Greece, 2010, pp. 1–6.
    24. 24)
      • 4. Li, X., Ibrahim, M.H., Kumari, S., et al: ‘Anonymous mutual authentication and key agreement scheme for wearable sensors in wireless body area networks’, Comput. Netw., 2017, 129, pp. 429–443.
    25. 25)
      • 19. Patarin, J.: ‘Hidden fields (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms’. Advances in Cryptology – EUROCRYPT ‘96, Berlin, Heidelberg, 1996, pp. 33–48.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2019.0333
Loading

Related content

content/journals/10.1049/iet-ifs.2019.0333
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading