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.
Shigeo TSUJII
Chuo University
Kohtaro TADAKI
Chubu University
Ryo FUJITA
Chuo University
Masahito GOTAISHI
Chuo University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Shigeo TSUJII, Kohtaro TADAKI, Ryo FUJITA, Masahito GOTAISHI, "Proposal of the Multivariate Public Key Cryptosystem Relying on the Difficulty of Factoring a Product of Two Large Prime Numbers" in IEICE TRANSACTIONS on Fundamentals,
vol. E99-A, no. 1, pp. 66-72, January 2016, doi: 10.1587/transfun.E99.A.66.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.66/_p
Copy
@ARTICLE{e99-a_1_66,
author={Shigeo TSUJII, Kohtaro TADAKI, Ryo FUJITA, Masahito GOTAISHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Proposal of the Multivariate Public Key Cryptosystem Relying on the Difficulty of Factoring a Product of Two Large Prime Numbers},
year={2016},
volume={E99-A},
number={1},
pages={66-72},
abstract={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.},
keywords={},
doi={10.1587/transfun.E99.A.66},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - Proposal of the Multivariate Public Key Cryptosystem Relying on the Difficulty of Factoring a Product of Two Large Prime Numbers
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 66
EP - 72
AU - Shigeo TSUJII
AU - Kohtaro TADAKI
AU - Ryo FUJITA
AU - Masahito GOTAISHI
PY - 2016
DO - 10.1587/transfun.E99.A.66
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2016
AB - 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.
ER -