Combining algorithm exploration with instruction set design: a case study in elliptic curve cryptography

ABSTRACT

In recent years, processor customization has matured to become a trusted way of achieving high performance with limited cost/energy in embedded applications. In particular, Instruction Set Extensions (ISEs) have been proven very effective in many cases. A large body of work exists today on creating tools that can select efficient ISEs given an application source code: ISE automation is crucial for increasing the productivity of design teams. In this paper we show that an additional motivation for automating the ISE process is to facilitate algorithm exploration: the availability of ISE can have a dramatic impact on the performance of different algorithmic choices to implement identical or equivalent functionality. System designers need fast feedbacks on the ISE-ability of various algorithmic flavors. We use a case study in elliptic curve (EC) cryptography to exemplify the following contributions: (1) ISE can reverse the relative performance of different algorithms for one and the same operation, and (2) automatic ISE, even without predicting speed-ups as precisely as detailed simulation can, is able to show exactly the trends that the designer should follow.

REFERENCES

• 1: ARM Limited. SecurCore#8482; Solutions. Product brief, available for download at http://www.arm.com, Feb. 2002.
• 2: Kubilay Atasu , Laura Pozzi , Paolo Ienne, Automatic application-specific instruction-set extensions under microarchitectural constraints, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775897]
• 3: Ian F. Blake , G. Seroussi , N. P. Smart, Elliptic curves in cryptography, Cambridge University Press, New York, NY, 1999
• 4: W. Bond. 64-bit architecture speeds RSA by 4x. Whitepaper, available for download at http://www.mips.com, 2002.
• 5: D. C. Burger and T. M. Austin. The SimpleScalar Tool Set, Version 2.0. Technical Report CS-TR-97-1342, University of Wisconsin, Madison, WI, USA, June 1997.
• 6: Nathan Clark , Hongtao Zhong , Scott Mahlke, Processor Acceleration Through Automated Instruction Set Customization, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.129, December 03-05, 2003
• 7: P. G. Comba, Exponentiation cryptosystems on the IBM PC, IBM Systems Journal, v.29 n.4, p.526-538, 1990
• 8: J.-F. Dhem. Design of an efficient public-key cryptographic library for RISC-based smart cards. Ph.D. Thesis, Université Catholique de Louvain, Louvain-la-Neuve, Belgium, 1998.
• 9: Paolo Faraboschi , Geoffrey Brown , Joseph A. Fisher , Giuseppe Desoli , Fred Homewood, Lx: a technology platform for customizable VLIW embedded processing, Proceedings of the 27th annual international symposium on Computer architecture, p.203-213, June 2000, Vancouver, British Columbia, Canada
• 10: J. Großschädl and G.-A. Kamendje. Instruction set extension for fast elliptic curve cryptography over binary finite fields GF(2m). In Proceedings of the 14th Conference on Application-specific Systems, Architectures and Processors (ASAP 2003), pp. 455--468. IEEE Computer Society Press, 2003.
• 11: J. Großschädl and G.-A. Kamendje. Optimized RISC architecture for multiple-precision modular arithmetic. In Security in Pervasive Computing --- SPC 2003, LNCS 2802, pp. 253--270. Springer Verlag, 2003.
• 12: Darrel Hankerson , Alfred J. Menezes , Scott Vanstone, Guide to Elliptic Curve Cryptography, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 13: Cetin K. Koc , Tolga Acar, Montgomery Multiplication in GF(2$^k$, Designs, Codes and Cryptography, v.14 n.1, p.57-69, April 1998 [doi>10.1023/A:1008208521515]
• 14: Rudolf Lidl , Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, New York, NY, 1986
• 15: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 16: MIPS Technologies, Inc. MIPS32#8482; Architecture for Programmers. Available for download at http://www.mips.com, Mar. 2001.
• 17: MIPS Technologies, Inc. SmartMIPS® Architecture Smart Card Extensions. Product brief, available for download at http://www.mips.com, Feb. 2001.
• 18: L. Pozzi, K. Atasu, and P. Ienne. Exact and approximate algorithms for the extension of embedded processor instruction sets. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, to appear.
• 19: J. Turley. Tensilica CPU bends to designers' will. Microprocessor Report, 13(3):12, Mar. 1999.