In this paper, we first prove an explicit formula which bounds the degree of regularity of the family of HFEv (“HFE with vinegar”) and HFEv- (“HFE with vinegar and minus”) multivariate public key cryptosystems over a finite field of size q. The degree of regularity of the polynomial system derived from an HFEv- system is less than or equal to \frac{(q−1)(r+v+a−1)}{2}+2 if q is even and r+a is odd, \frac{(q−1)(r+v+a−1)}{2}+2 otherwise, where the parameters v, D, q, and a are parameters of the cryptosystem denoting respectively the number of vinegar variables, the degree of the HFE polynomial, the base field size, and the number of removed equations, and r is the “rank” paramter which in the general case is determined by D and q as r=⌊log_q (D−1)⌋+1. In particular, setting a = 0 gives us the case of HFEv where the degree of regularity is bound by \frac{(q−1)(r+v−1)}{2}+2 if q is even and r is odd, \frac{(q−1)(r+v)}{2}+2 otherwise. This formula provides the first solid theoretical estimate of the complexity of algebraic cryptanalysis of the HFEv- signature scheme, and as a corollary bounds on the complexity of a direct attack against the QUARTZ digital signature scheme. Based on some experimental evidence, we evaluate the complexity of solving QUARTZ directly using F_4/F_5 or similar Gröbner methods to be around 2^{92}.

In 2006, Nie et al proposed an attack to break an instance of TTM cryptosystems. However, the inventor of TTM disputed this attack and he proposed two new instances of TTM to support his viewpoint. At this time, he did not give the detail of key construction --- the construction of the lock polynomials in these instances which would be used in decryption. The two instances are claimed to achieve a security of 2^{109} against Nie et al attack. In this paper, we show that these instances are both still insecure, and in fact, they do not achieve a better design in the sense that we can find a ciphertext-only attack utilizing the First Order Linearization Equations while for the previous version of TTM, only Second Order Linearization Equations can be used in the beginning stage of the previous attack. Different from previous attacks, we use an iterated linearization method to break these two instances. For any given valid ciphertext, we can find its corresponding plaintext within 2^{31} F_{2^8}-computations after performing once for any public key a computation of complexity less than 2^{44} . Our experiment result shows we have unlocked the lock polynomials after several iterations, though we do not know the detailed construction of lock polynomials.

This paper discusses two encryption schemes to fix the Square scheme. Square+ uses the Plus modification of appending randomly chosen polynomials. Double-Layer Square uses a construction similar to some signature schemes, splitting the variables into two layers, one of which depends on the other.

Anderson mixing (AM) is an acceleration method for fixed-point iterations. Despite its success and wide usage in scientific computing, the convergence theory of AM remains unclear, and its applications to machine learning problems are not well explored. In this paper, by introducing damped projection and adaptive regularization to the classical AM, we propose a Stochastic Anderson Mixing (SAM) scheme to solve nonconvex stochastic optimization problems. Under mild assumptions, we establish the convergence theory of SAM, including the almost sure convergence to stationary points and the worst-case iteration complexity. Moreover, the complexity bound can be improved when randomly choosing an iterate as the output. To further accelerate the convergence, we incorporate a variance reduction technique into the proposed SAM. We also propose a preconditioned mixing strategy for SAM which can empirically achieve faster convergence or better generalization ability. Finally, we apply the SAM method to train various neural networks including the vanilla CNN, ResNets, WideResNet, ResNeXt, DenseNet and LSTM. Experimental results on image classification and language model demonstrate the advantages of our method.

We consider the effect of small scale random fluctuations of the constitutive coefficients on boundary measurements of solutions to radiative transfer equations. As the correlation length of the random oscillations tends to zero, the transport solution is well approximated by a deterministic, averaged, solution. In this paper, we analyze the random fluctuations to the averaged solution, which may be interpreted as a central limit correction to homogenization. With the inverse transport problem in mind, we characterize the random structure of the singular components of the transport measurement operator. In regimes of moderate scattering, such components provide stable reconstructions of the constitutive parameters in the transport equation. We show that the random fluctuations strongly depend on the decorrelation properties of the random medium.