title: Small private key MQPKS on an embedded microprocessor.
abstract: 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.
authors.affiliation: Computer Engineering, Pusan National University, Pusan 609-735, Korea. hwajeong@pusan.ac.kr.
authors.forename: Hwajeong
authors.initials: H
authors.lastname: Seo
authors.affiliation: Computer Engineering, Pusan National University, Pusan 609-735, Korea. kjhps000@gmail.com.
authors.forename: Jihyun
authors.initials: J
authors.lastname: Kim
authors.affiliation: Computer Engineering, Pusan National University, Pusan 609-735, Korea. bestofcom@gmail.com.
authors.forename: Jongseok
authors.initials: J
authors.lastname: Choi
authors.affiliation: Computer Engineering, Pusan National University, Pusan 609-735, Korea. pth5804@gmail.com.
authors.forename: Taehwan
authors.initials: T
authors.lastname: Park
authors.affiliation: Laboratory of Algorithmics, Cryptology and Security, University of Luxembourg, 6 Rue RichardCoudenhove-Kalergi, Luxembourg L-1359, Luxembourg. zhe.liu@uni.lu.
authors.forename: Zhe
authors.initials: Z
authors.lastname: Liu
authors.affiliation: Computer Engineering, Pusan National University, Pusan 609-735, Korea. howonkim@pusan.ac.kr.
authors.forename: Howon
authors.initials: H
authors.lastname: Kim