## CryptoDB

### Akinori Hosoyamada

#### Publications

**Year**

**Venue**

**Title**

2021

TOSC

Provably Quantum-Secure Tweakable Block Ciphers
Abstract

Recent results on quantum cryptanalysis show that some symmetric key schemes can be broken in polynomial time even if they are proven to be secure in the classical setting. Liskov, Rivest, and Wagner showed that secure tweakable block ciphers can be constructed from secure block ciphers in the classical setting. However, Kaplan et al. showed that their scheme can be broken by polynomial time quantum superposition attacks, even if underlying block ciphers are quantum-secure. Since then, it remains open if there exists a mode of block ciphers to build quantum-secure tweakable block ciphers. This paper settles the problem in the reduction-based provable security paradigm. We show the first design of quantum-secure tweakable block ciphers based on quantum-secure block ciphers, and present a provable security bound. Our construction is simple, and when instantiated with a quantum-secure n-bit block cipher, it is secure against attacks that query arbitrary quantum superpositions of plaintexts and tweaks up to O(2n/6) quantum queries. Our security proofs use the compressed oracle technique introduced by Zhandry. More precisely, we use an alternative formalization of the technique introduced by Hosoyamada and Iwata.

2021

CRYPTO

On Tight Quantum Security of HMAC and NMAC in the Quantum Random Oracle Model
Abstract

HMAC and NMAC are the most basic and important constructions to convert Merkle-Damg{\aa}rd hash functions into message authentication codes (MACs) or pseudorandom functions (PRFs).
In the quantum setting, at CRYPTO~2017, Song and Yun showed that HMAC and NMAC are quantum pseudorandom functions (qPRFs) under the standard assumption that the underlying compression function is a qPRF.
Their proof guarantees security up to $O(2^{n/5})$ or $O(2^{n/8})$ quantum queries when the output length of HMAC and NMAC is $n$ bits.
However, there is a gap between the provable security bound and a simple distinguishing attack that uses $O(2^{n/3})$ quantum queries.
This paper settles the problem of closing the gap.
We show that the tight bound of the number of
quantum queries to distinguish HMAC or NMAC from a random function
is $\Theta(2^{n/3})$ in the quantum random oracle model,
where compression functions are modeled as quantum random oracles.
To give the tight quantum bound,
based on an alternative formalization of Zhandry's compressed oracle technique,
we introduce a new proof technique focusing on the symmetry of quantum query records.

2021

CRYPTO

Quantum Collision Attacks on Reduced SHA-256 and SHA-512
Abstract

In this paper, we study dedicated quantum collision attacks on SHA-256 and SHA-512 for the first time.
The attacks reach 38 and 39 steps, respectively, which significantly improve the classical attacks for 31 and 27 steps.
Both attacks adopt the framework of the previous work that converts many semi-free-start collisions into a 2-block collision, and are faster than the generic attack in the cost metric of time-space tradeoff.
We observe that the number of required semi-free-start collisions can be reduced in the quantum setting, which allows us to convert the previous classical 38 and 39 step semi-free-start collisions into a collision.
The idea behind our attacks is simple and will also be applicable to other cryptographic hash functions.

2020

EUROCRYPT

Finding Hash Collisions with Quantum Computers by Using Differential Trails with Smaller Probability than Birthday Bound
📺
Abstract

In this paper we spot light on dedicated quantum collision attacks on concrete hash functions, which has not received much attention so far.
In the classical setting, the generic complexity to find collisions of an $n$-bit hash function is $O(2^{n/2})$, thus classical collision attacks based on differential cryptanalysis such as rebound attacks build differential trails with probability higher than $2^{-n/2}$.
By the same analogy, generic quantum algorithms such as the BHT algorithm find collisions with complexity $O(2^{n/3})$.
With quantum algorithms, a pair of messages satisfying a differential trail with probability $p$ can be generated with complexity $p^{-1/2}$.
Hence, in the quantum setting, some differential trails with probability up to $2^{-2n/3}$ that cannot be exploited in the classical setting may be exploited to mount a collision attack in the quantum setting.
In particular, the number of attacked rounds may increase.
In this paper, we attack two international hash function standards: AES-MMO and Whirlpool.
For AES-MMO, we present a $7$-round differential trail with probability $2^{-80}$ and use it to find collisions with a quantum version of the rebound attack,
while only $6$ rounds can be attacked in the classical setting.
For Whirlpool, we mount a collision attack based on a $6$-round differential trail from a classical rebound distinguisher with a complexity higher than the birthday bound. This improves the best classical attack on 5 rounds by 1.
We also show that those trails are optimal in our approach.
Our results have two important implications.
First, there seems to exist a common belief that classically secure hash functions will remain secure against quantum adversaries. Indeed, several second-round candidates in the NIST post-quantum competition use existing hash functions, say SHA-3, as quantum secure ones. Our results disprove this common belief.
Second, our observation suggests that differential trail search should not stop with probability $2^{-n/2}$ but should consider up to $2^{-2n/3}$.
Hence it deserves to revisit the previous differential trail search activities.

2020

ASIACRYPT

Finding Collisions in a Quantum World: Quantum Black-Box Separation of Collision-Resistance and One-Wayness
📺 ★
Abstract

Since the celebrated work of Impagliazzo and Rudich (STOC 1989), a number of black-box impossibility results have been established. However, these works only ruled out classical black-box reductions among cryptographic primitives.
Therefore it may be possible to overcome these impossibility results by using quantum reductions.
To exclude such a possibility, we have to extend these impossibility results to the quantum setting.
In this paper, we study black-box impossibility in the quantum setting.
We first formalize a quantum counterpart of fully-black-box reduction following the formalization by Reingold, Trevisan and Vadhan (TCC 2004).
Then we prove that there is no quantum fully-black-box reduction from collision-resistant hash functions to one-way permutations (or even trapdoor permutations).
We take both of classical and quantum implementations of primitives into account.
This is an extension to the quantum setting of the work of Simon (Eurocrypt 1998) who showed a similar result in the classical setting.

2020

TOSC

Improved Attacks on sLiSCP Permutation and Tight Bound of Limited Birthday Distinguishers
Abstract

Limited birthday distinguishers (LBDs) are widely used tools for the cryptanalysis of cryptographic permutations. In this paper we propose LBDs on several variants of the sLiSCP permutation family that are building blocks of two round 2 candidates of the NIST lightweight standardization process: Spix and SpoC. We improve the number of steps with respect to the previously known best results, that used rebound attack. We improve the techniques used for solving the middle part, called inbound, and we relax the external conditions in order to extend the previous attacks. The lower bound of the complexity of LBDs has been proved only against functions. In this paper, we prove for the first time the bound against permutations, which shows that the known upper bounds are tight.

2019

ASIACRYPT

4-Round Luby-Rackoff Construction is a qPRP
Abstract

The Luby-Rackoff construction, or the Feistel construction, is one of the most important approaches to construct secure block ciphers from secure pseudorandom functions. The 3- and 4-round Luby-Rackoff constructions are proven to be secure against chosen-plaintext attacks (CPAs) and chosen-ciphertext attacks (CCAs), respectively, in the classical setting. However, Kuwakado and Morii showed that a quantum superposed chosen-plaintext attack (qCPA) can distinguish the 3-round Luby-Rackoff construction from a random permutation in polynomial time. In addition, Ito et al. recently showed a quantum superposed chosen-ciphertext attack (qCCA) that distinguishes the 4-round Luby-Rackoff construction. Since Kuwakado and Morii showed the result, a problem of much interest has been how many rounds are sufficient to achieve provable security against quantum query attacks. This paper answers to this fundamental question by showing that 4-rounds suffice against qCPAs. Concretely, we prove that the 4-round Luby-Rackoff construction is secure up to $$O(2^{n/12})$$ quantum queries. We also give a query upper bound for the problem of distinguishing the 4-round Luby-Rackoff construction from a random permutation by showing a distinguishing qCPA with $$O(2^{n/6})$$ quantum queries. Our result is the first to demonstrate the security of a typical block-cipher construction against quantum query attacks, without any algebraic assumptions. To give security proofs, we use an alternative formalization of Zhandry’s compressed oracle technique.

2019

ASIACRYPT

Quantum Attacks Without Superposition Queries: The Offline Simon’s Algorithm
Abstract

In symmetric cryptanalysis, the model of superposition queries has led to surprising results, with many constructions being broken in polynomial time thanks to Simon’s period-finding algorithm. But the practical implications of these attacks remain blurry. In contrast, the results obtained so far for a quantum adversary making classical queries only are less impressive.In this paper, we introduce a new quantum algorithm which uses Simon’s subroutines in a novel way. We manage to leverage the algebraic structure of cryptosystems in the context of a quantum attacker limited to classical queries and offline quantum computations. We obtain improved quantum-time/classical-data tradeoffs with respect to the current literature, while using only as much hardware requirements (quantum and classical) as a standard exhaustive search with Grover’s algorithm. In particular, we are able to break the Even-Mansour construction in quantum time $$\tilde{O}(2^{n/3})$$, with $$O(2^{n/3})$$ classical queries and $$O(n^2)$$ qubits only. In addition, we improve some previous superposition attacks by reducing the data complexity from exponential to polynomial, with the same time complexity.Our approach can be seen in two complementary ways: reusing superposition queries during the iteration of a search using Grover’s algorithm, or alternatively, removing the memory requirement in some quantum attacks based on a collision search, thanks to their algebraic structure.We provide a list of cryptographic applications, including the Even-Mansour construction, the FX construction, some Sponge authenticated modes of encryption, and many more.

2018

ASIACRYPT

Building Quantum-One-Way Functions from Block Ciphers: Davies-Meyer and Merkle-Damgård Constructions
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.

#### Coauthors

- Xavier Bonnetain (1)
- Tetsu Iwata (3)
- María Naya-Plasencia (2)
- Yu Sasaki (5)
- André Schrottenloher (1)
- Keita Xagawa (1)
- Takashi Yamakawa (1)
- Kan Yasuda (1)