License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2022.11
URN: urn:nbn:de:0030-drops-164890
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16489/
Go to the corresponding LIPIcs Volume Portal

Dhar, Chandranan ; Dodis, Yevgeniy ; Nandi, Mridul

Revisiting Collision and Local Opening Analysis of ABR Hash

pdf-format:
LIPIcs-ITC-2022-11.pdf (0.8 MB)

Abstract

The question of building the most efficient tn-to-n-bit collision-resistant hash function H from a smaller (say, 2n-to-n-bit) compression function f is one of the fundamental questions in symmetric key cryptography. This question has a rich history, and was open for general t, until a recent breakthrough paper by Andreeva, Bhattacharyya and Roy at Eurocrypt'21, who designed an elegant mode (which we call ABR) achieving roughly 2t/3 calls to f, which matches the famous Stam’s bound from CRYPTO'08. Unfortunately, we have found serious issues in the claims made by the authors. These issues appear quite significant, and range from verifiably false statements to noticeable gaps in the proofs (e.g., omissions of important cases and unjustified bounds).
We were unable to patch up the current proof provided by the authors. Instead, we prove from scratch the security of the ABR construction for the first non-trivial case t = 11 (ABR mode of height 3), which was incorrectly handled by the authors. In particular, our result matches Stam’s bound for t = 11. While the general case is still open, we hope our techniques will prove useful to finally settle the question of the optimal efficiency of hash functions.

BibTeX - Entry

@InProceedings{dhar_et_al:LIPIcs.ITC.2022.11,
  author =	{Dhar, Chandranan and Dodis, Yevgeniy and Nandi, Mridul},
  title =	{{Revisiting Collision and Local Opening Analysis of ABR Hash}},
  booktitle =	{3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
  pages =	{11:1--11:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-238-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{230},
  editor =	{Dachman-Soled, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16489},
  URN =		{urn:nbn:de:0030-drops-164890},
  doi =		{10.4230/LIPIcs.ITC.2022.11},
  annote =	{Keywords: ABR hash, collision resistance, local opening}
}

Keywords: ABR hash, collision resistance, local opening
Collection: 3rd Conference on Information-Theoretic Cryptography (ITC 2022)
Issue Date: 2022
Date of publication: 30.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI