Kryptonite: Rosehip Post-quantum electronic signature algorithm

The main articles are:

• Post-quantum cryptography
• Electronic signature (EDS)

2023: Open implementation of the Rosehip algorithm from QApp

Russian companies with expertise in cryptography and quantum technologies are joining forces to prevent threats to cryptographic systems from quantum computers.

Thus, the open sale of the domestic post-quantum algorithm "Rosehip" company "" Kryptonite was prepared by the company "QApp" in the course of its activities as part of the working group "Post-quantum cryptographic mechanisms" (Technical Committee 26 Rosstandart TK 26). The project is written in a language Xi optimized for SSE4.1, SSE2 and MMX command sets. Source code available on GitHub^[1]library that can be embedded in industrial cryptographic devices and software products. This was announced on November 14, 2023 by representatives of the company. "QApp

source = "Kryptonite"

The use of code optimization leads to the proper speed of implementation of Rosehip. In tests on the Intel Core i7-8700, the generation of the key pair took 3 ms, the signature of one message - 848 milliseconds, and the signature verification - only 11 ms. explained by Sergey Grebnev, cryptanalyst and head of applied research at QApp

As reported, Rosehip is an electronic signature algorithm that is resistant to attacks using a quantum computer. It was developed by cryptographic experts of the Russian company Kryptonit, participating in the activities of the working group TK 26.

The Rosehip algorithm is based on the Stern code-theoretic identification protocol. The resistance of this counterfeit signature scheme is based on the complexity of the random line code decoding problem. Mathematics professor Alvin Berlecamp in 1978 proved that this problem belongs to the class of NP-complex problems. For problems of this class, effective solving algorithms are still unknown either on a classical computer or on a quantum one.

According to Kryptonite, as of November 2023, the best known attack using a classic computer on the Rosehip scheme will require 2 * 256 bit operations. That is, it cannot be performed in a reasonable time on the fastest supercomputers. Theoretical resistance to a "quantum" attack is estimated at 2^170 operations, which also makes it impossible even on quantum computers of the future with billions of working qubits.

I consider the publication of the software implementation of the Rosehip signature scheme to be a significant event in the international cryptographic community and an important milestone in the development of domestic post-quantum cryptography. It allows you to create optimal implementations of electronic signature, resistant to attacks using supercomputers of traditional architecture and only quantum computers under development. explained Vasily Shishkin, head of the cryptography laboratory at Kryptonit

If you follow the path of the traditional principle of counteraction: first a problem, and then a solution, then you cannot build reliable information security solutions. In those distant years, scientists followed the path of developing protection without having a real threat. When mathematics and physics as a science stood at the origins of information protection, the main foundation was laid in post-quantum cryptography and protection against attacks using quantum computers in the real absence of powerful computers. In November 2023, when computing power performs the most complex operations in fractions of seconds, we see how the Post-Quantum Cryptographic Mechanisms working group, consisting of leading specialists from Kryptonit and Cyberhab Skolkovo resident company QApp, created an open implementation of the post-quantum algorithm of the Rosehip electronic signature. This algorithm will ensure the integrity and availability of information when transmitted over any distance and will be relevant for many more years. added Igor Biryukov, head of Cyberhab Skolkovo

The development of quantum computers is carried out by the largest players in the IT industry. Already in November 2023, there are existing prototypes that execute specific algorithms faster than supercomputers of traditional architecture. Gartner analysts expect universal and commercially available quantum computers by 2030. This poses risks to information security, since with a sufficiently powerful quantum computer it will be possible to hack many cryptographic algorithms. All online services - from online stores to large state portals, as well as remote management systems - can become vulnerable. Working proactively, Kryptonit and QApp are consistently developing and standardizing post-quantum cryptographic mechanisms that will remain relevant even after the advent of quantum computers.

Notes