Theoretical physics: Computing with rainbows

Olivier Pfister

Giovanni Battimelli, Giovanni Ciccotti, Pietro Greco

Steven E. Kaufman

In this article, physical reality as a whole is defined, thereby revealing the actual nature of physical reality to be that of a boundary created by a relation, as that boundary is apprehended from one side of the relation that brings it into existence. The reason we can’t pin down a specific physical reality, i.e., completely define any physical reality, is because in doing so we are trying to pin down what is effectively a miniature rainbow, trying to pin down that which is actually only the product of a relation, trying to pin down something that, in the final analysis, is not at all or in any way what is actually there, but only seems to be what is actually there. However, while we cannot ever pin down any specific physical reality for the reasons mentioned above, we can pin down the nature of physical reality as a whole. We cannot get to the end of a rainbow, because rainbows only appear to have an end. However, we can understand the true nature of the rainbow and understand how it is created and why it appears as it does. In the same way, although we cannot pin down any specific physical reality, we can understand the nature of physical reality as a whole, how physical reality is created and why physical reality appears as it does, if we are able to understand what it is that the phenomena of wave-particle duality and uncertainty are actually telling us about the nature of physical reality.

Michael J. Dinneen, Nies, André, Khoussainov, Bakhadyr

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.

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.