2011 | OriginalPaper | Buchkapitel
Small Public Keys and Fast Verification for ultivariate uadratic Public Key Systems
verfasst von : Albrecht Petzoldt, Enrico Thomae, Stanislav Bulygin, Christopher Wolf
Erschienen in: Cryptographic Hardware and Embedded Systems – CHES 2011
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Security of public key schemes in a post-quantum world is a challenging task—as both RSA and ECC will be broken then. In this paper, we show how post-quantum signature systems based on
$\mathcal{M}$
ultivariate
$\mathcal{Q}$
uadratic (
$\mathcal{MQ}$
) polynomials can be improved up by about 9/10, and 3/5, respectively, in terms of public key size and verification time. The exact figures are 88% and 59%. This is particularly important for small-scale devices with restricted energy, memory, or computational power. In addition, we provide evidence that this reduction does not affect security and that it is also optimal in terms of possible attacks. We do so by combining the previously unrelated concepts of reduced and equivalent keys. Our new scheme is based on the so-called
Unbalanced Oil and Vinegar
class of
$\mathcal{MQ}$
-schemes. We have derived our results mathematically and verified the speed-ups through a C++ implementation.