Advanced search
1 file | 540.78 KB Add to list

A framework for cryptographic problems from linear algebra

Author
Organization
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 problems coming from code-based cryptography. The framework allows to easily instantiate new hard problems and to automatically construct plausibly 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 generalisations of hard problems such as SIS, LWE and NTRU to free modules over quotients of Z[X] by ideals of the form (f,g), where f is a monic polynomial and g∈Z[X] is a ciphertext modulus coprime to f. For trivial modules (i.e. of rank one), the case f=Xn+1 and g=q∈Z>1 corresponds to ring-LWE, ring-SIS and NTRU, while the choices f=Xn−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.
Keywords
LWE, SIS, NTRU, quotient ring, post-quantum, GENERALIZED COMPACT KNAPSACKS, EFFICIENT, LATTICES

Downloads

  • published.pdf
    • full text (Published version)
    • |
    • open access
    • |
    • PDF
    • |
    • 540.78 KB

Citation

Please use this url to cite or link to this publication:

MLA
Bootland, Carl, et al. “A Framework for Cryptographic Problems from Linear Algebra.” JOURNAL OF MATHEMATICAL CRYPTOLOGY, vol. 14, no. 1, 2020, pp. 202–17, doi:10.1515/jmc-2019-0032.
APA
Bootland, C., Castryck, W., Szepieniec, A., & Vercauteren, F. (2020). A framework for cryptographic problems from linear algebra. JOURNAL OF MATHEMATICAL CRYPTOLOGY, 14(1), 202–217. https://doi.org/10.1515/jmc-2019-0032
Chicago author-date
Bootland, Carl, Wouter Castryck, Alan Szepieniec, and Frederik Vercauteren. 2020. “A Framework for Cryptographic Problems from Linear Algebra.” JOURNAL OF MATHEMATICAL CRYPTOLOGY 14 (1): 202–17. https://doi.org/10.1515/jmc-2019-0032.
Chicago author-date (all authors)
Bootland, Carl, Wouter Castryck, Alan Szepieniec, and Frederik Vercauteren. 2020. “A Framework for Cryptographic Problems from Linear Algebra.” JOURNAL OF MATHEMATICAL CRYPTOLOGY 14 (1): 202–217. doi:10.1515/jmc-2019-0032.
Vancouver
1.
Bootland C, Castryck W, Szepieniec A, Vercauteren F. A framework for cryptographic problems from linear algebra. JOURNAL OF MATHEMATICAL CRYPTOLOGY. 2020;14(1):202–17.
IEEE
[1]
C. Bootland, W. Castryck, A. Szepieniec, and F. Vercauteren, “A framework for cryptographic problems from linear algebra,” JOURNAL OF MATHEMATICAL CRYPTOLOGY, vol. 14, no. 1, pp. 202–217, 2020.
@article{8665510,
  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 problems coming from code-based cryptography. The framework allows to easily instantiate new hard problems and to automatically construct plausibly 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 generalisations of hard problems such as SIS, LWE and NTRU to free modules over quotients of Z[X] by ideals of the form (f,g), where f is a monic polynomial and g∈Z[X] is a ciphertext modulus coprime to f. For trivial modules (i.e. of rank one), the case f=Xn+1 and g=q∈Z>1 corresponds to ring-LWE, ring-SIS and NTRU, while the choices f=Xn−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.}},
  author       = {{Bootland, Carl and Castryck, Wouter and Szepieniec, Alan and Vercauteren, Frederik}},
  issn         = {{1862-2976}},
  journal      = {{JOURNAL OF MATHEMATICAL CRYPTOLOGY}},
  keywords     = {{LWE,SIS,NTRU,quotient ring,post-quantum,GENERALIZED COMPACT KNAPSACKS,EFFICIENT,LATTICES}},
  language     = {{eng}},
  number       = {{1}},
  pages        = {{202--217}},
  title        = {{A framework for cryptographic problems from linear algebra}},
  url          = {{http://dx.doi.org/10.1515/jmc-2019-0032}},
  volume       = {{14}},
  year         = {{2020}},
}

Altmetric
View in Altmetric