International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Side-Channel Attacks on Post-Quantum Signature Schemes based on Multivariate Quadratic Equations - Rainbow and UOV -

Authors:
Aesun Park , Department of Financial Information Security, Kookmin University, Seoul
Kyung-Ah Shim , Division of Mathematical Modeling, National Institute for Mathematical Sciences, Daejeon
Namhun Koo , Division of Mathematical Modeling, National Institute for Mathematical Sciences, Daejeon
Dong-Guk Han , Department of Financial Information Security, Kookmin University, Seoul
Download:
DOI: 10.13154/tches.v2018.i3.500-523
URL: https://tches.iacr.org/index.php/TCHES/article/view/7284
Search ePrint
Search Google
Abstract: 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.
BibTeX
@article{tches-2018-29043,
  title={Side-Channel Attacks on Post-Quantum Signature Schemes based on Multivariate Quadratic Equations - Rainbow and UOV -},
  journal={IACR Trans. Cryptogr. Hardw. Embed. Syst.},
  publisher={Ruhr-Universität Bochum},
  volume={2018, Issue 3},
  pages={500-523},
  url={https://tches.iacr.org/index.php/TCHES/article/view/7284},
  doi={10.13154/tches.v2018.i3.500-523},
  author={Aesun Park and Kyung-Ah Shim and Namhun Koo and Dong-Guk Han},
  year=2018
}