Authenticated Encryption with Variable Stretch

4/ Dec/ 2016
Hanoi, Vietnam
Reza Reyhanitabar, Serge Vaudenay, Damian Vizár
Name of Conference: 
Asiacrypt 2016

Paper entitled “Authenticated Encryption with Variable Stretch” has been accepted at Asiacrypt 2016.
This work relates to the work developed at TREDISEC project in WP5, addressed to design and evaluate new privacy preserving primitives to assure processing services such as word search, lookup and/or retrieval.
Pending to be published.


In conventional authenticated-encryption (AE) schemes, the ciphertext expansion, a.k.a. stretch or tag length, is a constant or a parameter of the scheme that must be fixed per key. However, using variablelength tags per key can be desirable in practice or may occur as a result of a misuse. The RAE definition by Hoang, Krovetz, and Rogaway (Eurocrypt 2015), aiming at the best-possible AE security, supports variable stretch among other strong features, but achieving the RAE goal incurs a particular inefficiency: neither encryption nor decryption can be online.

The problem of enhancing the well-established nonce-based AE (nAE) model and the standard schemes thereof to support variable tag lengths per key, without sacrificing any desirable functional and efficiency properties such as online encryption, has recently regained interest as evidenced by extensive discussion threads on the CFRG forum and the CAESAR competition. Yet there is a lack of formal definition for this goal.
First, we show that several recently proposed heuristic measures trying to augment the known schemes by inserting the tag length into the nonce and/or associated data fail to deliver any meaningful security in this setting. Second, we provide a formal definition for the notion of nonce-based variable-stretch AE (nvAE) as a natural extension to the traditional nAE model. Then, we
proceed by showing a second modular approach to formalizing the goal by combining the nAE notion and a new property we call key-equivalent separation by stretch (kess). It is proved that (after a mild adjustment to the syntax) any nAE scheme which additionally fulfills the kess property will achieve the nvAE goal.
Finally, we show that the nvAE goal is efficiently and provably achievable; for instance, by simple tweaks to
off-the-shelf schemes such as OCB.