Inoculating Multivariate Schemes Against Differential Attacks

Jintai Ding; Jason E.  Gower

Paper 2005/255

Inoculating Multivariate Schemes Against Differential Attacks

Jintai Ding and Jason E. Gower

Abstract

We demonstrate how to prevent differential attacks on multivariate public key cryptosystems using the Plus (+) method of external perturbation. In particular, we prescribe adding as few as 10 Plus polynomials to the Perturbed Matsumoto-Imai (PMI) cryptosystem when $g=1$ and $r=6$, where $\theta$ is the Matsumoto-Imai exponent, $n$ is the message length, $g=\gcd{(\theta,n)}$, and $r$ is the internal perturbation dimension; or as few as $g+10$ when $g \neq 1$. The external perturbation does not significantly decrease the efficiency of the system, and in fact has the additional benefit of resolving the problem of finding the true plaintext among several preimages of a given ciphertext. We call this new scheme the Perturbed Matsumoto-Imai-Plus (PMI+) cryptosystem.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: multivariate public key cryptography Matsumoto-Imai perturbation differential
Contact author(s): gowerj @ math uc edu
History: 2005-08-11: received
Short URL: https://ia.cr/2005/255
License: CC BY

BibTeX

@misc{cryptoeprint:2005/255,
      author = {Jintai Ding and Jason E.  Gower},
      title = {Inoculating Multivariate Schemes Against Differential Attacks},
      howpublished = {Cryptology {ePrint} Archive, Paper 2005/255},
      year = {2005},
      url = {https://eprint.iacr.org/2005/255}
}