TY - JOUR
T1 - Cryptanalysis of a public key cryptosystem based on Diophantine equations via weighted LLL reduction
AU - Ding, Jintai
AU - Kudo, Momonari
AU - Okumura, Shinya
AU - Takagi, Tsuyoshi
AU - Tao, Chengdong
N1 - Publisher Copyright:
© 2018, The Author(s).
PY - 2018/11/1
Y1 - 2018/11/1
N2 - Researching post-quantum cryptography is now an important task in cryptography. Although various candidates of post-quantum cryptosystems (PQC) have been constructed, sizes of their public keys are large. Okumura constructed a candidate of PQC whose security is expected to be based on certain Diophantine equations (DEC). Okumura analysis suggests that DEC achieves the high security with small public key sizes. This paper proposes a polynomial time-attack on the one-way property of DEC. We reduce the security of DEC to finding special short lattice points of some low-rank lattices derived from public data. The usual LLL algorithm could not find the most important lattice point in our experiments because of certain properties of the lattice point. Our heuristic analysis leads us to using a variant of the LLL algorithm, called a weighted LLL algorithm by us. Our experiments suggest that DEC with 128 bit security becomes insecure by our attack.
AB - Researching post-quantum cryptography is now an important task in cryptography. Although various candidates of post-quantum cryptosystems (PQC) have been constructed, sizes of their public keys are large. Okumura constructed a candidate of PQC whose security is expected to be based on certain Diophantine equations (DEC). Okumura analysis suggests that DEC achieves the high security with small public key sizes. This paper proposes a polynomial time-attack on the one-way property of DEC. We reduce the security of DEC to finding special short lattice points of some low-rank lattices derived from public data. The usual LLL algorithm could not find the most important lattice point in our experiments because of certain properties of the lattice point. Our heuristic analysis leads us to using a variant of the LLL algorithm, called a weighted LLL algorithm by us. Our experiments suggest that DEC with 128 bit security becomes insecure by our attack.
KW - Diophantine equation
KW - Post-quantum cryptosystem
KW - Public-key cryptosystem
KW - Weighted LLL reduction
UR - http://www.scopus.com/inward/record.url?scp=85048831412&partnerID=8YFLogxK
U2 - 10.1007/s13160-018-0316-x
DO - 10.1007/s13160-018-0316-x
M3 - Article
AN - SCOPUS:85048831412
SN - 0916-7005
VL - 35
SP - 1123
EP - 1152
JO - Japan Journal of Industrial and Applied Mathematics
JF - Japan Journal of Industrial and Applied Mathematics
IS - 3
ER -