International Association
for Cryptologic Research

Cryptographic group actions are a leading contender for post- quantum cryptography, and have also been used in the development of quantum cryptographic protocols. In this work, we explore quantum state group actions, which consist of a group acting on a set of quantum states. We show the following results: – If enough copies of each state are provided, statistical (even query bounded) security is impossible. – We construct quantum state group actions and prove them secure in the bounded-copy regime for many computational problems that have been proposed by cryptographers. Depending on the construc- tion, our proofs are either unconditional, rely on LWE, or rely on the quantum random oracle model. While our analysis does not di- rectly apply to classical group actions, we argue it gives at least a sanity check that there are no obvious flaws in the post-quantum assumptions made by cryptographers. – Our quantum state group actions allows for unifying two existing quantum money schemes: those based on group actions, and those based on non-collapsing hashes. We also explain how they can unify classical and quantum key distribution.

It is well-known that digital signatures can be constructed from one-way functions in a black-box way. While one-way functions are essentially the minimal assumption in classical cryptography, this is not the case in the quantum setting. A variety of qualitatively weaker and inherently quantum assumptions (e.g. EFI pairs, one-way state generators, and pseudorandom states) are known to be sufficient for non-trivial quantum cryptography. While it is known that commitments, zero-knowledge proofs, and even multiparty computation can be constructed from these assumptions, it has remained an open question whether the same is true for quantum digital signatures schemes (QDS). In this work, we show that there does not exist a black-box construction of a QDS scheme with classical signatures from pseudorandom states with linear, or greater, output length. Our result complements that of Morimae and Yamakawa (2022), who described a one-time secure QDS scheme with classical signatures, but left open the question of constructing a standard multi-time secure one.