International Association
for Cryptologic Research

Different flavors of quantum pseudorandomness have proven useful for various cryptographic applications, with the compelling feature that these primitives are potentially weaker than post-quantum one-way functions. Notably, Ananth, Lin, and Yuen (2023) have shown that logarithmic pseudorandom states can be used to construct a pseudo-deterministic $\PRG$: informally, for a fixed seed, the output is the same with $1-1/poly$ probability. In this work, we introduce new definitions for $\botPRG$ and $\botPRF$. The correctness guarantees are that, for a fixed seed, except with negligible probability, the output is either the same (with probability $1-1/poly$) or recognizable abort, denoted $\bot$. Our approach admits a natural definition of multi-time $\PRG$ security, as well as the adaptive security of a $\PRF$. We construct a $\botPRG$ from any pseudo-deterministic $\PRG$ and, from that, a $\botPRF$. While many Minicrypt primitives--such as symmetric encryption, commitments, MACs, and length-restricted one-time digital signatures--have been realized from quantum pseudorandomness assumptions, constructing full digital signatures remained an open challenge, and was explicitly posed as an open question by Morimae and Yamakawa (Crypto 2022). We resolve this by presenting the first (quantum) digital signature scheme with classical public keys and signatures from logarithmic pseudorandom states, utilizing our construction of $\botPRF$s. Additionally, we construct CPA secure public-key encryption with tamper-resilient quantum public keys. Combined with a recent work of Barhoush, Nishimaki, and Yamakawa (2025), our results demonstrate that these applications can be realized under assumptions that are separated from quantum evaluatable one-way functions.

In 1974, Ralph Merkle proposed the first unclassified protocol for secure communications over insecure channels. When legitimate communicating parties are willing to spend an amount of computational effort proportional to some parameter  N , an eavesdropper cannot break into their communication without spending a time proportional to  $$N^2$$ N 2 , which is quadratically more than the legitimate effort. In a quantum world, however, Merkle’s protocol is immediately broken by Grover’s algorithm, but it is easily repaired if we are satisfied with a quantum protocol against which a quantum adversary needs to spend a time proportional to $$N^{3/2}$$ N 3 / 2 in order to break it. Can we do better? We give two new key establishment protocols in the spirit of Merkle’s. The first one, which requires the legitimate parties to have access to a quantum computer, resists any quantum adversary who is not willing to make an effort at least proportional to  $$N^{5/3}$$ N 5 / 3 , except with vanishing probability. Our second protocol is purely classical, yet it requires any quantum adversary to work asymptotically harder than the legitimate parties, again except with vanishing probability. In either case, security is proved for a typical run of the protocols: the probabilities are taken over the random (or quantum) choices made by the legitimate participants in order to establish their key as well as over the random (or quantum) choices made by the adversary who is trying to be privy to it.

We investigate sampling procedures that certify that an arbitrary quantum state on n subsystems is close to an ideal mixed state $$\varphi ^{\otimes n}$$ for a given reference state $$\varphi $$, up to errors on a few positions. This task makes no sense classically: it would correspond to certifying that a given bitstring was generated according to some desired probability distribution. However, in the quantum case, this is possible if one has access to a prover who can supply a purification of the mixed state.In this work, we introduce the concept of mixed-state certification, and we show that a natural sampling protocol offers secure certification in the presence of a possibly dishonest prover: if the verifier accepts then he can be almost certain that the state in question has been correctly prepared, up to a small number of errors.We then apply this result to two-party quantum coin-tossing. Given that strong coin tossing is impossible, it is natural to ask “how close can we get”. This question has been well studied and is nowadays well understood from the perspective of the bias of individual coin tosses. We approach and answer this question from a different—and somewhat orthogonal—perspective, where we do not look at individual coin tosses but at the global entropy instead. We show how two distrusting parties can produce a common high-entropy source, where the entropy is an arbitrarily small fraction below the maximum.