Search

In post-quantum cryptography, Learning With Errors (LWE) is one of the dominant underlying mathematical problems. The dual attack is one of the main strategies for solving the LWE problem, and it has recently gathered significant attention within the research community. The attack strategy consists of a lattice reduction part and a distinguishing part. The latter includes an enumeration subroutine over a certain number of positions of the secret key. Our contribution consists of giving a precise and efficient approach for calculating the expected complexity of such an enumeration procedure, which was missing in the literature. This allows us to decrease the estimated cost of the whole dual attack, both classically and quantumly, on well-known protocols such as Kyber, Saber, and TFHE. In addition, we explore different enumeration strategies to investigate some potential further improvements. As our method of calculating the expected cost of enumeration is pretty general, it might be of independent interest in other areas of cryptanalysis or even in different research areas. [ABSTRACT FROM AUTHOR]

Combinatorial attacks on small max norm LWE keys suffer enormous memory requirements, which render them inefficient in realistic attack scenarios. Therefore, more memory-efficient substitutes for these algorithms are needed. In this work, we provide new combinatorial algorithms for recovering small max norm LWE secrets outperforming previous approaches whenever the available memory is limited. We provide analyses of our algorithms for secret key distributions of current NTRU, Kyber and Dilithium variants, showing that our new approach outperforms previous memory-efficient algorithms. For instance, considering uniformly random ternary secrets of length n we improve the best known time complexity for polynomial memory algorithms from 2 1.063 n down-to 2 0.926 n . We obtain even larger gains for LWE secrets in { - m , … , m } n with m = 2 , 3 as found in Kyber and Dilithium. For example, for uniformly random keys in { - 2 , … , 2 } n as is the case for Dilithium we improve the previously best time under polynomial memory restriction from 2 1.742 n down-to 2 1.282 n . Eventually, we provide novel time-memory trade-offs continuously interpolating between our polynomial memory algorithms and the best algorithms in the unlimited memory case (May, in: Malkin, Peikert (eds) CRYPTO 2021, Part II, Springer, Heidelberg 2021. ). [ABSTRACT FROM AUTHOR]

The swift advancement of quantum computing devices holds the potential to create robust machines that can tackle an extensive array of issues beyond the scope of conventional computers. Consequently, quantum computing machines create new risks at a velocity and scale never seen before, especially with regard to encryption. Lattice-based cryptography is regarded as post-quantum cryptography’s future and a competitor to a quantum computer attack. Thus, there are several advantages to lattice-based cryptographic protocols, including security, effectiveness, reduced energy usage and speed. In this work, we study the learning with errors (LWE) problem and the cryptosystems that are based on the LWE problem and, in addition, we present a new efficient variant of LWE cryptographic scheme.

The quest for perfect quantum oblivious transfer (QOT) with information‐theoretic security remains a challenge, necessitating the exploration of computationally secure QOT as a viable alternative. Unlike the unconditionally secure quantum key distribution (QKD), the computationally secure QOT relies on specific quantum‐safe computational hardness assumptions, such as the post‐quantum hardness of learning with errors (LWE) problem and quantum‐hard one‐way functions. This raises an intriguing question: Are there additional efficient quantum hardness assumptions that are suitable for QOT? In this work, leveraging the dihedral coset state derived from the dihedral coset problem (DCP), a basic variant of OT, known as the all‐or‐nothing OT, is studied in the semi‐quantum setting. Specifically, the DCP originates from the dihedral hidden subgroup problem (DHSP), conjectured to be challenging for any quantum polynomial‐time algorithms. First, a computationally secure quantum protocol is presented for all‐or‐nothing OT, which is then simplified into a semi‐quantum OT protocol with minimal quantumness, where the interaction needs merely classical communication. To efficiently instantiate the dihedral coset state, a powerful cryptographic tool called the LWE‐based noisy trapdoor claw‐free functions (NTCFs) is used. The construction requires only a three‐message interaction and ensures perfect statistical privacy for the receiver and computational privacy for the sender. [ABSTRACT FROM AUTHOR]

In ameaningful secret image-sharing scheme, the distribution of an image among participants occurs without arousing suspicion from potential adversaries. In this paper, we introduce two secret image-sharing schemes based on the learning-with-error (LWE) problem. Both schemes use the integer wavelet transform (IWT) domain of the cover image to embed the generated hidden values. The first scheme is reversible and allows accurate recovery of the cover image after extracting the secret image. In the second scheme, we use color overlay images in the frequency domain with meaningful representation. In this scheme, Joseph's problem is also used for embedding shadow images. Theoretical analysis and experimental results show that both schemes provide increased embedding capacity and produce superior steganographic overlay image quality compared to similar schemes. [ABSTRACT FROM AUTHOR]

We address the problem of user fast revocation in the lattice-based Ciphertext Policy Attribute-Based Encryption (CP-ABE) by extending the scheme originally introduced by Zhang and Zhang [Zhang J, Zhang Z. A ciphertext policy attribute-based encryption scheme without pairings. In: International Conference on Information Security and Cryptology. Springer; 2011. p. 324–40. doi: https://doi.org/10.1007/978-3-642-34704-7_23.]. While a lot of work exists on the construction of revocable schemes for CP-ABE based on pairings, works based on lattices are not so common, and – to the best of our knowledge – we introduce the first server-aided revocation scheme in a lattice-based CP-ABE scheme, hence being embedded in a post-quantum secure environment. In particular, we rely on semi-trusted “mediators” to provide a multi-step decryption capable of handling mediation without re-encryption. We comment on the scheme and its application, and we provide performance experiments on a prototype implementation in the Attribute-Based Encryption spin-off library of Palisade to evaluate the overhead compared with the original scheme.

Summary: Secure two‐party computation allows a pair of parties to compute a function together while keeping their inputs private. Ultimately, each party receives only its own correct output. In this paper, a post‐quantum secure two‐party computation protocol is proposed that can be used to effectively block malicious parties. The protocol solves the problems of traditional protocols based on garbled circuits, which are vulnerable to quantum attacks, high communication costs and low computational efficiency. The input garbled keys of the circuit constructor is structured as a Learning with Error (LWE) equation, enabling the circuit constructor to employ a zero‐knowledge proof that demonstrates the uniformity of inputs across all circuits.In the key transfer phase, an LWE‐based batch single‐choice cut‐and‐choose oblivious transfer is proposed to avoid selective failure attacks. In addition, the protocol employs a penalty mechanism to detect if the circuit constructor has generated an incorrect circuit. We have compared the communication overhead of this protocol with three other secure two‐party computation protocols based on Cut‐and‐Choose technology. The analytical results show that this protocol has the best error probability and is resilient to quantum attacks under the malicious adversary model. In addition, with appropriate parameters, the protocol is able to reduce its communication bandwidth by an average of 40.41%. [ABSTRACT FROM AUTHOR]

We address the problem of user fast revocation in the lattice-based Ciphertext Policy Attribute-Based Encryption (CP-ABE) by extending the scheme originally introduced by Zhang and Zhang [Zhang J, Zhang Z. A ciphertext policy attribute-based encryption scheme without pairings. In: International Conference on Information Security and Cryptology. Springer; 2011. p. 324–40. doi: https://doi.org/10.1007/978-3-642-34704-7%5f23.]. While a lot of work exists on the construction of revocable schemes for CP-ABE based on pairings, works based on lattices are not so common, and – to the best of our knowledge – we introduce the first server-aided revocation scheme in a lattice-based CP-ABE scheme, hence being embedded in a post-quantum secure environment. In particular, we rely on semi-trusted "mediators" to provide a multi-step decryption capable of handling mediation without re-encryption. We comment on the scheme and its application, and we provide performance experiments on a prototype implementation in the Attribute-Based Encryption spin-off library of Palisade to evaluate the overhead compared with the original scheme. [ABSTRACT FROM AUTHOR]

Cloud-based services have powerful storage functions and can provide accurate computation. However, the question of how to guarantee cloud-based services access control and achieve data sharing security has always been a research highlight. Although the attribute-based proxy re-encryption (ABPRE) schemes based on number theory can solve this problem, it is still difficult to resist quantum attacks and have limited expression capabilities. To address these issues, we present a novel linear secret sharing schemes (LSSS) matrix-based ABPRE scheme with the fine-grained policy on the lattice in the research. Additionally, to detect the activities of illegal proxies, homomorphic signature (HS) technology is introduced to realize the verifiability of re-encryption. Moreover, the non-interactivity, unidirectionality, proxy transparency, multi-use, and anti-quantum attack characteristics of our system are all advantageous. Besides, it can efficiently prevent the loss of processing power brought on by repetitive authorisation and can enable precise and safe data sharing in the cloud. Furthermore, under the standard model, the proposed learning with errors (LWE)-based scheme was proven to be IND-sCPA secure. [ABSTRACT FROM AUTHOR]

Today, the security of most existing PSI protocols are based on number theoretic assumptions, and with the development of quantum computing theory, these PSI protocols will become insecure. In order to solve this problem, this paper proposed a two-party PSI protocol based on ideal lattice in semi-honest model by using the decrypted features of function encryption on lattice and designing the party elements into vector forms conforming to LWE additive homomorphisms through binary decomposition. In terms of security, the PSI protocol achieves quantum-resistant security by using a function cryptographic system based on the ring learning with errors（RLWE）. In terms of efficiency,the communication complexity of the proposed protocol is O（w+v） and proportional to the party elements, which ensures higher communication efficiency. And the use of ideal lattice reduces the size of the public key by n-fold, which improves storage efficiency and reduces communication costs. [ABSTRACT FROM AUTHOR]

We consider multi-key fully homomorphic encryption (multi-key FHE) which is the richest variant of fully homomorphic encryption (FHE) that allows complex computation on encrypted data under different keys. Since its introduction López-Alt et al. (On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In: Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pp 1219–1234. ACM, 2012), numerous proposals have been presented yielding various improvements in security and efficiency. However, most of these multi-key FHE schemes encrypt a single-bit message. Constructing a multi-key FHE scheme encrypting multi-bit messages have been notoriously difficult without loosing efficiency for homomorphic evaluation and ciphertext extension under additional keys. In this work, we study multi-key FHE that can encrypt multi-bit messages. Motivated by the goals of improving the efficiency, we propose a new construction with non-interactive decryption and security against chosen-plaintext attack (IND-CPA) from the standard learning with errors (LWE) assumption. We consider a binary matrix as plaintext instead of a single-bit. Our approach supports efficient homomorphic matrix addition and multiplication. Another interesting feature is that our technique of extending a ciphertext under additional keys yields significant reduction in the computational overhead. More interestingly, when contrasted with the previous multi-key FHE schemes for multi-bit messages, our candidates exhibits favorable results in the length of the secret key, public key and ciphertext preserving non-interactive decryption. [ABSTRACT FROM AUTHOR]

We present the first leveled fully homomorphic encryption scheme for quantum circuits with classical keys. The scheme allows a classical client to blindly delegate a quantum computation to a quantum server: an honest server is able to run the computation while a malicious server is unable to learn any information about the computation. We show that it is possible to construct such a scheme directly from a quantum secure classical homomorphic encryption scheme with certain properties. Finally, we show that a classical homomorphic encryption scheme with the required properties can be constructed from the learning with errors problem. [ABSTRACT FROM AUTHOR]

In a meaningful secret image sharing scheme with authentication, an image is distributed among the participants without raising adversaries suspicion. Additionally the cheats of the dealer and participants in the reconstruction of the image are discoverable, which means that the integration of the shares is verifiable. In this paper, we propose a novel meaningful secret image sharing with authentication property based on learning with errors problem and rook polynomial. Compared with the previous schemes, it has a higher embedding rate and a better visual quality. [ABSTRACT FROM AUTHOR]

Multi-key fully homomorphic encryption (MFHE) supports arbitrary meaningful computations on encrypted data under different public keys even without access to the secret key, which is well tailored for the secure multiparty computation scenarios. Based on the Gentry–Sahai–Waters scheme (a single-key FHE in Crypto 2013) with the underlying learning with errors problem, MW16 scheme (Eurocrypt 2016) utilizes the method of 'linear combination procedure' (LCP) as a subroutine to construct the auxiliary information for the expanded ciphertexts of MFHE scheme. However, every party shares a common random string (CRS) to be distributed by a trusted setup, which is unpractical. Meanwhile, the noise in the auxiliary information is too much compared with the one in fresh ciphertexts. In this paper, we propose a modified MFHE scheme in the plain model, i.e. without CRS, to enhance the practicability of MFHE. Specifically, every involved party generates his own public key independent on a CRS. Then a potential improvement on the LCP is developed to provide auxiliary information, which largely reduces the noise and leads to a smaller modulus for our MFHE. Furthermore, the feasibility of our proposal is also proved by theoretical performance comparisons. [ABSTRACT FROM AUTHOR]

Autonomous path proxy re-encryption (AP-PRE) is a type of PRE that implements control on the delegation path in a multi-hop PRE. AP-PRE forces the proxy to perform the transformation along a predefined path without revealing the underlying plaintext. There are several applications of AP-PRE, including electronic medical systems, data sharing, and email systems. However, as far as we know, the existing AP-PRE scheme is provably secure in the random oracle model under the classical number-theoretic assumption, which might be vulnerable to quantum computers. Therefore, it raises the intriguing question of how to construct a quantum-resistant AP-PRE scheme. In this study, we proposed an AP-PRE scheme based on the widely accepted quantum-resistant learning with errors (LWE) assumptions. Our scheme supports the polynomial length of the delegation path. Furthermore, our scheme is proved to be selective-path CPA (sCPA) secure in the standard model under LWE assumptions. [ABSTRACT FROM AUTHOR]

The quantum computing being a threat motivates us to design a post quantum secure authentication protocol for mobile digital rights management system. In current, a post quantum secure protocol "learning with error based secure mobile digital rights management system" has been proposed. The protocol has been claimed to post quantum secure under the ring learning with errors assumption. We have analyzed that this protocol allows the server to keep a fixed private/public key that causes less communication and computation overheads. But, this leads to signal leakage/modified signal leakage attacks. In this paper, we have discussed signal leakage attacks during the authentication phase of the existing protocol. We have proposed a new post quantum authenticated key agreement protocol for the digital rights management system. In the proposed protocol, the server uses a random value instead of using fixed value chosen by the user, and it establishes a session key with the user. Moreover, this protocol needs to exchange just two messages that confirm the efficiency. The protocol has been proved secure in a random oracle model under ring learning with errors assumption. Moreover, the article contains an informal security discussion and a simulation using NS3 simulator. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Cryptologic Research (2095-7025) is the property of Editorial Board of Journal of Cryptologic Research and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

We introduce a novel method to derandomize the learning with errors (LWE) problem by generating deterministic yet sufficiently independent LWE instances that are constructed by using linear regression models, which are generated via (wireless) communication errors. We also introduce star-specific key-homomorphic (SSKH) pseudorandom functions (PRFs), which are defined by the respective sets of parties that construct them. We use our derandomized variant of LWE to construct a SSKH PRF family. The sets of parties constructing SSKH PRFs are arranged as star graphs with possibly shared vertices, i.e., the pairs of sets may have non-empty intersections. We reduce the security of our SSKH PRF family to the hardness of LWE. To establish the maximum number of SSKH PRFs that can be constructed — by a set of parties — in the presence of passive/active and external/internal adversaries, we prove several bounds on the size of maximally cover-free at most $t$ -intersecting $k$ -uniform family of sets $\mathcal {H}$ , where the three properties are defined as: (i) $k$ -uniform: $\forall A \in \mathcal {H}: |A| = k$ , (ii) at most $t$ -intersecting: $\forall A, B \in \mathcal {H}, B \neq A: |A \cap B| \leq t$ , (iii) maximally cover-free: $\begin{aligned} \forall A \in \mathcal {H}: A \not \subseteq \bigcup \limits _{\substack {B \in \mathcal {H} \\ B \neq A}} B \end{aligned}$ . For the same purpose, we define and compute the mutual information between different linear regression hypotheses that are generated from overlapping training datasets.

With the continuous and rapid development of Cloud Computing, Big Data and Internet of Things, it is extremely critical to protect data with homomorphism, privacy and integrity. For this, Rezaeibagha et al. proposed a new cryptographic primitive, called homomorphic signcryption. However, the current homomorphic signcryption schemes either only support linear computation or are built on non-standard assumption. Therefore, it is interesting to design a leveled fully homomorphic signcryption (FHSC) scheme from the standard assumption. In this work, we present a leveled FHSC scheme from lattices. For this, we exert classical sign-then-encrypt method and surmount the difficulty of homomorphic multiplicative evaluation in the way of encrypting every elements. Moreover, we prove its indistinguishability against chosen plaintext attacks (IND-CPA) and strong unforgeability (SUF) under hard problems of standard lattices.

The learning with errors (LWE) problem has emerged as the most popular hard problem for constructing lattice based cryptographic solutions. In this paper, we propose a verifiable multi secret sharing scheme based on LWE problem and prove the security of our scheme in the standard model. It is a threshold scheme and every t participants (t ≤ n) can recover multiple secrets, in one stage. Moreover, it has a non-interactive verification and no extra communication is needed among participants and the dealer in the verification phase. In short, it is the first LWE based threshold multi secret sharing scheme that has formal security in the standard model. [ABSTRACT FROM AUTHOR]

There are mostly semi-honest agents in cloud computing, so agents may perform unreliable calculations during the actual execution process. In this paper, an attribute-based verifiable conditional proxy re-encryption (AB-VCPRE) scheme using a homomorphic signature is proposed to solve the problem that the current attribute-based conditional proxy re-encryption (AB-CPRE) algorithm cannot detect the illegal behavior of the agent. The scheme implements robustness, that is the re-encryption ciphertext, can be verified by the verification server, showing that the received ciphertext is correctly converted by the agent from the original ciphertext, thus, meaning that illegal activities of agents can be effectively detected. In addition, the article demonstrates the reliability of the constructed AB-VCPRE scheme validation in the standard model, and proves that the scheme satisfies CPA security in the selective security model based on the learning with errors (LWE) assumption. [ABSTRACT FROM AUTHOR]

In this paper, we construct multi-key homomorphic and fully homomorphic encryption (resp. MKHE and MKFHE) schemes with malicious circuit privacy. Our schemes are based on learning with errors (LWE) besides appropriate circular security assumptions. In contrast, the previous maliciously circuit-private MKFHE scheme by Chongchitmate and Ostrovsky (PKC, 2017) is based on the non-standard decisional small polynomial ratio (DSPR) assumption with a super-polynomial modulus, besides ring learning with errors and circular security assumptions. We note that it was shown by Albrecht et al. (CRYPTO, 2016) that there exists a sub-exponential time attack against this type of DSPR assumption. The main building block of our maliciously circuit-private MKFHE scheme is a (plain) MKFHE scheme by Brakerski et al. (TCC, 2017), and the security of our schemes is proven under the hardness of LWE with sub-exponential modulus-to-noise ratio and circular security assumptions related to the Brakerski et al. scheme. Furthermore, based on our MKFHE schemes, we construct four-round multi-party computation (MPC) protocols with circuit privacy against a semi-honest server and malicious clients in the plain model. The protocols are obtained by combining our schemes with a maliciously sender-private oblivious transfer protocol and a circuit garbling scheme, all of which can be instantiated only assuming LWE. [ABSTRACT FROM AUTHOR]

In view of the problem of large ciphertext size and low efficiency of the current secure multi-party computation protocol based on fully homomorphic encryption,this paper proves that the fully homomorphic encryption scheme that supports multi-bit encryption proposed by Chen et al. satisfies the key homomorphism.Based on this scheme and threshold decryption,an efficient and secure multi-party computation protocol with three rounds of interaction under the common random string(CRS) model is designed.The protocol can be concluded from the non-interactive zero knowledge proof that the protocol is safe under the malicious model,and its security can be boiled down to the variants of the learning with errors problem(LWE).Compared with the existing protocol of the CRS model,the protocol supports multi-bit encryption,which can effectively reduce the complexity of the NAND gate.At the same time,the size of the ciphertext is smaller,the amount of calculation is reduced,and the time and space efficiency are improved.

Abstract In this paper, we study the hybrid dual attack over learning with errors (LWE) problems for any secret distribution. Prior to our work, hybrid attacks are only considered for sparse and/or small secrets. A new and interesting result from our analysis shows that for most cryptographic use cases a hybrid dual attack outperforms a standalone dual attack, regardless of the secret distribution. We formulate our results into a framework of predicting the performance of the hybrid dual attacks. We also present a few tricks that further improve our attack. To illustrate the effectiveness of our result, we re-evaluate the security of all LWE related proposals in round 3 of NIST’s post-quantum cryptography process, and improve the state-of-the-art cryptanalysis results by 2-15 bits, under the BKZ-core-SVP model.

As quantum computing advances rapidly, guaranteeing the security of cryptographic protocols resistant to quantum attacks is paramount. Some leading candidate cryptosystems use the learning with errors (LWE) problem, attractive for its simplicity and hardness guaranteed by reductions from hard computational lattice problems. Its algebraic variants, ring-learning with errors (RLWE) and polynomial learning with errors (PLWE), gain efficiency over standard LWE, but their security remains to be thoroughly investigated. In this work, we consider the “smearing” condition, a condition for attacks on PLWE and RLWE introduced in Elias et al. We expand upon some questions about smearing posed by Elias et al. and show how smearing is related to the coupon collector’s problem. Furthermore, we develop an algorithm for computing probabilities related to smearing. Finally, we present a smearing-based algorithm for solving the PLWE problem.