For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2016/01/01
Online ISSN: 1745-1337
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)>>
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.