Paper 2014/729

Faster Binary-Field Multiplication and Faster Binary-Field MACs

Daniel J. Bernstein and Tung Chou

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).

Note: expanded version of sac 2014 paper

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Minor revision. SAC 2014
Keywords
PerformanceFFTsPolynomial multiplicationUniversal hashingMessage authentication
Contact author(s)
authorcontact-auth256 @ box cr yp to
History
2020-12-28: revised
2014-09-19: received
See all versions
Short URL
https://ia.cr/2014/729
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/729,
      author = {Daniel J.  Bernstein and Tung Chou},
      title = {Faster Binary-Field Multiplication and Faster Binary-Field MACs},
      howpublished = {Cryptology ePrint Archive, Paper 2014/729},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/729}},
      url = {https://eprint.iacr.org/2014/729}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.