Given (a,b) \in \mZ^2, Euclid's algorithm outputs the generator \gcd(a,b) of the ideal a\mZ + b\mZ. Computing a lattice basis is a high-dimensional generalization: given \mathbfa _1,\dots,\veca _n \in \mZ^m, find a \mZ-basis of the lattice L=\ \sum_i=1 ^n x_i \veca _i, x_i \in \mZ\ generated by the \veca _i's. The fastest algorithms known are HNF algorithms, but are not adapted to all applications, such as when the output should not be much longer than the input. We present an algorithm which extracts such a short basis within the same time as an HNF, by reduction to HNF. We also present an HNF-less algorithm, which reduces to Euclid's extended algorithm and can be generalized to quadratic forms. Both algorithms can extend primitive sets into bases.

There is a well-known asymptotic formula, due to W. M. Schmidt [Duke Math. J., 35 (1968), pp. 327--339], for the number of full-rank integer lattices of index at most $V$ in ${\mathbb{Z}}^n$. This set of lattices $L$ can naturally be partitioned with respect to the factor group ${\mathbb{Z}}^n/L$. Accordingly, we count the number of full-rank integer lattices $L \subseteq {\mathbb{Z}}^n$ such that ${\mathbb{Z}}^n/L$ is cyclic and of order at most $V$, and deduce that these co-cyclic lattices are dominant among all integer lattices: their natural density is $(\zeta(6) \prod_{k=4}^n \zeta(k))^{-1} \approx 85\%$. The problem is motivated by complexity theory, namely worst-case to average-case reductions for lattice problems.

The Lenstra–Lenstra–Lovász lattice basis reduction algorithm (called LLL or ${\rm L}^3$) is a fundamental tool in computational number theory and theoretical computer science, which can be viewed as an efficient algorithmic version of Hermite's inequality on Hermite's constant. Given an integer d-dimensional lattice basis with vectors of Euclidean norm less than B in an n-dimensional space, the ${\rm L}^3$ algorithm outputs a reduced basis in $O(d^3n\,{\rm log}\,B\cdot\mathcal{M}(d\,{\rm log}\,B))$ bit operations, where $\mathcal{M}(k)$ denotes the time required to multiply k-bit integers. This worst-case complexity is problematic for applications where d or/and ${\rm log}\,B$ are often large. As a result, the original ${\rm L}^3$ algorithm is almost never used in practice, except in tiny dimension. Instead, one applies floating-point variants where the long-integer arithmetic required by Gram–Schmidt orthogonalization is replaced by floating-point arithmetic. Unfortunately, this is known to be unstable in the worst case: the usual floating-point ${\rm L}^3$ algorithm is not even guaranteed to terminate, and the output basis may not be ${\rm L}^3$-reduced at all. In this article, we introduce the ${\rm L}^2$ algorithm, a new and natural floating-point variant of the ${\rm L}^3$ algorithm which provably outputs ${\rm L}^3$-reduced bases in polynomial time $O(d^2n(d+{\rm log}\,B)\,{\rm log}\,B\cdot\mathcal{M}(d))$. This is the first ${\rm L}^3$ algorithm whose running time (without fast integer arithmetic) provably grows only quadratically with respect to ${\rm log}\,B$, like Euclid's gcd algorithm and Lagrange's two-dimensional algorithm.

Lattice reduction is a geometric generalization of the problem of computing greatest common divisors. Most of the interesting algorithmic problems related to lattice reduction are NP-hard as the lattice dimension increases. This article deals with the low-dimensional case. We study a greedy lattice basis reduction algorithm for the Euclidean norm, which is arguably the most natural lattice basis reduction algorithm because it is a straightforward generalization of an old two-dimensional algorithm of Lagrange, usually known as Gauss' algorithm, and which is very similar to Euclid's gcd algorithm. Our results are twofold. From a mathematical point of view, we show that up to dimension four, the output of the greedy algorithm is optimal: The output basis reaches all the successive minima of the lattice. However, as soon as the lattice dimension is strictly higher than four, the output basis may be arbitrarily bad as it may not even reach the first minimum. More importantly, from a computational point of view, we show that up to dimension four, the bit-complexity of the greedy algorithm is quadratic without fast integer arithmetic, just like Euclid's gcd algorithm. This was already proved by Semaev up to dimension three using rather technical means, but it was previously unknown whether or not the algorithm was still polynomial in dimension four. We propose two different analyzes: a global approach based on the geometry of the current basis when the length decrease stalls, and a local approach showing directly that a significant length decrease must occur every O (1) consecutive steps. Our analyzes simplify Semaev's analysis in dimensions two and three, and unify the cases of dimensions two to four. Although the global approach is much simpler, we also present the local approach because it gives further information on the behavior of the algorithm.

The celebrated Lenstra-Lenstra-Lovász lattice basis reduction algorithm (LLL) can naturally be viewed as an algorithmic version of Hermite's inequality on Hermite's constant. We present a polynomial-time blockwise reduction algorithm based on duality which can similarly be viewed as an algorithmic version of Mordell's inequality on Hermite's constant. This achieves a better and more natural approximation factor for the shortest vector problem than Schnorr's algorithm and its transference variant by Gama, Howgrave-Graham, Koy and Nguyen. Furthermore, we show that this approximation factor is essentially tight in the worst case.

We re-examine Paillier's cryptosystem, and show that by choosing a particular discrete log base g, and by introducing an alternative decryption procedure, we can extend the scheme to allow an arbitrary exponent e instead of N. The use of low exponents substantially increases the efficiency of the scheme. The semantic security is now based on a new decisional assumption, namely the hardness of deciding whether an element is a "small" e-th residue modulo N2.We also show how to use Paillier's original cryptosystem to build a trapdoor commitment scheme. This new scheme is information-theoretically private, and computationally binding (this property holds under the assumption that the RSA function with exponent N is hard to invert). A novel property of this new commitment scheme is that most of the work can be done offline before knowing the message one wants to commit to. Once the message is known only two multiplications are required. This is the first trapdoor commitment scheme with this online-offline efficiency property which is also length-preserving.