Abstract
This paper shows how to securely authenticate messages using just 29 bit operations per authenticated bit, plus a constant overhead per message. The authenticator is a standard type of "universal" hash function providing information-theoretic security; what is new is computing this type of hash function at very high speed.
At a lower level, this paper shows how to multiply two elements of a field of size 2^128 using just 9062 \approx 71 * 128 bit operations, and how to multiply two elements of a field of size 2^256 using just 22164 \approx 87 * 256 bit operations. This performance relies on a new representation of field elements and new FFT-based multiplication techniques.
This paper's constant-time software uses just 1.89 Core 2 cycles per byte to authenticate very long messages. On a Sandy Bridge it takes 1.43 cycles per byte, without using Intel's PCLMULQDQ polynomial-multiplication hardware. This is much faster than the speed records for constant-time implementations of GHASH without PCLMULQDQ (over 10 cycles/byte), even faster than Intel's best Sandy Bridge implementation of GHASH with PCLMULQDQ (1.79 cycles/byte), and almost as fast as state-of-the-art 128-bit prime-field MACs using Intel's integer-multiplication hardware (around 1 cycle/byte).
Keywords: Performance, FFTs, Polynomial multiplication, Universal hashing, Message authentication
Original language | English |
---|---|
Title of host publication | Selected Areas in Cryptography -- SAC 2014: 21st International Conference, Montreal, QC, Canada, August 14-15, 2014, Revised Selected Papers |
Editors | A. Joux, A. Youssef |
Publisher | Springer |
Pages | 92-111 |
ISBN (Print) | 978-3-319-13050-7 |
DOIs | |
Publication status | Published - 2014 |
Event | 21st International Conference on Selected Areas in Cryptography (SAC 2014) - Sackville, Canada Duration: 14 Aug 2014 → 15 Aug 2014 Conference number: 21 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
ISSN (Print) | 0302-9743 |
Conference
Conference | 21st International Conference on Selected Areas in Cryptography (SAC 2014) |
---|---|
Abbreviated title | SAC 2014 |
Country/Territory | Canada |
City | Sackville |
Period | 14/08/14 → 15/08/14 |