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.

We present a multivariate version of Hidden Field Equations (HFE) over a finite field of odd characteristic, with an extra "embedding'' modifier. Combining these known ideas makes our new MPKC (multivariate public key cryptosystem) more efficient and scalable than any other extant multivariate encryption scheme. Switching to odd characteristics in HFE-like schemes affects how an attacker can make use of field equations. Extensive empirical tests (using MAGMA-2.14, the best commercially available \mathbold{F_4} implementation) suggests that our new construction is indeed secure against algebraic attacks using Gröbner Basis algorithms. The "embedding'' serves both to narrow down choices of pre-images and to guard against a possible Kipnis-Shamir type (rank-based) attack. We may hence reasonably argue that for practical sizes, prior attacks take exponential time. We demonstrate that our construction is in fact efficient by implementing practical-sized examples of our "odd-char HFE'' with 3 variables (`"THFE'') over GF(31). To be precise, our preliminary THFE implementation is 15x--20x the speed of RSA-1024.

Micciancio defined a generalization of cyclic lattices, called ideal lattices. These lattices can be used in cryptosystems to decrease the number of parameters necessary to describe a lattice by a square root, making them more efficient. He proves that the computational intractability of classic lattice problems for these lattices gives rise to provably secure one-way and collision-resistant hash functions. This provable security relies on the assumption that reducing bases of ideal lattices is similar to reducing bases of random lattices. We give an indication that lattice problems in ideal lattices do not represent the general case by providing a distinguisher, which decides in time O(n^4) whether a given basis of rank spans an ideal lattice or not. Using this algorithm we perform a statistical analysis for several dimensions and show that randomly generated lattices are practically never ideal.

Sflash had recently been broken by Dubois, Stern, Shamir, etc., using a differential attack on the public key. The C^{*-} signature schemes are hence no longer practical. In this paper, we will study the new attack from the point view of symmetry, then (1) present a simple concept (projection) to modify several multivariate schemes to resist the new attacks; (2) demonstrate with practical examples that this simple method could work well; and (3) show that the same discussion of attack-and-defence applies to other big-field multivariates. The speed of encryption schemes is not affected, and we can still have a big-field multivariate signatures resisting the new differential attacks with speeds comparable to Sflash.

A Tamed Transformation Method (TTM) cryptosystem was proposed by T.T.Moh in 1999. We describe how the first implementation scheme of the TTM system can be defeated. The computational complexity of our attack is 2^{33} computations on the finite field with 2^8 elements.