Cryptology ePrint Archive: Report 2021/1267

Tight Quantum Indifferentiability of a Rate-1/3 Compression Function

Jan Czajkowski

Abstract: We prove classical and quantum indifferentiability of a rate-1/3 compression function introduced by Shrimpton and Stam (ICALP '08). This construction was one of the first constructions based on three random functions that achieved optimal collision-resistance. We also prove that our result is tight, we define a classical and a quantum attackers that match the indifferentiability security level. Our tight indifferentiability results provide a negative result on the optimality of security of the construction by Shrimpton and Stam, security level of the strong indifferentiability notion is below that of collision-resistance.

To arrive at these results, we generalize the results of Czajkowski, Majenz, Schaffner, and Zur (arXiv '19). Our generalization allows to analyze quantum security of constructions based on multiple independent random functions, something not possible before.

Category / Keywords: secret-key cryptography / quantum indifferentiability, compression functions

Date: received 22 Sep 2021, last revised 22 Sep 2021

Contact author: jan czajkowski at weizmann ac il

Available format(s): PDF | BibTeX Citation

Version: 20210922:151422 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]