An oracle refers to something that can be queried by an oracle algorithm, which is often oblivious to the internal working of that oracle. An oracle algorithm may be given query access to multiple oracles, choosing which oracle to query depending on its previous querying responses. We refer to a multi-oracle algorithm with such dependency as an adaptive oracle algorithm, as opposed to a static one with a pre-determined querying order, which may be easier to analyze and sometimes results in a better bound. In [DFH22], we show that, so long as dummy queries can be made, there is a generic compiler transforming any adaptive multi-oracle algorithm to a static one, with only a mild blow-up in its query complexity. Concretely, if A makes at most q₁, ... , qₙ queries to oracles O₁, ... , Oₙ respectively, then the after-compiled algorithm makes at most n·q₁, ... , n·qₙ queries to O₁, ... , Oₙ respectively.

Random Oracle Model (ROM)

A random oracle generally refers to a function H(x) where each entry of its output table is sampled uniformly and independently. An oracle algorithm can then interact with H in order to learn its output, expecting consistent response throughout different queries. It is often treated as an idealization of a cryptographic hash function, and security proven in this model typically carries over to a more realistic setting. E.g. an algorithm A given bounded query to H should be hard to find an input x such that H(x) = 0, which reflects the zero-preimage resistance of a cryptographic hash function.

In light of quantum algorithms that may evaluate a hash function in quantum superposition, it is then natural to consider a quantum query, which implements the unitary |x, y⟩ ↦ |x, y + H(x)⟩. However, this kind of queries is much tricker to handle, compared to its classical counterpart.

In [CFHL21], we revisit a powerful technique for analyzing query complexities in QROM that is due to Mark Zhandry called compressed oracle. One of our main contribution is a generic framework that is capable of liting a broad class of classical analyses into a quantum one, via only classical reasoning. E.g. with the framework in place, we are able to show that a hash chain x, H(x), H(H(x)), ... ,H(...H(x)...) of length q is hard to find in less than q sequential query rounds, even if each round consists of many queries in parallel. As a main application, we prove quantum security of a particular proof-of-sequentail-work (PoSW) scheme constructed by Cohen and Pietrzak, where a prover needs to perform sufficently many sequetial computational work in order to convince a verifier.

Split-key Pseudorandom Function (skPRF)

In the cryptographic setting, an oracle algorithm may as well be tasked to solve a decisional problem. One notable example is in the context of a pseudorandom function F, where an oralce algorithm in each query sends over an input x, and then is tasked to distinguish the following two cases:

1. Each query is responded with a function output F(k,x) where k is a secret key hidden away from A.

2. Each query is responded with a function output R(x) where R is a uniformly sampled random function independent of the key.

A pseudorandom function F should be such that it is infeasible to distinguish the two cases.

In addition, we are interested in the so-called split-key pseudorandom function (skPRF), which is a function F(k₁, ... , kₙ, x) consisting of many keys k₁, ... , kₙ and an input x, such that for every key kᵢ it is a PRF subject to a minor restriction that an attacker never queries the same input x twice. Giacon, Heuer, and Poettering pointed out that a skPRF give rise to a combiner for key encapsulation mechanisms (KEM), which combines multiple KEMs into one that is secure as long as one of the component is; in addition, they also constructed and analyzed the classical security of a particularly efficient construction of skPRF

F(k₁, ... , kₙ, x) := H(h(k₁, ... , kₙ, x)),

where H is a cryptographic hash function modelled as a random oracle, and the min-entropy of h(k₁, ... , kₙ, x) is high whenever one of the keys kᵢ is random. As a main application of our compiler for multi-oracle algorithms, we show in [DFH22] that this skPRF is indeed quantum secure (in ROM).

A digital signature scheme is a set of algorithms that, in analogy with a hand-written one, allows one with their own secret key to sign a message on behalf of themself (but no others), which can then be verified with a paired up public key. Such a scheme should prevent any feasible non-key-holder to produce a valid signature. This is generally referred to as the unforgeability. In a typical context, an attacker may even be given existing signatures, in which case they are tasked to forge a new one. These are known as the chosen message attack (CMA), and unforgeability in this setting, UF-CMA, has long been regarded as one of the standard, integral requirements of a signature scheme.

Fiat-Shamir with Aborts

For more than a decade, the so-called Fiat-Shamir with Aborts (FSwA) paradigm has been very useful in constructing many post-quantum signature schemes as well as non-interactive zero-knowledge proofs (NIZK).  E.g. one of the future global standard, Dillithium, is constructed via FSwA. In [BBD+24], we discovered a very subtle flaw in the security proof of FSwA. Such a flaw is discovered in the course of a formal verification project, and cannot be easily patched especially in the quantum setting. We fix the flaw via a new proof from scratch, with a worse generic bound compared to prior claims, and launch a more re-fined, computer-aided concrete analysis for the case of Dilithium in order to recover its security level.

Quantum Security of HAWK

HAWK is one of the new candidates in the NIST PQC competition. Upon its first proposal, there has been a classical security proof in the random oracle model (ROM), which reduces its (strong variant of) UF-CMA security into a novel lattice-based assumption called one-more Shortest Vector Problem (omSVP). However, the security proof does not carry over to the quantum setting. In [FH23], we provide a quantum security proof in ROM, reducing its UF-CMA security, into the very same omSVP, confirming prior intuition that HAWK is as secure against quantum attackers as it is against classical ones.

Advanced Signature Schemes

There have been studies on the signature schemes with advanced functionalities and/or securities. A notable example is the so-called ring signature schemes, which allow one to anonymously sign a message on behalf of a group of players. In [CHH+21], we further consider the setting where a manager with their master secret key is granted the power to open -- revealing signer's identity -- later. Depending on technical details, such a scheme may be referred to as a group signature (GS) scheme or an accountable ring signature (ARS) scheme. We construct such an ARS/GS from the group-action decisional Diffie-Hellman (GA-DDH) assumption, which can be realized in the isogeny-based cryptography. Our construction is proven quantum secure (in the random oracle model), which is the targeted selling point compared to existing constructions with classical analysis.

A hand-written signature (say, to sign for a parcel) typically also acts as a proof that the signed message was once at the hand of its signer. However, a digital signature is separable from its message, and an attacker may be able to produce a valid signature under a message he has never received. For instance, this may be done via adapting an existing signature without knowing its underlying message. Such a threat is not merely hypothetical -- there have been real-life protocols under attack because of it, which is a motivation aiming for additional security properties for a signature scheme.

As of 2016, the US National Institute of Standards and Technology (NIST) initiated a competition for establishing post-quantum cryptographic standards. Since the winner schemes of round 3 were sellected, they started an additional call for signature schemes for the sake of variety, in which they recommend candidates to aim for several "additional security properties" beyond the standard unforgeability. These additional properties, e.g. message-bound signature, exclusive ownership, and non-resignability (NR) works as an extra layer of protection in case a signature scheme is mis-used within a higher-level protocol. For our works, we are mainly concerned with NR.

In order to achieve the aforementioned securities, BUFF transformation is proposed by Cremers, Düzlü, Fiedler, Janson, and Fischlin. They set up formal definitions of these additional security properties, and argue that BUFF compiles any signature scheme into another one that achieves them. However, in [DFHS24], we showed that this particular definition of NR cannot be achieved, and in particular BUFF does not achieve it, reflecting flaws within prior security justification of BUFF. Several alternative definitions of NR that are still meaningful have been proposed ever since, but it remained open whether BUFF achieves any of them. In [DFHLS24], we then show that BUFF achieves almost the strongest possible definition of NR, facing existing negative results, regaining our confidence toward its security.