McBits : Fast constant-time code-based cryptography

D.J. Bernstein, T. Chou, P. Schwabe

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

34 Citations (Scopus)
2 Downloads (Pure)

Abstract

This paper presents extremely fast algorithms for code-based public-key cryptography, including full protection against timing attacks. For example, at a 2^128 security level, this paper achieves a reciprocal decryption throughput of just 60493 cycles (plus cipher cost etc.) on a single Ivy Bridge core. These algorithms rely on an additive FFT for fast root computation, a transposed additive FFT for fast syndrome computation, and a sorting network to avoid cache-timing attacks. Keywords: McEliece; Niederreiter; CFS; bitslicing; software implementation
Original languageEnglish
Title of host publicationCryptographic Hardware and Embedded Systems – CHES 2013 (15th International Workshop, Santa Barbara CA, USA, August 20-23, 2013. Proceedings)
EditorsG. Bertoni, J.-S. Coron
Place of PublicationBerlin
PublisherSpringer
Pages250-272
ISBN (Print)978-3-642-40348-4
DOIs
Publication statusPublished - 2013
Eventconference; 15th International Workshop on Cryptographic Hardware and Embedded Systems; 2013-08-20; 2013-08-23 -
Duration: 20 Aug 201323 Aug 2013

Publication series

NameLecture Notes in Computer Science
Volume8086
ISSN (Print)0302-9743

Conference

Conferenceconference; 15th International Workshop on Cryptographic Hardware and Embedded Systems; 2013-08-20; 2013-08-23
Period20/08/1323/08/13
Other15th International Workshop on Cryptographic Hardware and Embedded Systems

Fingerprint

Fast Fourier transforms
Cryptography
Public key cryptography
Sorting
Throughput
Costs
Side channel attack

Cite this

Bernstein, D. J., Chou, T., & Schwabe, P. (2013). McBits : Fast constant-time code-based cryptography. In G. Bertoni, & J-S. Coron (Eds.), Cryptographic Hardware and Embedded Systems – CHES 2013 (15th International Workshop, Santa Barbara CA, USA, August 20-23, 2013. Proceedings) (pp. 250-272). (Lecture Notes in Computer Science; Vol. 8086). Berlin: Springer. https://doi.org/10.1007/978-3-642-40349-1_15
Bernstein, D.J. ; Chou, T. ; Schwabe, P. / McBits : Fast constant-time code-based cryptography. Cryptographic Hardware and Embedded Systems – CHES 2013 (15th International Workshop, Santa Barbara CA, USA, August 20-23, 2013. Proceedings). editor / G. Bertoni ; J.-S. Coron. Berlin : Springer, 2013. pp. 250-272 (Lecture Notes in Computer Science).
@inproceedings{cb0e81d446e741c283dc3a9b5dc71337,
title = "McBits : Fast constant-time code-based cryptography",
abstract = "This paper presents extremely fast algorithms for code-based public-key cryptography, including full protection against timing attacks. For example, at a 2^128 security level, this paper achieves a reciprocal decryption throughput of just 60493 cycles (plus cipher cost etc.) on a single Ivy Bridge core. These algorithms rely on an additive FFT for fast root computation, a transposed additive FFT for fast syndrome computation, and a sorting network to avoid cache-timing attacks. Keywords: McEliece; Niederreiter; CFS; bitslicing; software implementation",
author = "D.J. Bernstein and T. Chou and P. Schwabe",
year = "2013",
doi = "10.1007/978-3-642-40349-1_15",
language = "English",
isbn = "978-3-642-40348-4",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "250--272",
editor = "G. Bertoni and J.-S. Coron",
booktitle = "Cryptographic Hardware and Embedded Systems – CHES 2013 (15th International Workshop, Santa Barbara CA, USA, August 20-23, 2013. Proceedings)",
address = "Germany",

}

Bernstein, DJ, Chou, T & Schwabe, P 2013, McBits : Fast constant-time code-based cryptography. in G Bertoni & J-S Coron (eds), Cryptographic Hardware and Embedded Systems – CHES 2013 (15th International Workshop, Santa Barbara CA, USA, August 20-23, 2013. Proceedings). Lecture Notes in Computer Science, vol. 8086, Springer, Berlin, pp. 250-272, conference; 15th International Workshop on Cryptographic Hardware and Embedded Systems; 2013-08-20; 2013-08-23, 20/08/13. https://doi.org/10.1007/978-3-642-40349-1_15

McBits : Fast constant-time code-based cryptography. / Bernstein, D.J.; Chou, T.; Schwabe, P.

Cryptographic Hardware and Embedded Systems – CHES 2013 (15th International Workshop, Santa Barbara CA, USA, August 20-23, 2013. Proceedings). ed. / G. Bertoni; J.-S. Coron. Berlin : Springer, 2013. p. 250-272 (Lecture Notes in Computer Science; Vol. 8086).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - McBits : Fast constant-time code-based cryptography

AU - Bernstein, D.J.

AU - Chou, T.

AU - Schwabe, P.

PY - 2013

Y1 - 2013

N2 - This paper presents extremely fast algorithms for code-based public-key cryptography, including full protection against timing attacks. For example, at a 2^128 security level, this paper achieves a reciprocal decryption throughput of just 60493 cycles (plus cipher cost etc.) on a single Ivy Bridge core. These algorithms rely on an additive FFT for fast root computation, a transposed additive FFT for fast syndrome computation, and a sorting network to avoid cache-timing attacks. Keywords: McEliece; Niederreiter; CFS; bitslicing; software implementation

AB - This paper presents extremely fast algorithms for code-based public-key cryptography, including full protection against timing attacks. For example, at a 2^128 security level, this paper achieves a reciprocal decryption throughput of just 60493 cycles (plus cipher cost etc.) on a single Ivy Bridge core. These algorithms rely on an additive FFT for fast root computation, a transposed additive FFT for fast syndrome computation, and a sorting network to avoid cache-timing attacks. Keywords: McEliece; Niederreiter; CFS; bitslicing; software implementation

U2 - 10.1007/978-3-642-40349-1_15

DO - 10.1007/978-3-642-40349-1_15

M3 - Conference contribution

SN - 978-3-642-40348-4

T3 - Lecture Notes in Computer Science

SP - 250

EP - 272

BT - Cryptographic Hardware and Embedded Systems – CHES 2013 (15th International Workshop, Santa Barbara CA, USA, August 20-23, 2013. Proceedings)

A2 - Bertoni, G.

A2 - Coron, J.-S.

PB - Springer

CY - Berlin

ER -

Bernstein DJ, Chou T, Schwabe P. McBits : Fast constant-time code-based cryptography. In Bertoni G, Coron J-S, editors, Cryptographic Hardware and Embedded Systems – CHES 2013 (15th International Workshop, Santa Barbara CA, USA, August 20-23, 2013. Proceedings). Berlin: Springer. 2013. p. 250-272. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-40349-1_15