{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,11]],"date-time":"2025-12-11T03:23:51Z","timestamp":1765423431627,"version":"build-2065373602"},"reference-count":20,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2023,6,28]],"date-time":"2023-06-28T00:00:00Z","timestamp":1687910400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computation"],"abstract":"<jats:p>The emergence of new embedded system technologies, such as IoT, requires the design of new lightweight cryptosystems to meet different hardware restrictions. In this context, the concept of Finite State Machines (FSMs) can offer a robust solution when using cryptosystems based on finite automata, known as FAPKC (Finite Automaton Public Key Cryptosystems), introduced by Renji Tao. These cryptosystems have been proposed as alternatives to traditional public key cryptosystems, such as RSA. They are based on composing two private keys, which are two FSMs M1 and M2 with the property of invertibility with finite delay to obtain the composed FSM M=M1oM2, which is the public key. The invert process (factorizing) is hard to compute. Unfortunately, these cryptosystems have not really been adopted in real-world applications, and this is mainly due to the lack of profound studies on the FAPKC key space and a random generator program. In this paper, we first introduce an efficient algebraic method based on the notion of a testing table to compute the delay of invertibility of an FSM. Then, we carry out a statistical study on the number of invertible FSMs with finite delay by varying the number of states as well as the number of output symbols. This allows us to estimate the landscape of the space of invertible FSMs, which is considered a first step toward the design of a random generator.<\/jats:p>","DOI":"10.3390\/computation11070125","type":"journal-article","created":{"date-parts":[[2023,6,29]],"date-time":"2023-06-29T00:41:45Z","timestamp":1687999305000},"page":"125","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Algebraic Method for Testing the Invertibility of Finite State Machines"],"prefix":"10.3390","volume":"11","author":[{"given":"Zineb","family":"Lotfi","sequence":"first","affiliation":[{"name":"ANISSE Research Team, Department of Computer Science, Faculty of Sciences, Mohammed V University in Rabat, Rabat BP 1014, Morocco"}]},{"given":"Hamid","family":"Khalifi","sequence":"additional","affiliation":[{"name":"ANISSE Research Team, Department of Computer Science, Faculty of Sciences, Mohammed V University in Rabat, Rabat BP 1014, Morocco"}]},{"given":"Faissal","family":"Ouardi","sequence":"additional","affiliation":[{"name":"ANISSE Research Team, Department of Computer Science, Faculty of Sciences, Mohammed V University in Rabat, Rabat BP 1014, Morocco"}]}],"member":"1968","published-online":{"date-parts":[[2023,6,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/BF02943149","article-title":"Fapkc3: A new finite automaton public key cryptosystem","volume":"12","author":"Tao","year":"1997","journal-title":"J. Comput. Sci. Technol."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1006\/jnca.1997.0057","article-title":"A variant of the public key cryptosystem fapkc3","volume":"20","author":"Tao","year":"1997","journal-title":"J. Netw. Comput. Appl."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"784","DOI":"10.1007\/BF02885019","article-title":"The generalization of public key cryptosystem fapkc4","volume":"44","author":"Tao","year":"1999","journal-title":"Chin. Sci. Bull."},{"key":"ref_4","unstructured":"Amorim, I. (2016). Linear Finite Transducers towards a Public Key Cryptographic System. [Ph.D. Thesis, Faculdade de Ci\u00eancias da Universidade do Porto]."},{"key":"ref_5","unstructured":"Renji, T. (2008). Finite Automata and Application to Cryptography, Springer."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Bao, F., and Igarashi, Y. (1995). Break Finite Automata Public Key Cryptosystem, Springer.","DOI":"10.1007\/3-540-60084-1_70"},{"key":"ref_7","unstructured":"Amorim, I., Machiavelo, A., and Reis, R. (2022, January 23\u201324). Formal power series and the invertibility of finite linear transducers. Proceedings of the Non-Classical Models for Automata and Applications, Fribourg, Switzerland."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Amorim, I., Machiavelo, A., and Reis, R. (August, January 30). Counting equivalent linear finite transducers using a canonical form. Proceedings of the 19th International Conference on Implementation and Application of Automata, CIAA 2014, Giessen, Germany.","DOI":"10.1007\/978-3-319-08846-4_5"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1051\/ita\/2014004","article-title":"On the invertibility of finite linear transducers","volume":"48","author":"Amorim","year":"2014","journal-title":"Rairo-Theor. Inform. Appl."},{"key":"ref_10","unstructured":"Amorim, I., Machiavelo, A., and Reis, R. (2014). Statistical study on the number of injective linear finite transducers. arXiv."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Wagner, F., Schmuki, R., and Wagner, T. (2006). Wolstenholme. Modeling Software with Finite State Machines: A Practical Approach, CRC Press.","DOI":"10.1201\/9781420013641"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1109\/34.55109","article-title":"Invariant image recognition by Zernike moments","volume":"12","author":"Khotanzad","year":"1990","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/s00165-016-0355-5","article-title":"Active learning for extended finite state machines","volume":"28","author":"Cassel","year":"2016","journal-title":"Form. Asp. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1142\/S0129054115400043","article-title":"On the Number of Linear Finite Transducers","volume":"26","author":"Amorim","year":"2015","journal-title":"Int. J. Found. Comput. Sci."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1109\/TSE.1978.231496","article-title":"Testing software design modeled by finite-state machines","volume":"SE-4","author":"Chow","year":"1978","journal-title":"IEEE Trans. Softw. Eng."},{"key":"ref_16","unstructured":"Friedman, A.D., and Menon, P.R. (1971). Fault Detection in Digital Circuits, Prentice-Hall, Inc."},{"key":"ref_17","unstructured":"Sethi, A.V.A.R., and Ullman, J.D. (1986). Compilers: Principles, Techniques, and Tools Reading, Addison-Wksley."},{"key":"ref_18","unstructured":"Bolzmann, G.J. (1990). Design and Validation of Protocols, Prentice-Hall."},{"key":"ref_19","unstructured":"(2023, June 23). The Source Code for the Algorithm. Available online: https:\/\/github.com\/ZinebLotfi\/InvertiblesFSMs."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Keromytis, A.D., and Di Pietro, R. (2013). Security and Privacy in Communication Networks, Proceedings of the 8th International ICST Conference, SecureComm 2012, Padua, Italy, 3\u20135 September 2012, Springer.","DOI":"10.1007\/978-3-642-36883-7"}],"container-title":["Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-3197\/11\/7\/125\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T20:03:08Z","timestamp":1760126588000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-3197\/11\/7\/125"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,28]]},"references-count":20,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2023,7]]}},"alternative-id":["computation11070125"],"URL":"https:\/\/doi.org\/10.3390\/computation11070125","relation":{},"ISSN":["2079-3197"],"issn-type":[{"type":"electronic","value":"2079-3197"}],"subject":[],"published":{"date-parts":[[2023,6,28]]}}}