Abstract Many quantum algorithms for attacking symmetric cryptography involve the rank problem of quantum linear equations. In this paper, two quantum algorithms are proposed to solve quantum linear systems of equations with coherent superposition, and their specific quantum circuits are constructed. In contrast to previous related studies, our quantum algorithms are universal, computing both the rank and general solution by one measurement. The difference between them is whether the data register containing the quantum coefficient matrix can be disentangled from the other registers while keeping the data qubits unchanged. On this basis, the two quantum algorithms are applied as subroutines to parallel Simon’s algorithm (with multiple periods), Grover Meets Simon algorithm, and Alg-PolyQ2 algorithm. Subsequently, a quantum classifier within Grover Meets Simon algorithm and a detailed test oracle within Alg-PolyQ2 algorithms are constructed, including their respective quantum circuits. To the best of our knowledge, no such specific analysis has been previously performed. The success probability of these algorithms is rigorously analyzed to ensure that the probability of success on the proposed quantum algorithms will not be lower than that of the original algorithms. Finally, we discuss the lower bound of the number of controlled-NOT gates for solving quantum linear systems of equations with coherent superposition. Our analysis indicates that the proposed algorithms are suitable for conducting attacks against lightweight symmetric ciphers within the effective working time of an ion-trap quantum computer.

Accountable anonymous credentials protect user privacy while holding the accountability of ill-intentioned individuals, which is a critical feature for applications such as online payments and other financial services. Existing accountable anonymous credentials rely on a public committee of trustworthy members who are assumed not to collude and are well protected to perform privacy revocation. However, this assumption is unsound in blockchain-based cryptocurrency systems because the selected committees may involve nodes with significant stakes, and public nodes serving as committee members are vulnerable against targeted attacks from high-computing power adversaries. In this paper, we propose an improved accountable anonymous credential called AccCred, allowing users and issuers to randomly select a hidden committee within a set of authenticated candidates for privacy revocation. No one except the members with corresponding private keys knows their identity, preventing proactive attacks. As a core component, we introduce the primitive of dynamic triple-hiding committees (DTHC), which achieves authentication, dynamic join/delete, random selection, and strong anonymity of committee members. As a building block of DTHC, we design a shuffle protocol to provide efficient shuffle proof of randomized public keys. We formally prove our scheme and compare its performance with previous work for demonstration of practicality.

Abstract The National Institute of Standards and Technology (NIST) has been working on standardization of post-quantum cryptography and is approaching the end of round-3 evaluation of algorithms. Key reuse security evaluation is an important part of algorithm evaluation. In order to evaluate the key reuse security of candidate IND-CPA PKEs, at Eurocrypt’19, B$\breve{\text{a}}$etu et al. proposed a classical key recovery under plaintext checking attack (KR-PCA) which can recover the reused secret keys by querying an oracle thousands of times. However, the method does not work for cryptosystems which shorten ciphertexts by rounding off the low bits, such as round-3 finalists Kyber and Saber. Subsequently, Dumittan and Vaudenay (ACNS’20) and Qin et al. (ASIACRYPT’21) came up with new effective methods, which require carefully constructed queries. In this paper, we propose an automatic method to recover the reused secret keys of IND-CPA PKEs in Kyber and Saber. Instead of constructing queries carefully, our method uses automated search combined with an optimized bruteforce. The effect and cost of the method depend on the specific parameters. In particular, we can recover the secret keys after thousands of queries in all parameter sets, which is comparable with the current best result.

In this paper, we study applications of Bernstein–Vazirani algorithm and present several new methods to attack block ciphers. Specifically, we first present a quantum algorithm for finding the linear structures of a function. Based on it, we propose new quantum distinguishers for the 3-round Feistel scheme and a new quantum algorithm to recover partial key of the Even–Mansour construction. Afterwards, by observing that the linear structures of a encryption function are actually high probability differentials of it, we apply our algorithm to differential analysis and impossible differential cryptanalysis respectively. We also propose a new kind of differential cryptanalysis, called quantum small probability differential cryptanalysis, based on the fact that the linear structures found by our algorithm are also the linear structure of each component function. To our knowledge, no similar method was proposed before. The efficiency and success probability of all attacks are analyzed rigorously. Since our algorithm treats the encryption function as a whole, it avoid the disadvantage of traditional differential cryptanalysis that it is difficult to extending the differential path.

The development of quantum computers has urged the cryptographic community to prepare cryptographic primitives for the eventual arrival of the post‐quantum world. To this end, the authors study the witness indistinguishability (WI) and witness hiding (WH) of proof systems against quantum adversaries. They give formal definitions of quantum WI (QWI) and quantum WH (QWH), present proof systems satisfying these definitions, and specify a condition under which QWI implies QWH. Regarding the non‐interactive proof systems, they prove that, even if a common reference string is used to generate polynomially many non‐interactive proofs, the QWI is still preserved, while quantum zero‐knowledge has no such beneficial property. To show the strength of QWI, they present two applications of them. First, they prove that the construction proposed by Feige et al . that transforms any non‐interactive bounded zero‐knowledge proof system to a general one is also feasible against quantum adversaries. Second, they construct a quantum‐secure signature scheme in the CRS model, which is existentially unforgeable against quantum adversaries and remains secure even if a common random string is used to sign polynomially many messages.