Time-Area Optimized Public-Key Engines: MQ-Cryptosystems as Replacement for Elliptic Curves?

Andrey Bogdanov, Thomas Eisenbarth, Andy Rupp, Christopher Wolf

Workshop on Cryptographic Hardware and Embedded Systems -- CHES 2008 (Best Paper Award). Washington DC, USA, August 10-13, 2008.


In this paper ways to efficiently implement public-key schemes based onMultivariate Qua- dratic polynomials (MQ-schemes for short) are investigated. In particular, they are claimed to resist quantum computer attacks. It is shown that such schemes can have a much better time-area product than elliptic curve cryptosystems. For instance, an optimised FPGA im- plementation of amended TTS is estimated to be over 50 times more efficient with respect to this parameter. Moreover, a general framework for implementing small-field MQ-schemes in hardware is proposed which includes a systolic architecture performing Gaussian elimination over composite binary fields.

[DOI] [pdf] [bib]