Paper 2022/249

The Summation-Truncation Hybrid: Reusing Discarded Bits for Free

Aldo Gunsing and Bart Mennink

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 2na/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 -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 bits of extra output is rendered for free. In the application of GCM-SIV, the current key derivation can be used to output bits of random material, or it can be reduced to three primitive evaluations. Both changes come with no security loss.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in CRYPTO 2020
DOI
10.1007/978-3-030-56784-2_7
Keywords
PRP-to-PRFTruncationSum of permutationsEfficiencyGCM-SIV
Contact author(s)
aldo gunsing @ ru nl
History
2022-03-02: received
Short URL
https://ia.cr/2022/249
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/249,
      author = {Aldo Gunsing and Bart Mennink},
      title = {The Summation-Truncation Hybrid: Reusing Discarded Bits for Free},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/249},
      year = {2022},
      doi = {10.1007/978-3-030-56784-2_7},
      url = {https://eprint.iacr.org/2022/249}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.