Paper 2017/1231

Integer Reconstruction Public-Key Encryption

Houda Ferradi and David Naccache

Abstract

In [AJPS17], Aggarwal, Joux, Prakash & Santha described an elegant public-key cryptosystem (AJPS-1) mimicking NTRU over the integers. This algorithm relies on the properties of Mersenne primes instead of polynomial rings. A later ePrint [BCGN17] by Beunardeau et al. revised AJPS-1’s initial security estimates. While lower than initially thought, the best known attack on AJPS-1 still seems to leave the defender with an exponential advantage over the attacker [dBDJdW17]. However, this lower exponential advantage implies enlarging AJPS-1’s parameters. This, plus the fact that AJPS-1 encodes only a single plaintext bit per ciphertext, made AJPS-1 impractical. In a recent update, Aggarwal et al. overcame this limitation by extending AJPS-1’s bandwidth. This variant (AJPS-ECC) modifies the definition of the public-key and relies on error-correcting codes. This paper presents a different high-bandwidth construction. By opposition to AJPS-ECC, we do not modify the public-key, avoid using errorcorrecting codes and use backtracking to decrypt. The new algorithm is orthogonal to AJPS-ECC as both mechanisms may be concurrently used in the same ciphertext and cumulate their bandwidth improvement effects. Alternatively, we can increase AJPS-ECC’s information rate by a factor of 26 for the parameters recommended in [AJPS17]. The obtained bandwidth improvement and the fact that encryption and decryption are reasonably efficient, make our scheme an interesting postquantum candidate.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. MAJOR revision.CANS 2019
Keywords
MERS assumptionKEMPost-Quantum Cryptography
Contact author(s)
houda ferradi @ ens fr
History
2019-08-06: last of 15 revisions
2017-12-22: received
See all versions
Short URL
https://ia.cr/2017/1231
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1231,
      author = {Houda Ferradi and David Naccache},
      title = {Integer Reconstruction Public-Key Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1231},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1231}},
      url = {https://eprint.iacr.org/2017/1231}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.