Paper 2019/282

A Framework for Cryptographic Problems from Linear Algebra

Carl Bootland, Wouter Castryck, Alan Szepieniec, and Frederik Vercauteren

Abstract

We introduce a general framework encompassing the main hard problems emerging in lattice-based cryptography, which naturally includes the recently proposed Mersenne prime cryptosystem, but also code-based cryptography. The framework allows to easily instantiate new hard problems and to automatically construct post-quantum secure primitives from them. As a first basic application, we introduce two new hard problems and the corresponding encryption schemes. Concretely, we study generalizations of hard problems such as SIS, LWE and NTRU to free modules over quotients of \(\mathbb{Z}[X]\) by ideals of the form \((f,g)\), where \(f\) is a monic polynomial and \(g \in \mathbb{Z}[X]\) is a ciphertext modulus coprime to \(f\). For trivial modules (i.e. of rank one) the case \(f=X^n+1\) and \(g = q \in \mathbb{Z}_{>0}\) corresponds to ring-LWE, ring-SIS and NTRU, while the choices \(f = X^n- 1\) and \(g = X - 2\) essentially cover the recently proposed Mersenne prime cryptosystems. At the other extreme, when considering modules of large rank and letting \(\deg f = 1\) one recovers the framework of LWE and SIS.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
LWESISNTRUquotient ringpost-quantum
Contact author(s)
carl bootland @ kuleuven be
frederik vercauteren @ kuleuven be
History
2019-03-12: received
Short URL
https://ia.cr/2019/282
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/282,
      author = {Carl Bootland and Wouter Castryck and Alan Szepieniec and Frederik Vercauteren},
      title = {A Framework for Cryptographic Problems from Linear Algebra},
      howpublished = {Cryptology ePrint Archive, Paper 2019/282},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/282}},
      url = {https://eprint.iacr.org/2019/282}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.