Search

In an encrypted database, all data items stored at the server are encrypted and some operations can be performed directly over ciphertexts. Most existing encrypted database schemes cannot support data interoperability, that is, it cannot handle complex queries which require the output of one operator as the input to another. Wong et al. presented the encrypted database SDB (SIGMOD'14), and it is the only scheme that achieves data interoperability to the best of our knowledge. Recently, Cao et al. revisited the security of SDB (PVLDB'21) and proposed a ciphertext-only attack named "co-prime" attack. Their attack has a high success rate (84.9–99.9% on real-world benchmarks) and works on several common operations in SDB, including addition, sum, equi-join and group-by. However, the attack is time-consuming when the plaintext space (denoted as M) is large, since the time complexity is O (M 2) , or O(M) with the meet-in-the-middle strategy. Cao et al. 's experiments showed that the attack takes ∼ 25 minutes on a laptop when M = 2 20 . And the expected time cost will be 15,261 years if M = 2 48 , which is infeasible. In addition, the authors provided the countermeasures to prevent co-prime attack. Our main contribution in this paper is twofold. First, we propose an improved ciphertext-only attack based on lattice reduction against SDB with time complexity O(1). Our attack works on not only the previous four operations discussed by Cao et al., but also some aggregate operations, and its success rate is the same as that of co-prime attack. With the same parameters, our attack only takes ∼ 40 s on a laptop, which is 37 × faster than co-prime attack. Besides, our attack works for large M up to 2 920 while the time cost remains almost unchanged. Thus, our attack is much more efficient and powerful. Next, we analyze the countermeasures proposed by Cao et al. and present an efficient attack with the orthogonal lattice reduction method, which denies the security of Cao et al.'s modified scheme. The time complexity is O (log M) , and the attack takes several minutes on a laptop. Furthermore, we validate our attacks on two real-world public datasets and make some discussions. [ABSTRACT FROM AUTHOR]

In recent years, there has been a significant amount of work conducted in the field of Lattice Basis Reduction Techniques, which is one of the crucial areas of Lattice-based Cryptography. This field finds applications in the cryptanalysis of important problems, including SIS, LWE, the Lattice Isomorphism Problem, and more. Another critical role of Lattice reduction is in determining key sizes for various cryptosystems based on Lattices. Therefore, the study and development of Lattice basis reduction techniques are closely tied to the assessment of the Quantum resistance nature of Lattice-based Cryptosystems, making it valuable to investigate Lattice Reduction Techniques. Furthermore, when combined with other techniques, Lattice Reduction Techniques can yield excellent results. In this paper, we delve into various essential Lattice Reduction Techniques, such as LLL, BKZ, Generalized basis reduction in dimension 3, along with their improvements like DeepLLL, DeepBKZ, Self-dual DeepBKZ. We also explore other important techniques, including Hybrid Method, Cubification, LDSF, and recent developments. Additionally, we provide discussions on their comparisons, complexities, and improvements. [ABSTRACT FROM AUTHOR]

Newly developed techniques have been recently documented, which capitalize on the security provided by prime power modulus denoted as N = prqs where 2 ≤ s < r. Previous research primarily concentrated on the factorization of the modulus of type at minimum N = p³q². In contrast, within the context of 2 ≤ s < r, we address scenarios in the modulus N = p²q (i.e. r = 2 and s = 1) still need to be covered, showing a significant result to the field of study. This work presents two factorization approaches for the multiple moduli Ni = p²i qi, relying on a good approximation of the Euler's totient function φ(Ni). The initial method for factorization deals with the multiple moduli Ni = p²i qi derived from m public keys (Ni, ei) and is interconnected through the equation eid - kiΦ(Ni) = 1. In contrast, the second factorization method is associated with the eidi - kΦ(Ni) = 1. By reorganizing the equations as a simultaneous Diophantine approximation problem and implementing the LLL algorithm, it becomes possible to factorize the list of moduli Ni = p²i qi concurrently, given that the unknowns d, di, k, and ki are sufficiently small. The key difference between our results and the referenced work is that we cover a real-world cryptosystem that uses the modulus N = p²q. In contrast, the previous work covers a hypothetical situation of modulus in the form of N = prqs. [ABSTRACT FROM AUTHOR]

The Lattice Isomorphism Problem (LIP) is the computational task of recovering, assuming it exists, an orthogonal linear transformation sending one lattice to another. For cryptographic purposes, the case of the trivial lattice Z n is of particular interest (Z LIP). Heuristic analysis suggests that the BKZ algorithm with blocksize β = n / 2 + o (n) solves such instances (Ducas, Postlethwaite, Pulles, van Woerden, ASIACRYPT 2022). In this work, I propose a provable version of this statement, namely, that Z LIP can indeed be solved by making polynomially many calls to a Shortest Vector Problem oracle in dimension at most n / 2 + 1 . [ABSTRACT FROM AUTHOR]

In recent years, the deployment of massive multiuser multiple-input multiple-output (MU-MIMO) systems with hundreds or even thousands of antennas at the enhanced-mobile broadband station (e-MBBS) has gained considerable attention in the research community and industry for emerging applications such as millimeter-wave (mm-wave) communications, 5G and Beyond, Beamforming and spatial division multiple access (SDMA) and IoT and Wearable Devices. In this paper, we propose a novel low-complexity detection algorithm, namely lattice reduction associated reactive Tabu search (LR-RTS), capable of providing near-optimal detection performances by mitigating both the inter-antenna interference (IAI) and multi-user interference (MUI). The lattice reduction (LR)-based precoding scheme is first incorporated by the mobile user to suppress the IAI. Then, the novel LR-associated RTS detection algorithm is used at the e-MBBS to mitigate the MUI. The initial signal vector of this algorithm is chosen from the solution of the LR pre-coded ZF detector. Simulation results and comparisons with state-of-the-art methods show that the proposed solution outperforms heuristic search-based algorithms, namely likelihood ascent search (LAS) and linear detection methods like zero-forcing (ZF). In addition, our method offers a better tradeoff between performance and computational complexity for systems with a massive number of antennas and higher-order QAM modulations, showing a performance gain between 2dB and 9dB versus the conventional techniques.

This paper presents a scheme that is designed for the effective implementation of lattice reduction for polynomial matrices within the list-decoding algorithm that is applied to the binary Goppa codes. The reduced form of a polynomial matrix is obtained by transforming the given polynomial matrix into a matrix in the weak Popov form. To achieve efficient lattice reduction within the list-decoding algorithm, the proposed scheme reorganizes the polynomial matrix by leveraging its inherent properties and converts it into the weak Popov form. When using the proposed implementation technique to convert the reorganized polynomial matrix into the weak Popov form, the number of simple transformations of the first kind that had to be performed was reduced by about 15% compared to the technique used to convert the original matrix to the weak Popov form. As a result, the execution time of lattice reduction was also decreased.

RSA stands as a widely adopted method within asymmetric cryptography, commonly applied for digital signature validation and message encryption. The security of RSA relies on the challenge of integer factorization, a problem considered either computationally infeasible or highly intricate, especially when dealing with sufficiently large security parameters. Effective exploits of the integer factorization problem in RSA can allow an adversary to assume the identity of the key holder and decrypt such confidential messages. The keys employed in secure hardware are particularly significant due to the typically greater value of the information they safeguard, such as in the context of securing payment transactions. In general, RSA faces various attacks exploiting weaknesses in its key equations. This paper introduces a new vulnerability that enables the concurrent factorization of multiple RSA moduli. By working with pairs (Ni,ei) and a fixed value y satisfying the Diophantine equation eixi2−y2ϕ(Ni)=zi, we successfully factorized these moduli simultaneously using the lattice basis reduction technique. Notably, our research expands the scope of RSA decryption exponents considered as insecure.

In this paper, we consider five variants of the RSA cryptosystem, where the modulus is N = p q , and the public key e and the secret key d satisfy e d − k (p 2 + p + 1) (q 2 + q + 1) = 1 or e d − k (p 2 − 1) (q 2 − 1) = 1. Our results show that if a certain amount of the most significant bits of p are known so that | p − p 0 | = N β with a known p 0 , then one can factor the RSA modulus with a better bound than low private exponent attacks. We also present the experimental results to verify our analysis. [ABSTRACT FROM AUTHOR]

RSA stands as a widely adopted method within asymmetric cryptography, commonly applied for digital signature validation and message encryption. The security of RSA relies on the challenge of integer factorization, a problem considered either computationally infeasible or highly intricate, especially when dealing with sufficiently large security parameters. Effective exploits of the integer factorization problem in RSA can allow an adversary to assume the identity of the key holder and decrypt such confidential messages. The keys employed in secure hardware are particularly significant due to the typically greater value of the information they safeguard, such as in the context of securing payment transactions. In general, RSA faces various attacks exploiting weaknesses in its key equations. This paper introduces a new vulnerability that enables the concurrent factorization of multiple RSA moduli. By working with pairs (N i , e i) and a fixed value y satisfying the Diophantine equation e i x i 2 − y 2 ϕ (N i) = z i , we successfully factorized these moduli simultaneously using the lattice basis reduction technique. Notably, our research expands the scope of RSA decryption exponents considered as insecure. [ABSTRACT FROM AUTHOR]