Faster binary-field multiplication and faster binary-field MACs

D.J. Bernstein, T. Chou

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

9 Citations (Scopus)


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 languageEnglish
Title of host publicationSelected Areas in Cryptography -- SAC 2014: 21st International Conference, Montreal, QC, Canada, August 14-15, 2014, Revised Selected Papers
EditorsA. Joux, A. Youssef
ISBN (Print)978-3-319-13050-7
Publication statusPublished - 2014
Event21st International Conference on Selected Areas in Cryptography (SAC 2014) - Sackville, Canada
Duration: 14 Aug 201415 Aug 2014
Conference number: 21

Publication series

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


Conference21st International Conference on Selected Areas in Cryptography (SAC 2014)
Abbreviated titleSAC 2014


Dive into the research topics of 'Faster binary-field multiplication and faster binary-field MACs'. Together they form a unique fingerprint.

Cite this