Efficient Variant of Rainbow without Triangular Matrix Representation
Multivariate Public Key Cryptosystems (MPKC) is one of candidates for post-quantum cryptography. Rainbow is an MPKC digital signature scheme, with relatively efficient encryption and decryption processes. However, the size of MPKC key is substantially lar
- PDF / 203,980 Bytes
- 10 Pages / 439.363 x 666.131 pts Page_size
- 3 Downloads / 152 Views
Institute of Systems, Information Technologies and Nanotechnologies 2 Institute of Mathematics for Industry, Kyushu University 3 Department of Informatics, Kyushu University
Abstract. Multivariate Public Key Cryptosystems (MPKC) is one of candidates for post-quantum cryptography. Rainbow is an MPKC digital signature scheme, with relatively efficient encryption and decryption processes. However, the size of MPKC key is substantially larger than that of an RSA cryptosystem for the same security level. In this paper, we propose a variant of Rainbow that has a smaller secret key. The smaller secret key is to the result of a different description of the quadratic polynomials appearing in the secret key from that of the original Rainbow. In addition, our scheme improves the efficiency of the Rainbow’s signature generation. In particular, the secret key is reduced in size by about 40% and the signature generation is sped up by about 30% at the security level of 100 bits. Keywords: Post-quantum cryptography, Multivariate cryptosystems, Rainbow.
1
public key
Introduction
Multivariate public key cryptosystems (MPKC) [1,7] are candidates for postquantum cryptography. Their security is based on the level of difficulty involved in finding solutions to a system of multivariate quadratic equations (MQ problem). Many MPKC schemes require secret and public keys that are larger than those of RSA and ECC. In recent years, a variety of MPKC schemes for encryption and for signatures, have been proposed. Unbalanced Oil and Vinegar (UOV) [5] is an MPKC signature scheme, whose signatures can be efficiently generated and verified. Rainbow [2] is a multilayer variant of UOV, with enhanced security. UOV and Rainbow both share the same problem of having large secret and public keys. In this paper, we propose a variant of Rainbow that has a shorter secret key than the corresponding Rainbow key. In the case of the original Rainbow, the quadratic polynomials appearing in the secret key are expressed using triangular matrices. The non-zero parts of the triangular matrices coincide with coefficients of the quadratic polynomials. If we change the triangular matrices into general matrices, then the quadratic polynomials remain but, the correspondence of the matrix elements becomes more complicated. Conversely, if we utilize the Linawati et al. (Eds.): ICT-EurAsia 2014, LNCS 8407, pp. 532–541, 2014. c IFIP International Federation for Information Processing 2014
Efficient Variant of Rainbow without Triangular Matrix Representation
533
complicated correspondence, then simple matrix operation like rotation of row vectors yields several quadratic polynomials which seem to have been chosen randomly. Our scheme uses this method to describe the quadratic polynomials appearing in the secret key. In Rainbow, we need the same number of triangular matrices as that of quadratic polynomials, whereas in our scheme, we need only one matrix to describe the secret key. Our scheme also improves the efficiency of signature generation. Here, we use several rotations of row vec
Data Loading...
