Cryptology ePrint Archive: Report 2018/841

Building Quantum-One-Way Functions from Block Ciphers: Davies-Meyer and Merkle-Damgård Constructions

Akinori Hosoyamada and Kan Yasuda

Abstract: We present hash functions that are almost optimally one-way in the quantum setting. Our hash functions are based on the Merkle-Damgård construction iterating a Davies-Meyer compression function, which is built from a block cipher. The quantum setting that we use is a natural extention of the classical ideal cipher model. Recent work has revealed that symmetric-key schemes using a block cipher or a public permutation, such as CBC-MAC or the Even-Mansour cipher, can get completely broken with quantum superposition attacks, in polynomial time of the block size. Since many of the popular schemes are built from a block cipher or a permutation, the recent findings motivate us to study such schemes that are provably secure in the quantum setting. Unfortunately, no such schemes are known, unless one relies on certain algebraic assumptions. In this paper we present hash constructions that are provably one-way in the quantum setting without algebraic assumptions, solely based on the assumption that the underlying block cipher is ideal. To do this, we reduce one-wayness to a problem of finding a fixed point and then bound its success probability with a distinguishing advantage. We develop a generic tool that helps us prove indistinguishability of two quantum oracle distributions.

Category / Keywords: secret-key cryptography / provable security, Merkle-Damgård, Davies-Meyer, one-wayness, non-invertibility, preimage-resistance, derangement, fixed point, indistinguishability, quantum ideal cipher model

Original Publication (with major differences): IACR-ASIACRYPT-2018

Date: received 7 Sep 2018, last revised 12 Oct 2018

Contact author: hosoyamada akinori at lab ntt co jp

Available format(s): PDF | BibTeX Citation

Note: Some errors about editorial things and citations have been corrected in the revised version.

Version: 20181012:101451 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]