Paper 2023/1471

NTRU in Quaternion Algebras of Bounded Discriminant

Cong Ling, Imperial College London
Andrew Mendelsohn, Imperial College London
Abstract

The NTRU assumption provides one of the most prominent problems on which to base post-quantum cryptography. Because of the efficiency and security of NTRU-style schemes, structured variants have been proposed, using modules. In this work, we create a structured form of NTRU using lattices obtained from orders in cyclic division algebras of index 2, that is, from quaternion algebras. We present a public-key encryption scheme, and show that its public keys are statistically close to uniform. We then prove IND-CPA security of a variant of our scheme when the discriminant of the quaternion algebra is not too large, assuming the hardness of Learning with Errors in cyclic division algebras.

Note: A minor revision of a publication in PQCrypto 2023.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. PQCrypto 2023
DOI
10.1007/978-3-031-40003-2_10
Keywords
NTRUquaternion algebraspost-quantumlattices
Contact author(s)
am3518 @ ic ac uk
History
2023-09-27: approved
2023-09-25: received
See all versions
Short URL
https://ia.cr/2023/1471
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1471,
      author = {Cong Ling and Andrew Mendelsohn},
      title = {{NTRU} in Quaternion Algebras of Bounded Discriminant},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1471},
      year = {2023},
      doi = {10.1007/978-3-031-40003-2_10},
      url = {https://eprint.iacr.org/2023/1471}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.