To see the other types of publications on this topic, follow the link: Rainbow Signature Scheme.
Journal articles on the topic 'Rainbow Signature Scheme'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 21 journal articles for your research on the topic 'Rainbow Signature Scheme.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.
1
Ostrianska, Yelyzaveta, and Olha Mirzoieva. "Generation of general system parameters for Rainbow signature scheme." Physico-mathematical modelling and informational technologies, no. 33 (September 3, 2021): 83–87. http://dx.doi.org/10.15407/fmmit2021.33.083.
Full textAbstract:
The paper considers the description of electronic signature scheme Rainbow, which is based on multivariate transformations. It is a generalization of the UOV structure, which provides efficient parameterization due to the additional algebraic structure. The article provides an initial analysis of known attacks on the ES Rainbow scheme. Also, algorithms for generating general system parameters for 384 and 512 security bits were developed and the results are presented in this paper. The study found that the Rainbow signature generation process consists of simple operations of linear algebra, such as multiplying matrix vectors and solving linear systems over small finite fields. Another advantage of Rainbow is that this scheme offers very small signatures of only a few hundred bits. But the main disadvantage of Rainbow is the large size of public keys.
2
Luyen, Le. "An Improved Identity-Based Multivariate Signature Scheme Based on Rainbow." Cryptography 3, no. 1 (March 17, 2019): 8. http://dx.doi.org/10.3390/cryptography3010008.
Full textAbstract:
Multivariate Public Key Cryptography (MPKC) is one of the main candidates for post-quantum cryptography, especially in the area of signature schemes. In this paper, we instantiate a certificate Identity-Based Signature (IBS) scheme based on Rainbow, one of the most efficient and secure multivariate signature schemes. In addition, we revise the previous identity-based signature scheme IBUOV based on the Unbalanced Oil and Vinegar (UOV) scheme on the security and choice of parameters and obtain that our scheme is more efficient than IBUOV in terms of key sizes and signature sizes.
3
Maleeva, G. A. "Analysis of partial key recovery attack on multivariate cryptographic transformations using rank systems." Radiotekhnika, no. 209 (June 24, 2022): 64–70. http://dx.doi.org/10.30837/rt.2022.2.209.06.
Full textAbstract:
The Rainbow signature scheme, proposed by Ding and Schmidt in 2005, is one of the oldest and most studied signature schemes in multidimensional cryptography. The Rainbow, based on the unbalanced Oil and Vinegar signature scheme, has the necessary cryptocurrency since 1999 with the right parameters. Interest in multivariate cryptography has increased in the last decade, as it is considered to be quantum-stable.
Cryptanalysis of the Rainbow and its predecessors was actively developed in the early 2000s. Attacks from this era include the MinRank attack, the HighRank attack, the Bill-Gilbert attack, the UOV agreement attack, and the Rainbow bandwidth attack. After 2008, cryptanalysis seemed to have stopped, until the Rainbow's participation in the NIST PQC project, which motivated the continuation of cryptanalysis. During the second round of NIST, Bardett and others proposed a new algorithm for solving the MinRank problem. This dramatically increased the effectiveness of MinRank's attack, although not enough to threaten the parameters provided to NIST. A less memory-intensive version of this algorithm was suggested by Baena et al. Perlner and Smith-Tone analyzed the Rainbow bandwidth attack in depth, which showed that the attack was more effective than previously thought. This prompted the Rainbow team to increase slightly the parameters for the third round. During the third round, Bellens introduced a new attack that reduced the Rainbow's security by 220 times for SL 1. The Rainbow team claimed that despite the new attacks, the Rainbow's parameters still met NIST requirement.
The purpose of this article is to present two new (partial) key recovery attacks on multivariate cryptographic transformations using rank systems.
4
Shang, Pei Ni, and Zhu Lian Gao. "An Authentication Scheme Based on the Light-Weight Rainbow Signature for Wireless Sensor Network." Applied Mechanics and Materials 519-520 (February 2014): 185–88. http://dx.doi.org/10.4028/www.scientific.net/amm.519-520.185.
Full textAbstract:
Based on the rainbow signature scheme and combining the minus perturbation method of the Shamir, a new light-weight rainbow signature scheme is proposed. This scheme only uses the addition and multiplication operation, so it can be performed easily. This scheme has high security and can resist the minimal rank, rank reduction attacks and oil-vinegar attacks, etc. Based new signature scheme, we also design authentication mechanism for the WSN. According to the characters of the cluster WSN, this authentication mechanism can choose proper authentication parameters to realize the authentication on the cluster WSN by the platform and the authentication between the sensor node and its neighbor nodes.
5
Yesina, M. V., S. O. Kandiy, E. V. Ostryanska, and I. D. Gorbenko. "Generation of general system parameters for Rainbow electronic signature scheme for 384 and 512 security bits." Radiotekhnika, no. 204 (April 9, 2021): 16–23. http://dx.doi.org/10.30837/rt.2021.1.204.02.
Full textAbstract:
Today, there is rapid progress in the creation of quantum computers to solve various computational problems and for different purposes. At the same time, special efforts are made to create such a quantum computer that can solve the problems of cryptanalysis of existing cryptosystems: asymmetric ciphers, key encapsulation protocols, electronic signatures, etc. Prevention of such threats can be achieved by developing cryptographic systems that will be protected against both quantum and classical attacks, and be able to interact with existing protocols and communication networks. There is also a significant need for protection against attacks by side channels. Currently, significant efforts of cryptologists are focused on the NIST PQC open competition. The main idea of the NIST PQC competition is to define mathematical methods based on which standards for asymmetric cryptotransformations, primarily electronic signatures, as well as asymmetric ciphers and key encapsulation protocols can be developed. Three electronic signature schemes – Crystals-Dilithium, Falcon and Rainbow become the finalists of the third stage of the NIST PQC competition according to the results of the second stage. The first two are based on the mathematics of algebraic lattices, and Rainbow is based on multivariate transformations. Currently, a comprehensive analysis of the finalists is an important task for the entire global crypto community. The vast majority of schemes that have become finalists or alternative algorithms are based on problems in the theory of algebraic lattices. Special attention was also paid to the Rainbow electronic signature scheme based on multivariate transformations. The purpose of this work consists in a preliminary analysis of existing attacks on promising electronic signature Rainbow, definition of requirements to the system-wide parameters to ensure cryptographic stability of at least 512 bits against classical and 256 bits against quantum cryptanalysis, as well as development and practical implementation of Rainbow algorithms for generating system-wide parameters for 512 bits against classical and 256 bits against quantum cryptanalysis.
6
Maleeva, G. А. "Analysis of security of post-quantum algorithm of Rainbow electronic signature against potential attacks." Radiotekhnika, no. 205 (July 2, 2021): 85–93. http://dx.doi.org/10.30837/rt.2021.2.205.08.
Full textAbstract:
Multidimensional public key cryptography is a candidate for post-quantum cryptography, and it makes it possible to generate particularly short signatures and quick verification. The Rainbow signature scheme proposed by J. Dean and D. Schmidt is such a multidimensional cryptosystem and it is considered to be protected against all known attacks. The need for research on Rainbow ES is justified by the fact that there is a need to develop and adopt a post-quantum national securities standard, and that in the process of the US NIST competition on the mathematical basis of cryptographic transformation method Rainbow, promising results. Therefore, it is considered important to take them into account and use them in Ukraine. The Rainbow signature scheme can be implemented simply and efficiently using linear algebra methods over a small finite field and, in particular, creates shorter signatures than those used in RSA and other post-quantum signatures [1]. In the 2nd round of NIST PQC, protected sets of Rainbow parameters are offered and several attacks on them are analyzed [1]. When comparing ES, preference is given to ES algorithms that have been selected according to unconditional criteria, as well as those that have better indicators for integral conditional criteria, because such a technique is more rational. In particular, the Rainbow-Band-Separation (RBS) attack [2] is the best known Rainbow attack with a certain set of parameters and is important. The Rainbow-Band-Separation attack restores the Rainbow secret key by solving certain systems of quadratic equations, and its complexity is measured by a well-known measure called the degree of regularity. However, as a rule, the degree of regularity is greater than the degree of solution in experiments, and it is impossible to obtain an accurate estimate. The paper proposes a new indicator of the complexity of the Rainbow-Band-Separation attack using F4 algorithm, which gives a more accurate estimate compared to the indicator that uses the degree of regularity.
The aim of the work is a comparative analysis of ES based on MQ-transformations on the criterion of stability-complexity and an attempt to understand the security of Rainbow against RBS attack using F4.
7
Kandiy, S. O., and G. A. Maleeva. "Analysis of the complexity of attacks on multivariate cryptographic transformations using algebraic field structure." Radiotekhnika, no. 204 (April 9, 2021): 59–65. http://dx.doi.org/10.30837/rt.2021.1.204.06.
Full textAbstract:
In recent years, interest in cryptosystems based on multidimensional quadratic transformations (MQ transformations) has grown significantly. This is primarily due to the NIST PQC competition [1] and the need for practical electronic signature schemes that are resistant to attacks on quantum computers. Despite the fact that the world community has done a lot of work on cryptanalysis of the presented schemes, many issues need further clarification. NIST specialists are very cautious about the standardization process and urge cryptologists [4] in the next 3 years to conduct a comprehensive analysis of the finalists of the NIST PQC competition before their standardization.
One of the finalists is the Rainbow electronic signature scheme [2]. It is a generalization of the UOV (Unbalanced Oil and Vinegar) scheme [3]. Recently, another generalization of this scheme – LUOV (Lifted UOV) [5] was found to attack [6], which in polynomial time is able to recover completely the private key. The peculiarity of this attack is the use of the algebraic structure of the field over which the MQ transformation is given. This line of attack has emerged recently and it is still unclear whether it is possible to use the field structure in the Rainbow scheme.
The aim of this work is to systematize the techniques used in attacks using the algebraic field structure for UOV-based cryptosystems and to analyze the obstacles for their generalization to the Rainbow scheme.
8
Chen, Jiahui, Jie Ling, Jianting Ning, and Jintai Ding. "Identity-Based Signature Schemes for Multivariate Public Key Cryptosystems." Computer Journal 62, no. 8 (March 5, 2019): 1132–47. http://dx.doi.org/10.1093/comjnl/bxz013.
Full textAbstract:
Abstract In this paper, we proposed an idea to construct a general multivariate public key cryptographic (MPKC) scheme based on a user’s identity. In our construction, each user is distributed a unique identity by the key distribution center (KDC) and we use this key to generate user’s private keys. Thereafter, we use these private keys to produce the corresponding public key. This method can make key generating process easier so that the public key will reduce from dozens of Kilobyte to several bits. We then use our general scheme to construct practical identity-based signature schemes named ID-UOV and ID-Rainbow based on two well-known and promising MPKC signature schemes, respectively. Finally, we present the security analysis and give experiments for all of our proposed schemes and the baseline schemes. Comparison shows that our schemes are both efficient and practical.
9
Tan, Yang, Yong Yu, Jie Chen, Shaohua Tang, and Xiangxue Li. "Building a new secure variant of Rainbow signature scheme." IET Information Security 10, no. 2 (March 1, 2016): 53–59. http://dx.doi.org/10.1049/iet-ifs.2015.0016.
Full text
10
Reshikeshan, Sree Subiksha, Myung Bae Koh, and Mahesh Illindala. "Rainbow Signature Scheme to Secure GOOSE Communications From Quantum Computer Attacks." IEEE Transactions on Industry Applications 57, no. 5 (September 2021): 4579–86. http://dx.doi.org/10.1109/tia.2021.3093375.
Full text
11
Harmash, D. V. "Properties of the Rainbow multi-variant algorithm and its ability to resist various crypto-analysis methods and attack by outside channels." Radiotekhnika, no. 205 (July 2, 2021): 79–84. http://dx.doi.org/10.30837/rt.2021.2.205.07.
Full textAbstract:
This work presents the analysis of the essence and possibilities of protection of the Rainbow post-quantum cryptographic algorithm. The main properties of the Rainbow algorithm and the general essence of cryptographic encryption and electronic signature algorithms based on multivariate quadratic transformations are determined. The main provisions regarding the protocols are given. Analyses are given regarding the ability to protect the algorithm against various attacks. The vulnerability of the algorithm to attack by third-party channels is investigated. The general provisions of the algorithm are considered. The algorithm is presented and considered from a mathematical point of view, as well as the mathematical essence of cryptographic algorithms for encryption and electronic signature based on multivariate quadratic transformations. The application of various methods of cryptanalysis against cryptographic algorithm based on multivariate quadratic Rainbow transformations is studied. The method of decreasing rank against the Rainbow algorithm is analyzed. The method of cryptanalysis by attacking the Oil-Vinegar scheme and the method of cryptanalysis "minranku method" are investigated. The attack is studied using a multilayer structure.
12
Richter, Maximilian, Magdalena Bertram, Jasper Seidensticker, and Alexander Tschache. "A Mathematical Perspective on Post-Quantum Cryptography." Mathematics 10, no. 15 (July 25, 2022): 2579. http://dx.doi.org/10.3390/math10152579.
Full textAbstract:
In 2016, the National Institute of Standards and Technology (NIST) announced an open competition with the goal of finding and standardizing suitable algorithms for quantum-resistant cryptography. This study presents a detailed, mathematically oriented overview of the round-three finalists of NIST’s post-quantum cryptography standardization consisting of the lattice-based key encapsulation mechanisms (KEMs) CRYSTALS-Kyber, NTRU and SABER; the code-based KEM Classic McEliece; the lattice-based signature schemes CRYSTALS-Dilithium and FALCON; and the multivariate-based signature scheme Rainbow. The above-cited algorithm descriptions are precise technical specifications intended for cryptographic experts. Nevertheless, the documents are not well-suited for a general interested mathematical audience. Therefore, the main focus is put on the algorithms’ corresponding algebraic foundations, in particular LWE problems, NTRU lattices, linear codes and multivariate equation systems with the aim of fostering a broader understanding of the mathematical concepts behind post-quantum cryptography.
13
Abdul Jamal, Nurul Amiera Sakinah, Muhammad Rezal Kamel Ariffin, Siti Hasana Sapar, and Kamilah Abdullah. "New Identified Strategies to Forge Multivariate Signature Schemes." Symmetry 14, no. 11 (November 10, 2022): 2368. http://dx.doi.org/10.3390/sym14112368.
Full textAbstract:
A rogue certificate authority (RCA) is a dishonest entity that has the trust of web browsers and users to produce valid key pairs which are vulnerable. This work analyses two acknowledged post-quantum secure Multivariate Quadratic Problem (MQP) based signature schemes, namely the UOV and Rainbow signature schemes that obtain their key pair from a potential RCA methodology. We revisit two and provide a novel RCA methodology that would enable adversaries to forge UOV and Rainbow signatures. We also lay out two strategies to identify whether the public parameters are generated by the first two methodologies. To this end, strategies to identify the third strategy remain elusive. As such, the UOV and Rainbow schemes remain vulnerable to forgery if it was forged via the third methodology.
14
Diachenko, Andriy, and Hanna Malieieva. "Description and generation of the key pair in the ES Rainbow algorithm." Physico-mathematical modelling and informational technologies, no. 32 (July 7, 2021): 111–15. http://dx.doi.org/10.15407/fmmit2021.32.111.
Full textAbstract:
This paper describes the representation and generation of a key pair for one of the promising candidates at the NIST USA level in the NIST PQC competition for the direction of digital signatures of the Rainbow algorithm. This algorithm is a candidate for the third round of selection and a possible option for Ukraine to build its own DS standards based on the mathematics of multivariable quadratic schemes (MQ transformations), which is used in this algorithm. Within the competition, the developers give several sets of parameters for different security levels and several possible implementations of the algorithm (classical, CZ, compressed), but the given description and performance measurements, for the described algorithm, concern the classical Rainbow scheme (although the declared performance improvement is also fair in relation to other versions).
15
Pokorný, David, Petr Socha, and Martin Novotný. "Equivalent Keys: Side-Channel Countermeasure for Post-Quantum Multivariate Quadratic Signatures." Electronics 11, no. 21 (November 4, 2022): 3607. http://dx.doi.org/10.3390/electronics11213607.
Full textAbstract:
Algorithms based on the hardness of solving multivariate quadratic equations present promising candidates for post-quantum digital signatures. Contemporary threats to implementations of cryptographic algorithms, especially in embedded systems, include side-channel analysis, where attacks such as differential power analysis allow for the extraction of secret keys from the device’s power consumption or its electromagnetic emission. To prevent these attacks, various countermeasures must be implemented. In this paper, we propose a novel side-channel countermeasure for multivariate quadratic digital signatures through the concept of equivalent private keys. We propose a random equivalent key to be generated prior to every signing, thus randomizing the computation and mitigating side-channel attacks. We demonstrate our approach on the Rainbow digital signature, but since an unbalanced oil and vinegar is its special case, our work is applicable to other multivariate quadratic signature schemes as well. We analyze the proposed countermeasure regarding its properties such as the number of different equivalent keys or the amount of required fresh randomness, and we propose an efficient way to implement the countermeasure. We evaluate its performance regarding side-channel leakage and time/memory requirements. Using test vector leakage assessment, we were not able to detect any statistically significant leakage from our protected implementation.
16
Kwon, HyeokDong, HyunJun Kim, MinJoo Sim, Wai-Kong Lee, and Hwajeong Seo. "Look-up the Rainbow: Table-based Implementation of Rainbow Signature on 64-bit ARMv8 Processors." ACM Transactions on Embedded Computing Systems, July 4, 2023. http://dx.doi.org/10.1145/3607140.
Full textAbstract:
Rainbow Signature Scheme is one of the finalists in the National Institute of Standards and Technology (NIST) Post-Quantum Cryptography (PQC) standardization competition, but failed to win because it has lack of stability in the parameter selection. It is the only signature candidate based on a multivariate quadratic equation. Rainbow signatures have smaller signature sizes compared to other post-quantum cryptography candidates. However, it requires expensive tower-field based polynomial multiplications. In this paper, we propose an efficient implementation of Rainbow signature using a look-up table-based multiplication method. The polynomial multiplications in Rainbow signatures are performed on the \(\mathbb {F}_{16} \) field, which is divided into sub-fields \(\mathbb {F}_{4} \) and \(\mathbb {F}_{2} \) under the tower-field method. To accelerate the multiplication process on target processors, we propose a look-up table-based tower-field multiplication technique. In \(\mathbb {F}_{16} \) , all values are expressed in 4-bit data format and can be implemented using a 256-byte look-up table access. The implementation uses the TBL and TBX instructions of the 64-bit ARMv8 target processor. For Rainbow III and Rainbow V, they are computed on the \(\mathbb {F}_{256} \) field using a additional 16-byte table instead of creating a new look-up table. The proposed technique uses the vector registers of 64-bit ARMv8 processors and can calculate 16 result values with a single instruction. We also proposed implementations that are resistant to timing attacks. There are two types of implementations. The first one is the cache side-attack resistant implementation, which utilizes the 128-byte cache lines of the M1 processor. In this implementation, cache misses do not occur, and cache hits always occur. The second type is the constant-time implementation. This method takes a step-by-step approach to finding the required look-up table value and ensures that the same number of accesses is made regardless of which look-up table value is called. This implementation is designed to be constant-time, meaning it does not leak timing information. Our experiments on modern Apple M1 processors showed up to 428.73 × and 114.16 × better performance for finite field multiplications and Rainbow signatures schemes, respectively, compared to previous reference implementations. To the best of our knowledge, this proposed Rainbow implementation is the first optimized Rainbow implementation for 64-bit ARMv8 processors.
17
Zhang, Min, Jie Zhang, Zhengping Jin, Hua Zhang, and Qiao-yan Wen. "A Light-Weight Rainbow Signature Scheme for WSN." Journal of Networks 7, no. 8 (August 1, 2012). http://dx.doi.org/10.4304/jnw.7.8.1272-1279.
Full text
18
Beullens, Ward, Ming-Shing Chen, Shih-Hao Hung, Matthias J. Kannwischer, Bo-Yuan Peng, Cheng-Jhih Shih, and Bo-Yin Yang. "Oil and Vinegar: Modern Parameters and Implementations." IACR Transactions on Cryptographic Hardware and Embedded Systems, June 9, 2023, 321–65. http://dx.doi.org/10.46586/tches.v2023.i3.321-365.
Full textAbstract:
Two multivariate digital signature schemes, Rainbow and GeMSS, made it into the third round of the NIST PQC competition. However, neither made its way to being a standard due to devastating attacks (in one case by Beullens, the other by Tao, Petzoldt, and Ding). How should multivariate cryptography recover from this blow? We propose that, rather than trying to fix Rainbow and HFEv- by introducing countermeasures, the better approach is to return to the classical Oil and Vinegar scheme. We show that, if parametrized appropriately, Oil and Vinegar still provides competitive performance compared to the new NIST standards by most measures (except for key size). At NIST security level 1, this results in either 128-byte signatures with 44 kB public keys or 96-byte signatures with 67 kB public keys. We revamp the state-of-the-art of Oil and Vinegar implementations for the Intel/AMD AVX2, the Arm Cortex-M4 microprocessor, the Xilinx Artix-7 FPGA, and the Armv8-A microarchitecture with the Neon vector instructions set.
19
Shim, Kyung-Ah, Sangyub Lee, and Namhun Koo. "Efficient Implementations of Rainbow and UOV using AVX2." IACR Transactions on Cryptographic Hardware and Embedded Systems, November 19, 2021, 245–69. http://dx.doi.org/10.46586/tches.v2022.i1.245-269.
Full textAbstract:
A signature scheme based on multivariate quadratic equations, Rainbow, was selected as one of digital signature finalists for NIST Post-Quantum Cryptography Standardization Round 3. In this paper, we provide efficient implementations of Rainbow and UOV using the AVX2 instruction set. These efficient implementations include several optimizations for signing to accelerate solving linear systems and the Vinegar value substitution. We propose a new block matrix inversion (BMI) method using the Lower-Diagonal-Upper decomposition of blocks matrices based on the Schur complement that accelerates solving linear systems. Compared to UOV implemented with Gaussian elimination, our implementations with the BMI result in speedups of 12.36%, 24.3%, and 34% for signing at security categories I, III, and V, respectively. Compared to Rainbow implemented with Gaussian elimination, our implementations with the BMI result in speedups of 16.13% and 20.73% at the security categories III and V, respectively. We show that precomputation for the Vinegar value substitution and solving linear systems dramatically improve their signing. UOV with precomputation is 16.9 times, 35.5 times, and 62.8 times faster than UOV without precomputation at the three security categories, respectively. Rainbow with precomputation is 2.1 times, 2.2 times, and 2.8 times faster than Rainbow without precomputation at the three security categories, respectively. We then investigate resilience against leakage or reuse of the precomputed values in UOV and Rainbow to use the precomputation securely: leakage or reuse of the precomputed values leads to their full secret key recoveries in polynomial-time.
20
Ustimenko, Vasyl. "On Multivariate Algorithms of Digital Signatures Based on Maps of Unbounded Degree Acting on Secure El Gamal Type Mode." Theoretical and Applied Cybersecurity 4, no. 1 (February 17, 2023). http://dx.doi.org/10.20535/tacs.2664-29132022.1.274125.
Full textAbstract:
Multivariate cryptography studies applications of endomorphisms of K[x1 x2, ..., xn] where K is a finite commutative ring given in the standard form xi →f1 (x1, x2,..., xn), i=1, 2,..., n. The importance of this direction for the constructions of multivariate digital signatures systems is well known. Close attention of researchers directed towards studies of perspectives of efficient quadratic unbalanced rainbow oil and vinegar system (RUOV) presented for NIST postquantum certification. Various cryptanalytic studies of these signature systems were completed. During Third Round of NIST standardisation projects ROUV digital signature system were rejected. Recently some options to seriously modify theses algorithms as well as all multivariate signature systems which alow to avoid already known attacks were suggested. One of the modifications is to use protocol of noncommutative multivariate cryptography based on platform of endomorphisms of degree 2 and 3. The secure protocol allows safe transfer of quadratic multivariate map from one correspondent to another. So the quadratic map developed for digital signature scheme can be used in a private mode. This scheme requires periodic usage of the protocol with the change of generators and the modification of quadratic multivariate maps. Other modification suggests combination of multivariate map of unbounded degree of size O(n) and density of each fi of size O(1). The resulting map F in its standard form is given as the public rule. We suggest the usage of the last algorithm on the secure El Gamal mode. It means that correspondents use protocols of Noncommutative Cryptography with two multivariate platforms to elaborate safely a collision endomorphism G: xi → gi of linear unbounded degree such that densities of each gi are of size O(n2). One of correspondents generates mentioned above F and sends F+G to his/her partner.
The security of the protocol and entire digital signature scheme rests on the complexity of NP hard word problem of finding decomposition of given endomorphism G of K[x1,x2,...,xn] into composition of given generators 1G, 2G, ...tG, t>1 of the semigroup of End(K[x1,x2,...,xn]). Differently from the usage of quadratic map on El Gamal mode the case of unbounded degree allows single usage of the protocol because the task to approximate F via interception of hashed messages and corresponding signatures is unfeasible in this case.
21
Park, Aesun, Kyung-Ah Shim, Namhun Koo, and Dong-Guk Han. "Side-Channel Attacks on Post-Quantum Signature Schemes based on Multivariate Quadratic Equations." IACR Transactions on Cryptographic Hardware and Embedded Systems, August 16, 2018, 500–523. http://dx.doi.org/10.46586/tches.v2018.i3.500-523.
Full textAbstract:
In this paper, we investigate the security of Rainbow and Unbalanced Oil-and-Vinegar (UOV) signature schemes based on multivariate quadratic equations, which is one of the most promising alternatives for post-quantum signature schemes, against side-channel attacks. We describe correlation power analysis (CPA) on the schemes that yield full secret key recoveries. First, we identify a secret leakage of secret affine maps S and T during matrix-vector products in signing when Rainbow is implemented with equivalent keys rather than random affine maps for optimal implementations. In this case, the simple structure of the equivalent keys leads to the retrieval of the entire secret affine map T. Next, we extend the full secret key recovery to the general case using random affine maps via a hybrid attack: after recovering S by performing CPA, we recover T by mounting algebraic key recovery attacks. We demonstrate how this leakage on Rainbow can be practically exploited on an 8-bit AVR microcontroller using CPA. Consequently, our CPA can be applied to Rainbow-like multi-layered schemes regardless of the use of the simple-structured equivalent keys and UOV-like single layer schemes with the implementations using the equivalent keys of the simple structure. This is the first result on the security of multivariate quadratic equations-based signature schemes using only CPA. Our result can be applied to Rainbow-like multi-layered schemes and UOV-like single layer schemes submitted to NIST for Post-Quantum Cryptography Standardization.