LWE/RLWE-based cryptosystems require sampling error term from discrete Gaussian distribution. However, some existing samplers are somehow slow under certain circumstances therefore efficiency of such schemes is restricted. In this paper, we introduce a more efficient discretized Gaussian sampler based on ziggurat sampling algorithm. We also analyze statistical quality of our sampler to prove that it can be adopted in LWE/RLWE-based cryptosystems. Compared with ziggurat-based sampler by Buchmann et al. related samplers by Peikert, Ducas et al. and Knuth-Yao, our sampler achieves more than 2x speedup when standard deviation is large. This can benefit constructions rely on noise flooding (e.g., homomorphic encryption). We also present two applications: First, we use our sampler to optimize the RLWE-based authenticated key exchange (AKE) protocol by Zhang et al. We achieve 1.14x speedup on total runtime of this protocol over major parameter choices. Second, we give practical post-quantum Transport Layer Security (TLS) ciphersuite. Our ciphersuite inherits advantages from TLS and the optimized AKE protocol. Performance of our proof-of-concept implementation is close to TLS v1.2 ciphersuites and one post-quantum TLS construction.

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.

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.

Okumura proposed a candidate of post-quantum cryptosystem based on Diophantine equations of degree increasing type (DEC). Sizes of public keys in DEC are small, e.g., 1,200 bits for 128 bit security, and it is a strongly desired property in post-quantum erea. In this paper, we propose a polynomial time attack against DEC. We show that the one-wayness of DEC is reduced to finding special (relatively) short vectors in some lattices. The usual LLL algorithm does not work well for finding the most important target vector in our attack. The most technical point of our method is to heuristically find a special norm called a weighted norm to find the most important target vector. We call this method “weighted LLL algorithm” in this paper. Our experimental results suggest that our attack can break the one-wayness of DEC for 128 bit security with sufficiently high probability.

This paper introduces a new central trapdoor for multivariate quadratic (MQ) public-key cryptosystems that allows for encryption, in contrast to time-tested MQ primitives such as Unbalanced Oil and Vinegar or Hidden Field Equations which only allow for signatures. Our construction is a mixed-field scheme that exploits the commutativity of the extension field to dramatically reduce the complexity of the extension field polynomial implicitly present in the public key. However, this reduction can only be performed by the user who knows concise descriptions of two simple polynomials, which constitute the private key. After applying this transformation, the plaintext can be recovered by solving a linear system. We use the minus and projection modifiers to inoculate our scheme against known attacks. A straightforward C++ implementation confirms the efficient operation of the public key algorithms.