International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

The Summation-Truncation Hybrid: Reusing Discarded Bits for Free

Authors:
Aldo Gunsing , Radboud University
Bart Mennink , Radboud University
Download:
DOI: 10.1007/978-3-030-56784-2_7 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2020
Abstract: A well-established PRP-to-PRF conversion design is truncation: one evaluates an n-bit pseudorandom permutation on a certain input, and truncates the result to a bits. The construction is known to achieve tight 2n−a/2 security. Truncation has gained popularity due to its appearance in the GCM-SIV key derivation function (ACM CCS 2015). This key derivation function makes four evaluations of AES, truncates the outputs to n/2 bits, and concatenates these to get a 2n-bit subkey. In this work, we demonstrate that truncation is wasteful. In more detail, we present the Summation-Truncation Hybrid (STH). At a high level, the construction consists of two parallel evaluations of truncation, where the truncated (n−a)-bit chunks are not discarded but rather summed together and appended to the output. We prove that STH achieves a similar security level as truncation, and thus that the n−a bits of extra output is rendered for free. In the application of GCM-SIV, the current key derivation can be used to output 3n bits of random material, or it can be reduced to three primitive evaluations. Both changes come with no security loss.
Video from CRYPTO 2020
BibTeX
@inproceedings{crypto-2020-30433,
  title={The Summation-Truncation Hybrid: Reusing Discarded Bits for Free},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-56784-2_7},
  author={Aldo Gunsing and Bart Mennink},
  year=2020
}