ring-LWE

A toolkit for ring-LWE cryptography. Recent advances in lattice cryptography, mainly stemming from the development of ring-based primitives such as ring-LWE, have made it possible to design cryptographic schemes whose efficiency is competitive with that of more traditional number-theoretic ones, along with entirely new applications like fully homomorphic encryption. Unfortunately, realizing the full potential of ring-based cryptography has so far been hindered by a lack of practical algorithms and analytical tools for working in this context. As a result, most previous works have focused on very special classes of rings such as power-of-two cyclotomics, which significantly restricts the possible applications.par We bridge this gap by introducing a toolkit of fast, modular algorithms and analytical techniques that can be used in a wide variety of ring-based cryptographic applications, particularly those built around ring-LWE. Our techniques yield applications that work in arbitrary cyclotomic rings, with no loss in their underlying worst-case hardness guarantees, and very little loss in computational efficiency, relative to power-of-two cyclotomics. To demonstrate the toolkit’s applicability, we develop two illustrative applications: a public-key cryptosystem and a “somewhat homomorphic” symmetric encryption scheme. Both apply to arbitrary cyclotomics, have tight parameters, and very efficient implementations.


References in zbMATH (referenced in 32 articles )

Showing results 1 to 20 of 32.
Sorted by year (citations)

1 2 next

  1. Cheon, Jung Hee; Kim, Dongwoo; Kim, Duhyeong; Lee, Keewoo: On the scaled inverse of ((x^i-x^j)) modulo cyclotomic polynomial of the form (\Phi_p^s(x)) or (\Phi_p^s q^t(x)) (2022)
  2. Damgård, Ivan; Orlandi, Claudio; Takahashi, Akira; Tibouchi, Mehdi: Two-round (n)-out-of-(n) and multi-signatures and trapdoor commitment from lattices (2022)
  3. Duong, Dung Hoang; Roy, Partha Sarathi; Susilo, Willy; Fukushima, Kazuhide; Kiyomoto, Shinsaku; Sipasseuth, Arnaud: Chosen-ciphertext lattice-based public key encryption with equality test in standard model (2022)
  4. Arunachalam, Srinivasan; Grilo, Alex Bredariol; Sundaram, Aarthi: Quantum hardness of learning shallow classical circuits (2021)
  5. Bert, Pauline; Eberhart, Gautier; Prabel, Lucas; Roux-Langlois, Adeline; Sabt, Mohamed: Implementation of lattice trapdoors on modules and applications (2021)
  6. Dachman-Soled, Dana; Gong, Huijing; Kulkarni, Mukul; Shahverdi, Aria: Towards a ring analogue of the leftover hash lemma (2021)
  7. Dachman-Soled, Dana; Gong, Huijing; Kulkarni, Mukul; Shahverdi, Aria: (In)security of ring-LWE under partial key exposure (2021)
  8. Halevi, Shai; Shoup, Victor: Bootstrapping for helib (2021)
  9. Katsumata, Shuichi; Yamada, Shota; Yamakawa, Takashi: Tighter security proofs for GPV-IBE in the quantum random oracle model (2021)
  10. Murphy, Sean; Player, Rachel: Discretisation and product distributions in ring-LWE (2021)
  11. Stange, Katherine E.: Algebraic aspects of solving ring-LWE, including ring-based improvements in the Blum-Kalai-Wasserman algorithm (2021)
  12. Falk, Brett Hemenway; Heninger, Nadia; Rudow, Michael: Properties of constacyclic codes under the Schur product (2020)
  13. Hu, Yupu; Jia, Huiwen: A new Gaussian sampling for trapdoor lattices with arbitrary modulus (2019)
  14. Ducas, Léo; van Woerden, Wessel P. J.: The closest vector problem in tensored root lattices of type A and in their duals (2018)
  15. Lyubashevsky, Vadim; Micciancio, Daniele: Asymptotically efficient lattice-based digital signatures (2018)
  16. Albrecht, Martin R.: On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL (2017)
  17. Batson, Scott C.: The linear transformation that relates the canonical and coefficient embeddings of ideals in cyclotomic integer rings (2017)
  18. Biasse, Jean-François; Espitau, Thomas; Fouque, Pierre-Alain; Gélin, Alexandre; Kirchner, Paul: Computing generator in cyclotomic integer rings. A subfield algorithm for the principal ideal problem in (L_|\varDelta_\mathbbK|\left(\frac12\right)) and application to the cryptanalysis of a FHE scheme (2017)
  19. Canetti, Ran; Chen, Yilei: Constraint-hiding constrained PRFs for (\textNC^1) from LWE (2017)
  20. Cheon, Jung Hee; Han, Kyoohyung; Kim, Jinsu; Lee, Changmin; Son, Yongha: A practical post-quantum public-key cryptosystem based on spLWE (2017)

1 2 next