The Rainbow signature scheme is the only multivariate scheme listed as a finalist in round 3 of the NIST post-quantum standardization process. A few recent attacks, including the intersection attack, rectangular MinRank attacks, and the “simple attack,” have changed this landscape; leaving questions about the viability of this scheme for future application.
The purpose of this paper is to analyze the possibility of repairing Rainbow by adding an internal perturbation modifier and to compare its performance with that of UOV at the same security level. While the costly internal perturbation modifier was originally designed with encryption in mind, the use of schemes with performance characteristics similar to Rainbow is most interesting for applications in which short signatures or fast verification is a necessity, while signing can be done offline. We find that Rainbow can be made secure while achieving smaller keys, shorter signatures and faster verification times than UOV, but this advantage comes at significant cost in terms of signing time.
The Rainbow signature scheme is the only multivariate scheme listed as a finalist in round 3 of the NIST post-quantum standardization process. A few recent attacks, including the intersection attack, rectangular MinRank attacks, and the “simple attack,” have changed this landscape; leaving questions...
See full abstract
The Rainbow signature scheme is the only multivariate scheme listed as a finalist in round 3 of the NIST post-quantum standardization process. A few recent attacks, including the intersection attack, rectangular MinRank attacks, and the “simple attack,” have changed this landscape; leaving questions about the viability of this scheme for future application.
The purpose of this paper is to analyze the possibility of repairing Rainbow by adding an internal perturbation modifier and to compare its performance with that of UOV at the same security level. While the costly internal perturbation modifier was originally designed with encryption in mind, the use of schemes with performance characteristics similar to Rainbow is most interesting for applications in which short signatures or fast verification is a necessity, while signing can be done offline. We find that Rainbow can be made secure while achieving smaller keys, shorter signatures and faster verification times than UOV, but this advantage comes at significant cost in terms of signing time.
Hide full abstract
