Equivalent keys in ℳultivariate uadratic public key systems
ℳultivariate uadratic public key schemes have been suggested as early as 1985 by Matsumoto and Imai as an alternative for the RSA scheme. Since then, several schemes have been proposed, for example hidden field equations, unbalanced oil and vinegar schemes, and stepwise triangular schemes. All these...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2011-04-01
|
| Series: | Journal of Mathematical Cryptology |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/jmc.2011.004 |
| _version_ | 1798024853998010368 |
|---|---|
| author | Wolf Christopher Preneel Bart |
| author_facet | Wolf Christopher Preneel Bart |
| author_sort | Wolf Christopher |
| collection | DOAJ |
| description | ℳultivariate uadratic public key schemes have been suggested as early as 1985 by Matsumoto and Imai as an alternative for the RSA scheme. Since then, several schemes have been proposed, for example hidden field equations, unbalanced oil and vinegar schemes, and stepwise triangular schemes. All these schemes have a rather large key space for a secure choice of parameters. Surprisingly, the question of equivalent keys has not been discussed in the open literature until recently. In this article, we show that for all basic classes mentioned above, it is possible to reduce the private – and hence the public – key space by several orders of magnitude, i.e. the size of the set of possible private and hence public keys can be reduced. For the Matsumoto–Imai scheme, we are even able to show that the reductions we found are the only ones possible, i.e. that these reductions are tight. While the theorems developed in this article are of independent interest themselves as they broaden our understanding of ℳultivariate uadratic public key systems, we see applications of our results both in cryptanalysis and in memory efficient implementations of -schemes. |
| first_indexed | 2024-04-11T18:09:22Z |
| format | Article |
| id | doaj.art-0dd1135c883b48d5a11f09891bc03c28 |
| institution | Directory Open Access Journal |
| issn | 1862-2976 1862-2984 |
| language | English |
| last_indexed | 2024-04-11T18:09:22Z |
| publishDate | 2011-04-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Journal of Mathematical Cryptology |
| spelling | doaj.art-0dd1135c883b48d5a11f09891bc03c282022-12-22T04:10:11ZengDe GruyterJournal of Mathematical Cryptology1862-29761862-29842011-04-014437541510.1515/jmc.2011.004Equivalent keys in ℳultivariate uadratic public key systemsWolf Christopher0Preneel Bart1K. U. Leuven, ESAT-COSIC, Kasteelpark Arenberg 10, BE-3001 Leuven-Heverlee, Belgium; and Horst Görtz Institute for IT-Security, Building NA 5/69, Ruhr-University Bochum, DE-44780 Bochum, Germany. K.U. Leuven, ESAT-COSIC, Kasteelpark Arenberg 10, BE-3001 Leuven-Heverlee, Belgium.ℳultivariate uadratic public key schemes have been suggested as early as 1985 by Matsumoto and Imai as an alternative for the RSA scheme. Since then, several schemes have been proposed, for example hidden field equations, unbalanced oil and vinegar schemes, and stepwise triangular schemes. All these schemes have a rather large key space for a secure choice of parameters. Surprisingly, the question of equivalent keys has not been discussed in the open literature until recently. In this article, we show that for all basic classes mentioned above, it is possible to reduce the private – and hence the public – key space by several orders of magnitude, i.e. the size of the set of possible private and hence public keys can be reduced. For the Matsumoto–Imai scheme, we are even able to show that the reductions we found are the only ones possible, i.e. that these reductions are tight. While the theorems developed in this article are of independent interest themselves as they broaden our understanding of ℳultivariate uadratic public key systems, we see applications of our results both in cryptanalysis and in memory efficient implementations of -schemes.https://doi.org/10.1515/jmc.2011.004ℳultivariate uadratic polynomialspublic key signaturehidden field equationsmatsumoto–imai scheme a, c*unbalanced oil and vinegarstepwise triangular systemsequivalent keyspost-quantum cryptography |
| spellingShingle | Wolf Christopher Preneel Bart Equivalent keys in ℳultivariate uadratic public key systems Journal of Mathematical Cryptology ℳultivariate uadratic polynomials public key signature hidden field equations matsumoto–imai scheme a, c* unbalanced oil and vinegar stepwise triangular systems equivalent keys post-quantum cryptography |
| title | Equivalent keys in ℳultivariate uadratic public key systems |
| title_full | Equivalent keys in ℳultivariate uadratic public key systems |
| title_fullStr | Equivalent keys in ℳultivariate uadratic public key systems |
| title_full_unstemmed | Equivalent keys in ℳultivariate uadratic public key systems |
| title_short | Equivalent keys in ℳultivariate uadratic public key systems |
| title_sort | equivalent keys in multivariate uadratic public key systems |
| topic | ℳultivariate uadratic polynomials public key signature hidden field equations matsumoto–imai scheme a, c* unbalanced oil and vinegar stepwise triangular systems equivalent keys post-quantum cryptography |
| url | https://doi.org/10.1515/jmc.2011.004 |
| work_keys_str_mv | AT wolfchristopher equivalentkeysinmultivariateuadraticpublickeysystems AT preneelbart equivalentkeysinmultivariateuadraticpublickeysystems |