In this paper, we will systematically study who indeed are the hard lattice cases in LLL reduction. The “hard” cases here mean for their special geometric structures, with a comparatively high “failure probability” that LLL can not solve SVP even by using a powerful relaxation factor. We define the perfect lattice as the “Beauty”, which is given by basis of vectors of the same length with the mutual angles of any two vectors to be exactly 60°. Simultaneously the “Beasts” lattice is defined as the lattice close to the Beauty lattice. There is a relatively high probability (e.g. 15.0% in 3 dimensions) that our “Beasts” bases can withstand the exact-arithmetic LLL reduction (relaxation factors δ close to 1), comparing to the probability (corresponding <0.01%) when apply same LLL on random bases from TU Darmstadt SVP Challenge. Our theoretical proof gives us a direct explanation of this phenomenon. Moreover, we give rational Beauty bases of 3 and 8 dimensions, an irrational Beauty bases of general high dimensions. We also give a general way to construct Beasts lattice bases from the Beauty ones. Experimental results show the Beasts bases derived from Beauty can withstand LLL reduction by a stable probability even for high dimensions. Our work in a way gives a simple and direct way to explain how to build a hard lattice in LLL reduction.

No abstract uploaded!

We adopt a recent work in Chung, Qian, Uhlmann and Zhao (Inverse Problems, 23 (2007) 309-329) to develop a phase space method for reconstructing pressure wave speed and shear wave speed of an elastic medium from travel time measurements. The method is based on the so-called Stefanov-Uhlmann identity which links two Riemannian metrics with their travel time information. We design a numerical algorithm to solve the resulting inverse problem. The algorithm is a hybrid approach that combines both Lagrangian and Eulerian formulations. In particular the Lagrangian formulation in phase space can take into account multiple arrival times naturally, while the Eulerian formulation for wave speeds allows us to compute the solution in physical space. Numerical examples are shown to validate the method.

We consider a class of Hamiltonians in L2(R2) with attractive interaction supported by piecewise C2 smooth loops of a fixed length L, formally given by (x) with &gt;0. It is shown that the ground state of this operator is locally maximized by a circular . We also conjecture that this property holds globally and show that the problem is related to an interesting family of geometric inequalities concerning mean values of chords of .

We show that Multivariate Public Key Cryptosystems (MPKCs) over fields of small odd prime characteristic, say 31, can be highly efficient. Indeed, at the same design security of 2^{80} under the best known attacks, odd-char MPKC is generally faster than prior MPKCs over \GF{2^k}, which are in turn faster than "traditional'' alternatives. This seemingly counter-intuitive feat is accomplished by exploiting the comparative over-abundance of small integer arithmetic resources in commodity hardware, here embodied by SSE2 or more advanced special multimedia instructions on modern x86-compatible CPUs. We explain our implementation techniques and design choices in implementing our chosen MPKC instances modulo small a odd prime. The same techniques are also applicable in modern FPGAs which often contains a large number of multipliers.