Practical Cryptanalysis of a Public-key Encryption Scheme Based on Non-linear Indeterminate Equations at SAC 2017

Keita Xagawa

Abstract

We investigate the security of a public-key encryption scheme, the Indeterminate Equation Cryptosystem (IEC), introduced by Akiyama, Goto, Okumura, Takagi, Nuida, and Hanaoka at SAC 2017 as postquantum cryptography. They gave two parameter sets PS1 (n,p,deg X,q) = (80,3,1,921601) and PS2 (n,p,deg X,q) = (80,3,2,58982400019). The paper gives practical key-recovery and message-recovery attacks against those parameter sets of IEC through lattice basis-reduction algorithms. We exploit the fact that n = 80 is composite and adopt the idea of Gentry's attack against NTRU-Composite (EUROCRYPT2001) to this setting. The summary of our attacks follows: * On PS1, we recover 84 private keys from 100 public keys in 30–40 seconds per key. * On PS1, we recover partial information of all message from 100 ciphertexts in a second per ciphertext. * On PS2, we recover partial information of all message from 100 ciphertexts in 30 seconds per ciphertext. Moreover, we also give message-recovery and distinguishing attacks against the parameter sets with prime n, say, n = 83. We exploit another subring to reduce the dimension of lattices in our lattice-based attacks and our attack succeeds in the case of deg X = 2. * For PS2’ (n,p,deg X,q) = (83,3,2,68339982247), we recover 7 messages from 10 random ciphertexts within 61,000 seconds \approx 17 hours per ciphertext. * Even for larger n, we can fnd short vector from lattices to break the underlying assumption of IEC. In our experiment, we can found such vector within 330,000 seconds \approx 4 days for n = 113.

Note: I have reported the attacks in this paper to the original authros, Akiyama et al. Their NIST submission reflects the attacks in this paper.

Metadata
Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.PQCrypto 2018
Keywords
Public-Key EncryptionIndeterminate Equations CryptosystemPost-quantum cryptographyGiophantus
Contact author(s)
xagawa keita @ lab ntt co jp
History
2018-01-30: last of 2 revisions
2017-12-22: received
See all versions
Short URL
https://ia.cr/2017/1224
License

CC BY

BibTeX

@misc{cryptoeprint:2017/1224,
author = {Keita Xagawa},
title = {Practical Cryptanalysis of a Public-key Encryption Scheme Based on Non-linear Indeterminate Equations at SAC 2017},
howpublished = {Cryptology ePrint Archive, Paper 2017/1224},
year = {2017},
note = {\url{https://eprint.iacr.org/2017/1224}},
url = {https://eprint.iacr.org/2017/1224}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.