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.

We propose a new nonmonotone filter method to promote global and fast local convergence for sequential quadratic programming algorithms. Our method uses two filters: a standard, global g-filter for global convergence, and a local nonmonotone l-filter that allows us to establish fast local convergence. We show how to switch between the two filters efficiently, and we prove global and superlinear local convergence. A special feature of the proposed method is that it does not require second-order correction steps. We present preliminary numerical results comparing our implementation with a classical filter SQP method.

Multivariate Cryptography, as one of the main candidates for establishing post-quantum cryptosystems, provides strong, efficient and well-understood digital signature schemes such as UOV, Rainbow, and Gui. While Gui provides very short signatures, it is, for efficiency reasons, restricted to very small finite fields, which makes it hard to scale it to higher levels of security and leads to large key sizes. In this paper we propose a signature scheme called HMFEv (“Hidden Medium Field Equations”), which can be seen as a multivariate version of HFEv. We obtain our scheme by applying the Vinegar Variation to the MultiHFE encryption scheme of Chen et al. We show both theoretically and by experiments that our new scheme is secure against direct and Rank attacks. In contrast to other schemes of the HFE family such as Gui, HMFEv can be defined over arbitrary base fields and therefore is much more efficient in terms of both performance and memory requirements. Our scheme is therefore a good candidate for the upcoming standardization of post-quantum signature schemes.

A product formula is proved which involves the unitary group generated by a semibounded self-adjoint operator and an orthogonal projection P. It gives a partial answer to the question about existence of the limit which describes quantum Zeno dynamics in the subspace Ran P.

In 2017, Ward Beullens et al. submitted Lifted Unbalanced Oil and Vinegar [3], which is a modification to the Unbalanced Oil and Vinegar Scheme by Patarin. Previously, Ding et al. proposed the Subfield Differential Attack [22] which prompted a change of parameters by the authors of LUOV for the second round of the NIST post quantum standardization competition [4]. In this paper we propose a modification to the Subfield Differential Attack called the Nested Subset Differential Attack which fully breaks half of the parameter sets put forward. We also show by experimentation that this attack is practically possible to do in under 210 min for the level I security parameters and not just a theoretical attack. The Nested Subset Differential attack is a large improvement of the Subfield differential attack which can be used in real world circumstances. Moreover, we will only use what is called the “lifted” structure of LUOV, and our attack can be thought as a development of solving “lifted” quadratic systems.