Black-box security of stream ciphers under the quantum algorithm for linear systems of equations

Abstract

In this paper, we analyse the impact of the HHL quantum algorithm on stream ciphers in a black-box setting. We assume a black-box access to an oracle MS defining the output of the stream cipher. For a state k encapsulating the key material, the value MS ⋅ k is the keystream (k'1, k'2, ..., k'N) generated by some stream cipher S. We translate this scenario into the quantum setting and describe how the HHL algorithm could be used to attack this construction. Further, we give simple and verifiable criteria under which a black-box attack on stream ciphers with the HHL algorithm is not efficiently feasible. Usually, these criteria follow from already known design principles for symmetric ciphers and should apply to the ciphers used today. We complement the criteria with a simple test, which confirms the resistance of said cipher. Moreover, we use our technique to test the currently used stream ciphers: Trivium, HC-128, and Salsa20.