skip to main content
10.5555/1131481.1131543guideproceedingsArticle/Chapter ViewAbstractPublication PagesdateConference Proceedingsconference-collections
Article
Free access

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

Published: 06 March 2006 Publication History

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]
K. Atasu, L. Pozzi, and P. Ienne. Automatic application-specific instruction-set extensions under microarchitectural constraints. In Proceedings of the 40th Design Automation Conference (DAC 2003), pp. 256--261. ACM Press, 2003.
[3]
I. F. Blake, G. Seroussi, and N. P. Smart. Elliptic Curves in Cryptography. Cambridge University Press, 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]
N. Clark, H. Zhong, and S. Mahlke. Processor acceleration through automated instruction set customization. In Proceedings of the 36th Annual International Symposium on Micro-architecture (MICRO-36), pp. 129--140. ACM Press, 2003.
[7]
P. G. Comba. Exponentiation cryptosystems on the IBM PC. IBM Systems Journal, 29(4):526--538, Dec. 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]
P. Faraboschi, G. Brown, J. A. Fisher, G. Desoli, and F. Homewood. Lx: A technology platform for customizable VLIW embedded processing. In Proceedings of the 27th Annual International Symposium on Computer Architecture (ISCA 2000), pp. 203--213. ACM Press, 2000.
[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]
D. R. Hankerson, A. J. Menezes, and S. A. Vanstone. Guide to Elliptic Curve Cryptography. Springer Verlag, 2004.
[13]
Ç. Koç and T. Acar. Montgomery multiplication in GF(2k). Designs, Codes and Cryptography, 14(1):57--69, Mar. 1998.
[14]
R. Lidl and H. Niederreiter. Introduction to Finite Fields and Their Applications. Cambridge University Press, 1994.
[15]
A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 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.

Cited By

View all
  • (2016)Instruction set extensions for secure applicationsProceedings of the 2016 Conference on Design, Automation & Test in Europe10.5555/2971808.2972165(1529-1534)Online publication date: 14-Mar-2016
  • (2007)CReconfigurable finite field instruction set architectureProceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays10.1145/1216919.1216954(216-220)Online publication date: 18-Feb-2007

Recommendations

Comments

Information & Contributors

Information

Published In

cover image Guide Proceedings
DATE '06: Proceedings of the conference on Design, automation and test in Europe: Proceedings
March 2006
1390 pages
ISBN:3981080106

Sponsors

  • EDAA: European Design Automation Association
  • The EDA Consortium
  • IEEE-CS\DATC: The IEEE Computer Society

Publisher

European Design and Automation Association

Leuven, Belgium

Publication History

Published: 06 March 2006

Qualifiers

  • Article

Acceptance Rates

DATE '06 Paper Acceptance Rate 267 of 834 submissions, 32%;
Overall Acceptance Rate 518 of 1,794 submissions, 29%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)64
  • Downloads (Last 6 weeks)9
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2016)Instruction set extensions for secure applicationsProceedings of the 2016 Conference on Design, Automation & Test in Europe10.5555/2971808.2972165(1529-1534)Online publication date: 14-Mar-2016
  • (2007)CReconfigurable finite field instruction set architectureProceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays10.1145/1216919.1216954(216-220)Online publication date: 18-Feb-2007

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media