Small Stretch Problem of the DCT Scheme and How to Fix It

Yuchao Chen; Tingting Guo; Lei Hu; Lina Shang; Shuping Mao; Peng Wang

Paper 2023/1808

Small Stretch Problem of the DCT Scheme and How to Fix It

Yuchao Chen

, School of Cyber Science and Technology, Shandong University, Qingdao, China, Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China

Tingting Guo

, Research Center for Data Hub and Security, Zhejiang lab

Lei Hu, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, School of Cyber Security, University of Chinese Academy of Sciences

Lina Shang, Space Star Technology Co., Ltd.

Shuping Mao

, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, School of Cyber Security, University of Chinese Academy of Sciences

Peng Wang

, School of Cryptology, University of Chinese Academy of Sciences

Abstract

DCT is a beyond-birthday-bound~(BBB) deterministic authenticated encryption~(DAE) mode proposed by Forler et al. in ACISP 2016, ensuring integrity by redundancy. The instantiation of DCT employs the BRW polynomial, which is more efficient than the usual polynomial in GCM by reducing half of the multiplication operations. However, we show that DCT suffers from a small stretch problem similar to GCM. When the stretch length $\tau$ is small, choosing a special $m$-block message, we can reduce the number of queries required by a successful forgery to $\mathcal{O}(2^{\tau}/m)$. We emphasize that this attack efficiently balances space and time complexity but does not contradict the security bounds of DCT. Finally, we propose an improved scheme named Robust DCT~(RDCT) with a minor change to DCT, which improves the security when $\tau$ is small and makes it resist the above attack.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published by the IACR in TOSC 2024
Keywords: DCT Deterministic Authenticated Encryption AEAD BRW polynomial Forgery Attack Stretch
Contact author(s): chenyuchao @ mail sdu edu cn
guotingting4633 @ gmail com
hulei @ iie ac cn
sln-8108 @ 163 com
maoshuping @ iie ac cn
w rocking @ gmail com
History: 2024-04-13: last of 3 revisions; 2023-11-23: received; See all versions
Short URL: https://ia.cr/2023/1808
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1808,
      author = {Yuchao Chen and Tingting Guo and Lei Hu and Lina Shang and Shuping Mao and Peng Wang},
      title = {Small Stretch Problem of the DCT Scheme and How to Fix It},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1808},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1808}},
      url = {https://eprint.iacr.org/2023/1808}
}