Many lattice-based crypstosystems employ ideal lattices for high efficiency. However, the additional algebraic structure of ideal lattices usually makes us worry about the security, and it is widely believed that the algebraic structure will help us solve the hard problems in ideal lattices more efficiently. In this paper, we study the additional algebraic structure of ideal lattices further and find that a given ideal lattice in a polynomial ring can be embedded as an ideal into infinitely many different polynomial rings by the coefficient embedding. We design an algorithm to verify whether a given full-rank lattice in \mathbbZ^n is an ideal lattice and output all the polynomial rings that the given lattice can be embedded into as an ideal with time complexity \mathcalO(n^3B(B+\log n), where n is the dimension of the lattice and B is the upper bound of the bit length of the entries of the input lattice basis. We would like to point out that Ding and Lindner proposed an algorithm for identifying ideal lattices and outputting a single polynomial ring that the input lattice can be embedded into with time complexity \mathcalO(n^5B^2) in 2007. However, we find a flaw in Ding and Lindner’s algorithm that causes some ideal lattices can’t be identified by their algorithm.

PPFE Attack

Partial Prime Factor Exposure Attacks on Some RSA Variants

In this paper, we consider five variants of the RSA cryptosystem, where the modulus is N=pq, and the public key e and the secret key d satisfy ed−k(p2+p+1)(q2+q+1)=1 or ed−k(p2−1)(q2−1)=1. Our results show that if a certain amount of the most significant bits of p are known so that |p−p0|=Nβ with a known p0, 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.

The Implicit Factorization Problem (IFP) was first introduced by May and Ritzenhofen at PKC’09, which concerns the factorization of two RSA moduli N_1=p_1q_1 and N_2=p_2q_2, where p_1 and p_2 share a certain consecutive number of least significant bits. Since its introduction, many different variants of IFP have been considered, such as the cases where p_1 and p_2 share most significant bits or middle bits at the same positions. In this paper, we consider a more generalized case of IFP, in which the shared consecutive bits can be located at \textitany positions in each prime, not necessarily required to be located at the same positions as before. We propose a lattice-based algorithm to solve this problem under specific conditions, and also provide some experimental results to verify our analysis.

2022

Rangasamy

On Rangasamy’s outsourcing algorithm for solving quadratic congruence equations

Outsourcing computation is a desired approach for IoT (Internet of Things) devices to transfer their burdens of heavy computations to those nearby, resource-abundant cloud servers. Recently, Rangasamy presented a passive attack against two outsourcing algorithms proposed by Zhang et al. for solving quadratic congruence equations, which is widely used in IoT applications. Furthermore, he also proposed a modified algorithm to fix these schemes and claimed that his algorithm was correct and enabled secure and verifiable delegation of solving quadratic congruence equations in IoTs. However, we show that Rangasamy’s modified algorithm has a flaw which makes it incorrect and also propose some further attacks to break the security claim, even when the flaw has been corrected.