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]

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]

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 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 is a well-known cryptosystem in Modern Cryptography and its efficiency is based on the hardness of the Integer Factorization problem. The algorithm is shown to be vulnerable to several attacks in a number of special scenarios with assumptions. In this paper, the strength of RSA is investigated if the primes in the modulus are close and the same modulus is used for two instances. The attack is highly efficient compared to other known attacks which are only concentrated on either closeness of the primes or the same modulus used for two or more instances. This attack examines the closeness of the primes chosen whenever the RSA system is used for two instances with the same modulus. The LLL algorithm is used to obtain the bound, and the bound is highly efficient compared to other known attacks. [ABSTRACT FROM AUTHOR]

Crystallographic literature is relying more on observational rules for the determination of the motif that could generate the whole representing Bravais lattice of a crystal. Here, we devise an algebraic method that can serve in this regard at least in cases when the associated unit cell is made of quasi-orthogonal vectors. To let our approach be applicable to other reduction problems, we introduce a concept which is about starting first from any ’bad’ crystal cell, not necessarily the primitive elementary cell, in order to find a ’good’ crystal cell and that means seeking a motif made of a basis whose vectors are close-to-orthogonal. The orthogonalization loss could happen any time of vectors swapping which represents a very important process in dealing with lattice reduction, but it has insufficiently been discussed in this subject. Thus, through our present version of vectors exchange theorem, and by using examples of two processes, namely the Gram-Schmidt (GS) procedure and its modified version (MGS), we provide formulations for the new reduced unit cell vectors and analyze the impact of the repeated exchange of vectors on the orthogonalization precision. Finally, we give a detailed explanation to our procedure named as Abdelalim-Elmouki (AE) algorithm. More interestingly, we show that MGS is not only better than GS because of the classical reason related to numerics, but also because its formulation for the new motif vectors in four conditions, has been preserved in three times rather than two for GS, and this may recommend more the introduction of MGS in a harder problem, namely when the crystal dimension is very big. [ABSTRACT FROM AUTHOR]

Copyright of Journal of South China Normal University (Natural Science Edition) / Huanan Shifan Daxue Xuebao (Ziran Kexue Ban) is the property of Journal of South China Normal University (Natural Science Edition) Editorial Office 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.)

In LWE-based KEMs, observed decryption errors leak information about the secret key in the form of equations or inequalities. Several practical fault attacks have already exploited such leakage by either directly applying a fault or enabling a chosen-ciphertext attack using a fault. When the leaked information is in the form of inequalities, the recovery of the secret key is not trivial. Recent methods use either statistical or algebraic methods (but not both), with some being able to handle incorrect information. Having in mind that integration of the side-channel information is a crucial part of several classes of implementation attacks on LWEbased schemes, it is an important question whether statistically processed information can be successfully integrated in lattice reduction algorithms. We answer this question positively by proposing an error-tolerant combination of statistical and algebraic methods that make use of the advantages of both approaches. The combination enables us to improve upon existing methods – we use both fewer inequalities and are more resistant to errors. We further provide precise security estimates based on the number of available inequalities. Our recovery method applies to several types of implementation attacks in which decryption errors are used in a chosen-ciphertext attack. We practically demonstrate the improved performance of our approach in a key-recovery attack against Kyber with fault-induced decryption errors.

The post-quantum digital signature scheme CRYSTALS-Dilithium has been recently selected by the NIST for standardization. Implementing CRYSTALSDilithium, and other post-quantum cryptography schemes, on embedded devices raises a new set of challenges, including ones related to performance in terms of speed and memory requirements, but also related to side-channel and fault injection attacks security. In this work, we investigated the latter and describe a differential fault attack on the randomized and deterministic versions of CRYSTALS-Dilithium. Notably, the attack requires a few instructions skips and is able to reduce the MLWE problem that Dilithium is based on to a smaller RLWE problem which can be practically solved with lattice reduction techniques. Accordingly, we demonstrated key recoveries using hints extracted on the secret keys from the same faulted signatures using the LWE with side-information framework introduced by Dachman-Soled et al. at CRYPTO’20. As a final contribution, we proposed algorithmic countermeasures against this attack and in particular showed that the second one can be parameterized to only induce a negligible overhead over the signature generation.

Inspired by the advancements in (fully) homomorphic encryption in recent decades and its practical applications, we conducted a preliminary study on the underlying mathematical structure of the corresponding schemes. Hence, this paper focuses on investigating the challenge of deducing bivariate polynomials constructed using homomorphic operations, namely repetitive additions and multiplications. To begin with, we introduce an approach for solving the previously mentioned problem using Lagrange interpolation for the evaluation of univariate polynomials. This method is well-established for determining univariate polynomials that satisfy a specific set of points. Moreover, we propose a second approach based on modular knapsack resolution algorithms. These algorithms are designed to address optimization problems in which a set of objects with specific weights and values is involved. Finally, we provide recommendations on how to run our algorithms in order to obtain better results in terms of precision. [ABSTRACT FROM AUTHOR]

Multiple recursive generators are an important class of pseudorandom number generators which are widely used in cryptography. Methods to predict the whole sequences by the truncated high-order bits of the sequences are not only a crucial aspect of evaluating the security of pseudorandom number generators but also important concerns in the design of pseudorandom number generators. This paper improves the work of Sun et al. (Des Codes Cryptogr 88:1083–1102, 2020) on the predictability of truncated multiple recursive generators with unknown parameters. Given a few truncated digits of high-order bits output by a multiple recursive generator, we first apply the resultant to recover the modulus, then use the Chinese Remainder Theorem and the idea of recovering p-adic coordinates of the coefficients layer by layer to recover the coefficients, and finally employ Kannan's embedding technique to recover the initial state. Experimental results show that our new method is superior to that of Sun et al. (2020), no matter in terms of the running time or the number of truncated digits required. [ABSTRACT FROM AUTHOR]

This paper presents a study of the LLL algorithm from the perspective of statistical physics. Based on our experimental and theoretical results, we suggest that interpreting LLL as a sandpile model may help understand much of its mysterious behavior. In the language of physics, our work presents evidence that LLL and certain 1-d sandpile models with simpler toppling rules belong to the same universality class. This paper consists of three parts. First, we introduce sandpile models whose statistics imitate those of LLL with compelling accuracy, which leads to the idea that there must exist a meaningful connection between the two. Indeed, on those sandpile models, we are able to prove the analogues of some of the most desired statements for LLL, such as the existence of the gap between the theoretical and the experimental RHF bounds. Furthermore, we test the formulas from finite-size scaling theory (FSS) against the LLL algorithm itself, and find that they are in excellent agreement. This in particular explains and refines the geometric series assumption (GSA), and allows one to extrapolate various quantities of interest to the dimension limit. In particular, we obtain the estimate that the empirical average RHF converges to ≈1.02265 as the dimension goes to infinity. [ABSTRACT FROM AUTHOR]

From the opinion of data representation, feature data fusion is a process of transforming the redundant source representation into the concise object representation by removing redundant data from source feature data. Based on the structured lattice representation of source feature data, this paper addresses the transformation of data representation by reducing the quantum representations of lattice nodes, and then proposes the fusion method based on lattice reduction directed index migration. This method classifies all lattice nodes into different node subsets through the gradual migration of the indexes of the qubits in different lattice nodes. The source lattice nodes in a subset will be fused into a new object node based on their measurement probabilities. The experimental data evaluation results demonstrate that the proposed fusion method can obtain concise and reliable fusion results for intelligent decision-making. [ABSTRACT FROM AUTHOR]

Inspired by the advancements in (fully) homomorphic encryption in recent decades and its practical applications, we conducted a preliminary study on the underlying mathematical structure of the corresponding schemes. Hence, this paper focuses on investigating the challenge of deducing bivariate polynomials constructed using homomorphic operations, namely repetitive additions and multiplications. To begin with, we introduce an approach for solving the previously mentioned problem using Lagrange interpolation for the evaluation of univariate polynomials. This method is well-established for determining univariate polynomials that satisfy a specific set of points. Moreover, we propose a second approach based on modular knapsack resolution algorithms. These algorithms are designed to address optimization problems in which a set of objects with specific weights and values is involved. Finally, we provide recommendations on how to run our algorithms in order to obtain better results in terms of precision.

Lattices are a popular field of study in mathematical research, but also in more practical areas like cryptology or multiple-input/multiple-output (MIMO) transmission. In mathematical theory, most often lattices over real numbers are considered. However, in communications, complex-valued processing is usually of interest. Besides, by the use of dual-polarized transmission as well as by the combination of two time slots or frequencies, four-dimensional (quaternion-valued) approaches become more and more important. Hence, to account for this fact, well-known lattice algorithms and related concepts are generalized in this work. To this end, a brief review of complex arithmetic, including the sets of Gaussian and Eisenstein integers, and an introduction to quaternion-valued numbers, including the sets of Lipschitz and Hurwitz integers, are given. On that basis, generalized variants of two important algorithms are derived: first, of the polynomial-time LLL algorithm, resulting in a reduced basis of a lattice by performing a special variant of the Euclidean algorithm defined for matrices, and second, of an algorithm to calculate the successive minima—the norms of the shortest independent vectors of a lattice—and its related lattice points. Generalized bounds for the quality of the particular results are established and the asymptotic complexities of the algorithms are assessed. These findings are extensively compared to conventional real-valued processing. It is shown that the generalized approaches outperform their real-valued counterparts in complexity and/or quality aspects. Moreover, the application of the generalized algorithms to MIMO communications is studied, particularly in the field of lattice-reduction-aided and integer-forcing equalization. [ABSTRACT FROM AUTHOR]

In this paper, a new receive antenna subset (RAS) selection scheme is proposed for precoding-aided spatial modulation (PSM). First, a lattice reduction (LR)-based precoder is employed instead of a conventional zero-forcing (ZF) precoder. It is analytically shown that a full diversity gain can be achieved by the LR-based ZF precoder without RAS selection. Then, an optimal LR-based RAS selection criterion is derived for the over-determined LR-based PSM systems, and a suboptimal selection algorithm is additionally presented. It is also shown that optimal and suboptimal RAS selection algorithms based on LR improve the BER performance of the LR-based PSM system. Further, the overall diversity order of the over-determined LR-based PSM systems with optimal LR-based RAS selection is analyzed. Finally, diversity analysis and simulation results show that the LR-ZF-based PSM system with optimal LR-based RAS selection outperforms the conventional ZF-based PSM system with conventional optimal RAS selection. [ABSTRACT FROM AUTHOR]

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]

The strength of the GNSS precise positioning model degrades in cases of a lack of visible satellites, poor satellite geometry or uneliminated atmospheric delays. The least-squares solution to a weak GNSS model may be unreliable due to a large mean squared error (MSE). Recent studies have reported that Tikhonov’s regularization can decrease the solution’s MSE and improve the success rate of integer ambiguity resolution (IAR), as long as the regularization matrix (or parameter) is properly selected. However, there are two aspects that remain unclear: (i) the optimal regularization matrix to minimize the MSE and (ii) the IAR performance of the regularization method. This contribution focuses on these two issues. First, the “optimal” Tikhonov’s regularization matrix is derived conditioned on an assumption of prior information of the ambiguity. Second, the regularized integer least-squares (regularized ILS) method is compared with the integer least-squares (ILS) method in view of lattice theory. Theoretical analysis shows that regularized ILS can increase the upper and lower bounds of the success rate and reduce the upper bound of the LLL reduction complexity and the upper bound of the search complexity. Experimental assessment based on real observed GPS data further demonstrates that regularized ILS (i) alleviates the LLL reduction complexity, (ii) reduces the computational complexity of determinate-region ambiguity search, and (iii) improves the ambiguity fixing success rate. [ABSTRACT FROM AUTHOR]

The extensive computer-aided search applied in Bena et al. (The tadpole problem, 2020) to find the minimal charge sourced by the fluxes that stabilize all the (flux-stabilizable) moduli of a smooth K3 × K3 compactification uses differential evolutionary algorithms supplemented by local searches. We present these algorithms in detail and show that they can also solve our minimization problem for other lattices. Our results support the Tadpole Conjecture: The minimal charge grows linearly with the dimension of the lattice and, for K3 × K3, this charge is larger than allowed by tadpole cancellation. Even if we are faced with an NP-hard lattice-reduction problem at every step in the minimization process, we find that differential evolution is a good technique for identifying the regions of the landscape where the fluxes with the lowest tadpole can be found. We then design a "Spider Algorithm," which is very efficient at exploring these regions and producing large numbers of minimal-tadpole configurations. [ABSTRACT FROM AUTHOR]