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 $2^{n-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.

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},
      note = {\url{https://eprint.iacr.org/2022/249}},
      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.