Abstract
Multivariate (or \(\mathcal{MQ}\)) public-key cryptosystems (PKC) are alternatives to traditional PKCs based on large algebraic structures (e.g., RSA and ECC); they usually execute much faster than traditional PKCs on the same hardware. However, one major challenge in implementing multivariates in embedded systems is that the key size can be prohibitively large for applications with stringent resource constraints such as low-cost smart cards, sensor networks (e.g., Berkeley motes), and radio-frequency identification (RFID). In this paper, we investigate strategies for shortening the key of a multivariate PKC. We apply these strategies to the Tame Transformation Signatures (TTS) as an example and quantify the improvement in key size and running speed, both theoretically and via implementation. We also investigate ways to save die space and energy consumption in hardware, reporting on our ASIC implementation of TTS on a TSMC 0.25μm process. Even without any key shortening, the current consumption of TTS is only 21 μA for computing a signature, using 22,000 gate equivalents and 16,000 100-kHz cycles (160 ms). With circulant-matrix key shortening, the numbers go down to 17,000 gates and 4,400 cycles (44 ms). We therefore conclude: besides representing a future-proofing investment against the emerging quantum computers, multivariates can be immediately useful in niches.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Akkar, M., Courtois, N., Duteuil, R., Goubin, L.: A Fast and Secure Implementation of SFLASH. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 267–278. Springer, Heidelberg (2002)
Chou, C.-Y., Hu, Y.-H., Lai, F.-P., Wang, L.-C., Yang, B.-Y.: Tractable Rational Map Signature. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 244–257. Springer, Heidelberg (2005)
Courtois, N.: Generic Attacks and the Security of Quartz. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 351–364. Springer, Heidelberg (2002)
Courtois, N., Goubin, L., Meier, W., Tacier, J.: Solving Underdefined Systems of Multivariate Quadratic Equations. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 211–227. Springer, Heidelberg (2002)
Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, Springer, Heidelberg (2000)
Daemen, J., Rijmen, V.: The Design of Rijndael, AES - the Advanced Encryption Standard. Springer, Heidelberg (2002)
Davis, P.: Circulant matrices. John Wiley & Sons, New York-Chichester-Brisbane (1979)
Diem, C.: The XL-Algorithm and a Conjecture from Commutative Algebra. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 323–337. Springer, Heidelberg (2004)
Ding, J.: A New Variant of the Matsumoto-Imai Cryptosystem through Perturbation. In: Bao, F., Deng, R., Zhou, J. (eds.) PKC 2004. LNCS, vol. 2947, pp. 305–318. Springer, Heidelberg (2004)
Ding, J., Gower, J., et al.: Innoculating Multivariate Schemes against Differential Attacks, http://eprint.iacr.org/2005/255/
Ding, J., Schmidt, D.: Rainbow, a new Digitial Multivariate Signature Scheme. In: Ioannidis, J., Keromytis, A.D., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 164–177. Springer, Heidelberg (2005)
Ding, J., Yin, Z.: Cryptanalysis of TTS and tame-like multivariable signature schemes. In: IWAP 2004 (presentation, 2004)
Faugère, J.-C.: A New Efficient Algorithm for Computing Gröbner Bases without Reduction to Zero (F5). In: Proceedings of ISSAC 2002, pp. 75–83. ACM Press, New York (2002)
Faugère, J.-C.: invited talk at AES4 conference, and private communication
Feldhofer, M., Dominikus, S., Wolkerstorfer, J.: Strong Authentication for RFID Systems Using the AES Algorithm. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 357–370. Springer, Heidelberg (2004)
Garey, M., Johnson, D.: Computers and Intractability, A Guide to the Theory of NP-completeness, p. 251. Freeman and Co., New York (1979)
Gaubatz, G., Kaps, J.-P., Sunar, B.: Public Key Cryptography in Sensor Networks—Revisited. In: Castelluccia, C., Hartenstein, H., Paar, C., Westhoff, D. (eds.) ESAS 2004. LNCS, vol. 3313, Springer, Heidelberg (2005)
Gay, D., Levis, P., von Behren, R., Welsh, M., Brewer, E., Culler, D.: The nesC Language: A Holistic Approach to Networked Embedded Systems. In: ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation (PLDI), San Diego, CA, USA (June 2003)
Gilbert, H., Minier, M.: Cryptanalysis of SFLASH. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, Springer, Heidelberg (2002)
Geiselmann, W., Steinwandt, R., Beth, T.: Attacking the Affine Parts of SFLASH. In: Honary, B. (ed.) Cryptography and Coding 2001. LNCS, vol. 2260, pp. 355–359. Springer, Heidelberg (2001)
Goubin, L., Courtois, N.: Cryptanalysis of the TTM Cryptosystem. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, Springer, Heidelberg (2000)
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proc. 28th Annual ACM Symposium on the Theory of Computing (May 1996), pp. 212–220 (1996)
Hill, J., Szewczyk, R., Woo, A., Hollar, S., Culler, D.E., Pister, K.S.J.: System Architecture Directions for Networked Sensors. In: Proc. 9th International Conference on Architectural Support for Programming Languages and Operating Systems, November 2000, pp. 93–104 (2000)
Hu, Y., Wang, L., Chen, J., Lai, F., Chou, C.: A Performance Report and Security Analysis of a fast TTM implementation. In: 2003 IEEE Int’l Symp. on Information Theory, Yokohama, Japan (June 2003)
Hu, Y., Wang, L., Lai, F., Chou, C.: Similar Keys of Multivariate Quadratic Public Key Cryptosystems. In: Desmedt, Y.G., Wang, H., Mu, Y., Li, Y. (eds.) CANS 2005. LNCS, vol. 3810, pp. 211–222. Springer, Heidelberg (2005)
Joux, A., Kunz-Jacques, S., Muller, F., Ricordel, P.-M.: Cryptanalysis of the Tractable Rational Map Cryptosystem. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 258–274. Springer, Heidelberg (2005)
Kipnis, A., Patarin, J., Goubin, L.: Unbalanced Oil and Vinegar Signature Schemes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, Springer, Heidelberg (1999)
Lidl, R., Niederreiter, H.: Finite Fields. Addison-Wesley, Reading (1984)
Ljungkvist, S.: in the 8051 code library, http://www.8052.com/codelib.phtm
Malan, D., Welsh, M., Smith, M.: A Public-Key Infrastructure for Key Distribution in TinyOS Based on Elliptic Curve Cryptography. In: First IEEE International Conference on Sensor and Ad hoc Communications and Networks (SECON), Santa Clara, CA, USA (October 2004)
Matsumoto, T., Imai, H.: Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 419–453. Springer, Heidelberg (1988)
Matsumoto, M., Nishimura, T.: Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator. ACM Trans. on Modeling and Computer Sim. 8, 3–30 (1998)
The NESSIE project homepage, http://www.cryptonessie.org
Paar, C.: Some Remarks on Efficient Inversion in Finite Fields. In: 1995 IEEE International Symposium on Information Theory, Whistler, B.C. Canada (September 1995); available from the author’s website
Paar, C.: A New Architechture for a Parallel Finite Field Multiplier with Low Complexity Based on Composition Fields. Brief Contributions section of IEEE Transactions on Computers 45(7), 856–861 (1996)
Patarin, J.: Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt 1988. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 248–261. Springer, Heidelberg (1995)
Patarin, J.: Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 33–48. Springer, Heidelberg (1996)
Patarin, J., Goubin, L., Courtois, N.: C\(^*_{-+}\) and HM: Variations Around Two Schemes of T. Matsumoto and H. Imai. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 35–49. Springer, Heidelberg (1998)
Patarin, J., Courtois, N., Goubin, L.: FLASH, a Fast Multivariate Signature Algorithm. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 298–307. Springer, Heidelberg (2001), Updated version available at: http://www.cryptonessie.org
Shor, P.W.: Algorithms for quantum computation: Discrete logarithms and factoring. In: Goldwasser, S. (ed.) Proc. 35nd Annual Symposium on Foundations of Computer Science, pp. 124–134. IEEE Computer Society Press, Los Alamitos (1994)
Wolf, C., Preneel, B.: Taxonomy of Public-Key Schemes based on the Problem of Multivariate Quadratic Equations (2005), http://eprint.iacr.org/2005/077
Wolf, C., Preneel, B.: Equivalent Keys in HFE, C*, and variations. In: Dawson, E., Vaudenay, S. (eds.) Mycrypt 2005. LNCS, vol. 3715, pp. 33–49. Springer, Heidelberg (2005)
Yang, B.-Y., Chen, J.-M.: Rank Attacks and Defence in Tame-Like Multivariate PKC’s. In: Boyd, C., González Nieto, J.M. (eds.) ACISP 2005. LNCS, vol. 3574, pp. 518–531. Springer, Heidelberg (2005)
Yang, B.-Y., Chen, Y.-H., Chen, J.-M.: TTS: High-Speed Signatures on a Low-Cost Smart Card. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 371–385. Springer, Heidelberg (2004)
Yang, B.-Y., Cheng, C.-M., Chen, B.-R., Chen, J.-M.: Technical Research Report Number 11, Taiwan Information Security Center (TWISC) (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yang, BY., Cheng, CM., Chen, BR., Chen, JM. (2006). Implementing Minimized Multivariate PKC on Low-Resource Embedded Systems. In: Clark, J.A., Paige, R.F., Polack, F.A.C., Brooke, P.J. (eds) Security in Pervasive Computing. SPC 2006. Lecture Notes in Computer Science, vol 3934. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11734666_7
Download citation
DOI: https://doi.org/10.1007/11734666_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33376-0
Online ISBN: 978-3-540-33377-7
eBook Packages: Computer ScienceComputer Science (R0)