What a lovely hat

The Gentry-Peikert-Vaikuntanathan (GPV) framework is utilized for constructing practical digital signatures, which is proven to be secure in both the classical/quantum random-oracle models. Falcon is such a signature scheme, recognized as a compact and efficient signature among NIST-standardized signature schemes. Recently, Guerreau et al. (CHES 2022) and Zhang et al. (Eurocrypt 2023) proposed the secret key recovery attack on Falcon utilizing signatures filtered by simple power analysis...

Collision-resistant hashing, a fundamental primitive in modern cryptography, ensures that there is no efficient way to find distinct inputs that produce the same hash value. This property underpins the security of various cryptographic applications, making it crucial to understand its complexity. The complexity of this problem is well-understood in the classical setting and $\Theta(N^{1/2})$ queries are needed to find a collision. However, the advent of quantum computing has introduced new...

In the quantum computation verification problem, a quantum server wants to convince a client that the output of evaluating a quantum circuit $C$ is some result that it claims. This problem is considered very important both theoretically and practically in quantum computation [arXiv:1709.06984, 1704.04487, 1209.0449]. The client is considered to be limited in computational power, and one desirable property is that the client can be completely classical, which leads to the classical...

A multitude of post-quantum key encapsulation mechanisms (KEMs) and public key encryption (PKE) schemes implicitly rely on a protocol by which Alice and Bob exchange public messages and converge on secret values that are identical up to some small noise. By our count, 24 out of 49 KEM or PKE submissions to the NIST Post-Quantum Cryptography Standardization project follow this strategy. Yet the notion of a noisy key agreement (NKA) protocol lacks a formal definition as a primitive in its own...

A fuzzy extractor (FE), proposed for deriving cryptographic keys from biometric data, enables reproducible generation of high-quality randomness from noisy inputs having sufficient min-entropy. FEs rely in their operation on a public "helper string" that is guaranteed not to leak too much information about the original input. Unfortunately, this guarantee may not hold when multiple independent helper strings are generated from correlated inputs as would occur if a user registers their...

We construct new leakage-resilient signature schemes. Our schemes remain unforgeable against an adversary leaking arbitrary (yet bounded) information on the entire state of the signer (sometimes known as *fully* leakage resilience), including the random coin tosses of the signing algorithm. The main feature of our constructions is that they offer a graceful degradation of security in situations where standard existential unforgeability is impossible. This property was recently put forward...

It is a long-standing open problem to prove the existence of (deterministic) hard-core predicates for the Computational Diffie-Hellman (CDH) problem over finite fields, without resorting to the generic approaches for any one-way functions (e.g., the Goldreich-Levin hard-core predicates). Fazio et al. (FGPS, Crypto '13) make important progress on this problem by defining a weaker Computational Diffie-Hellman problem over $\mathbb{F}_{p^2}$, i.e., Partial-CDH problem, and proving, when...

Fuzzy extractors (Dodis et al., Eurocrypt 2004) convert repeated noisy readings of a secret into the same uniformly distributed key. To eliminate noise, they require an initial enrollment phase that takes the first noisy reading of the secret and produces a nonsecret helper string to be used in subsequent readings. Reusable fuzzy extractors (Boyen, CCS 2004) remain secure even when this initial enrollment phase is repeated multiple times with noisy versions of the same secret, producing...

We adapt the concept of a programmable hash function (PHF, Crypto 2008) to a setting in which a multilinear map is available. This enables new PHFs with previously unachieved parameters. To demonstrate their usefulness, we show how our (standard-model) PHFs can replace random oracles in several well-known cryptographic constructions. Namely, we obtain standard-model versions of the Boneh-Franklin identity-based encryption scheme, the Boneh-Lynn-Shacham signature scheme, and the...

In a related-key attack (RKA) an adversary attempts to break a cryptographic primitive by invoking the primitive with several secret keys which satisfy some known, or even chosen, relation. We initiate a formal study of RKA security for \emph{randomized encryption} schemes. We begin by providing general definitions for semantic security under passive and active RKAs. We then focus on RKAs in which the keys satisfy known linear relations over some Abelian group. We construct simple and...

Consider an abstract storage device $\Sigma(\G)$ that can hold a single element $x$ from a fixed, publicly known finite group $\G$. Storage is private in the sense that an adversary does not have read access to $\Sigma(\G)$ at all. However, $\Sigma(\G)$ is non-robust in the sense that the adversary can modify its contents by adding some offset $\Delta \in \G$. Due to the privacy of the storage device, the value $\Delta$ can only depend on an adversary's {\em a priori} knowledge of $x$. We...