Paper 2015/214 Original: eprint.iacr.org/2015/214 ↗
GCM Security Bounds Reconsidered
Abstract
A constant of $2^{22}$ appears in the security bounds of the Galois/Counter Mode of Operation, GCM. In this paper, we first develop an algorithm to generate nonces that have a high counter-collision probability. We show concrete examples of nonces with the counter-collision probability of about $2^{20.75}/2^{128}$. This shows that the constant in the security bounds, $2^{22}$, cannot be made smaller than $2^{19.74}$ if the proof relies on ``the sum bound.'' We next show that it is possible to avoid using the sum bound, leading to improved security bounds of GCM. One of our improvements shows that the constant of $2^{22}$ can be reduced to 32.
Metadata
- Available format(s)
PDF- Category
- Secret-key cryptography
- Publication info
- Preprint.
- History
- 2015-03-08: last updated
- 2015-03-08: published
- Short URL
- https://ia.cr/2015/214
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2015/214,
author = {Yuichi Niwa and Keisuke Ohashi and Kazuhiko Minematsu and Tetsu Iwata},
title = {GCM Security Bounds Reconsidered},
howpublished = {Cryptology {ePrint} Archive, Paper 2015/214},
year = {2015},
url = {https://eprint.iacr.org/2015/214}
}