Proposal of the Multivariate Public Key Cryptosystem Relying on the Difficulty of Factoring a Product of Two Large Prime Numbers

Shigeo TSUJII  Kohtaro TADAKI  Ryo FUJITA  Masahito GOTAISHI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.1   pp.66-72
Publication Date: 2016/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.66
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Multivariate Public Key Cryptosystem,  Public Key Cryptosystem,  prime factorization,  Gröbner bases,  rank attack,  

Full Text: PDF(1.3MB)>>
Buy this Article

Currently there is not any prospect of realizing quantum computers which can compute prime factorization, which RSA relies on, or discrete logarithms, which ElGamal relies on, of practical size. Additionally the rapid growth of Internet of Things (IoT) is requiring practical public key cryptosystems which do not use exponential operation. Therefore we constituted a cryptosystem relying on the difficulty of factoring the product of two large prime numbers, based on the Chinese Remainder Theorem, fully exploiting another strength of MPKC that exponential operation is not necessary. We evaluated its security by performing the Gröbner base attacks with workstations and consequently concluded that it requires computation complexity no less than entirely random quadratic polynomials. Additionally we showed that it is secure against rank attacks since the polynomials of central map are all full rank, assuming the environment of conventional computers.