Quantum computing over the rainbow

Seong-Min Cho, Seung-Hyun Seo

Recent rank-based attacks have reduced the security of Rainbow below the security requirements set out by NIST by speeding up repeated kernel finding operations using classical mathematics techniques. If quantum algorithms are applied to perform these repeated operations, the rank-based attacks may be more threatening and could dramatically lower the security level of Rainbow. In this paper, we propose a novel MinRank attack called Q-rMinRank attack, the first quantum approach to the key recovery attacks on Rainbow. By designing quantum circuits that can find the kernel, we achieved quadratic speedup for the MinRank attack to recover the private keys of Rainbow. We show that even the parameter set V of Rainbow does not meet the 128-bit security level, the minimum security requirement through our Q-rMinRank attack. It means that Rainbow is no longer secure in quantum computing environments.

Ryan Wilkinson

Paul M. B. Vitanyi

Yevheniy Kaptol

The paper identifies and analyzes attacks aimed at Rainbow post-quantum electronic signature cryptanalysis. Today, due to advances in the quantum computers development, the need to present new standards for electronic signatures resistant to both quantum and classical cryptanalysis arisen. To solve the lack of such electronic signatures, NIST USA is running the NIST PQC competition. As part of this competition some electronic signatures designed to resist quantum cryptanalysis were presented, including Rainbow electronic signature. CZ-Rainbow and the compressed Rainbow algorithm were also presented along with the regular Rainbow algorithm. This paper analysis attacks on all three types of electronic signature. The possibility of a quantum attack against the Rainbow electronic signature, as well as the complexity of such an attack, defines the possibility of this electronic signature usage during the post-quantum period.

Junghoon Park, Jiook Cha, Samuel Yen-Chi Chen +2 more

In the realm of artificial intelligence, deep rein-forcement learning (RL) agents struggle with generalizability and require substantial computational resources, unlike humans who easily adapt and generalize across tasks. To address these challenges, we introduce Quantum Rainbow, a hybrid algorithm that leverages the neural mechanisms of human decision-making and the efficiency of quantum computing. Quantum Rainbow combines variational quantum circuits with the Rainbow Deep Q-Network (DQN) model to create a novel approach in rein-forcement learning that integrates quantum principles into deep learning paradigms. We evaluate our model using behavioral experiments through the Iowa Gambling Task and 4-Armed Bandit Task. Our investigations reveal a significant relationship between the architecture of quantum circuits and the performance of quantum RL agents. Specifically, using causal discovery methods, we demonstrate the critical role of quantum entanglement in enhancing model performance. These findings not only show promising results but also pave the way for future explorations into optimizing quantum circuit architectures for reinforcement learning applications. This study underscores the potential of quantum-enhanced algorithms to achieve “quantum advantage” by addressing fundamental limitations in conventional deep RL methods.