Stronger Security Variants of GCM-SIV

  • Tetsu Iwata Nagoya University
  • Kazuhiko Minematsu NEC Corporation, Kawasaki
Keywords: GCM-SIV, nonce-reuse misuse-resistance authenticated encryption, provable security, beyond-birthday-bound security

Abstract

At CCS 2015, Gueron and Lindell proposed GCM-SIV, a provably secure authenticated encryption scheme that remains secure even if the nonce is repeated. While this is an advantage over the original GCM, we first point out that GCM-SIV allows a trivial distinguishing attack with about 248 queries, where each query has one plaintext block. This shows the tightness of the security claim and does not contradict the provable security result. However, the original GCM resists the attack, and this poses a question of designing a variant of GCM-SIV that is secure against the attack. We present a minor variant of GCM-SIV, which we call GCM-SIV1, and discuss that GCM-SIV1 resists the attack, and it offers a security trade-off compared to GCM-SIV. As the main contribution of the paper, we explore a scheme with a stronger security bound. We present GCM-SIV2 which is obtained by running two instances of GCM-SIV1 in parallel and mixing them in a simple way. We show that it is secure up to 285.3 query complexity, where the query complexity is measured in terms of the total number of blocks of the queries. Finally, we generalize this to show GCM-SIVr by running r instances of GCM-SIV1 in parallel, where r ≥ 3, and show that the scheme is secure up to 2128r/(r+1) query complexity. The provable security results are obtained under the standard assumption that the blockcipher is a pseudorandom permutation.
Published
2016-12-01
How to Cite
Iwata, T., & Minematsu, K. (2016). Stronger Security Variants of GCM-SIV. IACR Transactions on Symmetric Cryptology, 2016(1), 134-157. https://doi.org/10.13154/tosc.v2016.i1.134-157
Section
Articles