Paper 2025/376

Another Look at the Quantum Security of the Vectorization Problem with Shifted Inputs

Abstract

Cryptographic group actions provide a basis for simple post-quantum generalizations of many cryptographic protocols based on the discrete logarithm problem (DLP). However, many advanced group action-based protocols do not solely rely on the core group action problem (the so called vectorization problem), but also on variants of this problem, to either improve efficiency or enable new functionalities. For example, the security of the CSI-SharK threshold signature protocol relies on the hardness of the Vectorization Problem with Shifted Inputs where (in DLP formalism) the adversary not only receives g and g^x, but also g^(x^c) for multiple known values of c. A natural open question is whether the additional data allows adversaries to solve the underlying problem more efficiently. We revisit the concrete quantum security of this problem. We start from a quantum multiple hidden shift algorithm of Childs and van Dam, which to the best of our knowledge was never applied in cryptography before. We describe and analyze a variant of this algorithm, and we specify and analyze all its subroutines to provide concrete complexity estimates. We then apply our analysis to the CSI-SharK protocol. In prior analyses based on Kuperberg’s algorithms, group action evaluations contributed to a significant part of the overall T-gate cost. For CSI-SharK’s suggested parameters, our new approach requires significantly fewer calls to the group action evaluation subroutine, leading to significant complexity improvements overall. We describe two instances of our approach, one minimizing the T-gate complexity, and the other one keeping qubit requirements small, both of them resulting in significant complexity improvements over previous works. More generally, we quantify the quantum security degradation resulting from additional published data in the CSI-SharK protocol.

Note: Includes full proofs and appendices. Small changes made to probability of success proof in Section 3, and qubit counts in Table 1. Publication info updated.