×

Survey on SAP and its application in public-key cryptography. (English) Zbl 1462.94037

Summary: The concept of the semigroup action problem (SAP) was first introduced by C. J. Monico [Semirings and semigroup actions in public-key cryptography. Notre Dame, IN: University of Notre Dame (PhD Thesis) (2002)]. Monico explained in his paper that the discrete logarithm problem (DLP) can be generalized to SAP. After defining the action problem in a semigroup, the concept was extended using different mathematical structures. In this paper, we discuss the concept of SAP and present a detailed survey of the work which has been done using it in public-key cryptography.

MSC:

94A60 Cryptography
68P25 Data encryption (aspects in computer science)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. E. Atani, S. E. Atani and S. Mirzakuchaki, Public key cryptography using semigroup actions and semirings, J. Discrete Math. Sci. Cryptogr. 11 (2008), no. 4, 437-445. · Zbl 1206.94049
[2] R. Canetti and H. Krawczyk, Analysis of key-exchange protocols and their use for building secure channels, Advances in Cryptology—EUROCRYPT 2001, Lecture Notes in Comput. Sci. 2045, Springer, Berlin (2001), 453-474. · Zbl 0981.94032
[3] A. M. Childs and G. Ivanyos, Quantum computation of discrete logarithms in semigroups, J. Math. Cryptol. 8 (2014), no. 4, 405-416. · Zbl 1304.68050
[4] W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory IT-22 (1976), no. 6, 644-654. · Zbl 0435.94018
[5] R. Ebrahimi Atani, S. Ebrahimi Atani and S. Mirzakuchaki, Public key cryptography based on semimodules over quotient semirings, Int. Math. Forum 2 (2007), no. 49-52, 2561-2570. · Zbl 1136.94004
[6] T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inform. Theory 31 (1985), no. 4, 469-472. · Zbl 0571.94014
[7] A. Kendziorra, Computational aspects of finite simple semirings, Ph.D. thesis, University College Dublin, 2012.
[8] P. H. Kropholler, S. J. Pride, W. A. M. Othman, K. B. Wong and P. C. Wong, Properties of certain semigroups and their potential as platforms for cryptosystems, Semigroup Forum 81 (2010), no. 1, 172-186. · Zbl 1201.94110
[9] G. Maze, Algebraic Methods for Constructing One-way Trapdoor Functions, ProQuest LLC, Ann Arbor, 2003;Thesis (Ph.D.)-University of Notre Dame.
[10] G. Maze, C. Monico and J. Rosenthal, Public key cryptography based on semigroup actions, preprint (2005), https://arxiv.org/abs/cs/0501017v2.
[11] G. Maze, C. Monico and J. Rosenthal, Public key cryptography based on semigroup actions, preprint 2007, https://arxiv.org/abs/cs/0501017v4. · Zbl 1194.94190
[12] G. Maze, C. Monico, J. Rosenthal and J. J. Climent, Public key cryptography based on simple modules over simple rings, in: Proceedings of the 15th International Symposium of the Mathematical Theory of Networks and Systems—MTNS, University of Notre Dame, Paris (2002).
[13] C. J. Monico, Semirings and Semigroup Actions in Public-key Cryptography, ProQuest LLC, Ann Arbor, 2002;Thesis (Ph.D.)-University of Notre Dame.
[14] S. C. Pohlig and M. E. Hellman, An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Trans. Inform. IT-24 (1978), no. 1, 106-110. · Zbl 0375.68023
[15] R. L. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM 21 (1978), no. 2, 120-126. · Zbl 0368.94005
[16] E. Sakalauskas, New digital signature scheme in Gaussian monoid, Informatica (Vilnius) 15 (2004), no. 2, 251-270. · Zbl 1098.68589
[17] E. Sakalauskas, One digital signature scheme in semimodule over semiring, Informatica (Vilnius) 16 (2005), no. 3, 383-394. · Zbl 1090.68035
[18] E. Sakalauskas and T. Burba, Digital signature scheme based on action of infinite ring, Inform. Technol. Control. 31 (2004), no. 2, 10.5755/j01.itc.31.2.11849. · doi:10.5755/j01.itc.31.2.11849
[19] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26 (1997), no. 5, 1484-1509. · Zbl 1005.11065
[20] R. Steinwandt and A. Suárez Corona, Cryptanalysis of a 2-party key establishment based on a semigroup action problem, Adv. Math. Commun. 5 (2011), no. 1, 87-92. · Zbl 1213.94134
[21] A. Stolbunov, Reductionist security arguments for public-key cryptographic scheme based on group action, The Norwegian Information Security Conference, 2009.
[22] I. D. Trendafilov and M. I. Durcheva, Discrete logarithm in finite fields some algorithms for computing new public key cryptosystem, AIP Conf. Proc. 1293 (2010), 10.1063/1.3515599. · doi:10.1063/1.3515599
[23] J. Zumbr̈agel, Public-key cryptography based on simple semirings, Ph.D. thesis, University of Zürich, 2008.
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.