Multimedia contents are inherently sensitive signals that must be protected when processed in untrusted environments. The field of Secure Signal Processing addresses this challenge by developing methods which enable operating with sensitive signals in a privacy-conscious way. Recently, we introduced a hard lattice problem called m-RLWE (multivariate Ring Learning with Errors) which gives support to efficient encrypted processing of multidimensional signals. Afterwards, Bootland et al. presented an attack to m-RLWE that reduces the security of the underlying scheme from a lattice with dimension \prod_in_i to \max\n_i\ _i . Our work introduces a new pre-/post-coding block that addresses this attack and achieves the efficient results of our initial approach while basing its security directly on RLWE with dimension \prod_in_i, hence preserving the security and efficiency originally claimed. Additionally, this work provides a detailed comparison between a conventional use of RLWE, m-RLWE and our new pre-/post-coding procedure, which we denote "packed''-RLWE. Finally, we discuss a set of encrypted signal processing applications which clearly benefit from the proposed framework, either alone or in a combination of baseline RLWE, m-RLWE and "packed''-RLWE.
Multimedia contents are inherently sensitive signals that must be protected when processed in untrusted environments. The field of Secure Signal Processing addresses this challenge by developing methods which enable operating with sensitive signals in a privacy-conscious way. Recently, we introduced a hard lattice problem called m-RLWE (multivariate Ring Learning with Errors) which gives support to efficient encrypted processing of multidimensional signals. Afterwards, Bootland et al. presented an attack to m-RLWE that reduces the security of the underlying scheme from a lattice with dimension \prod_in_i to \max\n_i\ _i . Our work introduces a new pre-/post-coding block that addresses this attack and achieves the efficient results of our initial approach while basing its security directly on RLWE with dimension \prod_in_i, hence preserving the security and efficiency originally claimed. Additionally, this work provides a detailed comparison between a conventional use of RLWE, m-RLWE and our new pre-/post-coding procedure, which we denote "packed''-RLWE. Finally, we discuss a set of encrypted signal processing applications which clearly benefit from the proposed framework, either alone or in a combination of baseline RLWE, m-RLWE and "packed''-RLWE.
Lattice-based cryptography has emerged as a powerful paradigm for constructing secure cryptographic primitives, offering resistance to quantum attacks and providing a versatile framework for building post-quantum cryptographic systems. This research paper provides an in-depth exploration of lattice-based cryptography, focusing specifically on its applications for problems based on Ring Learning with Errors (RLWE). We analyze the fundamental concepts of lattice theory, delve into the RLWE problem, and highlight the security properties and challenges associated with lattice-based schemes. Furthermore, we discuss various real-world applications of lattice-based cryptography, demonstrating its potential for secure communication, privacy-preserving protocols, and post-quantum cryptography.
Lattice-based cryptography stands at the forefront of contemporary cryptographic research, offering robust security guarantees that withstand the challenges posed by quantum computing. This research paper undertakes a comprehensive exploration of lattice-based key exchange protocols, with a specific and meticulous focus on the Ring Learning with Errors (RLWE) problem—a cornerstone in the lattice-based paradigm. In addition, the paper delves deeply into the innovative ding reconciliation technique, strategically employed to amplify the efficiency and effectiveness of RLWE-based key exchange protocols.Within this paper's purview lies a holistic examination of key concepts, intricacies, and recent developments in the field of lattice-based cryptography. The paper rigorously analyzes the theoretical foundations that underpin the security assurances of lattice-based protocols, particularly in the context of post-quantum cryptography. The RLWE problem, as a central tenet, is dissected to unveil its significance as a building block for cryptographic constructions, especially in the realm of key exchange.The integration of the ding reconciliation technique introduces an added layer of depth to the research. By elucidating the mechanics of this method, the paper showcases its role in streamlining the error correction process inherent in RLWE-based protocols. The reconciliation technique's contribution to efficiency is examined through both theoretical analysis and empirical validation, presenting a compelling case for its adoption in practical scenarios.Moreover, this paper critically surveys the landscape of recent developments in lattice-based cryptography, elucidating novel protocol designs, algorithmic optimizations, and real-world applications. The inherent challenges, ranging from computational complexity to practical implementation considerations, are scrutinized, providing a balanced perspective on the field's ongoing evolution.As the paper concludes, it consolidates the insights garnered from its comprehensive review, offering a panoramic understanding of lattice-based cryptography's inner workings. It outlines the broader implications of these cryptographic protocols in safeguarding digital communications and securing data transmission in a quantum-advantaged era. By synthesizing a comprehensive overview, this research paper aims to provide researchers, practitioners, and enthusiasts with a nuanced understanding of lattice-based cryptography, RLWE-based key exchange protocols, and the innovative ding reconciliation technique.
Abstract. The decision Learning With Errors problem has proven an extremely flexible foundation for devising provably secure cryptographic primitives. LWE can be expressed in terms of linear algebra over Z/qZ. This modulus q is the subject of study of the present work. When q is prime and small, or when it is exponential and composite with small factors, LWE is known to be at least as hard as standard worst-case problems over euclidean lattices (sometimes using quantum reductions). The Ring Learning With Errors problem is a structured variant of LWE allowing for more compact keys and more efficient primitives. It is known to be at least as hard as standard worst-case problems restricted to so-called ideal lattices, but under even more restrictive arithmetic conditions on q. In this work, we prove that the arithmetic form of the modulus q is irrelevant to the computational hardness of LWE and RLWE. More precisely, we show that these problems are at least as hard as standard worst-case problems on lattices, under the unique condition that q is of polynomial bit-size. This result is most useful for adapting LWE-based cryptographic constructions to the RLWE setting. Among others, this allows us to derive the first Identity-Based Encryption scheme of quasi-optimal performance proven secure under standard worst-case lattice assumptions, in the standard model. Other applications include authentication, functional encryption and traitor tracing.
Abstract The security of most early fully homomorphic encryption schemes was based on the hardness of the Learning with Errors (LWE) problem. These schemes were inefficient in terms of per gate computations and public‐key size. More efficient schemes were later developed based on the hardness of the Ring‐LWE (RLWE) problem. While the hardness of the LWE problem is based on the hardness of the approximate shortest vector problem (GapSVP γ ) over regular lattices, the hardness of the RLWE problem is based on the hardness of the approximate shortest vector problem over ideal lattices. As of now, it has not been proved that the (GapSVP γ ) problem over ideal lattices is as difficult as the corresponding problem over regular lattices. In this work, the authors propose a multi‐bit levelled fully homomorphic encryption scheme using multivariate polynomial evaluations whose security depends on the hardness of the LWE problem. In terms of per gate computation cost, this scheme is more efficient than existing LWE‐based schemes. Further, for an appropriate choice of parameters, the per computation cost for homomorphic multiplication can be made asymptotically comparable to RLWE‐based schemes in a parallel computing environment. For homomorphic multiplication, the scheme uses a polynomial‐based technique that does not require relinearization (and key switching).
This article deals with designing an efficient post-quantum lattice based encryption scheme that relies on the multi-authority Ciphertext-Policy Attribute-Based Encryption (CP-ABE). The security of the proposed scheme is based on the hardness of the ring learning with errors (RLWE) problem. The construction of the proposed scheme is done using the Shamir's threshold secret sharing along with the Lagrange interpolation during the key generation and decryption processes in order to achieve the segmentation and restoration of private keys. A comparative study with the existing state of art schemes has been performed to show the feasibility and efficiency of the proposed scheme. Furthermore, experiments on the proposed scheme have been conducted to illustrate the computational time required during the key generation, encryption and decryption processes.
Encryption and signature schemes based on worst-case lattice problems are promising candidates for the post-quantum era, where classic number-theoretic assumptions are rendered false. Although there have been many important results and breakthroughs in lattice cryptography, the questions of how to systematically evaluate their security in practice and how to choose secure parameters are still open. This is mainly due to the fact that most security proofs are essentially asymptotic statements. In addition, the hardness of the underlying complexity assumption is controlled by several interdependent parameters rather than just a simple bit length as in many classic schemes. With our work, we close this gap by providing a framework that (1) distills a hardness estimate out of a given parameter set and (2) relates the complexity of practical lattice-based attacks to symmetric “bit security” for the first time. Our approach takes various security levels, or attacker types, into account. Moreover, we use it to predict long-term security in a similar fashion as the results that are collected on www.keylength.com. In contrast to the experiments by Gama and Nguyen (Eurocrypt 2008), our estimates are based on precisely the family of lattices that is relevant in modern lattice-based cryptography. Our framework can be applied in two ways: Firstly, to assess the hardness of the (few) proposed parameter sets so far and secondly, to propose secure parameters in the first place. Our methodology is applicable to essentially all lattice-based schemes that are based on the learning with errors problem (LWE) or the small integer solution problem (SIS) and it allows us to compare efficiency and security across different schemes and even across different types of cryptographic primitives.