Cryptography Reference
In-Depth Information
On the Differential Security of Multivariate
Public Key Cryptosystems
Daniel Smith-Tone
1
,
2
1
Department of Mathematics, University of Louisville,
Louisville, Kentucky, USA
2
National Institute of Standards and Technology,
Gaithersburg, Maryland, USA
daniel.smith@nist.gov
Abstract.
Since the discovery of an algorithm for factoring and com-
puting discrete logarithms in polynomial time on a quantum computer,
the cryptographic community has been searching for an alternative for
security in the approaching post-quantum world. One excellent candidate
is multivariate public key cryptography. Though the speed and parame-
terizable nature of such schemes is desirable, a standard metric for deter-
mining the security of a multivariate cryptosystem has been lacking. We
present a reasonable measure for security against the common differen-
tial attacks and derive this measurement for several modern multivariate
public key cryptosystems.
Keywords:
Matsumoto-Imai, multivariate public key cryptography, dif-
ferential, symmetry.
1
Introduction
In recent years a great deal of focus has been directed towards post-quantum
cryptology. This increased attention is indicative of a paradigm shift which has
been occurring since, in [1], Peter Shor developed algorithms for factoring and
computing discrete logarithms in polynomial time on a quantum computing de-
vice. In the face of mounting evidence that quantum computing is not a physical
impossibility but merely an engineering challenge, it is more important than ever
that we develop secure systems relying on problems of greater diculty than the
classical number theoretic schemes.
Multivariate Public Key Cryptography(MPKC) has emerged as one of a few
serious candidates for security in the post-quantum world. This emergence is
due to several facts. First, the problem of solving a system of quadratic equa-
tions is known to be NP-hard, and seems to be hard even in the average case.
No great reduction of the complexity of this problem has been found in the
quantum model of computing, and, indeed, if this problem is discovered to be
solvable in the quantum model, we can solve all NP problems, which seems par-
ticularly wishful. Second, multivariate systems are very ecient, often having
speeds dozens of times faster than RSA, [2-4]. Finally, it is easy to parameterize
