Improved Bounds and New Schemes for Nonce-Length Extension - Viet Tung Hoang
Charlotte Lefevre
Dear GAPS community,
The next talk in the online GAPS seminar series has been announced:
Improved Bounds and New Schemes for Nonce-Length Extension
Viet Tung Hoang (Florida State University)
Thursday, April 30, 2026 at 15:00 UTC (10:00 EST)
In distributed systems, it’s common to use random nonces for authenticated encryption to avoid synchronization. Unfortunately, the national standard GCM has a relatively short nonce length (96 bits), resulting in poor security. Moreover, cloud systems now have to deal with an exponential growth of data, leading to a frequent key rotation of GCM. Both NIST and the industry have been calling for a solution for these issues. Ideally, such a solution should retain the speed of GCM, as using a slower encryption scheme would cost cloud servers millions of dollars per year, which is highly undesirable. In this talk, we consider two different approaches to address this problem.
1) Nonce-length extension transform: given a long (say 192-bit) nonce N and a key K, derive a 96-bit sub-nonce and a subkey, and then run GCM with the latter. We first revisit a particular nonce-length extension method called NX that is used in DNDK-GCM and XAES-256-GCM. We substantially improve its security guarantees by giving good (tight) bounds for both random-nonce and any-nonce security. We go on to give an even better transform that we call RtX. Both NX and RtX provide 96-bit security under the random-nonce setting.
2) Finally, towards longer-term mitigation, we give a new scheme GCX that provides optimal 128-bit security with 192-bit nonce at the speed of GCM. Our scheme GCX is very simple, and uses standard components (AES and GHASH), making it easy to implement and adopt for standardization. Unlike prior work that assumes message length is short, GCX can handle messages up to 2^{58} bytes.
The link will be sent before the talk as usual.
Charlotte
On behalf of the GAPS organizing committee
