Choosing subfields for LUOV and lifting fields for rainbow
Dung Hoang Duong, Le Van Luyen, Ha Thanh Nguyen Tran · IET Information Security · 2019
Multivariate public key cryptography is one of the main candidates for post‐quantum cryptography. Rainbow, an improved (multi‐layer) version of unbalanced oil and vinegar (UOV), is one of the most famous multivariate signature schemes that is a promising candidate for NIST standardisation. At INDOCRYPT 2017, Beullens and Preneel introduced a new variant LUOV of UOV. Their idea is to generate a UOV scheme over the binary field and then lift it into a bigger field and hence dramatically reduce the public key size. In this study, the authors first theoretically deduce the choice for the subfield L (which is different from ) which results in smaller signature sizes (up to 40%). Moreover, they extend the idea to Rainbow and theoretically yield the optimal choice for the subfield L over which a Rainbow is generated before being lifted to K . As a result, they can reduce the public key size of the obtained Rainbow scheme up to at least 36%.