{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:26:43Z","timestamp":1760243203019,"version":"build-2065373602"},"reference-count":22,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2014,3,19]],"date-time":"2014-03-19T00:00:00Z","timestamp":1395187200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Multivariate quadratic (MQ) cryptography requires the use of long public and private keys to ensure a sufficient security level, but this is not favorable to embedded systems, which have limited system resources. Recently, various approaches to MQ cryptography using reduced public keys have been studied. As a result of this, at CHES2011 (Cryptographic Hardware and Embedded Systems, 2011), a small public key MQ scheme, was proposed, and its feasible implementation on an embedded microprocessor was reported at CHES2012. However, the implementation of a small private key MQ scheme was not reported. For efficient implementation, random number generators can contribute to reduce the key size, but the cost of using a random number generator is much more complex than computing MQ on modern microprocessors. Therefore, no feasible results have been reported on embedded microprocessors. In this paper, we propose a feasible implementation on embedded microprocessors for a small private key MQ scheme using a pseudo-random number generator and hash function based on a block-cipher exploiting a hardware Advanced Encryption Standard (AES) accelerator. To speed up the performance, we apply various implementation methods, including parallel computation, on-the-fly computation, optimized logarithm representation, vinegar monomials and assembly programming. The proposed method reduces the private key size by about 99.9% and boosts signature generation and verification by 5.78% and 12.19% than previous results in CHES2012.<\/jats:p>","DOI":"10.3390\/s140305441","type":"journal-article","created":{"date-parts":[[2014,3,19]],"date-time":"2014-03-19T13:33:16Z","timestamp":1395235996000},"page":"5441-5458","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Small Private Key MQPKS on an Embedded Microprocessor"],"prefix":"10.3390","volume":"14","author":[{"given":"Hwajeong","family":"Seo","sequence":"first","affiliation":[{"name":"Computer Engineering, Pusan National University, Pusan 609-735, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jihyun","family":"Kim","sequence":"additional","affiliation":[{"name":"Computer Engineering, Pusan National University, Pusan 609-735, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jongseok","family":"Choi","sequence":"additional","affiliation":[{"name":"Computer Engineering, Pusan National University, Pusan 609-735, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Taehwan","family":"Park","sequence":"additional","affiliation":[{"name":"Computer Engineering, Pusan National University, Pusan 609-735, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhe","family":"Liu","sequence":"additional","affiliation":[{"name":"Laboratory of Algorithmics, Cryptology and Security, University of Luxembourg, 6 Rue RichardCoudenhove-Kalergi, Luxembourg L\u20131359, Luxembourg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Howon","family":"Kim","sequence":"additional","affiliation":[{"name":"Computer Engineering, Pusan National University, Pusan 609-735, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2014,3,19]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1090\/S0025-5718-1987-0866109-5","article-title":"Elliptic curve cryptosystems","volume":"48","author":"Koblitz","year":"1987","journal-title":"Math. Comput."},{"key":"ref_2","unstructured":"Miller, V.S. (1986). Advances in Cryptology\u2014CRYPTO85 Proceedings, Springer."},{"key":"ref_3","unstructured":"Ding, J., and Schmidt, D. (2006). Advances in Information Security, Citeseer."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1016\/j.comcom.2010.05.013","article-title":"Tinypbc: Pairings for authenticated identity-based non-interactive key distribution in sensor networks","volume":"34","author":"Oliveira","year":"2011","journal-title":"Comput. Commun."},{"key":"ref_5","unstructured":"Braeken, A., Wolf, C., and Preneel, B. (2005). Topics in Cryptology\u2013CT-RSA 2005, Springer."},{"key":"ref_6","unstructured":"Kipnis, A., Patarin, J., and Goubin, L. (1999). Advances in Cryptology\u2014EUROCRYPT99, Springer."},{"key":"ref_7","unstructured":"Petzoldt, A., Thomae, E., Bulygin, S., and Wolf, C. (2011). Cryptographic Hardware and Embedded Systems\u2013CHES 2011, Springer."},{"key":"ref_8","unstructured":"Borges, F., Petzoldt, A., and Portugal, R. Small Private Keys for Systems of Multivariate Quadratic Equations Using Symmetric Cryptography. Avaliable online: http:\/\/www.informatik.tu-darmstadt.de\/fileadmin\/user_upload\/Group_TK\/UOV_cnmac2012-final.pdf."},{"key":"ref_9","unstructured":"Von Maurich, I., and G\u00fcneysu, T. (2012). Progress in Cryptology-INDOCRYPT 2012, Springer."},{"key":"ref_10","unstructured":"Prescott, T. Random Number Generation Using Aes. Availabel online: http:\/\/www.atmel.com\/ja\/jp\/Images\/article_random_number.pdf."},{"key":"ref_11","unstructured":"Yang, B.-Y., Cheng, C.-M., Chen, B.-R., and Chen, J.-M. (2006). Security in Pervasive Computing, Springer."},{"key":"ref_12","unstructured":"Yang, B.-Y., Chen, J.-M., and Chen, Y.-H. (2004). Cryptographic Hardware and Embedded Systems-CHES 2004, Springer."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1109\/MDT.2007.178","article-title":"A survey of lightweight-cryptography implementations","volume":"24","author":"Eisenbarth","year":"2007","journal-title":"IEEE Des. Test Comput."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Osvik, D.A., Bos, J.W., Stefan, D., and Canright, D. (2010). Fast Software Encryption, Springer.","DOI":"10.1007\/978-3-642-13858-4_5"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Rukhin, A., Soto, J., Nechvatal, J., Smid, M., and Barker, E. (2001). A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, National Institute of Standards and Technology.","DOI":"10.6028\/NIST.SP.800-22"},{"key":"ref_16","unstructured":"Preneel, B., Govaerts, R., and Vandewalle, J. (1994). Advances in Cryptology\u2014CRYPTO93, Springer."},{"key":"ref_17","unstructured":"Otte, D. Avrcryptolib.2009. Availabel online: http:\/\/www.daslabor.org\/wiki\/AVRCryptoLib\/en."},{"key":"ref_18","first-page":"2012","article-title":"Fast embedded software hashing","volume":"156","author":"Osvik","year":"2012","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref_19","unstructured":"Eisenbarth, T., Heyse, S., Von Maurich, I., Poeppelmann, T., Rave, J., Reuber, C., and Wild, A. (2010, January 23\u201324). Evaluation of Sha-3 Candidates for 8-bit Embedded Processors. Santa Barbara, CA, USA."},{"key":"ref_20","unstructured":"Czypek, P., Heyse, S., and Thomae, E. (2012). Cryptographic Hardware and Embedded Systems\u2013CHES 2012, Springer."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1510","DOI":"10.1137\/S0097539796300933","article-title":"Strengths and weaknesses of quantum computing","volume":"26","author":"Bennett","year":"1997","journal-title":"SIAM J. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"470","DOI":"10.2197\/ipsjdc.1.470","article-title":"Dihedral hidden subgroup problem: A survey","volume":"1","author":"Kobayashi","year":"2005","journal-title":"IPSJ Digital Courier"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/14\/3\/5441\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:09:21Z","timestamp":1760216961000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/14\/3\/5441"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,3,19]]},"references-count":22,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2014,3]]}},"alternative-id":["s140305441"],"URL":"https:\/\/doi.org\/10.3390\/s140305441","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2014,3,19]]}}}